Get the complete, step-by-step math solution for: "A fair coin is flipped repeatedly. What is the expected number of flips until the pattern HTH appears?". Powered by SolveForX AI math tutor.
Step 1: Define states and expected values
We define three states based on the longest suffix of the target pattern HTH that has just occurred. E0 is the expected number of flips from the beginning (no pattern yet). EH is the expected number of flips if the last flip was H. EHT is the expected number of flips if the last two flips were HT.
Step 2: Formulate equations for expected values
For each state, we consider the outcome of the next flip (H or T, each with probability 1/2). If the next flip completes the pattern, the process stops (expected flips = 0 from that point). Otherwise, we transition to a new state. For example, from E0, if we flip H, we go to EH; if we flip T, we stay in E0. From EHT, if we flip H, the pattern HTH is complete, so we add 0 to the expected value. If we flip T, we are back to the initial state E0 because HTT does not contain H or HT as a suffix.
Step 4: Solve the system of equations
Substitute equation (3) into equation (2) to express EH in terms of E0. Then, substitute this new expression for EH into equation (1). This results in a single equation with only E0, which we can then solve.