Let $Q_n$denote the probability that no run of $3$consecutive heads appears in $n$tosses of a fair coin. Show that

$Q_n=\frac{1}{2}{Q}_{n-1}+\frac{1}{4}{Q}_{n-2}+\frac{1}{8}{Q}_{n-3}$

$Q_0=Q_1=Q_2=1$

Find $Q_8$.

Hint: Condition on the first tail

$n$tosses of a fair coin

$S_n$, there are no three heads in a row.

$A_i$the first tails is $i=1,2,3,4,5,..$

Probabilities:

$P\left(S_n\right)=Q_n$

$P\left(A_1\right)=\frac{1}{2}$

$$\begin{gathered} P\left(A_2\right)=\frac{1}{2}\times \frac{1}{2} \\ =\frac{1}{4} \end{gathered}$$

$$\begin{gathered} P\left(A_3\right)={\left(\frac{1}{2}\right)}^3 \\ =\frac{1}{8} \end{gathered}$$

probabilities of a1, a2, a3 are obtained using independence:

Prove:

$Q_n=\frac{1}{2}{Q}_{n-1}+\frac{1}{4}{Q}_{n-2}+\frac{1}{8}{Q}_{n-3}$

$Q_0=Q_1=Q_2=1$

The first tail can be divided by the number of events$S_n$. If there are no three consecutive heads, a first tail can only appear in the first, second, or third row.

$P\left(S_n\right)=P\left(S_n{A}_1\right)+P\left(S_n{A}_2\right)+P\left(S_n{A}_3\right)$ $\left(1\right)$

These intersections are mutually exclusive because $A_1$,$A_2$and $A_3$are mutually exclusive.

Because all events are independent, after the initial tail, the remaining flips work in the same way as the original chain, but with a smaller size. consequently,

$P\left(S_n{A}_1\right)=P\left(A_1\right)P\left(S_{n-1}\right)$

$P\left(S_n{A}_2\right)=P\left(A_1\right)P\left(S_{n-2}\right)$

$P\left(S_n{A}_3\right)=P\left(A_1\right)P\left(S_{n-3}\right)$

substituting this into equation $\left(1\right)$and changing $P\left(S_n\right)=Q_n$we obtain recursive

$Q_n=\frac{1}{2}{Q}_{n-1}+\frac{1}{4}{Q}_{n-2}+\frac{1}{8}{Q}_{n-3}$

$Q_0=Q_1=Q_2=1$

Using recursive formula:

$Q_n=\frac{1}{2}{Q}_{n-1}+\frac{1}{4}{Q}_{n-2}+\frac{1}{8}{Q}_{n-3}$

$Q_0=Q_1=Q_2=1$

$Q_3=\frac{1}{2}\times 1+\frac{1}{4}\times 1+\frac{1}{8}\times 1=\frac{7}{8}$

$Q_4=\frac{1}{2}\times \frac{7}{8}+\frac{1}{4}\times 1+\frac{1}{8}\times 1=\frac{13}{16}$

$Q_5=\frac{1}{2}\times \frac{13}{16}+\frac{1}{4}\times \frac{7}{8}+\frac{1}{8}\times 1=\frac{3}{4}$

$Q_7=\frac{1}{2}\times \frac{11}{16}+\frac{1}{4}\times \frac{3}{4}+\frac{1}{8}\times \frac{13}{16}=\frac{81}{128}$

$Q_8=\frac{1}{2}\times \frac{81}{128}+\frac{1}{4}\times \frac{11}{16}+\frac{1}{8}\times \frac{3}{4}=\frac{149}{256}$