Originally posted by ThudanBlunder
Bill has n+1 coins and Ben has n coins. They both throw all of their coins simultaneously and observe the number that come up heads. Assuming all the coins are fair, what is the probability that Bill gets more heads than Ben?
The probability of Bill getting "m" heads with his (n+1) coins is:
(n+1)choose(m)/2^(n+1)
The probability of Ben getting (m-1) or less heads with his "n" coins is:
SUM{(n)choose(i)/2^n}, where i=0...(m-1)
The probability of both these events happening simultaneously is simply their product. Now, to count all the possible outcomes we use the double sum:
P = SUM{(n+1)choose(j)/2^(n+1) * SUM{(n)choose(i)/2^n}}, where j=1...n+1, and i=0...j-1
For example, for n=10 at some point we would calculate the probability that Bill got 3 heads (j=3), and Bill got 0, 1, and 2 heads (i=0,1,2), at some other point we would calculate the probability that Bill got 8 heads (j=8), and Ben got 0, 1, 2, 3, 4, 5, 6, and 7 heads (i=0,1,2,3,4,5,6,7), etc...
I don't know if there's a good way to simplify the above expression, or if there's an easier "aha!" solution, but this one will give you the correct answer if you grind it out.