Player A throws ninety-nine coins and player B throws a hundred. What is the probability that player A will have more heads than player B do ?

I know the chance of B having more heads than A is 1/2.

  • $\begingroup$ Hint: Think binary number representation of uniformly distributed real numbers. If you are from information coding then also thinking arithmetic coding may help. $\endgroup$ – mathreadler Apr 1 '17 at 1:08
  • $\begingroup$ can you please elaborate little bit more ? thanks. $\endgroup$ – szd116 Apr 1 '17 at 1:13

Clearly, as an interview question, either:

  1. You have misinterpreted or incorrectly recalled the question;
  2. The interviewer misstated the question.

As it is posed, the question is not trivially answered, as a simple Mathematica command shows:

Probability[a > b, {Distributed[a, BinomialDistribution[n, p]],
   Distributed[b, BinomialDistribution[n + 1, p]]} /. {n -> 99, p -> 1/2}]

which gives the output $$\frac{89115063434173982075697108636637142173324613401997885101171}{200867255532373784442 745261542645325315275374222849104412672}.$$

This of course assumes all coins are fair ($p = 1/2$). Had the problem been posed as, "What is the probability that $A$ has at least as many heads as $B$," then yes, the answer is exactly $1/2$ for $p = 1/2$. But this is not what you stated.

It is easy to see that the answer will be complicated by considering the small-$n$ case; e.g., suppose $n = 1$, in which $A$ has one coin and $B$ has $n+1 = 2$ coins. Then the only outcome in which $A > B$ is when $A = 1$ head and $B = 0$ heads, which when $p = 1/2$ occurs with probability $1/2^3 = 1/8$. When $n = 2$, the probability is $6/2^5$; when $n = 3$, the probability is $29/2^7$. In the general case, $$\begin{align*} \Pr[A > B \mid p = 1/2] &= \Pr[A \ge B \mid p = 1/2] - \Pr[A = B \mid p = 1/2] \\ &= \frac{1}{2} - \frac{1}{2^{2n+1}} \sum_{k=0}^n \binom{n}{k} \binom{n+1}{k} \\ &= \frac{1}{2} - \frac{\Gamma(n+3/2)}{\Gamma(1/2)\Gamma(n+2)}. \end{align*}$$ I do not think this is the kind of answer the interviewer intended you to produce, hence my claim above.

Furthermore, in the general case for $p \in (0,1)$, the probability $\Pr[A > B]$ is a polynomial function of $p$, as is $\Pr[A \ge B]$. Thus it may be reasonable to infer that $p = 1/2$, but regarding the question as it is posed, there can be no doubt that the answer is not simply $1/2$.

  • $\begingroup$ Thanks for the confirmation that the interviewer may have stated the problem incorrectly, I was really kicking myself for this one. $\endgroup$ – szd116 Apr 1 '17 at 2:42

Let $A_n$ and $B_n $ respectively be the number of heads A and B gets by throwing $n$ coins, and $X_n \in ${head, tail} be the outcome of the $n-$th toss of B. \begin{align} \mathbb{P}(B_{n+1}>A_n) &= \mathbb{P}(B_{n+1}>A_n| X_{n+1}=\textrm{head})\mathbb{P}(X_{n+1}=\textrm{head}) + \mathbb{P}(B_{n+1}>A_n| X_{n+1}=\textrm{tail})\mathbb{P}(X_{n+1}=\textrm{tail})\\ &=\mathbb{P}(B_{n}\geq A_n)\frac{1}{2} + \mathbb{P}(B_{n}>A_n)\frac{1}{2}\\ &=\frac{1}{2}\left[\mathbb{P}(B_{n}\geq A_n) + \mathbb{P}(B_{n}>A_n)\right]\\ &=\frac{1}{2}\left[\mathbb{P}(B_{n}\geq A_n) + \mathbb{P}(B_{n}<A_n)\right] \quad \because \mathbb{P}(B_n > A_n ) = \mathbb{P}(A_n > B_n ) \textrm{ by symmetry}\\ &=\frac{1}{2} \quad \because \mathbb{P}(B_{n}\geq A_n) + \mathbb{P}(B_{n}<A_n) = 1 \end{align}

Now answering the actual question that is asked.... \begin{align} \mathbb{P}(A_n > B_{n+1}) &= \frac{1}{2}\left[ \mathbb{P}(A_n > B_n +1) + \mathbb{P}(A_n > B_n) \right] \\ &= \frac{1}{2}\left[ \mathbb{P}(A_n > B_n +1) + \mathbb{P}(A_n < B_n) \right] \\ &= \frac{1}{2}\left[ 1 - \mathbb{P}(A_n = B_n ) - \mathbb{P}(A_n = B_n +1) \right]\\ &= \frac{1}{2}\left[ 1 - \sum_{k=0}^n \mathrm{Binomial}\left(k;n,\frac{1}{2}\right)\left(\mathrm{Binomial}\left(k;n,\frac{1}{2}\right) + \mathrm{Binomial}\left(k+1;n,\frac{1}{2}\right)\right) \right] \\ &= \frac{1}{2}\left[ 1 - 4^{-n} \binom{2n+1}{n+1}\right] \end{align} With $n=99$, this is $= 0.44365152099$

  • $\begingroup$ that plus 1 in your answer should be subscript correct ? $\endgroup$ – szd116 Apr 1 '17 at 3:29
  • $\begingroup$ If you are referring to the '$B_n +1$'s- they are not typos. $\endgroup$ – ChargeShivers Apr 1 '17 at 14:40

HINT: observe that $A\sim\operatorname{Binom}(99,1/2)$ and $B\sim\operatorname{Binom}(100,1/2)$, and you are asking for $\Pr[A>B]$, what is the same to ask for $\Pr[A-B>0]$.

If we name $Z:=A-B$ we have that

$$F_Z(z)=\sum_{\{(j,k):j-k=z\}} f_{AB}(j,k)=\sum_{k=-\infty}^\infty f_{AB}(z+k,k)=\sum_{k=-\infty}^\infty f_A(z+k)f_B(k)$$

because $A$ and $B$ are independent.


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.