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 of being heads. Let 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 ?

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 , or is tails, with probability . 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 must satisfy the following equation:

Solving it, we get , which should make sense if you think about it. (For example, if the probability of getting a head is , 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 until we see consecutive heads for the first time. Suppose that we have just seen consecutive flips. Then, with probability , we get a head on the next flip. This would give us consecutive heads. With probability we get a tail on the next flip, and so the process of obtaining consecutive heads restarts itself. In other words,

which can be rewritten as

Applying the law of iterated expectation, we get

or

This gives us a nice recurrence for that is easy to unroll. Doing so, while using the fact that , yields

and, in general,

.

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

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

### Like this:

Like Loading...

*Related*

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

Good catch, Chris! I’ll fix it.

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

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.