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.

I'm writing an algorithm for a coin toss problem. But I have a problem understanding the calculation given.

Here is the question:

You have an unbiased coin which you want to keep tossing until you get N consecutive heads. You've tossed the coin M times and surprisingly, all tosses resulted in heads. What is the expected number of additional tosses needed until you get N consecutive heads?

If N = 2 and M = 0, you need to keep tossing the coin until you get 2 consecutive heads. It is not hard to show that on average, 6 coin tosses are needed.

If N = 2 and M = 1, you need 2 consecutive heads and have already have 1. You need to toss once more no matter what. In that first toss, if you get heads, you are done. Otherwise, you need to start over, as the consecutive counter resets, and you need to keep tossing the coin until you get N=2 consecutive heads. The expected number of coin tosses is thus 1 + (0.5 * 0 + 0.5 * 6) = 4.0

If N = 3 and M = 3, you already have got 3 heads, so you do not need any more tosses.

Now my problem is understanding the calculation: 1 + (0.5 * 0 + 0.5 * 6) = 4.0 when N = 2 and M = 1. I understood how they got the 6 (which is basically calculating it when M = 0, formula here).

Now what if I'm going to calculate N = 3, M = 1 or N = 3, M = 2?

Could someone write this calculation in a formula for me please? What is the 1? What is (0.5 * 0 + 0.5 * 6)?

share|improve this question
    
So, what is the final formula? (N-M) + (2^N - 1) Is this correct? –  JJ Liu Jan 7 '12 at 23:24
    
Im still not sure –  Shawn Mclean Jan 7 '12 at 23:41
1  
The general formula is $2^{N+1}-2^{M+1}$. –  Byron Schmuland Jan 7 '12 at 23:41
    
@ByronSchmuland really? so N=3, M=1 will be 12? –  JJ Liu Jan 8 '12 at 0:10
add comment

4 Answers

The reasoning behind the calculation $1+\frac12\cdot 0+\frac12\cdot 6$ is as follows. You definitely have to toss the coin one more time, no matter what; that’s the initial $1$ term. With probability $1/2$ you get a head, and in that case you’re done: you need $0$ more tosses. That’s the $\frac12\cdot 0$ term: with probability $1/2$ you use $0$ extra tosses beyond the first. But with probability $1/2$ you get a tail, and in that case you are in effect starting over, as if you’d not tossed the coin at all. In this case you already know that the expected number of tosses to get two consecutive heads is $6$, so you know that with probability $1/2$ you’ll need $6$ extra tosses beyond the first one; this is the $\frac12\cdot 6$ term.

Now suppose that $N=3$ and $M=1$. You’ll definitely need at least $1$ more toss. With probability $1/2$ it’s a tail, and you’ll be starting over. In that case the expected number of flips after this first one is $2^{3+1}-2=14$, giving a $\frac12\cdot 14$ term (analogous to the $\frac12\cdot 6$ term in the original problem). With probability $1/2$ you’ll get a head, and at this point you’ll be solving the $N=3,M=2$ problem. Suppose that you’ve already done it and discovered that the expected number of flips is $x$; then with probability $1/2$ it will take another $x$ flips after the first one, so you get a $\frac12x$ term, for a total of $1+\frac12\cdot14+\frac12x$ expected extra flips.

I’ll leave it to you to try the $N=3,M=2$ problem using these ideas and substitute the result for $x$.

share|improve this answer
    
so 1+0.5*14 = 8 is correct for N = 3, M = 1 and 1+0.5*14+0.5*8 = 12 for N = 3 and M = 2? –  Shawn Mclean Jan 7 '12 at 22:29
    
My last calculation seems wrong, the number should be lower. I understand it when it comes to M = 1 but when it gets higher I don't know what to do. –  Shawn Mclean Jan 7 '12 at 22:40
    
so basically this is formula 1 + 0.5y + 0.5x where y is expected number of flips if we start over and x is the expected in the next step? –  lukas Jan 9 '12 at 0:12
    
@lukas: Yes. After the first flip, the expected number of additional flips is $$P(\text{tail})\cdot(\text{ expected number of flips starting from }0)+P(\text{head})\cdot(\text{ exp. nr. of additional flips starting from }M+1)$$ –  Brian M. Scott Jan 9 '12 at 2:14
    
hmmm my solution somehow produces incorrect results. I calculate the expected nr form m = n-1 to m+1 pastie.org/3152025 –  lukas Jan 9 '12 at 2:57
add comment

