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
 A: 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.
A: 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.
A: 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}.$$
A: There is an intuitive way to think about this.
Let $E$ be the probability of success. Let $\mathbb{T}$ denote the probability of success starting with a T first; Let $\mathbb{H}$ denote the probability of success starting with an H first.
To illustrate, the event space can be partitioned into $\mathbb{T}$ and $\mathbb{H}$:
\begin{align}
\mathbb{H}&: &H \\
\mathbb{T}&: &TH \\
& &TTH \\
& &TTTH \\
& &TTTTH \\
& &TTTTT
\end{align}
If we get H on the first flip, to succeed requires getting a T next. If we get T on the first flip, the series of outcomes listed above under $\mathbb{T}$ can lead to success. With these, we can derive the following equations.
$$
P(E|\mathbb{H}) = \frac{1}{2}P(E|\mathbb{T}) \\
P(E|\mathbb{T}) = \left ( \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} \right )  P(E|\mathbb{H}) + \frac{1}{16}
$$
Finally, $P(E) = \frac{1}{2} P(E|\mathbb{H}) +  \frac{1}{2} P(E|\mathbb{T}) = \frac{3}{34}$.
In general,
$$
P(E|\mathbb{H}) = \left( 1 - \frac{1}{2^{h-1}} \right) P(E|\mathbb{T}) \\
P(E|\mathbb{T}) = \left( 1 - \frac{1}{2^{t-1}} \right) P(E|\mathbb{H}) + \frac{1}{2^{t-1}}
$$
Solving them gives
$$
P(E) = \frac{2^h - 1}{2^h + 2^t - 2}
$$
