16
$\begingroup$

Question

A flips a fair coin 11 times, B 10 times, what is the probability A gets more head than B?

Naive first thought

For the first 10 times of A, he has the same expected number of heads as B.

So if the 11th flip of A results in H, he get more head than B, so the answer is $50\%$.

More careful thought

instead of making arguments, I like to find systematic solutions:

$$ \Pr[H_A = a] = C(11, a) ({1\over 2})^{a} ({1\over 2})^{11-a} = C(11, a) ({1\over 2})^{11}\\ \Pr[H_B = b] = C(10, b) ({1\over 2})^{b} ({1\over 2})^{10-b} = C(10, b) ({1\over 2})^{10}\\ \Pr[H_A > H_B] = \sum_{a=0}^{11} \Pr[H_A = a] \sum_{b=0}^{a-1} \Pr[H_B = b] = ({1\over 2})^{21} \sum_{a=0}^{11} C(11, a) \sum_{b=0}^{a-1} C(10, b) $$

I don't know how to find the sum from the last line, can someone help?

$\endgroup$
9
  • 2
    $\begingroup$ Hint: A tosses more Heads than B if and only if they are tied after ten tosses and then A tosses a Head on the 11th toss. So you need to figure out the probability that A and B are tied after ten tosses, which is the sum of the probabilities that they are tied at 0 Heads each, tied at 1 Head each, tied at 2 Heads each, ..., tied at 10 Heads each. $\endgroup$ Aug 2 at 14:00
  • 5
    $\begingroup$ @DilipSarwate I don't think this A tosses more Heads than B if and only if they are tied after ten tosses is right. For example, after 10 tosses, if A has 5 heads, and B has 2 heads, they are not tied, and A has more tosses at the end $\endgroup$ Aug 2 at 14:05
  • $\begingroup$ Correct, you need to add the probability that A has more heads than B after 10 tosses to the probability described by Dilip (multiplied by the probability that A gets head on the 11th toss) $\endgroup$
    – LuckyPal
    Aug 2 at 14:09
  • $\begingroup$ @LuckyPal that is what I did right? note that my question is how to find the sum in the last line haha $\endgroup$ Aug 2 at 14:11
  • 1
    $\begingroup$ @Barry That would entirely miss the point of this exercise (which is an old probability chestnut). The "naive first thought" is the correct answer. $\endgroup$
    – whuber
    Aug 2 at 14:22

5 Answers 5

4
$\begingroup$

