# Coin toss and number of groups

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:

$1+2(n−1)p(1−p)$

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?

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

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.

• 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. – darkhipo Feb 4 '17 at 21:05
• Thank you for the thorough response, as darkhipo said, I would also appreciate the code for this. – josh453 Feb 4 '17 at 21:27
• @darkhipo Yes i made a quick snippet in R to check if it looks correct. – Łukasz Grad Feb 4 '17 at 21:29
• Thanks for this answer. I'm curious as to what the reasoning is between the difference of the odd and even numbers of groups? – KRS-fun Feb 5 '17 at 13:03
• @KRS-fun I added short explanation to my answer – Łukasz Grad Feb 5 '17 at 13:56