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],$

$\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.)

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

Chris WoytowitzChris says:

May 22, 2013 at 7:52 pm

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

- mzspivey says:
  
  May 22, 2013 at 8:02 pm
  
  Good catch, Chris! I’ll fix it.
  
velikod says:

February 8, 2017 at 7:34 am

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