Solving the probability difference equation $p_{n} = p(1 - p_{n-1}) + (1 - p)p_{n-1}$ yields a questionable closed-form equation?

Question

I am trying to solve the following difference equation by writing it in closed-form, which represents the probability that a person flips an even number of heads in $n$ tries, with $p$ being the probability that a person flips a head at any given time: $p_{n} = p(1 - p_{n-1}) + (1 - p)p_{n-1}$.

To derive this equation, I did a simple case analysis. There are 2 cases that $n$ flips yields an even number of heads:

1. odd # of heads $n - 1$ times, then a head: $(1 - p_{n - 1})p$

2. even # of heads $n - 1$ times, then a tail: $p_{n-1}(1 - p)$

Adding the cases up yields the difference equation I wrote above.

My strategy was to derive the characteristic equation, as this is a non-homogeneous linear equation:

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

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

$x = (1 - 2p)$

$p_{n} = C(1-2p)^{n}$

We know that $p_{1} = p$:

$C(1 - 2p) = p$

$C = \frac{p}{1 - 2p}$

And plugging back into the original equation, we get:

$p_{n} = \frac{p}{1 - 2p}(1 - 2p)^n = p(1 - 2p)^{n - 1}$.

However, this does not seem to be correct, because if $p$ is $1/2$ (if it is a $1/2$ chance of getting a head on a flip), $p_{n}$ will always be 0.

Answer 1

Your recurrence

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

is correct, but you seem to have lost track of the $p$ term when you solved it. For convenience let $c=1-2p$, so that the recurrence is $p_n=cp_{n-1}+p$. Let $a_n=p_n-d$ for some constant $d$ that will be determined later; the recurrence can then be written

$$a_n+d=c(a_{n-1}+d)+p\,.$$

Rewrite this as

$$a_n=ca_{n-1}+[(c-1)d+p]$$

and choose $d$ to eliminate the expression in square brackets:

$$d=\frac{p}{1-c}=\frac{p}{1-(1-2p)}=\frac12\,.$$

Then $a_n=ca_{n-1}$, and $p_0=1$ (after $0$ tosses you’re bound to have $0$ heads, an even number), so

$$a_n=c^na_0=c^n(p_0-d)=\frac12c^n$$

for each $n\ge 0$, and

$$p_n=a_n+\frac12=\frac12(c^n+1)=\frac12\big((1-2p)^n+1\big)\,.$$

When $p=\frac12$ we have $p_0=1$ (because $0^0=1$) and $p_n=\frac12$ for all $n\ge 1$, as expected. When $p=0$ we have $p_n=1$ for all $n\ge 0$, again as expected: we’ve always tossed $0$ heads. And for $p=1$ we have $p_n=1$ when $n$ is even and $p_n=0$ when $n$ is odd, yet again as expected.

Answer 2

It is maybe worth pointing out that it's possible to compute this probability without using a recurrence, as follows. Let $E_n$ be the probability of flipping an even number of heads and let $O_n$ be the probability of flipping an odd number of heads. We have

$$E_n + O_n = 1$$ $$E_n - O_n = \sum_{k=0}^n (-1)^k {n \choose k} p^k (1 - p)^{n-k} = (1 - 2p)^n$$

which immediately gives

$$E_n = \frac{1 + (1 - 2p)^n}{2}, O_n = \frac{1 - (1 - 2p)^n}{2}.$$

This is a special case of a general trick for isolating the terms with exponent congruent to $a \bmod n$ in a generating function using the discrete Fourier transform, which is sometimes known in a contest-math setting as the "roots of unity filter." Here we are using the second roots of unity $\pm 1$ only, but if we used $k^{th}$ roots of unity then we could express e.g. the probability of flipping a number of heads divisible by $k$.

Answer 3

Just another perspective for this problem.

Treat this as a two-state Markov chain, with state space $\{0,1\}$ corresponding to the number of heads flipped modulo $2$. The transition matrix is $$P=\begin{pmatrix}1-p & p \\ p & 1-p\end{pmatrix}.$$ The initial distribution is $\lambda=(1,0)$ (with $0$ flips, we always flip an even number of heads!), so that the probability of flipping $0$ heads (mod $2$) after $n$ flips is $(\lambda P^n)_0$.

To compute this, the eigenvalues of $P$ are $1-2p$ and $1$. Now we don't actually need to diagonalise $P$: just note that if we did, then we would find that $$(\lambda P^n)_0=A(1-2p)^n+B,$$ for some suitable constants $A$, $B$ independent of $n$. But finding $A$ and $B$ is very easy: look at the $n=0$ and $n=1$ cases to get \begin{align*} 1&=A+B \\ 1-p&=A(1-2p)+B, \end{align*} from which we find $A=B=\frac{1}{2}$.