Show that given n coins, if the probability of getting heads an even number of times is 1/2 then there is at least one fair coin

Question

So the set up is as follows: We have n coins being flipped independently, not necessarily all fair. I know that if there is at least one fair coin then the probability of getting an even number of heads after flipping is 1\2. I want to show the converse, that if the probability is 1/2(of getting an even number of heads) then there is at least one fair coin.

Answer 1

Not as Elegant a Basic Approach as I Had Foreseen. We show this by induction.

First, for $n = 1$, a single coin. Obviously, then the probability of an even number of heads is simply the probability that this coin flips tails. If this coin is unfair, this probability is clearly not equal to $1/2$. Therefore the coin must be fair. This establishes the basis step.

Now, suppose that the proposition is true for some $n > 0$. Let us now show it for $n+1$. The antecedent is that the probability of an even number of heads in these $n+1$ flips is $1/2$. If (at least) one of the first $n$ coins is fair, then the consequent is true.

If, on the other hand, none of the first $n$ coins is fair, we already know that such a circumstance does not permit the probability of an even number of heads in the first $n$ tosses to be $1/2$. Let us say therefore that this probability is instead $P_n \not= 1/2$, and let the $n+1$th coin have a probability of heads of $q$. Then the probability that the number of heads is even after all $n+1$ tosses is

$$ P_{n+1} = P_n(1-q) + (1-P_n)q = P_n + q(1-2P_n) $$

But we know, by hypothesis, that $P_{n+1} = 1/2$, so we write

$$ \frac12 = P_n + q(1-2P_n) $$

which gives us, after some simple algebra,

$$ q = \frac{1/2-P_n}{1-2P_n} = \frac12 $$

This establishes the induction step and the proposition is shown.

Answer 2

This is really the same as the answer by @BrianTung but the presentation is a tad shorter. :)

Assume a set of $n$ coins has that property. Partition this set into two arbitrary non-empty subsets $X, Y$ and let $p_X = ({1 \over 2} + x), p_Y = ({1\over 2} + y)$ be the respective probabilities of each set to have an even number of heads. Then:

$$ {1 \over 2} = p_X p_Y + (1 - p_X) (1 - p_Y) = ({1 \over 2} + x) ({1 \over 2} + y) + ({1 \over 2} - x) ({1 \over 2} - y) = {1 \over 2} + 2xy$$

after you expand and realize the cross-terms cancel. Thus either $x$ or $y$ (or both) must be $0$, i.e. one (or both) of the subsets must have this property. As you recur downward you eventually reach a single coin which must be fair.

Answer 3

Case $n=3$.

Let: $$p(h_1)=x,p(h_2)=y,p(h_3)=z,0<x<y<z<1.$$ The probability of even number ($0$ or $2$) of heads: $$p(h_1h_2t_3)+p(h_1h_3t_2)+p(h_2h_3t_1)+p(t_1t_2t_3)=0.5\iff \\ xy(1-z)+xz(1-y)+yz(1-x)+(1-x)(1-y)(1-z)=0.5 \iff \\ x+y+z-2(xy+yz+xz)+4xyz=0.5 \iff \\ y(1-2x-2z+4xz)=0.5-x-z+2xz \Rightarrow \\ \begin{cases}0<x=\frac12<y<z<1\\ 0<x<y=\frac12<z<1\\ 0<x<y<z=\frac12\end{cases}.$$

Answer 4

Does this solution work? this is inspired from Brian Tung's solution above.

We use an induction argument. Let $n$ be the number of coins. When $n=1$, $$P(\text{even number of heads}) = \frac{1}{2}= P(T)$$ So, the coin must be fair.

For $n>1,$ assume that the probability of even number of heads appearing is $\frac{1}{2}$ and at least one of the coins is a fair coin. We will show that the probability of even number of heads appearing after tossing $n+1$ coins is also $\frac{1}{2}$ and there exists at least one fair coin among the $n+1$ coins. Let $q$ be the probability the $n+1$th coin is heads.

$$P(\text{even number of heads after n+1 tosses}) = \frac{1}{2} q + \frac{1}{2} (1-q) = \frac{1}{2} $$

So, we can see that for $n+1$ coins, the probability that an even number of heads appear when they are tossed is also $\frac{1}{2}$ and by induction hypotheses one of the coins is guaranteed to be fair.