Probability of getting even number of tails after flipping n coins I was first asked the probability of getting an even number of heads ($P_n$) supposedly after flipping $n$ fair coins. I calculated that to be $1/2$.
Using this information, I don't know how to solve the same question if the coins are biased such that the probability of getting heads is $x$ and tails is $1-x$. My main confusion is that I don't know how to tackle or isolate $x$ with unfair/biased coins, and thus don't know what formula to generate for the new $P_n$ with this condition.
Any help would be appreciated. Thanks.
 A: Let $p$ be the probability of getting a head, and let $q=1-p$ be the probability of getting a tail. Let $p_n$ be the probability of getting an even number of heads in $n$ flips, and let $q_n=1-p_n$ be the probability of getting an odd number of heads in $n$ flips. Then
$$p_n=p_{n-1}q+q_{n-1}p\;:$$
to get an even number of heads in $n$ flips you must either get an even number of heads in $n-1$ flips and then get a tail, or get an odd number of heads in $n-1$ flips and then get a head. Rewrite this to get rid of $q$ and $q_n$:
$$p_n=p_{n-1}(1-p)+(1-p_{n-1})p=p_{n-1}(1-2p)+p\;.$$
This is a simple first order linear recurrence that can be solved in many ways. One simple way is to ‘unwind’ it:
$$\begin{align*}
p_n&=(1-2p)p_{n-1}+p\\
&=(1-2p)\big((1-2p)p_{n-2}+p\big)+p\\
&=(1-2p)^2p_{n-2}+(1-2p)p+p\\
&=(1-2p)^2\big((1-2p)p_{n-3}+p\big)+(1-2p)p+p\\
&=(1-2p)^3p_{n-3}+(1-2p)^2p+(1-2p)p+p\\
&\;\;\vdots\\
&=(1-2p)^kp_{n-k}+p\sum_{\ell=0}^{k-1}(1-2p)^\ell\\
&\;\;\vdots\\
&=(1-2p)^np_0+p\sum_{\ell=0}^{n-1}(1-2p)^\ell\\
&\overset{*}=(1-2p)^n+p\frac{1-(1-2p)^n}{1-(1-2p)}\\
&=(1-2p)^n+\frac12\big(1-(1-2p)^n\big)\\
&=\frac12\big(1+(1-2p)^n\big)
\end{align*}$$
At the starred step I used the fact that $p_0=1$: the number of heads when no coins have been tossed is $0$, which is even.
You can see that this is always $\frac12$ if $p=\frac12$, is always $1$ if $p=0$ (so that you always have $0$ heads), and alternates between $1$ and $0$ if $p=1$, since in that case you have a head on every throw and therefore have an even number of heads if and only if $n$ is even. Finally, you can check that if $0<p<1$, then $\lim\limits_{n\to\infty}p_n=\frac12$.
