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

[…] https://bbzippo.wordpress.com/2009/11/25/expected-number-of-tosses-general/ – What is the average number of coin tosses needed to throw n heads in a row? […]

On the “Son born on a Tuesday” probability puzzle « Drawing Blanks08/30/2010 at 12:10 am

[…] of tosses to get m heads in a row. UPDATE: Expected number of tosses to get N heads in a row: https://bbzippo.wordpress.com/2009/11/25/expected-number-of-tosses-general/ “Expectaion” is an anagram of “Inexact […]

Expected number of coin tosses « Drawing Blanks09/17/2010 at 11:42 pm