# Flip a fair coin until three consecutive heads or tails appear

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

-
Try to do an easier case first, then you might get the idea. What is the expected number of flips until 1 consecutive heads or tails appears? What is the expected number of flips until 2 consecutive heads or tails appears? Can you get a formula for $n$ consecutive heads or tails? –  Euler....IS_ALIVE Oct 6 '12 at 23:42

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$$

-

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$

-

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.

-

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.

-
We were asked for either three heads or three tails. The other answers take account of this. –  Ross Millikan Apr 24 '13 at 17:35