On 2016-03-22 06: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.
Can anyone find a "bijective" proof of this formula for the probability of an even number of heads? Or, alternatively, an "injective" or "surjective" proof that the probability is greater than or equal to 1/2? (I'm not completely sure what I mean by this, but I think I'll recognize it when I see it.)
I have what is probably a naive question --- I don't know what you mean by a "bijective" proof etc. Do you mean something more directly mapping to the individual events, like, for example, if you look at pairs of coin tosses for the biased coin, prob( TT or HH ) > prob( TH or HT )? (You have to deal with odd n, though [q > p, by assumption], which also shows why it only works for H and not T). (This ties loosely into the random bits conversation, because it is the same argument about why the effective bit rate drops with higher bias of the hardware source, when you use the normal trick to convert a biased random source of bits to an unbiased one.) I'm asking about your rough meaning of "bijective", "injective" or "surjective" in this context --- not about the specifics of a proof. (This may be obvious to everyone but me). Thanks, Michael
Jim
On Monday, March 21, 2016, James Propp <jamespropp@gmail.com> wrote:
Show that, for any bias p < 1/2, and any positive integer n, if you take a biased coin that shows heads with probability p and toss it n times, the number of times the coin shows heads is likelier to be even than odd.
I know one proof (by way of an exact formula for the probability in question) but I'll bet some of you will find other ways to prove this.
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun