Marilyn Vos Savant question in Parade a couple of weeks ago.

[Steven G]

I think you're missing the case where I had fewer heads among the n, but my extra k make up for it.

That also is where 1 comes into my argument: To have more heads with n+1 coins, I have to have either tied or better with n. That isn't true for n+k.

Yes, I once again am guilty of sloppy thinking. I think that the part you mentioned might be difficult to compute but I have to give it a little thought.

 

[Dr.Peterson]

... In fact, it's too late for me to take the time to think it through enough, so I'll look into it tomorrow.

Okay, let's try to settle this. My argument was:

The real justification for her conclusion, though, is symmetry. If we posed the same problem, asking about the probability that I have more tails, the answer has to be the same as the probability that I have more heads, since heads and tails are interchangeable. Since, as she says, we can't tie, I must be equally likely to win or lose, and that probability is 1/2.

So, what is "the same problem"? The original problem is, "I have n+1 coins, you have n. What is the probability that I toss more heads than you?" Clearly the probability that I toss more tails than you is the same.

So far, nothing is different if I have 100 coins and you have 2. But now, both of those probabilities are very high; and they certainly don't add up to 1, but in fact close to 2. My having more heads and my having more tails are not mutually exclusive; that is, if "winning" means having more heads, having more tails isn't equivalent to "losing" (or not winning). That is why the argument doesn't work for 100 vs 2.

But in the n+1 vs n case, they are mutually exclusive, because if I have more heads than you, I must not have more tails than you, due to the difference being 1. To elaborate, suppose you have 10 coins and I have 11. If I have, say, 4 heads and you have 3, then I have 7 tails and you have 7. I don't have more tails. Generalizing, if you have n and I have n+1, and I get x heads while you get y<x, then I get n+1-x tails while you get n-y tails. The difference is (n+1-x)-(n-y) = y-x+1 < 1, which implies that the difference is non-positive. If we replaced 1 with k, the final conclusion would not be true.

So now the question is, (a) how do we say this briefly and convincingly, and (b) does Marilyn's version somehow imply this but we missed it?

 

[LCKurtz]

Thanks for your thoughts on this Dr. Peterson. I think that clears it up. When I first read the problem I didn't think (and still don't) that Marilyn's argument held water. Therefore, I was skeptical that the answer 1/2 was even correct. So I ran off some cases in Maple to test the n,n+1 pair for several values of n and was surprised it was apparently correct. So I'm thinking it shouldn't be that hard to prove it directly. This leads pretty quickly to trying to prove
[MATH]\sum_{r=1}^{n+1}\sum_{c=0}^{r-1}\binom{n+1}{r}\binom{n}{c} =2^{2n}[/MATH]What seems interesting about this is that, any way you write it, it seems to involve (weighted) partial sums of binomial coefficients. Your reasoning apparently gives a probability argument for the truth of the identity. Since whoever posed the problem to Marilyn got it from somewhere, I'm guessing this is all "well known", but not to me. Anyway, I found it interesting enough to post it here.