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

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.

• My guess is that there is some reasonably elegant argument by induction. – Brian Tung Mar 10 at 19:47

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.

• For $n=1$, shouldn't the probability of an even number of heads be the probability to get tails? Since that is the probability of getting 0 heads, which is even, rather than 1 heads, which is odd. – Dasherman Mar 10 at 20:57
• @Dasherman: Yes, it should! In fact, when I read your comment, I thought I had in fact written "tails" (as is correct), and was dismayed to notice that I actually wrote "heads." Thanks for the catch! – Brian Tung Mar 10 at 20:58

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.

Case $$n=3$$.

Let: $$p(h_1)=x,p(h_2)=y,p(h_3)=z,0 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