After 10 throws, A and B are in the exact same position. The chance that A has more heads is p, the chance that B has more heads is also p (we don't know p), and the chance for same number of heads is the remainder, 1-2p.

After the 11th throw for A only, A has more heads if he had more heads after 10 throws, or the number of heads was the same after 10 throws, and he throws head. We add the probabilities: p + (1 - 2p) / 2 = p + (0.5 - p) = 0.5.

$\endgroup$
3
  • $\begingroup$ This is already in the question under the heading "naive first thought." In comments, the OP has insisted that the question concerns how to evaluate the sum. $\endgroup$
    – whuber
    Aug 4 at 17:21
  • $\begingroup$ @whuber I agree that this does not answer the question but it does show the real base of his "naive first thought". The OP mentions equality of expectation as base but that is not correct. Also see my answer. $\endgroup$
    – drhab
    Aug 6 at 17:06
  • $\begingroup$ @drhab YES YES YES, that is what I have been trying to say in the original question until some one deleted it from the original question! $\endgroup$ Sep 1 at 2:26
18
$\begingroup$

Your "naive first thought" is the clever (standard) solution.

To make it rigorous, let $\mathscr E_0$ be the event "A and B are tied after each has tossed 10 times;" let $\mathscr E_A$ and $\mathscr E_B$ be the events "A has more heads than B after 10 tosses each" and "B has more heads than A after 10 tosses each," respectively. Let $\mathscr F$ designate the event "A has more heads than B after all tosses are made."

Notice:

  1. $\mathscr E_0,$ $\mathscr E_A,$ and $\mathscr E_B$ are mutually exclusive: no two have any outcomes in common and collectively they include all the possibilities. Therefore $$\Pr(\mathscr E_0) + \Pr(\mathscr E_A) + \Pr(\mathscr E_B)=1.$$

  2. $\Pr(\mathscr F\mid \mathscr E_A) = 1$ (A has won by the first 10 tosses); $\Pr(\mathscr F\mid \mathscr E_B) = 0$ (A is behind after 10 tosses and therefore cannot win with the last toss); and $\Pr(\mathscr F\mid \mathscr E_0) = 1/2$ (if both are tied after 10 tosses, A's 11th toss is the tiebreaker).

  3. $\Pr(\mathscr E_A) = \Pr(\mathscr{E_B})$ (after 10 tosses the game is symmetric -- both players are equally situated -- and therefore they have equal chances of being ahead at that point).

By the law of total probability,

$$\begin{aligned} \Pr(\mathscr F) &= \Pr(\mathscr F\mid \mathscr E_0)\Pr(\mathscr E_0) + \Pr(\mathscr F\mid \mathscr E_A)\Pr(\mathscr E_A) + \Pr(\mathscr F\mid \mathscr E_B)\Pr(\mathscr E_B)\\ & = \Pr(\mathscr E_0)\left(\frac{1}{2}\right) + \Pr(\mathscr E_A)(1) + \Pr(\mathscr E_B)(0)\\ &= \frac{1}{2}\left(\Pr(\mathscr E_0) + \Pr(\mathscr E_A) + \Pr(\mathscr E_A)\right)\\ &= \frac{1}{2}\left(\Pr(\mathscr E_0) + \Pr(\mathscr E_A) + \Pr(\mathscr E_B)\right)\\ & = \frac{1}{2}\left(1\right) = \frac{1}{2}. \end{aligned} $$


As an alternative approach, you wish to evaluate the double sum

$$\sum_{a \gt b} \binom{11}{a}\binom{10}{b} = \sum_{a \gt b} \binom{11}{11-a}\binom{10}{10-b} = \sum_{a^\prime \le b^\prime} \binom{11}{a^\prime}\binom{10}{b^\prime}.$$

(In case the algebra isn't obvious, the first equality exploits the Binomial coefficient symmetry and the second is the change of variable $a^\prime = 11-a,$ $b^\prime = 10-b.$ We can be a vague about the endpoints of the summations because whenever $a$ or $a^\prime$ is not in the range from $0$ through $11$ or $b$ or $b^\prime$ is not in the range from $0$ through $10$ the Binomial coefficients are zero.)

Because the indexes in the two sums on the left and right sides (1) never overlap and (2) cover all the possibilities (since either $a\gt b$ or $a\le b$ but never both), together they give the total probability, which is $1.$ Consequently, since those sums are equal, each is $1/2,$ QED.

Figure

This figure shows the rotational symmetry of the distribution under the mapping $(a,b)\to(11-a,10-b).$ The blue circles are rotated around the yellow dot into red triangles of exactly the same probability. The desired sum is the total of the blue circles, which therefore must be $1/2.$

$\endgroup$
9
  • 1
    $\begingroup$ I do not find the "naive first thought" intuitive, since when $n$ (the number of tosses) gets large, the probability remains 50% but the impact of the $n+1$th toss approximates null. I think there is a step missing in the "naive" argument. $\endgroup$
    – LuckyPal
    Aug 2 at 14:53
  • 2
    $\begingroup$ I expanded this answer to bolster that first thought. The key is the "tiebreaker" idea: the 11th toss allowed A determines the winner if neither player wins outright by the 10th toss. $\endgroup$
    – whuber
    Aug 2 at 15:19
  • $\begingroup$ thank you @whuber. Although one might characterize this explanation as less "naive", it's intuitive and I can sleep at peace again. $\endgroup$
    – LuckyPal
    Aug 3 at 5:31
  • $\begingroup$ @whuber please see my edited question where I added what if the coin is unfair? can we still use the naive approach? $\endgroup$ Aug 3 at 6:08
  • 1
    $\begingroup$ Because that completely changes the question, please undo your edits and post it as a new question. Know, however, that there is no simple closed formula or special insight that will find the answer quickly: the answer is a polynomial in the two probabilities $p$ and $q$ of degree $10$ and so it not useful. $\endgroup$
    – whuber
    Aug 3 at 13:32
3
$\begingroup$

I like your first approach, it's neat.

Here's how I often approach this kind of 'probability that player A scores more than player B' problem (which I first came up with when dealing with similar questions involving dice, many years ago). It's not clever, but it generalizes in various ways and does reduce the calculations involved. I'll try to explain in fair bit of detail but in practice the whole process takes a few moments of thought before a simplified calculation in this case involving no summing or combinatorics at all.

Let's score each head '1' and each tail '0' and sum the scores (this is just counting but emphasizes the fact that we're summing outcomes). Let $X_A$ be the score for $A$ and similarly for $B$ ($X_B$).

Now consider a different game where player B counted tails instead of heads, and call that variable $Y_B$. The probabilities of interest with fair coins are unchanged, so we would get the same answer if we responded to this question (i.e. if we computed $P(X_A>Y_B)$). Now for this new game, player B's score $Y_B=10-X_B$. Consequently:

$P(X_A>X_B) = P(X_A>Y_B) = P(X_A>10-X_B) = P(X_A+X_B>10)$

Now $X_A+X_B$ is just the number of heads in 21 tosses of a fair coin, which has expectation 10.5.

By symmetry the probability that this total exceeds 10 is $\frac12$. $\qquad\square$


Note that this strategy works for other questions like "Player A tosses 12 times and player B tosses 9 times, what's the probability player A beats player B by more than 3?".

In that case $P(X_A>X_B+3) = P(X_A>(9-X_B)+3) = P(X_A+X_B>12)$. This is a straight binomial problem, though we can use symmetry to simplify it further to calculating just two adjacent binomial probabilities.

With sums of dice, you take one more than the number of faces to flip it around. e.g. for a six-sided die, it's equivalent to subtracting a six-sided die from 7. This lets you put B's rolls on A's side of the probability again, reducing comparing two sums of dice to comparing a single sum (with more dice) to a constant number, reducing it to a straight convolution, which is easy to automate calculations for.

$\endgroup$
4
  • 1
    $\begingroup$ +1. This is memorable. In summary, you are telling us that if we know how to add a Binomial$(n,p)$ variable and an independent Binomial$(m,q)$ variable ($Y$) then we also know how to find the difference of a Binomial$(n,p)$ variable and a Binomial$(m,1-q)$ variable ($Y^\prime$) because $Y^\prime$ and $m-Y$ have the same distribution. $\endgroup$
    – whuber
    Aug 2 at 18:06
  • $\begingroup$ Well, sure, though it applies to more than just binomials; there are quite a few potential use cases in the right circumstances. In the case of a general binomial with different success proportions that would not often help much, but sometimes it's very useful. If you're already set up to do convolutions for the components (perhaps A and B's results are each already sums of binomials with different p's) you just have a bigger convolution to do. $\endgroup$
    – Glen_b
    Aug 3 at 1:12
  • $\begingroup$ @Glen_b please see my edited question where I added What if the coin is unfair? can we still use the naive approach? $\endgroup$ Aug 3 at 6:16
  • 1
    $\begingroup$ For the present I'm satisfied with answering the question that was asked when I responded. Updating a question to clarify it when it's unclear is all good but a new question is ... a new question. $\endgroup$
    – Glen_b
    Aug 3 at 8:30
2
$\begingroup$

This is not really an answer but purely involves your "naive first thought".

You base that on the fact that A and B have the same expected value of heads if only the first $10$ times are taken into account.

This is not correct.

Imagine a game where A throws $5$ coins and $B$ throws $4$ coins.

The first coin of A has probability $1$ on resulting in head, and the second, third and fourth have probability $\frac13$ on resulting in head and finally the fifth has probability $\frac12$ on heads.

The first coin of B has probability $0$ on resulting in head, and the second, third and fourth have probability $\frac23$ on resulting in head.

Then for both the expected number of heads gained in the first $4$ throws is $2$.

However the probability that A throws in total more heads than B in the whole game appears to be $\frac{706}{1458}<0.5$.

It would be correct to base it on the fact that A and B have the same probability of winning if only the first $10$ times are taken into account.

Think about it like this: A and B want to play a fair game ($10$ flips for each) but foreseeing that the game can end in a draw (which they want to prevent) they make the following agreement:

If the game ends in a draw then A throws a coin. If it is a head then A is declared to be the winner and otherwise B is declared to be the winner. Also if the game does not end in a draw A throws a coin but then evidently its result has no real impact on the question who wins.

Then evidently this game is fair and gives both players a chance of 50% to win.

Further it is true that A wins iff he throws more heads than B.

$\endgroup$
0
-2
$\begingroup$

An approximation. The coin flipping experiment is a binomial distribution, the binomial distribution can be approximated using a normal distribution (under certain conditions), the result then is the convolution of the two approximated normal distributions, which has a simple analytical solution.

If $X \sim \mathcal{B}(n,p)$ then $X \sim \mathcal{N}(np,\sqrt{(np(1-p)})$, if $np \geq 5$ and $n(1-p) \geq 5$ (rule of thumb).

For your specific case (R code)

ap=0.5
an=11

bp=0.5
bn=10

pnorm(
  0,
  (ap*an-bp*bn)/2,
  sqrt((an*ap*(1-ap)+bn*bp*(1-bp))/2),
  lower.tail=F
)

[1] 0.5613147
$\endgroup$
3
  • $\begingroup$ This result is remarkably misleading, but it can be fixed up. If you would like to get on to a better track while maintaining the approximation idea, replace "0" by "1/4" ;-). The key is to justify the choice of 1/4. $\endgroup$
    – whuber
    Aug 3 at 16:10
  • $\begingroup$ @whuber I can't justify that choice. $\endgroup$ Aug 5 at 5:45
  • $\begingroup$ It's 1/4 because you have already divided everything by 2 in your calculation; if you had not, the offset would be 1/2. You may think of this as a "continuity correction" or, if you look hard at the horizontal location of the yellow central dot in my plot, you will see exactly where $1/2$ must come from. $\endgroup$
    – whuber
    Aug 5 at 13:13

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.