Steve flips 499 coins and Marissa flips 500 coins. What is the probability that Marissa flips more heads than Steve does?
We use casework for each of the possible number of heads that Steve flips. The first is $$\frac{1}{2^{499}\cdot2^{500}}\left(\binom{500}{1}+\binom{500}{2}+\dots+\binom{500}{500}\right),$$ because there is a $1/2^{499}$ chance that Steve flips 0 heads, and each of the possible number of heads that Marissa can flip have a denominator of $1/2^{500}$, because that is the total number of arrangements of heads and tails for Marissa. Following this, we have $$\frac{\dbinom{499}{1}}{2^{499}\cdot2^{500}}\left(\binom{500}{2}+\binom{500}{3}+\dots+\binom{500}{500}\right),$$ omitting the possibility of Marissa flipping 1 head, because in this case Steve flips 1 head. Then, we just keep going with this summation $$\sum_{k=0}^{499}\frac{\dbinom{499}{k}}{2^{499}\cdot2^{500}}\left(\sum_{i=k+1}^{500}\dbinom{500}{i} \right).$$ I am unsure of how to simplify it.
I understand that Marissa has a $1/2$ chance of winning by a $1-1$ correspondence between the number of non-winning and winning outcomes, but I would just like to see how the above could be simplified. In other words, it would be nice if I could get a solution similar to mine.
It can be simplified algebraically, but it’s a bit of a pain. I actually did the first five steps of the second computation first, then came back and did the first computation, and finally finished it off.
First observe that
$$\begin{align*} \sum_{0\le k<i\le 500}\binom{499}k\binom{500}i&=\sum_{0\le k<i\le 500}\binom{499}k\left(\binom{499}{i-1}+\binom{499}i\right)\\ &=\sum_{0\le k\le i\le 499}\binom{499}k\binom{499}i+\sum_{0\le k<i\le499}\binom{499}k\binom{499}i\;. \end{align*}$$
Then
$$\begin{align*} \sum_{k=0}^{499}\binom{499}k\sum_{i=k+1}^{500}\binom{500}i&=\sum_{0\le k<i\le 500}\binom{499}k\binom{500}i\\ &=\left(\sum_{k=0}^{499}\binom{499}k\right)\left(\sum_{i=0}^{500}\binom{500}i\right)\\ &\quad\quad-\sum_{0\le i\le k\le 499}\binom{499}k\binom{500}i\\ &=2^{499}\cdot2^{500}-\sum_{0\le i\le k\le 499}\binom{499}k\binom{500}i\\ &=2^{499}\cdot2^{500}-\sum_{0\le i\le k\le499}\binom{499}k\left(\binom{499}{i-1}+\binom{499}i\right)\\ &=2^{499}\cdot2^{500}-\sum_{0\le i\le k\le499}\binom{499}k\binom{499}i\\ &\quad\quad-\sum_{0\le i<k\le499}\binom{499}k\binom{499}i\\ &=2^{499}\cdot2^{500}-\sum_{0\le k<i\le 500}\binom{499}k\binom{500}i\\ &=2^{499}\cdot2^{500}-\sum_{k=0}^{499}\binom{499}k\sum_{i=k+1}^{500}\binom{500}i\;, \end{align*}$$
so
$$\sum_{k=0}^{499}\binom{499}k\sum_{i=k+1}^{500}\binom{500}i=\frac12\cdot2^{499}\cdot2^{500}\;,$$
and
$$\frac1{2^{499}\cdot2^{500}}\sum_{k=0}^{499}\binom{499}k\sum_{i=k+1}^{500}\binom{500}i=\frac12\;.$$