A coin with heads probability p is flipped n times. A "run" is a maximal sequence of consecutive flips that are all the same. What is the probability of exceeding 4 groups after 10 tosses?

Now, I have already found that the expected number of runs is:


But I have been stuck on this part of the question, I can figure out that the probability of having 10 groups is:

$2 * (P(H)^5 + P(T)^5)$

Where P(H) is probability of heads and P(T) is probability of tails.

Because there is only two possible arrangements, but how do I generalize the equation?


1 Answer 1


Let's say we have $n$ tosses.

Let $P(H) = p$.

Let $g(m,k)$ be the number of $n$-tosses with exactly $m$ heads and $k$ groups.

Then the number of possibilities (of $n$ tosses) not exceeding $l$ groups is:

$$P(n,l) = \sum\limits_{m=0}^n\Big[\sum\limits_{k=1}^{l}g(m,k)\Big]$$

The probability of not exceeding $l$ groups is:

$$P(n,p,l) = \sum\limits_{m=0}^n\Big[\sum\limits_{k=1}^{l}g(m,k)\Big]p^m(1-p)^{n-m}$$ This is not easily simplified (?), also note that it implies:

$$\sum\limits_{k=1}^{m}g(m,k) = \binom{n}{m}$$

$g(m,k) = \begin{cases} 2c_m(k/2)c_{n-m}(k/2), & \text{if } 2 \mid k, \\ c_m(\frac{k-1}{2})c_{n-m}(\frac{k+1}{2})+ c_m(\frac{k+1}{2})c_{n-m}(\frac{k-1}{2}), & \text{otherwise}. \end{cases}$

Where $c_m(k) = \binom{m-1}{k-1}$ is a number of compositions of $m$ from $k$ summands: $$m = a_1 + \dots + a_k$$

Why is the parity of $k$ important for $g(m,k)$ function?

Let $H_i, T_j$ represent whole group of heads, tails. Then possible arrangements are:

$$2 \mid k \implies H_1T_1\dots H_lT_l\ \lor \ T_1H_1\dots T_lH_l,\ k = 2l$$ $$2 \nmid k \implies H_1T_1\dots H_{l-1}T_{l-1}H_l\ \lor \ T_1H_1\dots T_{l-1}H_{l-1}T_l,\ k = 2l - 1$$

We have $P(10,10) = 1024 = 2^{10}$ as expected.

Here is the plot for $P(10,l)$ for different $l$.

Count for different l and n = 10

Here is the probability distribution of exactly $i$ groups in 80-tosses with $P(H) = p = 0.2$ You can see the distinction stemming from the $g$ function. We have different distributions for even and odd group sizes.

enter image description here

  • $\begingroup$ Thank you for this correct answer Lukasz. I have successfully repeated your results and verified that they are correct. Would you mind saying which language you used to encode this and make the plots? It looks like R, but I'm not sure. $\endgroup$
    – darkhipo
    Feb 4, 2017 at 21:05
  • $\begingroup$ Thank you for the thorough response, as darkhipo said, I would also appreciate the code for this. $\endgroup$
    – josh453
    Feb 4, 2017 at 21:27
  • $\begingroup$ @darkhipo Yes i made a quick snippet in R to check if it looks correct. $\endgroup$ Feb 4, 2017 at 21:29
  • $\begingroup$ Thanks for this answer. I'm curious as to what the reasoning is between the difference of the odd and even numbers of groups? $\endgroup$
    – KRS-fun
    Feb 5, 2017 at 13:03
  • $\begingroup$ @KRS-fun I added short explanation to my answer $\endgroup$ Feb 5, 2017 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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