# Occurrence of 5 consecutive tails before occurrence of 2 consecutive heads

In repeated tossing of a fair coin find the probability that $5$ consecutive tails occur before occurrence of $2$ consecutive heads.

My attempt: I tried to find the probability of non-occurrence of two consecutive heads in $n$ throws.

Let $a_{n}$ be the number of possibilities in which $2$ consecutive heads do not occur in $n$ throws.

I managed to find the recursion formula.

$a_{1}=2$

$a_{2}=3$

$a_{n}=a_{n-1}+a_{n-2}$

But I am not able to get a closed form of $a_{n}$.

Once $a_{n}$ gets determined it may be possible then to find probability of occurrence of $5$ consecutive heads

-
The solutions to your recurrence are basically the Fibonacci seqience, for which there is a closed form that I think will not be helpful. – André Nicolas Jan 19 at 1:19
Besides, I don't understand the last sentence- You want the probability of 5 consecutive tails, and I don't see how $a_n$ would lead you you that. – leonbloy Jan 19 at 1:40
@leonbloy Well you're doing better than me, I don't understand even the question. It's a unique nonrepeating 7-bit sequence, so the odds of it starting at any particular coin toss seems obviously 1 in 2^7, or 1 in 128. So the odds of it happening in any sequence of tosses is gonna be the same as rolling a 1 on a 128 sided dice, when rolling it (sequence length - 6) times. The minus six because the last 6 coin-tosses cannot start the sequence. So I don't get what's being asked. But then I'm bad at math. – Dewi Morgan Jan 19 at 5:31

A different approach: consider two independent geometric vars $X_1$ ,$X_2$, each of which measures the amount of trials until getting a success, in an experiment with prob. of success $p_1$ (resp $p_2)$

Then $$P(X_1 \le X_2)=p_1 + p_1 q_1 q_2 +p_1 (q_1 q_2)^2+\cdots=\frac{p_1}{1- q_1 q_2}$$

$$P(X_1 < X_2)=p_1 q_2 + p_1 q_2 q_1 q_2 +p_1 q_2 (q_1 q_2)^2+\cdots=\frac{p_1 q_2}{1- q_1 q_2}$$

We can consider each run of tails/heads such experiments, with $p_1=1/2^{5-1}=2^{-4}$, $p_2 =1/2$

Let $E$ be the desired event (run of 5 tails happens before run of 2 heads). Let $T$ be the event that the first coin is a tail. Then

$$P(E)=P(E|T)P(T)+P(E|T^c)P(T^c)=\\ =\frac{p_1}{1- q_1 q_2} \frac{1}{2}+\frac{p_1 q_2}{1- q_1 q_2} \frac{1}{2}=\\=\frac{1}{2} (1+q_2)\frac{p_1}{1- q_1 q_2} =\frac{3}{34}$$

In general

$$P(E)=\frac{2^h-1}{2^t+2^h-2}$$

Seeing that the final formula is so simple, I wonder if there is a simpler derivation.

-
Upvoted (+1) after verification. – Marko Riedel Jan 19 at 4:55
@leonbloy: Instructive answer! (+1) – Markus Scheuer Jan 19 at 11:38
why is $p_{1}=\frac{1}{2^{5-1}}$ and not $\frac{1}{2^5}$. Similarly,should not $p_{2}=\frac{1}{2^2}$ instead of $\frac{1}{2}$ – Pankaj Sinha Feb 1 at 0:43
@PankajSinha Each run of head (tails) has by itself a starting head (tail). That should not be counted. For example, (for $p_2$) the probability that a head run is of length at least 2 is $p_2 = 1/2$ (or one minus the probaiblity that the head run has length $1$) – leonbloy Feb 1 at 1:42
Can I say that to obtain a run of $5$ tails it is necessary to obtain $4$ tails whose probability is $\frac{1}{2^{-4}}$ and then for a run of $5$ tails to occur one tail may happen before $4$ consecutive tails occur or after these $4$ consecutive tails occur whose probability will be $\left(\frac{1}{2}+\frac{1}{2}\right)$ – Pankaj Sinha Feb 3 at 2:17

This problem can be solved using Markov chains. Unfortunatley, this approach requires a bunch of tiresome matrix manipulations. I won't work through the details for you, but instead outline of solution.

Define the following states $0$ : the ground state. $t_1$: 1 tail has occurred ... $t_5$: 5 tails have occurred $h_1$: 1 head has occurred $h_2$ : 2 heads have occurred.

Here $t_5$ and $h_2$ are your termination states - i.e your game ends when you reach either state. So basically, you need to the expected time of hitting first $t_5$ versus first hitting $h_2$.

Now, write down the transition probability matrix. It will look something like this: $$Pr[ 0 \rightarrow t_1] = 1/2$$ $$Pr[0 \rightarrow h_1] = 1/2$$ $$Pr[t_i \rightarrow h_1] = 1/2$$ $$Pr[t_i \rightarrow t_{i+1}] = 1/2$$ etc.

Next, solve the expectation relationships as follows.

Define $\tau_{j,k}$ = time to go from state $j$ to state $k$.

