Probability of Coins Flips

Person A has 5 fair coins and Person B has 4 fair coins. Person A wins only if he flips more heads than B does. What is the probability of A winning?

When I initially thought about the problem, I thought of it as if both had 4 coins, then they would on average get the same number of heads. If Person A had one more coin, then it would be a 50/50 shot for Person A to have more each time. But the more I think about this, its making less sense to me as an explanation, or at least it is incomplete.

Logically as I think about it if you have 2 people with the same amount of coins, they both have the same chance of winning, although that percent is less than 50 for each person because of the chance of them tying. When you give a person an extra coin, that reduces the probability of tying by half (one half is tie when the guy flips tails with his extra and the other half is when the guy flips and gets heads and get an extra point). I'm not sure how to justify the thought that the original percentage of winning + the extra gain from the tie scenarios given by the extra coin = 50%.

I guess I'm just looking for any tips on how to think about this problem so I can more fully understand it.

Thanks

-
One way to look at it is that Person A and Person B have only one coin. Person A has 5 flips with which to maximize the number of heads, Person B has 4. –  Joel Cornett May 19 '12 at 2:27

Imagine that A and B each toss $4$ times. There is a certain probability $p$ that A is ahead, and by symmetry the same probability $p$ that B is ahead. If A is already ahead, she will win, whatever her $5$th toss. If B is already ahead, she will win. And if they are tied, there is probability $1/2$ that A will get a head on her $5$th toss and win. Thus by symmetry the probability that A wins is $1/2$.

Or else we can compute. The probability they are tied after $4$ is $1-2p$. Thus the probability that A wins is $$p+\frac{1}{2}(1-2p)=\frac{1}{2}.$$

Remark: The same argument applies if B has $n$ coins and A has $n+1$.

-
Very nice argument! –  bgins May 18 '12 at 19:56

The sample space is the grid of points $\{0,1,2,3,4,5\} \times \{0,1,2,3,4\}$, corresponding to $(H_A, H_B)$. Orange dots are those where $A$ wins. There are as many gray dots as orange dots.

$H_A$ and $H_B$ are independent symmetric binomial random variables, hence $$\begin{eqnarray} \mathbb{P}(H_A = h_a, H_B = h_b) &\stackrel{\text{independent}}{=}& \mathbb{P}(H_A = h_a)\mathbb{P}( H_B = h_b) \\ &\stackrel{\text{symmetry}}{=}& \mathbb{P}(H_A = 5-h_a)\mathbb{P}( H_B =4- h_b) \\ &=& \mathbb{P}(H_A = 5-h_a, H_B = 4-h_b) \end{eqnarray}$$ But $(h_a, h_b) \mapsto (5-h_a, 4-h_b)$ interchanges orange and gray dots, therefore the total probability of $A$ winning (orange dots) is $\frac{1}{2}$.

-
Beautiful. May I ask how you created the nice graphic? –  bgins May 18 '12 at 19:42
@bgins I used Mathematica, Graphics[Table[{If[h1 > h2, Orange, Gray], Disk[{h1, h2}, 1/4]}, {h1, 0, 5}, {h2, 0, 4}], GridLines -> {Range[0, 5], Range[0, 4]}, Frame -> True]. –  Sasha May 18 '12 at 19:43
Don't we need to account for the fact that dot at $(a,b)$ has non-uniform probability, namely $$\frac{{5\choose a}}{2^5}\cdot\frac{{4\choose b}}{2^4}\,?$$ Don't we need a symmetry argument for why the orange parts have the same weight as the grey parts? –  bgins May 18 '12 at 19:53
@bgins Yes! But the symmetry $(a,b) \to (5-a,4-b)$ is what matters. –  Sasha May 18 '12 at 19:56
@NeilG It should be. I will extend the answer once I have a chance. –  Sasha May 18 '12 at 22:11

Here is the plodding method, using the definition and -- as it turns out -- more computation than is necessary.

As random variables, we could say that $A\sim\operatorname{Binom}\left(5,~\tfrac12\right)$ and $B\sim\operatorname{Binom}\left(4,~\tfrac12\right)$ are independent (but not identically distributed) binomial with $n=5,4$ respectivly and both with $p=\tfrac12$. Since they are independent, we can calculate the probability that $A>B$ thus: $$\mathbb{P}\left(A > B\right) =\sum_{a=1}^5 {5\choose a}\frac1{2^5} \sum_{b=0}^{a-1}{4\choose b}\frac1{2^4} =\frac1{2^9}\sum_{a=1}^5\sum_{b=0}^{a-1}{5\choose a}{4\choose b} =\frac{256}{2^9}=\frac12$$ The trick to finding this sum without computation is Sasha's nice diagram, with the symmetry $(a,b)\leftrightarrow(5-a,4-b)$; using this transformation, the above sum has a complementary sum, which is equal, and the two of which together must sum to unity.

-

Assume A and B used 4 coins each only, getting a and b heads respectively. If a>b, A has already more heads than B hence A has more heads than B once the result of the 9th coin is added, and A wins. If b>a, B still has at least as many heads as A once the result of the 9th coin is added hence B wins. If a=b, A wins if the last coin is head and loses otherwise.

Since a and b are i.i.d., A wins with probability one-half.

-