8
$\begingroup$

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)?

  • 0
    @ByronSchmuland really? so N=3, M=1 will be 12?2012-01-08

4 Answers 4

5

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

  • 0
    hmmm my solution somehow produces incorrect results. I calculate the expected nr form m = n-1 to m+1 http://pastie.org/31520252012-01-09
2

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

  • 0
    @David so the algo is: 1 if N equals 0 then result is 0. 2. if m equals 0 then result equals 2^n+1 -2. 3. http://pastie.org/31515382012-01-09
0

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.

  • 0
    also check this li$n$k for a detailed explanation: http://marknelson.us/2011/01/17/20-heads-in-a-row-what-are-the-odds/2012-01-07
0

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