Two gamblers are playing coin toss game: Gambler A has (n+1) coins and B has n coins. What is the probability that A will have more heads than B if both flip all their coins.

Not sure how to go about solving it. Any ideas? What if A has (n+2) coins.

  • 1
    $\begingroup$ Possible duplicate of A probability theory question about independent coin tosses by two players $\endgroup$ – lulu May 29 '16 at 0:32
  • $\begingroup$ Hint: After $A$ has tossed $n$ of her coins, and $B$ has tossed all of hers, either (i) $A$ is leading or (ii) $B$ is leading or (iii) they are tied. Note that (i) and (ii) are equally likely. $\endgroup$ – André Nicolas May 29 '16 at 0:39
  • $\begingroup$ @lulu: This one has the additional $A$ has $n+2$ coins question. $\endgroup$ – André Nicolas May 29 '16 at 0:44
  • $\begingroup$ @AndréNicolas Ah, missed that. Thanks. Doubt that case is easy... $\endgroup$ – lulu May 29 '16 at 0:45

Assuming a fair coin.

Let $X$ be the count of successes in the first $n$ flips by A, $Y$ the indicator that the last flip by A is also a success, and $Z$ the count of successes in $n$ flips by B.

Because $Y$ is independent of $X$ and $Z$, then:

$$\begin{align}\mathsf P(X+Y>Z) ~=&~ \mathsf P(Y=1)\,\mathsf P(X\geq Z)+\mathsf P(Y=0)\,\mathsf P(X>Z)\\ = &~ \tfrac 12(\mathsf P(X=Z)+2~\mathsf P(X>Z)) \end{align}$$

Note by symmetry that $\mathsf P(X>Z) = \mathsf P(Z>X)$ and so ...


Suppose there are $n+1$ coins for Gambler A and $n$ coins for Gambler B.

The possibilities for Gambler B are $2^n$ and the possibilities for Gambler A are $2^{n+1}$ or $2^n \cdot 2$. There are twice as many possibilities and half of them in which there is an additional heads. Simply put Gambler A has a $50\%$ chance of having strictly more head flips.

But the real insights come when you generalize the problem to say that Gambler B has $n$ coins and flips $k$ heads. What are the chances that Gambler A flips more than $k$ heads given they have $n + m$ coins.

Well the chance, $p$, that someone flips a given number of heads or more than a given number of heads is given by the binomial distribution which can be used to show that the probability of Gambler A achieving at least more heads than Gambler B is given by the following equation:

$\begin{align*} p =\sum_{k=0}^{n} \left({n \choose k} \cdot 0.5^k \cdot 0.5^{n-k} \cdot \sum_{j=k+1}^{n+m} \left( {n+m \choose j} \cdot 0.5^j \cdot 0.5^{n+m-j}\right)\right) \end{align*}$

I'll add more when I can. But in the mean time you may be able to see that $p$ remains $0.5$ no matter how large $n$ becomes as long as $m$ is $1$.

However if $m$ is $2$ the situation becomes exceedingly more complicated because the answer is not constant. Here are the first few cases:

  • $n$ is $1$ then $p$ is $0.6875$.
  • $n$ is $2$ then $p$ is $0.65625$.
  • $n$ is $3$ then $p$ is about $0.63671$.
  • $n$ is $1000$ then $p$ is about $0.50891$.

Gambler A loses his comparative advantage the more coins that are tossed for both Gamblers. But Gambler A will always maintain the advantage and has quite a heavy advantage when few coins are tossed.

When Gambler A has one extra coin he may as well just toss one coin. When Gambler A has more than one extra coins, I don't see a way to simplify things here (which doesn't mean that it doesn't exist).

  • $\begingroup$ how about the case when m>1, say m=2 $\endgroup$ – Gerry May 29 '16 at 12:37
  • $\begingroup$ @Gerry When $m=2$ the highest $p$ will be is when $n=1$, which is $0.6875$. As $n$ increases the relative advantage of Gambler A decreases and $p$ approaches $0.5$. $\endgroup$ – Marcus Helmer May 29 '16 at 17:18
  • $\begingroup$ Thanks. Can you please elaborate on how you arrived at expression for p in your solution. $\endgroup$ – Gerry May 29 '16 at 20:26
  • $\begingroup$ @Gerry The largest summation, that is $\sum_{k=0}^{n}$ covers all cases of Gambler B flipping $k$ heads from 0 heads to $n$ heads. The second part comes from the binomial distribution and is the probability that Gambler B flips exactly $k$ heads. That is multiplied by the chance that Gambler A flips $k$ or more heads ($k+1$ to $n+m$ heads). So it is a summation of binomial distributions so to speak. The summation essentially adds the chance of Gambler A flipping more than $k$ heads for each possible number of heads that can be flipped for Gambler B. Does that make it clear? $\endgroup$ – Marcus Helmer May 29 '16 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.