1
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Is the sequence $THTHH$ valid as well for the case two consecutive heads? $\endgroup$ Apr 20, 2018 at 15:09
  • $\begingroup$ @callculus Oops yes, you got what I meant.. I wonder if I missed anything else $\endgroup$
    – Richard
    Apr 20, 2018 at 15:10
  • $\begingroup$ I will say the answer is 19 by my method, but I cannot tell what is missing right now. $\endgroup$
    – Hw Chu
    Apr 20, 2018 at 15:16
  • 1
    $\begingroup$ I'd do it recursively. Count the "bad" sequences, i.e. those without a string of the form $H^k$. if a bad sequence has at least $k$ terms then it must end in one of $\{T,TH,\cdots, TH^{k-1}\}$. $\endgroup$
    – lulu
    Apr 20, 2018 at 15:19
  • $\begingroup$ @lulu So is it too hard to get a closed form? Or at least a couple of bounds $\endgroup$
    – Richard
    Apr 20, 2018 at 15:42

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I need to leave now. lulu's idea is the same of mine, but I cannot elaborate, will edit this post later if needed. $\endgroup$
    – Hw Chu
    Apr 20, 2018 at 15:20
  • $\begingroup$ +1 So is it too hard to get a closed form? Or at least a couple of bounds $\endgroup$
    – Richard
    Apr 20, 2018 at 15:41
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.