A probability theory question about independent coin tosses by two players

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.

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$$

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$.