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

This entry was posted in coin flipping, probability. Bookmark the permalink.

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

• mzspivey says:

Good catch, Chris! I’ll fix it.

2. velikod says:

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

3. jordancurve says:

I solved this with (what I regard as) a simpler approach that uses the *number of flips until heads* lemma twice: http://mathb.in/34950

Basically, I calculate the expected number of *trials* until a *successful trial*, where each trial involves flipping the coin until it comes up tails, and a trial is successful if it has n or more heads before the tail. I then multiply the expected number of trials by the expected number of flips per trial, and I subtract from that the expected number of *excess flips* that happened after the nth head on the final (successful) trial.