Maybe I shouldn't have brought up "injective" and "surjective" here. A more down-to-earth concrete proof would entail contriving a discrete probability space (that is, a set of outcomes, each of which is assigned a non-negative probability, with probabilities summing to 1 over the whole space) and two events E and F on the space (where an event is a set of outcomes) satisfying three properties: the probability of E is easily seen to be equal to the probability of getting an even number of heads in n tosses; the probability of F is easily seen to be 1/2; and F is easily seen to be a subset of E. One could in principle look for proofs of a similar flavor in which, instead of a single probability space, one has two probability spaces, and a probability-preserving map between them; that's more the sort of thing I had in mind. But now I think that's needlessly complex. Jim On Tue, Mar 22, 2016 at 10:09 AM, Michael Greenwald <mbgreen@seas.upenn.edu> wrote:
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