A fair coin is flipped repeatedly. What is the expected number of flips until the pattern HTH appears?

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. $E_0$ is the expected number of flips from the beginning (no pattern yet). $E_H$ is the expected number of flips if the last flip was H. $E_{HT}$ 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 $E_0$, if we flip H, we go to $E_H$; if we flip T, we stay in $E_0$. From $E_{HT}$, 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 $E_0$ because HTT does not contain H or HT as a suffix.

Step 3: Simplify the equations

We simplify the system of linear equations by isolating the expected values. This makes it easier to substitute and solve for each variable.

Step 4: Solve the system of equations

Substitute equation (3) into equation (2) to express $E_H$ in terms of $E_0$. Then, substitute this new expression for $E_H$ into equation (1). This results in a single equation with only $E_0$, which we can then solve.

More from this chapter

• A factory has six machines. The numbers of defective chips produced by machines 1 to 6 are 1, 0, 3, 2, 1 and 0 respectively. One machine is selected at random a
• (a) Two cards are drawn at random and one by one with replacement from a well-shuffled pack of 52 playing cards. Find the probability distribution of the number
• If the probability that the random variable X takes the value x is given by P(X=x)=k (x+1)3^(-x), x=0,1,2,, where k is a constant, then P(X 3) is equal to:
• A candidate has to reach the examination center in time. The probability that he travels by metro, bus, or taxi are 3/10, 1/5, and 1/10 respectively, and 2/5 by
• A bag contains 19 unbiased coins and one coin with heads on both sides. One coin drawn at random is tossed and a head turns up. If the probability that the draw
• Bag 1 contains 4 white balls and 5 black balls, and Bag 2 contains n white balls and 3 black balls. One ball is drawn randomly from Bag 1 and transferred to Bag
• Three defective oranges are accidentally mixed with seven good ones and on looking at them, it is not possible to differentiate between them. Two oranges are dr
• Let a random variable X take values 0, 1, 2 and 3 with P(X = 0) = P(X = 1) = p and P(X = 2) = P(X = 3) = (1 - 2p)/(2). If E(X²) = 2E(X), then the value of 8p -

All Probability solutions →