Give a recursion

Question

A biased coin is tossed repeatedly. The probability that a toss of the coin results in heads is $p$ with $0 < p < 1$. Give a recursion for the probability that the total number of heads after $n$ tosses is even.

I know that for $n-1$:

• if the number of heads is even, the number of tails is odd;

• if the number of heads is odd, the number of tails is even.

So the probability that the number of heads is even is strictly decided by the last trial: $\mathbb{P}(Z_n)=\frac{1}{2}$.

I also know that for $A_n=[$# heads on $n$ trials is even$]$ and $B_n=[$# heads on $n$ trials is odd$]$ we have:

$\mathbb{P}(A_n)=\mathbb{P}(A_{n-1})\mathbb{P}(A_n|A_{n-1})+\mathbb{P}(B_{n-1})\mathbb{P}(A_n|T_{n-1})=\mathbb{P}(A_{n-1})q+[1-\mathbb{P}(A_{n-1})]p$

$=\mathbb{P}(A_{n-1})q+p-\mathbb{P}(A_{n-1})p=p+\mathbb{P}(A_{n-1})(q-p)=p+(q-p)[\mathbb{P}(A_{n-2})\mathbb{P}(A_{n-1}|A_{n-2})+\mathbb{P}(A_{n-2})\mathbb{P}(A_{n-1}|A_{n-2}))]$

$=p+(q-p)(\mathbb{P}(A_{n-2})q+[1-\mathbb{P}(A_{n-2})]p)=p+(q-p)(\mathbb{P}(A_{n-2})q+p-\mathbb{P}(A_{n-2})p)$

$=p+(q-p)(p+\mathbb{P}(A_{n-2})(q-p))=p+p(q-p)+\mathbb{P}(A_{n-2})(q-p)^2=p+p(1-2p)+\mathbb{P}(A_{n-2})(1-2p)^2$

$=p+p-2p^2+\mathbb{P}(A_{n-2})(1-2p)^2=2p-2p^2+\mathbb{P}(A_{n-2})(1-2p)^2$

where, as $n$ decreases to $x$, we have $\mathbb{P}(A_{n-x})(1-2p)^x$ and $2p-2p^2-...-2p^x=\sum_{i=0}^{x}2p^x$ (that for $p\in [0,1]$ converges to $\frac{1}{1-2p}$). Thus I thought to write:

$\mathbb{P}(A_{n-x})(1-2p)^x-\sum_{i=0}^{x}2p^x=\mathbb{P}(Z)\Rightarrow \mathbb{P}(A_{n-x})=\frac{(\frac{1}{2}+\frac{1}{1-2p})}{(1-2p)^x}$ that is different comparing to the solution $\frac{1}{2}+\frac{1}{2}(1-2p)^x$.

Where am I wrong?

Thanks for any help.

EDIT: The second question is Give a recursion for the probability that a sequence of n tosses does not show five or more consecutive heads.

Is it possible to obtain the same result writing

$\mathbb{P}(X\geq 5)=1-\mathbb{P}(X<5)=1-[\binom{n}{0}q^n+\binom{n}{1}pq^{n-1}+\binom{n}{2}p^2q^{n-2}+\binom{n}{3}p^3q^{n-3}+\binom{n}{4}p^4q^{n-4}]$?

Answer 1

Actually, your recursion starts fairly good:

$$\mathbb{P}(A_n) = \mathbb{P}(A_{n-1)})q + [1 - \mathbb{P}(A_{n-1})]p$$

which can be rewritten, with $p_n = \mathbb{P}(A_n)$, as

$$p_n = (1-p)p_{n-1}+p(1-p_{n-1}) = (1-2p)p_{n-1}+p$$

That gives a recursion formula of the form $p_{n+1} = ap_n +b$, with $p_0=1$. There is a standard method to solve this kind of formula, that is :

• Find the fixed point : $l=al+b$. Here, $ l =(1-2p)l+p$, which gives $l=1/2$.
• Defines a new sequence $v_n = p_n -l$. $v_n$ is a geometric sequence. Indeed: $$v_{n+1}=p_{n+1}-l = ap_n+b - (al+b) = a(p_n-l) = av_n$$
• Therefore, $v_n = a^{n}v_0 = a^{n}(p_0-l)$
• Finally, $p_n = v_n+l = a^{n}(p_0-l)+l$ This gives in your case $$p_n = (1-2p)^{n}(1-1/2)+1/2 = \frac{1}{2}+\frac{1}{2}(1-2p)^n$$

That should answer the first question!

Answer 2

Let $a_n$ be the probability that, after $n$ tosses, the number of heads is even. $$ \begin{align} a_n &=p(1-a_{n-1})+(1-p)a_{n-1}\tag1\\[9pt] &=p+(1-2p)a_{n-1}\tag2\\[3pt] a_n-\frac12 &=(1-2p)\left(a_{n-1}-\frac12\right)\tag3\\ &=(1-2p)^n\left(a_0-\frac12\right)\tag4\\ a_n &=\frac12+\frac12(1-2p)^n\tag5 \end{align} $$ Explanation:
$(1)$: the probability that on this toss we have an even number of heads
$\phantom{\text{(1):}}$ is the probability that last toss we had an odd number of heads
$\phantom{\text{(1):}}$ and then rolled a head, plus the probability that last toss we had
$\phantom{\text{(1):}}$ an even number of heads and then rolled a tail
$(2)$: simplify
$(3)$: rewrite $(2)$ with $a_n+x=(1-2p)(a_{n-1}+x)$; $x=-\frac12$
$(4)$: induction
$(5)$: solve with $a_0=1$ ($0$ is an even number of heads)

So your answer looks correct.