0
$\begingroup$

I'm wondering if there is a nice solution for this problem. As stated, I flip a coin $n$ times, and want the probability of a run of 3 (or more) heads appearing within it. For example, if I toss a coin 9 times, an example that would include a run of 3 heads is TTHHHTHTH, as is THTHHHHHT, but TTHHTHTTH is not.

Generalisations to runs of $m$ (or more) heads also welcome!

$\endgroup$
  • $\begingroup$ Are you familiar with Markov chains? $\endgroup$ – Crostul Apr 23 '18 at 9:31
  • 1
    $\begingroup$ somewhat. Gave a quick google and believe I'd be fine with an answer relating to them. I have a pure maths degree, but it's been a while since I've looked at this sort of stuff $\endgroup$ – John Apr 23 '18 at 9:38
  • $\begingroup$ @Crostul I answered without Markov. Am I wrong? $\endgroup$ – BCLC Apr 23 '18 at 9:40
  • $\begingroup$ ? gregegan.net/QUARANTINE/Runs/Runs.html $\endgroup$ – BCLC Apr 23 '18 at 10:19
1
$\begingroup$

The time $T_{m+1}$ needed to get a run of $m+1$ heads is $$T_{m+1}=T_m+1$$ with probability $p_H=\frac12$ and $$T_{m+1}=T_m+1+T'_{m+1}$$ with probability $p_T=1-p_H=\frac12$, where $T'_{m+1}$ is distributed like $T_{m+1}$ and independent of $T_m$.

Thus, the generating functions $g_m(s)=E(s^{T_m})$ are such that

$$g_{m+1}(s)=\frac12s(g_m(s)+g_m(s)g_{m+1}(s))\tag{$\ast$}$$

From there, the solution is standard. First, $(\ast)$ can be rewritten as $$g_{m+1}(s)=\frac{sg_m(s)}{2-sg_m(s)}$$ hence $$\frac1{g_{m+1}(s)}-\frac{s}{2-s}=\frac2s\left(\frac1{g_m(s)}-\frac{s}{2-s}\right)$$ that is, using $g_0(s)=1$,$$\frac1{g_m(s)}=\left(\frac2s\right)^m\left(1-\frac{s}{2-s}\right)+\frac{s}{2-s}$$ from which every $g_m(s)$ follows as

$$g_m(s)=\frac{s^m(2-s)}{2^{m+1}(1-s)+s^{m+1}}$$

For example, for $m=1$, $$g_1(s)=\frac{s^2}{2-s}$$ that is, $T_1$ is a shifted geometric random variable. More generally, recall that each function $g_m$ fully encodes the distribution of $T_m$ since, by definition, $$g_m(s)=\sum_{k=0}^\infty P(T_m=k)s^k$$ thus, expanding $g_m(s)$ as a power series yields every $P(T_m=k)$. If one is interested to observe a run of length $m$ during the $k$ first draws, one would simply compute $$P(T_m\leqslant k)$$

$\endgroup$
  • 1
    $\begingroup$ It's been a long time since I've used generating functions, so I may just be a little rusty - but looking to use this to find a probability of a run occurring within a given number of flips (not the number of flips before a given run occurs), and I'm not quite clear how to get that from your answer. Could you explain? Thanks! $\endgroup$ – John Apr 23 '18 at 9:50
  • 1
    $\begingroup$ See addition at the end of the post. $\endgroup$ – Did Apr 23 '18 at 9:54
  • 1
    $\begingroup$ thanks! My follow on question then I suppose is if there is a nice closed form for the last expression $\endgroup$ – John Apr 23 '18 at 10:01
  • $\begingroup$ There is: factor the denominator of $g_m(s)$, cancel the factor $2-s$ an decompose the rest into a sum of simple elements $$g_m(s)=s^m\sum_w\frac{c_w}{w-s}$$ for some given $w$ and $c_w$, to conclude that, for every $k\geqslant m$, $$P(T_m=k)=\sum_w\frac{c_w}{w^{k+1-m}}$$ and $$P(T_m\geqslant k)=\sum_w\frac{c_w}{w^{k-m}(w-1)}$$ $\endgroup$ – Did Apr 23 '18 at 10:04
0
$\begingroup$

If you toss a coin $n$ times, there are $2^n$ possible outcomes, each of which has probability $1/2^n$ of occurring.

The number of favorable outcomes is found by subtracting those outcomes in which three consecutive heads do not occur from the total number of outcomes.

Let $a_n$ be the number of sequences of length $n$ which do not contain three consecutive heads. Since it is not possible for three consecutive heads to occur until the coin has been tossed three times, $a_1 = 2$ and $a_2 = 4$. Since the only outcome in which three consecutive heads occurs when the coin is tossed three times is HHH, $a_3 = 2^3 - 1 = 7$.

We write a recurrence relation for the number of sequences of length $n$ that do not contain three consecutive heads. We condition based on the most recent occurrence of tails. The most recent occurrence of tails must occur in one of the last three positions, otherwise we would have three consecutive heads.

  • An admissible sequence of length $n$ that ends in tails is formed by appending a T to an admissible sequence of length $n - 1$, of which there are $a_{n - 1}$.
  • An admissible sequence of length $n$ that ends in TH is formed by appending a TH to an admissible sequence of length $n - 2$, of which there are $a_{n - 2}$.
  • An admissible sequence of length $n$ that ends in THH is formed by appending an THH to an admissible sequence of length $n - 3$, of which there are $a_{n - 3}$.

Hence, the number of sequences of length $n$ that do not contain three consecutive heads satisfy the recurrence relation $$a_n = a_{n - 1} + a_{n - 2} + a_{n - 3}, n \geq 4$$ Thus, the number of sequences of length $n$ that do not contain three consecutive heads is given by the recursion \begin{align*} a_1 & = 2\\ a_2 & = 4\\ a_3 & = 7\\ a_n & = a_{n - 1} + a_{n - 2} + a_{n - 3}, n \geq 4 \end{align*} This is oeisA000073.

The desired probability is then $$\Pr(\text{contains run of three consecutive heads}) = \frac{2^n - a_n}{2^n} = 1 - \frac{a_n}{2^n}$$

$\endgroup$
-1
$\begingroup$

Let $H_m$ be the event that the $m$th toss is heads. Then 3 heads is $$A_m := H_m \cap H_{m+1} \cap H_{m+2}$$

where $m = 1$ to $n-2$. Thus, by inclusion-exclusion, a probability of a run of 3 heads is

$$P(\bigcup_{k=1}^{n-2} \bigcap_{i=0}^2 H_{k+i}) = P(\bigcup_{k=1}^{n-2} A_k)$$

$$ = \sum_{i=1}^{n-2} P(A_i) - \sum_{1 \le i < j \le n-2} P(A_i \cap A_j) + \sum_{1 \le i < j < k \le n-2} P(A_i \cap A_j \cap A_k)$$

Now, $P(A_i \cap A_j \cap A_k) = 0$ unless $i+2=j+1=k$ in which case we have $P(A_i \cap A_j \cap A_k) = P(H_k)$

Similarly, $P(A_i \cap A_j) = 0$ unless $i+1=j$ or $i+2=j$ in which cases we respectively have $P(A_i \cap A_j) = P(H_j \cap H_{j+1})$ and $P(A_i \cap A_j) = P(H_j)$

$\endgroup$
  • $\begingroup$ yes, but actually enumerating this (particularly given the intersection of Hk∩Hk+1∩Hk+2 with Hj∩Hj+1∩Hj+2 is non-empty) is the challenge $\endgroup$ – John Apr 23 '18 at 9:45
  • $\begingroup$ @John What do you mean by enumerating? $\endgroup$ – BCLC Apr 23 '18 at 9:52
  • $\begingroup$ enumerating might not be the best word, but providing an actual expression for the result, not just describing the set. Note that the sequence HHHH...HHH for example would be in every Hk∩Hk+1∩Hk+2, but should only feature once in the union $\endgroup$ – John Apr 23 '18 at 9:55
  • $\begingroup$ @John ok now? $ \ $ $\endgroup$ – BCLC Apr 23 '18 at 10:15
  • $\begingroup$ @John you mean evaluate? $\endgroup$ – BCLC Apr 24 '18 at 19:43

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.