[math-fun] Biased coin parity puzzle
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
this follows by induction from the easy lemma: if p>1/2 and q>1/2, then pq+(1-p)(1-q)>1/2 proof: pq+(1-p)(1-q) is larger than its complement p(1-q)+(1-p)q since this reduces to (2p-1)(2q-1) > 0. erich
On Mar 21, 2016, at 11:06 PM, 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
Aren't there are two cases required here, requiring two separate lemmas, one for when n is even and the other for when n is odd? I don't quite follow this proof. Jim On Monday, March 21, 2016, Erich Friedman <erichfriedman68@gmail.com> wrote:
this follows by induction from the easy lemma: if p>1/2 and q>1/2, then pq+(1-p)(1-q)>1/2 proof: pq+(1-p)(1-q) is larger than its complement p(1-q)+(1-p)q since this reduces to (2p-1)(2q-1) > 0.
erich
On Mar 21, 2016, at 11:06 PM, James Propp <jamespropp@gmail.com <javascript:;>> 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 <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
if you believe the purely algebraic lemma, then your result about an even number of heads being more likely than an odd number of heads follows easily. let p be the probability of heads on n flips, and let q be the probability of heads on 1 more flip. by the inductive hypothesis, p>1/2 and q>1/2. and therefore the probability of an even number of heads on all n+1 flips, pq+(1-p)(1-q) > 1/2 as well. erich
On Mar 22, 2016, at 8:53 AM, James Propp <jamespropp@gmail.com> wrote:
Aren't there are two cases required here, requiring two separate lemmas, one for when n is even and the other for when n is odd? I don't quite follow this proof.
Jim
On Monday, March 21, 2016, Erich Friedman <erichfriedman68@gmail.com> wrote:
this follows by induction from the easy lemma: if p>1/2 and q>1/2, then pq+(1-p)(1-q)>1/2 proof: pq+(1-p)(1-q) is larger than its complement p(1-q)+(1-p)q since this reduces to (2p-1)(2q-1) > 0.
erich
On Mar 21, 2016, at 11:06 PM, James Propp <jamespropp@gmail.com <javascript:;>> 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 <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sorry to be dense, but I'm still confused. (Actually, in the course of composing this email I think I un-confused myself; see below.) On Tuesday, March 22, 2016, Erich Friedman <erichfriedman68@gmail.com> wrote:
if you believe the purely algebraic lemma, then your result about an even number of heads being more likely than an odd number of heads follows easily.
let p be the probability of heads on n flips,
p is already defined to be the bias of the coin. But I can be flexible about notation. Anyway, I'm unsure what you mean by "the probability of heads on n flips"; I think you mean the probability of an even number of heads on n flips. and let q be the probability of heads on 1 more flip. Actually, I think you want to let q be the probability of a single toss (the n+1st) coming up tails (see below).
by the inductive hypothesis, p>1/2 and q>1/2.
q<1/2 if q denotes the probability of heads on a single flip. So I'll proceed on the assumption that you meant that q is the probability of getting an even number of heads (which is to say none at all) on the last toss, i.e., the probability of getting tails.
and therefore the probability of an even number of heads on all n+1 flips, pq+(1-p)(1-q) > 1/2 as well.
Yes, I think I get it now. Nice! Jim
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.) 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
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
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
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
participants (4)
-
Erich Friedman -
Gareth McCaughan -
James Propp -
Michael Greenwald