The Expected Number of Flips for a Coin to Achieve n Consecutive Heads

A common probability problem is to determine the expected number of flips required before a coin comes up heads the first time.  The coin doesn’t even have to be fair; the analysis is pretty much the same even if the coin is biased.

So let’s suppose we have a biased coin with probability p of being heads.  Let X_1 denote the number of flips before the coin turns up heads for the first time.  (The “1” is because we’re after the first occurrence of heads.)  What is E[X_1]?

There is more than one way to tackle this problem.  In my opinion the following argument is simplest.  The first flip is heads, with probability p, or is tails, with probability 1-p.  If the first flip is heads, then we’re done.  If the first flip is tails, then the coin flipping process essentially restarts itself.  This means that E[X_1] must satisfy the following equation:

\displaystyle E[X_1] = p(1) + (1-p)(1 + E[X_1]).

Solving it, we get E[X_1] = \frac{1}{p}, which should make sense if you think about it.  (For example, if the probability of getting a head is \frac{1}{5}, then it should take about 5 flips on average to obtain the first head.)

This argument generalizes nicely to the problem of finding the expected number of flips X_n until we see n consecutive heads for the first time.  Suppose that we have just seen n-1 consecutive flips.  Then, with probability p, we get a head on the next flip.  This would give us n consecutive heads.  With probability 1-p we get a tail on the next flip, and so the process of obtaining n consecutive heads restarts itself.  In other words,

\displaystyle E[X_n | X_{n-1}] = p(X_{n-1}+1) + (1-p)(X_{n-1} + 1 + E[X_n]),

which can be rewritten as

\displaystyle E[X_n | X_{n-1}] = X_{n-1}+1 + (1-p)E[X_n].

Applying the law of iterated expectation, we get

\displaystyle E[X_n] = E[X_{n-1}] + 1 + (1-p)E[X_n],

or

\displaystyle E[X_n] = \frac{E[X_{n-1}] + 1}{p}.

This gives us a nice recurrence for E[X_n] that is easy to unroll.  Doing so, while using the fact that E[X_1] = \frac{1}{p}, yields

\displaystyle E[X_2] = \frac{1}{p^2} + \frac{1}{p},

\displaystyle E[X_3] = \frac{1}{p^3} + \frac{1}{p^2} + \frac{1}{p},

and, in general,

\displaystyle E[X_n] = \frac{1}{p^n} + \frac{1}{p^{n-1}} + \cdots + \frac{1}{p}.

This expression for E[X_n] is the partial sum of a geometric series.  There is a nice formula for that, and so our expression for E[X_n] simplifies to

\displaystyle E[X_n] = \frac{1-p^n}{(1-p)p^n} = \frac{1/p^n-1}{1-p}.

(This post is based on my answer to the math.SE question “Expected number of tosses for two coins to achieve the same outcome for five consecutive flips,” where a slightly different problem is considered.  David Mitra’s answer there gives another approach.)

Advertisements
This entry was posted in probability. Bookmark the permalink.

3 Responses to The Expected Number of Flips for a Coin to Achieve n Consecutive Heads

  1. Nice work! I think you missed a minus sign in your last simplification.

  2. velikod says:

    The best (neatest) solution to this problem I’ve seen on the Internet!

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