The Probability of Runs of k Consecutive Heads in n Coin Tosses
Problem: What’s the probability that at least one run of k consecutive heads occurs in n coin tosses?
Method One:
Definitions:
- R{k,n}: the fact that at least one run of k consecutive heads occurs in n coin tosses.
- ~E: the fact that event E does not occur.
- A & B: the fact that event A and event B occur simultaneously.
- P(E): the number of permutations that cause event E to occur.
- H(k,n): the number of head-or-tail permutations for n coins that contain at least one run of k consecutive heads; the same as P(R{k,n}).
Theorem:
P(A & B) + P(A & ~B) = P(A)
Analysis:
If n = k, R{k,n} occurs in exactly once case, so H(k,n) = 1.
If n < k, R{k,n} is impossible, so H(k,n) = 0.
Otherwise(n > k), H(k,n) permutations can be divided into two groups: (a) R{k,n-1}, and (b) ~R{k,n-1}.
- R{k,n-1}
R{k,n} follows necessarily. There are 2H(k,n-1) permutations of this kind.
- ~R{k,n-1}
R{k,n} occurs only if the last k-1 of the first n-1 toss are all heads and the nth toss is head. Then the kth last toss of the first n-1 tosses must be tail, otherwise the last k of the first n-1 tosses are all heads, which contradicts ~R{k,n-1}. Hence, the last k+1 tosses are fixed as [T,H,H,...,H].
Definition:
- S: the fact that the last k+1 tosses of n tosses are [T,H,H,...,H].
The condition now turns out to be ~R{k,n-1} & S, which is equivalent to ~R{k,n-k-1} & S. Thus the permutation number is
P(~R{k,n-k-1} & S) = P(S) – P(R{k,n-k-1} & S) = 2(n-k-1) – H(k,n-k-1).
Thus,
- H(k,n) = 2H(k,n-1) + 2(n-k-1) – H(k,n-k-1), for n > k;
- H(k,n) = 1, for n = k;
- H(k,n) = 0, for n < k.
Method Two:
A cool method using probability distribution vector and probability distribution transition matrix. The original post is in Chinese. I am trying to translate it into English below. The author even proved the property used in Method Three along the line; however, this part is beyond my knowledge.
The states during the process of coin tossing is defined as follows:
- St(0 ≤ t < k): no runs of k consecutive heads have occurred, and t heads have accumulated in the last run.
- Sk: at least one run of k consecutive heads has occurred.
Lemmas:
- The initial state is S0.
- If current state is St(0 ≤ t < k), next state has equal opportunity, i.e.1/2, to be St+1 or S0.
- Once state becomes Sk, it will never change again.
Definition:
- di: the probability distribution vector after the ith toss is a column vector of length k+1, whose hth element is the probability that current state is Sh-1.
Initially, d0 = [1;0;0;...;0]; di+1 = M ⋅ di, wherein M is the probability distribution transition matrix.
M can be reduced from lemmas above:

Thus, the last element of dn is the probability desired, denoted as P.
P = [0,0,...,0,1] ⋅ dn = [0,0,...,0,1] ⋅ Mn ⋅ d0.
Method Three:
Use the fact “the probability that no runs of
consecutive tails will occur in
coin tosses is given by
, where
is a Fibonacci
-step number” from mathworld.wolfram.com/CoinTossing.html.
Loading...