Probability question asked in a interview

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.

• Hint: Think binary number representation of uniformly distributed real numbers. If you are from information coding then also thinking arithmetic coding may help. – mathreadler Apr 1 '17 at 1:08
• can you please elaborate little bit more ? thanks. – 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$.

• Thanks for the confirmation that the interviewer may have stated the problem incorrectly, I was really kicking myself for this one. – 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$

• that plus 1 in your answer should be subscript correct ? – szd116 Apr 1 '17 at 3:29
• If you are referring to the '$B_n +1$'s- they are not typos. – 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.