# Probability question regarding flipping coins

I have the following probability problem that I am having trouble with.

"Jane tossed a symmetric coin n+1 times independently and counted the number of tails. John did the same n times. Compute the probability Jane counted more tails than John?"

Now, I know how to solve this problem using a very tedious summation procedure, but apparently, there is a more elegant solution to this problem without taking tedious summations. I was wondering if anybody can help me find this alternative solution?

Thanks!

-
OOPS, sorry for the mistake, I just changed Bob to Jane... – szhong Jan 23 '13 at 1:08
If Jane got $x$ tails, she got $n+1-x$ heads; if John got $y$ tails, he got $n-y$ heads. Keep a count; add one when Jane gets a tail or John gets a head ($x+n-y=n+(x-y)$) and subtract one when Jane gets a head or John gets a tail ($n+1-x+y=(n+1)-(x-y)$). The result is $-1+2(x-y)$, which is positive exactly when $x>y$. But the process is just a symmetric random walk with $2n+1$ steps, and the probability that such a walk winds up in positive territory is clearly $1/2$ by symmetry. – mjqxxxx Jan 23 '13 at 1:17
Thank you for the explanations. I completely understand what is going on now! – szhong Jan 23 '13 at 1:20

Consider the situation after each has tossed a coin $n$ times. If Jane is ahead, Jane will win, no matter what the outcome of her $(n+1)$-st toss. If Jane is behind, she won’t win: the best she can do is tie. If they are tied, she will win with probability $\frac12$. Clearly the probability that she is ahead after $n$ tosses is equal to the probability that she is behind, so overall she will win with probability $\frac12$.
Let $X$ be the number of tails Jane counted, and $Y$ be the number of tails John counted. Then $X$ and $Y$ are independent, and $X \sim \operatorname{Bin}\left(n+1,\frac{1}{2}\right)$, $Y \sim \operatorname{Bin}\left(n,\frac{1}{2}\right)$. Note that $X$ is equal in distribution to $Z + U$, where $Z \sim \operatorname{Bin}\left(n,\frac{1}{2}\right)$ and $U \sim \operatorname{Bern}\left(\frac{1}{2}\right)$, where $U$, $Z$ and $Y$ are independent. Thus: $$\mathbb{P}\left(X > Y\right) = \mathbb{P}\left(Z + U > Y\right) = \mathbb{P}\left(Z + U > Y | U = 0 \right) \mathbb{P}\left(U = 0 \right) + \mathbb{P}\left(Z + U > Y | U = 1 \right) \mathbb{P}\left(U = 1 \right)$$ Meaning $$\begin{eqnarray} \mathbb{P}\left(X > Y\right) &=& \frac{1}{2} \left( \mathbb{P}\left(Z > Y\right) + \mathbb{P}\left(Z + 1 > Y\right) \right) \\ &=& \frac{1}{2} \left( \mathbb{P}\left(Z > Y\right) + \mathbb{P}\left(Z \geqslant Y\right) \right) = \frac{1}{2} \left( \mathbb{P}\left(Z > Y\right) + \left(1- \mathbb{P}\left(Z < Y\right) \right) \right) = \frac{1}{2} \end{eqnarray}$$ since by symmetry $\mathbb{P}\left(Z>Y\right) = \mathbb{P}\left(Z<Y\right)$.