Wangling

Problem: What’s the probability that at least one run of k consecutive heads occurs in n coin tosses?

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}.

1. R{k,n-1}

   R{k,n} follows necessarily. There are 2H(k,n-1) permutations of this kind.

2. ~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.

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:

• S_t(0 ≤ t < k): no runs of k consecutive heads have occurred, and t heads have accumulated in the last run.
• S_k: at least one run of k consecutive heads has occurred.

Lemmas:

• The initial state is S₀.
• If current state is S_t(0 ≤ t < k), next state has equal opportunity, i.e.1/2, to be S_t+1 or S₀.
• Once state becomes S_k, it will never change again.

Definition:

• d_i: 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 S_h-1.

Initially, d₀ = [1;0;0;...;0]; d_i+1 = M ⋅ d_i, wherein M is the probability distribution transition matrix.

M can be reduced from lemmas above:

Thus, the last element of d_n is the probability desired, denoted as P.

P = [0,0,...,0,1] ⋅ d_n = [0,0,...,0,1] ⋅ Mⁿ ⋅ d₀.

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.