Probability of no pair of consecutive heads in $n$ flips of a coin

Question

I am trying to solve the following problem. A biased coin shows heads with probability $p=1-q$ when it is flipped. Let $u_{n}$ be the probability that in $n$ flips, no pair of heads occur successively. Show that for $n \geq q$,

$$u_{n+2} = qu_{n+1} + pqu_{n}.$$

I know I need to use the partition theorem $P(X) = \sum P(X|B_{i})P(B_{i})$ where the set of events $B_{i}$ partition the sample space (the question event gives the hint "use partition theorem with $B_{i}$ the event that first $i-1$ flips yield heads and the $i$th yields tails"), but I still have no idea as to how to proceed and to how to choose the partition. I intuitively see why the answer is what it is, but I can't rigorously formulate the approach to the solution in my head.

Answer 1

Decompose $u_n=a_n+b_n$, where the latter two sequences are defined like $u_n$ except that they only consider those sequences ending in a head or a tail respectively. Then $$\begin{bmatrix}a_{n+1}\\b_{n+1}\end{bmatrix}=\begin{bmatrix}0&p\\q&q\end{bmatrix}\begin{bmatrix}a_n\\b_n\end{bmatrix}$$ From this we derive $$\begin{bmatrix}a_{n+2}\\b_{n+2}\end{bmatrix}=\begin{bmatrix}pq&pq\\q^2&pq+q^2\end{bmatrix}\begin{bmatrix}a_n\\b_n\end{bmatrix}$$ and hence $$u_{n+2}=a_{n+2}+b_{n+2}=pq(a_n+b_n)+q^2a_n+(pq+q^2)b_n$$ $$=pqu_n+q(qa_n+(p+q)b_n)=pqu_n+qu_{n+1}$$

Answer 2

Let's follow the (clever) hint. Let $U_{n}$ be the event of interest, so that $P(U_n)=u_n$.

Let $B_i$ be the event that, in $i$ flips, the first $i-1$ flips yield head and the $i$th yields tails. Let $A_i$ be the event that, in $i$ flips, all are head. Clearly, the events $\{A_j, B_1, B_2 , B_3, \cdots B_j \}$ are disjoint and exhaustive for any given $j\ge 1$.

Then, for any $n\ge 0$ $$u_{n+2}=P(U_{n+2})=P(U_{n+2}|A_{n+2})P(A_{n+2}) + \sum_{i=1}^{n+2} P(U_{n+2}|B_i)P(B_i) $$

Now, $P(U_{n+2}|B_i)=0$ if $i>2$ (we had at least two consecutive heads); same goes for $P(U_{n+2}|A_{n+2})=0$.

Further, $P(U_{n+2}|B_1)=P(U_{n+1})$ and $P(U_{n+2}|B_2)=P(U_{n})$.

Hence $$u_{n+2}=u_{n+1} q + u_{n} \, p \, q$$

Answer 3

Am I missing something? The recurrence can be explained super-easily if you just condition on the last flip, right?

• If the last flip is T, the $(n+2)$-sequence is good iff the initial $(n+1)$-subsequence is good.

• If the last flip is H, the $(n+2)$-sequence is good iff the second-to-last flip is T and the initial $n$-subsequence is good.