Probability that binomial random variable is greater than another Let $X$ and $Y$ be two independent random variables with respective distributions $B(n+1,\frac{1}{2})$ and $B(n,\frac{1}{2})$. I am trying to determine $\mathbb{P}(X>Y)$. So far, I have written that:
$$\mathbb{P}(X>Y)=\sum_{k=0}^n \mathbb{P}(X>k)\mathbb{P}(Y=k)=\frac{1}{2^{2n+1}}\sum_{k=0}^n {n \choose k}\sum_{j=k+1}^{n+1}{n+1 \choose j}.$$
However, at this point, I am not sure how to compute the double sum involving the binomial coefficients. Is there any way we can re-arrange the terms to make use of the identity $\sum_{k=0}^n {n \choose k}=2^n$? 
 A: Alicia and Beti each toss a fair coin repeatedly. Alicia does it $n+1$ times and Beti does it $n$ times. Alicia wins if her number $X$ of heads is greater than Beti's number $Y$ of heads.
We find the probability that $X\gt Y$, that is, the probability that Alicia wins.
After $n$ tosses by Alicia, and $n$ by Beti, there are three possibilities:
(i) Alicia is leading. Then, whatever happens on her $(n+1)$-th toss, Alicia will win
(ii) Beti is leading. Then whatever happens on Alicia's $(n+1)$-th toss, Beti will win.
(iii) They are tied. Then, depending on the result of her $(n+1)$-th toss, Alicia will win or lose.
By symmetry (i) and (ii) are equally likely. And in Case (iii), Alicia has probability $1/2$ of winning.
Thus the probability that Alicia wins the game is $1/2$.  So $\Pr(X\gt Y)=1/2$.
A: Note that
$$ \mathbb{P}(X\leq Y)=2^{-2n-1}\sum_{k=0}^n{n\choose k}\sum_{j=0}^{k}{n+1\choose j} $$
by the same argument as in your question.
Now let $l=n-k$ and $i=n+1-j$, so that ${n\choose k}={n\choose l}$ and ${n+1\choose j}={n+1\choose i}$. 
If $0\leq j\leq k$ then $n+1-k\leq n+1-j\leq n+1$, i.e. $l+1\leq i\leq n+1$. Therefore
$$ \mathbb{P}(X\leq Y)=2^{-2n-1}\sum_{k=0}^n{n\choose k}\sum_{j=0}^{k}{n+1\choose j}=2^{-2n-1}\sum_{l=0}^n{n\choose l}\sum_{i=l+1}^{n+1}{n+1\choose i}=\mathbb{P}(X>Y) $$
Since the events $\{X\leq Y\}$ and $\{X>Y\}$ are complementary, each must have probability $\frac{1}{2}$.
