If a coin is flipped 25 times with eight tails occurring, what is the probability that no run of $6$ or more heads occurs?

Question

I'm trying to approach this question using generating functions.

I set the problem up similar to a "toss $17$ balls into $9$ bins, what's the probability that no bin gets $6$ or balls in it." as the $9$ bins correlate to the $9$ possible places between tails that heads can occur in.

My generating function ended up like this:

$$(1-x^6)^9 \times (1/(1-x))^9 = 17$$

and this is where I sort of hit a dead end in my work. I assume we should solve for coefficients of $f(x)g(x)$, making sure they add up to $17$.

Starting this, I found that the only coefficients that were nonzero and under $17$ for $(1-x^6)^9$ would be $0, 6$, and $12$. But these are giving me some ugly numbers and I don't really know where to go from here, or how to calculate the probability at the end.

Could anybody give me some pointers on where to go from here?

Answer 1

I just ran a simple computer simulation and got $447,669$ "winners" out of $1,081,575$ cases which have exactly $8$ tails occurring (out of $25$ fair coin flips), so the probability is $41.39$%. I looped thru all $2^{25}$ = $33,554,432$ possible states of $25$ coin flips.

Answer 2

Your approach using generating functions is correct. I will work the whole solution so others still trying to understand generating functions can follow.

First, we know the probability will be the following occurrences,

( 8 tails and 17 heads with runs < 6)/( 8 tails and 17 heads)

To calculate the function occurrences without runs visualize it as a boxes and balls problem. Separate the boxes with the 8 Tails

_T_T_T_T_T_T_T_T_

This leads to 8 boxes and 17 balls to place. (25 - 8 = 17)

Since our boxes can contain 0-5 balls the function takes the form for a single box

$x^0+x^1+x^2+x^3+x^4+x^5=\mathbf{1+x^1+x^2+x^3+x^4+x^5}$

Since we have 9 boxes, we take this result to the 9th power $\mathbf{(1+x^1+x^2+x^3+x^4+x^5)^9}$

using $\frac{1-x^{m+1}}{1-x} = 1+x+x^2+...+x^m $ $$\mathbf{1+x^1+x^2+x^3+x^4+x^5 =\frac{(1-x^6)^9}{(1-x)^9}}$$

Break this into two functions f(x) and g(x)

$$f(x)= (1-x^6)^9$$ $$f(x)= \frac{1}{(1-x)^9}$$

Their corresponding expansions are,

$(1-x^m)^n=1-\binom{n}{1}x^{1*m}+\binom{n}{2}x^{2*m}....+(-1)^n\binom{n}{n}x^{nm}$

$\frac{1}{(1-x)^n}=1+(\frac{1+n-1}{1})x+(\frac{2+n-1}{2})x^2+......+(\frac{r+n-1}{r})x^r$

We need to find the coefficient for $x^{17}$ which is equal to $$\Sigma f(x)g(x)$$ Where the resulting power of x is 17

The only values of $\mathbf{f(x)}$ that can meet this constraint are $\mathbf{x^0,x^6,x^{12}}$

Lets represent the power of x in f(x) with $a^k$ and g(x) with $b^k$ This leads to the only valid combinations being $$a^0b^{17}+a^6b^{11}+a^{12}b^5$$

Therefore, the number of occurrences of 8 tails and 17 heads with runs < 6 is $$1*\binom{17+9-1}{17}-\binom{9}{1}\binom{11+9-1}{11}+\binom{9}{2}\binom{5+9-1}{5}$$

This evaluates to 447669 occurrences.

Next we find all possible occurrences with no constraints. Using the formula for placement of n identical objects in k boxes $\binom{n+k-1}{n}$ Which gives us $$\binom{17+9-1}{17}=1081575$$

$$100*\frac{447669}{1081575}\approx41.39\%$$