How many possibilities are there for at least $k$ consecutive heads to show up out of $n$ tosses?

Question

Consider $n$ coin tosses. In how many ways can we have at least $k$ consecutive heads? Call this number $f(n,k)$. Is there a general expression for it? Or at least tight upper and lower bounds?

For example take $n=5,k=2$. Then the possibilities are:

HHTTT, THHTT, TTHHT,TTTHH,

HHHTT, HHTHT, HHTTH, THHHT, THTHH, THHTH, HTHHT, TTHHH, HTTHH,

HHHHT, HHHTH, HHTHH, HTHHH, THHHH,

HHHHH.

that is 19 ways

Answer 1

We consider the binary alphabet $V=\{H,T\}$. We are looking for the number $g(n,k)$ of strings of length $n$ having runs of $H$ at most length $k-1$. The wanted number is $$f(n,k)=2^n-g(n,k)$$

Strings with no consecutive equal characters at all are called Smirnov or Carlitz words. See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.

A generating function for the number of Smirnov words over a binary alphabet is given by \begin{align*} \left(1-\frac{2z}{1+z}\right)^{-1}\tag{1} \end{align*}

Replacing occurrences of $H$ in a Smirnov word by one up to $k-1$ $H$ generates words having runs of $H$ with length less than $k$. \begin{align*}\ z\longrightarrow z+z^2+\cdots+z^{k-1}=\frac{z\left(1-z^{k-1}\right)}{1-z}\tag{2} \end{align*}

Since there are no restrictions to the length of runs of $T$'s we replace occurrences of $T$ in a Smirnov word by one or more $T$s. \begin{align*}\ z\longrightarrow z+z^2+\cdots=\frac{z}{1-z}\tag{3} \end{align*}

The resulting generating function is by substituting (2) and (3) in (1) \begin{align*} \left(1- \frac{\frac{z\left(1-z^{k-1}\right)}{1-z}}{1+\frac{z\left(1-z^{k-1}\right)}{1-z}}-\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}\right)^{-1} &=\frac{1-z^k}{1-2z+z^{k+1}} \end{align*}

Denoting with $[z^n]$ the coefficient of $z^n$ in a series we obtain the number of wanted words of length $n$ as \begin{align*} \color{blue}{f(n,k)}&=2^n-g(n,k)\\ &\color{blue}{=[z^n]\left(\frac{1}{1-2z}-\frac{1-z^k}{1-2z+z^{k+1}}\right)} \end{align*}

Example: Let's look at OPs example. We take $k=2$. We obtain with some help of Wolfram Alpha \begin{align*} \frac{1}{1-2z}-\frac{1-z^2}{1-2z+z^{3}}=z^2+3 z^3 + 8z^4+\color{blue}{19} z^5 + 43 z^6 +\cdots \end{align*}

The blue colored coefficient of $z^5$ shows there are $\color{blue}{19}$ words of length $5$ built from characters $\{H,T\}$ and runs of $H$ with length at least $k=2$ in accordance with OP's result.

Answer 2

The "dual" question is easier to answer. Namely, let us define $g(n,k)$ as the number of combinations of $n$ coin tosses where at most $k$ consecutive heads can show up. By adding a $T$ in front of the sequence, it is equivalent to count a sequence of length $n+1$ composed by $k+1$ possible sequences $T$, $TH$, $THH$, ..., $TH\cdots H$ ($k$ $H$'s). So you have the recursive relation:

$$ g(n, k) = g(n-1, k) + g(n-2, k) + \cdots + g(n-k-1, k), $$

with the initial conditions $g(n, k) = 2^n$ for $1 \leq k \leq n$ and $g(n+1, k) = 2^{n+1}-1$. This gives you enough information for a general formula, though it will still be hard for a "pen and paper" calculation.

Answer 3

This problem is better approached by looking first at the number $g(n,k)$ of $n$ coin toss outcomes that have less than $k$ consecutive heads. Call such outcome 'valid'. Each valid outcome will start with one of T, HT, HHT,... up to H...HT with $k-1$ H's at the beginning, and the number of valid outcomes in each case will be $g(n-1,k), g(n-2,k), \dots , g(n-k,k)$. This leads to the recurrence relation: $g(n,k) = g(n-1,k) + g(n-2,k) + \cdots + g(n-k,k)$. The initial values for that recurrence are $g(1,k) = 2, g(2,k) = 4,\dots, g(k-1,k) = 2^{k-1}, g(k,k) = 2^k - 1$. Solve the recurrence, and then the function you are looking for is $f(n,k) = 2^n - g(n,k)$. The particular case you mention with $n=5$, $k=2$ yields the recurrence $g(n,2) = g(n-1,2) + g(n-2,2)$, $g(1,2) = 2$, $g(2,2) =3$, so $g(n,k)$ is the $(n+2)$th Fibonacci number, hence $g(5,2) = F_7 = 13$, and $f(5,2) - 2^5 - 13 = 19$ (besides the 17 outcomes you wrote there are two more, namely HTTHH and THTHH).