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