4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}$$

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.