Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say Bob tosses his $n+1$ fair coins and Alice tosses her $n$ fair coins. Lets assume independent coin tosses. Now after all the $2n+1$ coin tosses one wants to know the probability that Bob has gotten more heads than Alice.

The way I thought of it is this : if Bob gets $0$ heads then there is no way he can get more heads than Alice. Otherwise the number of heads Bob can get which allows him to win is anything in the set $\{1,2,\dots,n+1\}$. And if Bob gets $x$ heads then the number of heads that Alice can get is anything in the set $\{0,1,2,..,x-1\}$. So\begin{align}P(\text{Bob gets more heads than Alice})&= \sum_{x=1}^{n+1} \sum_{y=0}^{x-1} P( \text{Bob gets x heads }\cap \text{Alice gets y heads }) \\[0.2cm]&= \sum_{x=1}^{n+1} \sum_{y=0}^{x-1} \left(C^{n+1}_x \frac{1}{2}^{x} \frac{1}{2}^{n+1-x}\right)\left( C^n_y \frac{1}{2}^y \frac {1}{2}^{n-y}\right)\\[0.2cm]& = \sum_{x=1}^{n+1} \sum_{y=0}^{x-1} \frac{C^{n+1}_x C^n_y}{2^{2n+1}}\end{align}

  • How does one simplify this?

Apparently the answer is $\frac{1}{2}$ by an argument which looks like this, Since Bob tosses one more coin that Alice, it is impossible that they toss both the same number of heads and the same number of tails. So Bob tosses either more heads than Alice or more tails than Alice (but not both). Since the coins are fair, these events are equally likely by symmetry, so both events have probability 1/2.

share|cite|improve this question
    
The probability that Bob throws $x$ heads is binomial,so you're missing coefficients here. – Henno Brandsma Feb 19 at 14:27
    
I did put in the binomial in the edit. But I have no clue how to simplify this! – guest Feb 19 at 14:36
    
The "but not both" is key. Note that if Bob flips 3 more coins, he might have more heads and more tails than Alice. Also, the advantage Bob gets from flipping one more coin is precisely counterbalanced by the fact that he loses ties. – Kyle Strand Feb 19 at 21:50

the answer is indeed $\frac 12$ .

As an alternative way to see that: let's pause just before Bob tosses his final (extra) toss. At this point, there are three possible states: either Bob is ahead, Alice is ahead, or they are tied. Let $p$ be the probability that Bob is ahead. By symmetry, $p$ is also the probability that Alice is ahead (so the probability of a tie is $1-2p$). Note that symmetry does clearly apply here since they have thrown the same number of tosses. Bob has exactly two ways to win: either he is ahead before the last toss, or they are tied and Bob gets $H$ on the last throw. Thus the probability that Bob eventually wins is $$p+\frac 12 \times (1-2p)=p+\frac 12 -p =\frac 12$$

share|cite|improve this answer
    
In your first case shouldn't it be "Bob is ahead before the last toss and he also wins the last toss"? – guest Feb 19 at 14:43
1  
@guest No, he is the only one to toss a last time, so if he is ahead before this last toss, he will remain first no matter what. – Jimmy R. Feb 19 at 14:44
    
@guest What Jimmy R. says is exactly the point. If Bob is ahead before the last throw, he can stop. He can't lose from there. – lulu Feb 19 at 14:46
1  
@guest If Alice (not sure why I switched it to Ann) is ahead before Bob's last turn, then Bob is doomed. Getting $H$ might tie them up but so what? He can't end up with more Heads. So if Alice is ahead before the final toss, Bob can not win. – lulu Feb 19 at 14:51
1  
@guest Well, you'll notice that I did not try to compute $p$. Also, the argument I gave (and the symmetry argument sketched in your question) don't work if the coin is weighted...symmetry gives us a happy cancellation. – lulu Feb 19 at 15:59

Get out some red paint. Paint all the heads sides on Bob's coins, and paint all the tails sides of Alice's coins. Bob wins if and only if at least $n + 1$ coins out of $2n + 1$ land red side up. By symmetry, the probability of this happening is $1/2$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.