Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

4 Answers 4

up vote 5 down vote accepted

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

share|improve this answer

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$

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.