then the expected time to go from the ground state to $t_5$ can be composed into the path taken at the first step, either via $t_1$ or $h_1$... $$E[ \tau_{0, t_5} ] = 1+E[ \tau_{t_1, t_5} ]1/2 + E[ \tau_{h_1, t_5} ]1/2$$

similarly the time to go from the 1-tail state $t_1$ to the final state $t_5$ can be broken down by intermediate paths: $$E[ \tau_{t_1, t_5} ]= 1+E[\tau_{t_2, t_5} ]1/2 + E[ \tau_{h_1, t_5}]1/2$$ $$E[ \tau_{t_2, t_5} ]= 1+E[\tau_{t_3, t_5} ]1/2 + E[ \tau_{h_1, t_5}]1/2$$ $$E[ \tau_{t_3, t_5} ]= 1+E[\tau_{t_4, t_5} ]1/2 + E[ \tau_{h_1, t_5}]1/2$$ $$E[ \tau_{t_4, t_5} ]= 1/2 + E[ \tau_{h_1, t_5}]1/2$$

and so on an so forth.

As I said, it's quite tedious, but it'll get you the solution as linear system of equations.

-

Here is a slightly different proof which may be of interest although it is not as elegant as the one by @leonbloy.

Suppose we treat the problem of $t$ tails before $h$ heads.

Encoding this in a generating function with $u$ marking sequences of tails of length at least $t$ and $v$ sequences of heads of length at least $h$ and finally $w$ marking the final occurrence of $h$ heads and introducing

$$G_t(z) = z+z^2+\cdots +z^{t-1}+uz^t\frac{1}{1-z} \quad\text{and}\quad G_h(z) = z+z^2+\cdots +z^{h-1}+vz^h\frac{1}{1-z}$$

we obtain

$$H(z) = (1+G_t(z)) \left(\sum_{k\ge 0} G_h(z)^k G_t(z)^k\right) \left(1+z+\cdots+z^{h-1} + wz^h + z^{h+1}\frac{1}{1-z}\right).$$

Observe that when we remove the three markers $u,v$ and $w$ we obtain

$$Q(z) = \frac{1}{1-z} \left(\sum_{k\ge 0} \frac{z^k}{(1-z)^k} \frac{z^k}{(1-z)^k}\right) \frac{1}{1-z} \\ = \frac{1}{(1-z)^2} \frac{1}{1-z^2/(1-z)^2} = \frac{1}{(1-z)^2-z^2} = \frac{1}{1-2z}$$

which is good news because it means we have enumerated all $2^n$ possible bit strings of length $n.$

Now extracting coefficients we are interested in the series on $w$ which yields

$$H_1(z) = z^h (1+G_t(z)) \left(\sum_{k\ge 0} G_h(z)^k G_t(z)^k\right)$$

The next step is to discard those terms that have $v\ge 1$ (meaning an internal occurrence of $h$ heads) which yields on setting $v=0$

$$H_2(z) = z^h (1+G_t(z)) \left(\sum_{k\ge 0} \left(z\frac{1-z^{h-1}}{1-z}\right)^k G_t(z)^k\right).$$

Finally we need to compute $$H_3(z) = \left. H_2(z)\right|_{u=1} - \left. H_2(z)\right|_{u=0}$$

to remove those terms not containing a run of at least $t$ tails.

This yields

$$H_3(z) = z^h \frac{1}{1-z} \left(\sum_{k\ge 0} \left(z\frac{1-z^{h-1}}{1-z}\right)^k \left(\frac{z}{1-z}\right)^k\right) \\ - z^h \frac{1-z^t}{1-z} \left(\sum_{k\ge 0} \left(z\frac{1-z^{h-1}}{1-z}\right)^k \left(z\frac{1-z^{t-1}}{1-z}\right)^k\right).$$

This finally produces

$$H_3(z) = z^h\frac{1}{1-z} \frac{1}{1-z^2 (1-z^{h-1})/(1-z)^2} \\ - z^h\frac{1-z^t}{1-z} \frac{1}{1- z^2(1-z^{h-1})(1-z^{t-1}))/(1-z)^2} \\ = z^h \frac{1-z}{(1-z)^2-z^2 (1-z^{h-1})} \\ - z^h (1-z^t) \frac{1-z}{(1-z)^2- z^2 (1-z^{h-1})(1-z^{t-1})} \\ = z^h \frac{1-z}{1 - 2z + z^{h+1}} - z^h (1-z^t) \frac{1-z}{1 - 2z + z^{h+1} + z^{t+1} - z^{h+t}}.$$

We obtain the probability by setting $z=1/2$ which yields

$$\frac{1}{2^{h+1}} 2^{h+1} - \frac{1}{2^{h+1}} \left(1-\frac{1}{2^t}\right) \frac{1}{1/2^{h+1}+1/2^{t+1}-1/2^{h+t}} \\ = 1 - \frac{2^t-1}{2^{h+t+1}} \frac{1}{1/2^{h+1}+1/2^{t+1}-1/2^{h+t}} \\ = 1 - (2^t-1) \frac{1}{2^t+2^h-2} = \frac{2^t+2^h-2-(2^t-1)}{2^t+2^h-2} \\ = \frac{2^h-1}{2^t+2^h-2}.$$

-
Nice approach! (+1) – Markus Scheuer Jan 19 at 11:33