[sidchilling]

What is the number of expected number of coin tosses to get N consecutive heads when M consecutive heads has been obtained?

For example, suppose we need 3 consecutive heads. It is given that in the first two coin tosses you get 2 heads. Now, what is the expected number of coin tosses for getting 3 consecutive heads.

[ebaines]

The number of expected tosses to get to 3 heads in a row is 14. If you do a table of the probability for it taking N tosses, you get this:

P(N=3) = (1/2)^3 = 1/8. This is the probabuility for the sequence HHH.
P(N=4) = (1/2)^4 = 1/16 The only sequence that works for 4 is THHH, hence P(4) = 1/16.
P(N= 5) = 1/16. You don't care what the first toss is, but the last 4 must be THHH.
P(N=6) = 1/16. You don't care what either of the first two tosses are, but the last 4 must be THHH.
P(N=7) = P(N not equal 3) x 1/16. This is where it starts to get interesting. You have to take care that the first three tosses are not all heads - otherwise you wouldn't get past the 3rd toss. So we have to subtract that probability, and we get (1-P3) x 1/16 = 7/8 x 1/16.
P(N=8) = (1-P3-P4) x 1/16 = 13/16 x 1/16.
P(N=9) = (1 - P3 - P4 - P5) x 1/16 = 3/4 x 1/16
P(N=10)= (1-P3-P3-P5-p6) x 1/16 = 11/16 x 1/16
P(N=11) = (1 - P3-P4-P5-P6-P7)x 1/16 = (1-P3-P4-P5-P6-(1-P3)/16)) x 1/16
etc.

You can see this becomes a recursive calculation.

The expected value is then the sum of N times P(N) for N = 3 to infinity. I don't have a proof for why this turns out to be 14, but using a spreadsheet to sum the first 200 tems that's what I get. And as a check the sum of the probabilities for the first 200 terms is 0.99999994, which is very close to 1, as expected.

[corrigan]

If you have two consecutive heads and toss a coin again and it isn't heads, then you will no longer have two consecutive heads. You may get a heads on a subsequent toss, but that would not be three consecutive heads. So I don't know why you included

when M consecutive heads has been obtained?

I think you need to review the problem, or review your definition of "consecutive".

[ebaines]

To follow up on this thread, we can get a general solution for the expected number of flips to get n consecutive heads. Start with the simplest case of N=1. If we define the expected number of flips to get 1 head as E, the we can create an equation for E as follows:

Suppose on the first flip we get a head. Then E=1 and the chance of that happening is 1/2. But if we get a tails instead we've used up 1 flip and still have E to go. So we get an equation that defins E in terms of itself like this:

E = 1/2(E+1) + 1/2 (1)

The second term on the right hand side of the equation accounts for the probability of getting a head on flip number 1, and the first term accounts for the probability of not getting a head and still having E flips to go. Solve for E and you find E=2.

Now let's try it for N=2. If we get tails on the first flip we've wasted a one turn and have 1/2(E+1) on the right side again. But if we get a heads then we have to think about what might happen next: there's a 1/2 chance of the next flip being tails, in which case we have to start over again and have wasted 2 flips. But if its heads we're done. Putting this together we have:

E=1/2(E+1) + 1/4(E+2) + 1/4(3)

Solve for E and you get E=6 for n = 3.

For three heads it works out to be E = 1/2(E+1) + 1/4(E+2) + 1/8(E+3) + 1/8(3), which gives E = 14.

The general solution formula for this can be written as:



Hence:
E(1) = 2,
E(2) = 6,
E(3) = 14,
E(4) = 30, etc.