What is the probability of flipping N consecutive heads in K coin flips? Now that you are all on the edge of your seats, let me explain.
We flip a coin with probability of success, p, and probability of failure, q (for a fair coin, p = q = 0.5). P(K) denotes the probability of flipping a run of N successes in K coin flips. In order to successfully achieve a run of N successes in K coin flips (P(K)), one of two scenarios must be true:
- You already flipped the run of N successes somewhere in the previous sequence of K-1 flips
- You flip the run of N successes with the N’th successful outcome at flip K
The union of scenario 1 and 2 equals P(K), the probability you achieve a run of N successes in K coin flips:
P(K) = P(scenario 1) + P(scenario 2)
Scenario 1 is straightforward to formulate. By definition, we say:
P(scenario 1) = P(K-1)
Scenario 2 is a bit trickier to formulate. But if we know the K’th coin flip was involved in the successful run, and the success was not found in the previous 1 to K-1 coin flips (otherwise we would be in scenario 1), we know three facts about the outcomes of the previous coin flips:
Using N=3 as an example, we know the sequence of coin flips from 1 to K must look like:
The sequence of pink “?” from coin flip 1 to K-N-1 means we don’t know exactly whether the flip was a success (S) or fail (F), but just that there was not a run of N successes in that sequence. The probability that there was a run of N successes from flips 1 to K-N-1 is simply given by P(K-N-1), but since we want the probability of this not happening, we formulate it as 1-P(K-N-1).
The red “F” at flip K-N means that specific flip must have been a fail. If it were a success, the K’th flip would not have contributed to the run of N successes and we again would be in scenario 1, not scenario 2. This probability of the one fail is simply denoted as q.
The green “S” from flips K-N+1 (K-2 in this example with N=3) to K means those flips all had to be a success. This is formulated as the probability of success (p) N times in a row, or p^N.
We multiply the probabilities of the three terms to formulate scenario 2 as:
Putting it all together, the probability of achieving a run of N successes in K coin flips is given by:
Note that this equation is recursive, so we have some base cases to fill in. When K < N, P(K) = 0 because, for example, you cannot achieve a run of 3 successful coin flips in only 2 coin flips. When K = N, the probability is equal to p^N (the probability of a run of N successes in N coin flips means every flip has to be a success).
