# 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 one 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: $R{k,n - 1}$ and $~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 $n$th toss is head. Then the $k$th 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,cdots,H]$.Define $S$ as the fact that the last $k+1$ tosses of $n$ tosses are $[T,H,H,cdots,H]$. The condition now becomes $~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)$.

- $R{k,n - 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:

- $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_0$.
- 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_0$.
- Once state becomes $S_k$, it will never change again.

*Definition*:

- $d_i$
- The probability distribution vector after the $i$th toss is a column vector of length $k+1$, whose $h$th element is the probability that current state is $S_(h - 1)$.

Initially, $d_0 = [1, 0, 0, cdots, 0]^T$; $d_(i+1) = M xx d_i$, wherein $M$ is the probability distribution transition matrix.

$M$ can be reduced from lemmas above:

$M = [[1/2, 1/2, 1/2, cdots, 1/2, 0], [1/2, 0, 0, cdots, 0, 0], [0, 1/2, 0, cdots, 0, 0], [0, 0, 1/2, cdots, 0, 0], [vdots, vdots, vdots, ddots, 0, 0], [0, 0, 0, cdots, 1/2, 1]]$

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

$P = [0,0,cdots,0,1] xx d_n$ $= [0,0,cdots,0,1] xx M^n xx d_0$.

### Method Three

Use the fact “the probability that no runs of k consecutive tails will occur in n coin tosses is given by $F_(n+2)^((k))//2^n$, where $F_l^((k))$ is a Fibonacci $k$-step number” from Wolfram MathWorld.