Flip a fair coin until three consecutive heads or tails appear

Question

What is the expected number of flips until three consecutive heads or tails appear?

Answer 1

This can be seen as an MC with 4 states. Denote for convenience $S=\{HHH, TTT\}$

One thing to notice first, is that only before you have tossed any coins at all you need 3 matching tosses till $S$. After that, regardless of the outcome, you have no more than two matching tosses from $S$. Hence we have the following MC:

$S_0$: 3 matching tosses till $S$

$S_1$: 2 matching tosses till $S$

$S_2$: 1 matching tosses till $S$

$S_3$: 0 matching tosses till $S$

Denoting $m_{i,j}$ the mean hitting time of state $j$ starting in state $i$, we obtain the following set of recurrent equations: $$ m_{0,3}=1+m_{1,3}\\ m_{1,3}=1+0.5 m_{1,3} +0.5m_{2,3}\\ m_{2,3}=1+0.5 m_{1,3} +0.5m_{3,3} $$ And the boundary condition is of course $m_{3,3}=0$. Solving this set of equations we get $$ m_{0,3}=1+6=7 $$

Answer 2

Let $P$ be the expected number when the last two flips match, $Q$ the expected number when the last two flips don't match (or there has only been one flip). Our answer is $Q+1$ as the first flip will take us to state $Q$. Then $P=\frac 12 \text{(that we match the last 2)}+\frac 12 (Q+1)\text{ (as we are now in state} Q)$

$Q=\frac 12 (1+P)\text{(that we match the last flip)} + \frac 12 (1+Q)\text{(that we don't match the last flip)}$

This gives $P=4, Q=6$ and our final answer is $7$

Answer 3

Here is probably another way and hope this can be easier to understand. Let us assume to get HHH for X number of times, then for {HHH, TTT} is just X/2.

1)first time get T, then just waste one time, everything turns to be same as before, plus this event chance is 1/2. Then to get HHH is 1/2*(X+1)

2)first time get H 2.1)second time get T, then waste two times plus 1/4 probability of this event. Then total number is 1/4*(X+2) 2.2)second time get H 2.2.1) third time get T, then waste 3 times plus 1/8 prob of this event. Then total number is 1/8*(X+3) 2.2.2) third time get H, this is perfect and prob is 1/8. So total number is 1/8*3.

Now, everything sum together should converge to X. we have: 1/2*(X+1) + 1/4*(X+2) + 1/8*(X+3) + 1/8*3 = X => X = 14.

So to get {HHH, TTT} is X/2 = 7.

Answer 4

I think it should be 14.

$X_k$=number of flips needed to obtain first k consecutive heads.

$$E[X_k]=\frac{1}{p}+\frac{1}{p*2}+\cdots+\frac{1}{p*k}$$ where $$p(\text{Heads})=p \\ p(\text{Tails})=1-p$$

and p is not equal to zero.