On 22/03/2016 13:42, James Propp wrote:
Here's my proof: Let q=1-p, so that for all i+j=n, the coefficient of p^i q^j in the binomial expansion of (p+q)^n gives the probability of getting heads i times and tails j times. Meanwhile, the coefficient of p^i q^j in the binomial expansion of (-p+q)^n is (-1)^i times the aforementioned probability. So if we add the two expressions and divide by 2, we obtain just those terms in which i is even. That is, the probability of an even number of heads in n tosses is exactly ((p+q)^n + (-p+q)^n)/2, and since (p+q)^n = 1, that probability is bigger than 1/2.
The proof that feels natural to me is almost equivalent but seems neater. If you expand (px+qy)^n you get all possibilities, weighted by probability times x^#heads y^#tails. In particular, if you expand (-p+q)^n you get them with a factor (-1)^#tails, which means you get Pr(even #heads) - Pr(odd #heads). But of course (-p+q)^n is non-negative because p<q. This feels to me like a "bijective" proof not exactly of the formula for Pr(even #heads) but of the formula for Pr(even)-Pr(odd). You might briefly hope for a "bijective" proof that Pr(even) >= Pr(odd) by pairing even-H and odd-H n-tuples so that in each pair the "even" one has fewer heads and hence higher probability. But that can't work. (E.g., when n=3 we have HHT,HTH,THH which would all need pairing with something whose #heads is even and <1, but there's only one of those.) Perhaps there's an approach along these lines that shares the pairings somehow and uses AM>=GM to prove the necessary inequalities, but that feels clearly more complicated than the proof above. -- g