Does there exist an unfair coin such that the probability of an even number of heads in $n$ flips is $\frac{1}{2}$?

Question

Question:

Does there exist an unfair coin and an $n$ such that the probability of an even number of heads in $n$ flips is $\frac{1}{2}$?

First attempt

Let $p$ be the probability of our coin flipping heads. If we try $n=2 $ then we must have:

$p^2+(1-p)^2 = \frac{1}{2}$ and the only root to this is $p = \frac{1}{2}$ so no bias coin works in only $2$ flips.

Moving on to $n=3$ we must have:

$p^3 + 3p(1-p^2) = \frac{1}{2} $ and again the only root is $p = \frac{1}{2}$

I then proceeded to check these up to $n=6$ and found that the only root was $p=\frac{1}{2}$. This suggested to me that the answer was no but I wasnt able to go much further with this method for a general $n$. I could have proceeded by proving $(p-\frac{1}{2})^n \propto $ "the polynomials we were getting - 0.5 " but this is cumbersome.

Second attempt

I then noticed that if we found such a $p$ and an $n$ then it would also be true for $n+1$ as the probability of an even number of heads in $n+1$ tosses = $\frac{p}{2}+\frac{1-p}{2} = \frac{1}{2} $ (conditioning on the first $n$ tosses ) I then wanted to do this in reverse i.e showing if its true for $n$ its true for $n-1$

Define $P_n^p$ as the probability of getting an even number of heads from a coin having bias $p$ in $n$ flips.

Then we have $P_n^p = (1-p)\cdot P_{n-1}^p + p \cdot (1-P_{n-1}^p)$ and if $P_{n}^p = \frac{1}{2}$ then

$\frac{1}{2} = P_{n-1}^p -2pP_{n-1}^p +p $ and so

$\frac{1}{2} - p = P_{n-1}^p (1-2p)$ and then

$P_{n-1}^p = \frac{1}{2}$

And so if it is true for $n$ it is true for $n-1$ but we know that for $n=2$ no bias coins work and so inductively there do not exist any coins with bias that work! (as true for $n$ implies $n-1 $ , implies $n-2$ , implies $n-3$ ,.... implies $2$ But we already showed $n=2$ is false.

Something more streamline?

I cannot help but think that due to the symmetry of this problem there must surely exist such a simple and elegant way of showing it is not true! Notice if $p$ works then so does $1-p$. Can someone find a very simple way of solving this problem ? :)

Answer 1

Consider the random variable in which the value of a flip sequence is $1$ if the number of heads is even and $-1$ if the number of flips is odd.

Its expected value is $\sum\limits_{i=0}^n \binom{n}{i}(-1)^ip^i(1-p)^{n-i} = ((-p) + (1-p))^n = (1-2p)^n$.

We need this expected value to be $0$, this happens only when $p$ is $\frac{1}{2}$.

Answer 2

With the probability of heads being $p$ and $n$ tosses the probability of getting an even number of heads is $$\sum_{k=0}^{\lfloor n/2\rfloor}\binom n{2k}p^{2k}(1-2p)^{n-2k}=\frac12+\frac{(1-2p)^n}2$$ which is $\frac12$ iff $\frac{(1-2p)^n}2=0$ iff $1-2p=0$ iff $p=\frac12$. Hence if the probability of tossing an even number of heads is exactly $\frac12$, the coin is fair.