To answer your first question:

They are doing what's called conditioning.

If $\Bbb E(X)$ denotes the expected value of $X$ and if $A$ and $B$ are disjoint and exhaustive events (either $A$ or $B$ must occur, but they cannot both occur at the same time), then $$ \Bbb E(X)=P(A) \Bbb E( X\text{ given }A) +P(B) \Bbb E( X\text{ given }B) $$

The 1 is there because you know the number of additional flips needed is at least one. Then, they compute the number of (even more) additional flips needed to obtain three heads in a row. Towards this end they use the conditioning formula above with $A$ and $B$ as below:
Case A: that flip was a head. This occurs with probability 1/2 and in this case, no more flips are needed.

Case B: that flip was a tail. This occurs with probability 1/2, and in this case the expected number of additional flips is 6 (since it's as if you start over).

So overall, the expected number of additional flips is

$$ 1+ \underbrace{ (1/2) }_{ \text{prob of }\atop\text{ case A}}\cdot \underbrace{\vphantom{(/} 0 }_{\text{exp. num. of add. }\atop\text{flips in case A}}+ \underbrace{ (1/2) }_{\text{prob of} \atop \text{case B} }\cdot \underbrace{6\vphantom{(/}}_{\text{exp. num. of add.}\atop \text{flips in case B}}. $$


I think it's easier to understand if you don't start with "1":

Let $A$ be the event that the second flip is heads and $B$ be the event that the second flip is tails. Note if $A$ occurs, then the expected number of additional flips past the first is 1. If $B$ occurs, the expected number of additional flips past the first flip is $1+6$.

The expected number of additional flips (past the first flip) is

$$ \underbrace{ (1/2) }_{ \text{prob of }\atop\text{ case A}}\cdot \underbrace{\vphantom{(/} 1 }_{\text{exp. num. of add. }\atop\text{flips in case A}}+ \underbrace{ (1/2) }_{\text{prob of} \atop \text{case B} }\cdot \underbrace{7\vphantom{(/}}_{\text{exp. num. of add.}\atop \text{flips in case B}}. $$

share|improve this answer
    
Thank you, could you do this example: N = 3, M = 2 so I can see if this formula is expanded? –  Shawn Mclean Jan 7 '12 at 22:24
    
@Lol coder For $N=3$ and $M=2$, It's almost exactly the same argument; except that you first need to find the expected number of flips to obtain three heads in a row (replace the "6" above with this number, and it goes through). Try your hand at it please. If you run into trouble, I'll be glad to help. (Certain other cases have an "expanded formula", where you condition on three or more events...) –  David Mitra Jan 7 '12 at 22:39
    
Its supposed to be 8 based on the examples but when I calculate it I get 8.5. Here is my calculation: 1 + 0.5 * 1 + 0.5 * 14 –  Shawn Mclean Jan 7 '12 at 22:44
    
@Lol coder $1+0.5*0+0.5*14$ (assuming that the expected number of flips to get three heads in a row is 14). –  David Mitra Jan 7 '12 at 22:51
    
and with M = 1, 2 + 0.5 * 0 + 0.5 * 14 which is 9 right? –  Shawn Mclean Jan 7 '12 at 23:06
show 3 more comments

Let the expected number of coin flips be x. The case analysis goes as follows:

a. If the first flip is a tails, then we have wasted one flip. The probability of this event is 1/2 and the total number of flips required is x+1

b. If the first flip is a heads and second flip is a tails, then we have wasted two flips. The probability of this event is 1/4 and the total number of flips required is x+2

c. If the first flip is a heads and second flip is also heads, then we are done. The probability of this event is 1/4 and the total number of flips required is 2.

Adding, the equation that we get is - x = (1/2)(x+1) + (1/4)(x+2) + (1/4)2

Solving, we get x = 6.

Thus, the expected number of coin flips for getting two consecutive heads is 6.

share|improve this answer
    
I know how to do this part, the confusing part is the calculation: 1 + (0.5 * 0 + 0.5 * 6) = 4.0 due to already having 1 heads. –  Shawn Mclean Jan 7 '12 at 22:17
    
also check this link for a detailed explanation: marknelson.us/2011/01/17/20-heads-in-a-row-what-are-the-odds –  Abhishek Sakhaparia Jan 7 '12 at 22:19
add comment

I posted a derivation of the generalized solution to this problem here.

share|improve this answer
add comment

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.