# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## Expected number of tosses to get N heads in a row

I wrote before how to compute the expected number of coin tosses needed to throw a head:
https://bbzippo.wordpress.com/2009/11/05/expected-number-of-coin-tosses/

I mentioned that I didn’t have a rigorous solution for N heads in a row, and I was asked to at least present a non-rigorous one.
Ok, let’s say we know the expectation to get N heads in a row and it equals to E(N). Now we want to compute E(N+1). How many tosses on average do we need to turn N heads into N+1 heads? With the probability 1/2 you need only 1 additional toss. But if you fail to throw a head with that one toss, you need to start over and end up tossing the coin E(N+1) times on average, plus that 1 time that gave you a tail.
So E(N+1) = E(N) + 1/2 + 1/2*(E(N + 1) + 1)
Or E(N+1) = 2*E(N) + 2
Since we know E(1) = 2 then E(2) = 6, E(3) = 14, etc.
It’s not difficult to come up with a non-recursive formula:
E(N) = 2*(2^N – 1)

Why is this solution not rigorous? Because you can’t manipulate expectation values like this without saying a lot of additonal blah-blah about your random variables being independent or dependent, and the expectation being a linear function, maybe about Markov chains, etc.

Written by bbzippo

11/25/2009 at 7:19 pm

Posted in math