Drawing Blanks

Premature Optimization is a Prerequisite for Success

Expected number of tosses to get N heads in a row

with 2 comments

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.

Advertisements

Written by bbzippo

11/25/2009 at 7:19 pm

Posted in math

2 Responses

Subscribe to comments with RSS.

  1. […] 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? […]

  2. […] 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 […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: