1
$\begingroup$

We toss $n$ coins and the probability that coin $i$ gets a head is $p_i$. All the coin tosses are independent.

I am interested in the probability that there exists a run of consecutive heads of length at least $k$ for $k \geq 1$. I am aware of a solution where all the coins are fair (https://oeis.org/A50232).

As I can't solve my problem I ran a simulation with $n = 10$ and $p_i = i/10$ for $i=\{1,\dots, 10\}$. Here we get the following approximations (two decimal places) for the probability that the maximum length run of heads is exactly $t$:

  • t = 1. 0.02
  • t = 2. 0.16
  • t = 3. 0.26
  • t = 4. 0.24
  • t = 5. 0.16
  • t = 6. 0.09
  • t = 7. 0.04
  • t = 8. 0.01
  • t = 9. 0.00
  • t = 10. 0.00

Note that the probability for $t=0$ is $0$ as the tenth coin toss has probability $1$ of being a head in this example.

$\endgroup$
2
  • $\begingroup$ It isn't a solution per se, but it often helps to handle these problems "one event at a time". Hence consider the case where the first coin toss turns up heads (with probability $p_1$) and then solve the sub-problem: what is the probability of $\geq k$ heads in $n - 1$ flips when $p = 1$ past flips are already heads? Also consider the case where the first coin toss is tails (prob. $1-p_1$), in which case you have $n\to n - 1$, $p = 0$ and the $p_i$'s shifted down by one index. Once you've solved the problem for $(n = k-p,p)$, you can then recursively substitute to solve the original problem. $\endgroup$
    – COTO
    Apr 17, 2021 at 19:08
  • 1
    $\begingroup$ @COTO Are you able to turn this into a full answer or did you get stuck? $\endgroup$
    – graffe
    Apr 18, 2021 at 10:34

1 Answer 1

2
$\begingroup$

Let $p(m,h;\,n,k)$ be the probability of turning up a run of $k$ or more heads given:

  • $m$ coins out of $n$ have already been flipped and no runs of $\geq k$ heads have occurred
  • the last $h$ coins flipped have turned up heads; either no flip preceded this run of $h$ heads or the preceding flip was tails

Then we have the implications:

  1. If we've completed a run of $k$ flips on the $m$'th flip: $$h = k \implies p(m,h;\,n,k) = 1$$
  2. If we no longer have sufficient tosses remaining to make a run of length $\geq k$: $$(n-m) + h < k \implies p(m,h;\,n,k) = 0$$
  3. Otherwise, we partition the event space: the $(m+1)$'th flip is heads with probability $p_{m+1}$ or tails with probability $q_{m+1} \triangleq 1 - p_{m+1}$: $$(n-m) + h \geq k \implies p(m,h;\,n,k) = p_{m+1}p(m+1,h+1;\,n,k) + q_{m+1}p(m+1,0;\,n,k)$$

The probability of a run existing of length $\geq k$ in $n$ flips, which we denote $p_{\text{run}\geq k}$ is given by $$p_{\text{run}\geq k} = p(0,0;\,n,k)$$ and we can recursively substitute in $p$ values for larger values of $m$ and $h$ until the expression is complete. Note that this process runs in $O(n^2)$ [i.e. quadratic] time.

Example

Given $n = 6,\,k = 3$, and omitting the latter two parameters of $p$ for brevity:

$$p_{\text{run}\geq 3} = p(0,0)$$

$$\begin{array}{rcll}\mathbf{Function} & {} & \mathbf{Expression} & \mathbf{Condition} \\ p(0,0) & = & p_1p(1,1) + q_1p(1,0) & (6^{=\,n}-0^{=\,m}) + 0^{=\,h} \geq 3^{=\,k} \\\hline p(1,0) & = & p_2p(2,1) + q_2p(2,0) & (6^{=\,n}-1^{=\,m}) + 0^{=\,h} \geq 3^{=\,k} \\ p(1,1) & = & p_2p(2,2) + q_2p(2,0) & (6^{=\,n}-1^{=\,m}) + 1^{=\,h} \geq 3^{=\,k} \\\hline p(2,0) & = & p_3p(3,1) + q_3p(3,0) & (6^{=\,n}-2^{=\,m}) + 0^{=\,h} \geq 3^{=\,k} \\ p(2,1) & = & p_3p(3,2) + q_3p(3,0) & (6^{=\,n}-2^{=\,m}) + 1^{=\,h} \geq 3^{=\,k} \\ p(2,2) & = & p_3p(3,3) + q_3p(3,0) & (6^{=\,n}-2^{=\,m}) + 2^{=\,h} \geq 3^{=\,k} \\\hline p(3,0) & = & p_4p(4,1) + q_4p(4,0) & (6^{=\,n}-3^{=\,m}) + 0^{=\,h} \geq 3^{=\,k} \\ p(3,1) & = & p_4p(4,2) + q_4p(4,0) & (6^{=\,n}-3^{=\,m}) + 1^{=\,h} \geq 3^{=\,k} \\ p(3,2) & = & p_4p(4,3) + q_4p(4,0) & (6^{=\,n}-3^{=\,m}) + 2^{=\,h} \geq 3^{=\,k} \\ p(3,3) & = & 1 & 3^{=\,h} = 3^{=\,k} \\\hline p(4,0) & = & 0 & (6^{=\,n}-4^{=\,m}) + 0^{=\,h} < 3^{=\,k} \\ p(4,1) & = & p_5p(5,2) + q_5p(5,0) & (6^{=\,n}-4^{=\,m}) + 1^{=\,h} \geq 3^{=\,k} \\ p(4,2) & = & p_5p(5,3) + q_5p(5,0) & (6^{=\,n}-4^{=\,m}) + 2^{=\,h} \geq 3^{=\,k} \\ p(4,3) & = & 1 & 3^{=\,h} = 3^{=\,k} \\\hline p(5,0) & = & 0 & (6^{=\,n}-5^{=\,m}) + 0^{=\,h} < 3^{=\,k} \\ p(5,1) & = & 0 & (6^{=\,n}-5^{=\,m}) + 1^{=\,h} < 3^{=\,k} \\ p(5,2) & = & p_6p(6,3) + q_6p(6,0) & (6^{=\,n}-5^{=\,m}) + 2^{=\,h} \geq 3^{=\,k} \\ p(5,3) & = & 1 & 3^{=\,h} = 3^{=\,k} \\\hline p(6,0) & = & 0 & (6^{=\,n}-6^{=\,m}) + 0^{=\,h} < 3^{=\,k} \\ p(6,3) & = & 1 & 3^{=\,h} = 3^{=\,k} \end{array}$$

Back-substituting yields: $$\begin{split}p_{\text{run}\geq 3} = {p_1}{p_2}{p_3} + {p_1}{p_2}{q_3}{p_4}{p_5}{p_6} + {p_1}{q_2}{p_3}{p_4}{p_5} + {p_1}{q_2}{q_3}{p_4}{p_5}{p_6} + {} \\ {q_1}{p_2}{p_3}{p_4} + {q_1}{p_2}{q_3}{p_4}{p_5}{p_6} + {q_1}{q_2}{p_3}{p_4}{p_5} + {q_1}{q_2}{q_3}{p_4}{p_5}{p_6}\end{split}$$

As for getting a closed-form expression when $p_i = f(i)$, you may want to play around with various values of $n$ and $k$ and see if the sequence of coefficients in the multinomial appears somewhere in OEIS. (Note that if you do this, you'll probably want to express the multinomial solely in terms of $p_i$'s [not $q_i$'s], since the multinomial exhibits no symmetries in terms otherwise.)

$\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.