9
$\begingroup$

Say Bob tosses his $n+1$ fair coins and Alice tosses her $n$ fair coins. Lets assume independent coin tosses. Now after all the $2n+1$ coin tosses one wants to know the probability that Bob has gotten more heads than Alice.

The way I thought of it is this : if Bob gets $0$ heads then there is no way he can get more heads than Alice. Otherwise the number of heads Bob can get which allows him to win is anything in the set $\{1,2,\dots,n+1\}$. And if Bob gets $x$ heads then the number of heads that Alice can get is anything in the set $\{0,1,2,..,x-1\}$. So\begin{align}P(\text{Bob gets more heads than Alice})&= \sum_{x=1}^{n+1} \sum_{y=0}^{x-1} P( \text{Bob gets x heads }\cap \text{Alice gets y heads }) \\[0.2cm]&= \sum_{x=1}^{n+1} \sum_{y=0}^{x-1} \left(C^{n+1}_x \frac{1}{2}^{x} \frac{1}{2}^{n+1-x}\right)\left( C^n_y \frac{1}{2}^y \frac {1}{2}^{n-y}\right)\\[0.2cm]& = \sum_{x=1}^{n+1} \sum_{y=0}^{x-1} \frac{C^{n+1}_x C^n_y}{2^{2n+1}}\end{align}

  • How does one simplify this?

Apparently the answer is $\frac{1}{2}$ by an argument which looks like this, Since Bob tosses one more coin that Alice, it is impossible that they toss both the same number of heads and the same number of tails. So Bob tosses either more heads than Alice or more tails than Alice (but not both). Since the coins are fair, these events are equally likely by symmetry, so both events have probability 1/2.

$\endgroup$
  • $\begingroup$ The probability that Bob throws $x$ heads is binomial,so you're missing coefficients here. $\endgroup$ – Henno Brandsma Feb 19 '16 at 14:27
  • $\begingroup$ I did put in the binomial in the edit. But I have no clue how to simplify this! $\endgroup$ – guest Feb 19 '16 at 14:36
  • $\begingroup$ The "but not both" is key. Note that if Bob flips 3 more coins, he might have more heads and more tails than Alice. Also, the advantage Bob gets from flipping one more coin is precisely counterbalanced by the fact that he loses ties. $\endgroup$ – Kyle Strand Feb 19 '16 at 21:50
18
$\begingroup$

the answer is indeed $\frac 12$ .

As an alternative way to see that: let's pause just before Bob tosses his final (extra) toss. At this point, there are three possible states: either Bob is ahead, Alice is ahead, or they are tied. Let $p$ be the probability that Bob is ahead. By symmetry, $p$ is also the probability that Alice is ahead (so the probability of a tie is $1-2p$). Note that symmetry does clearly apply here since they have thrown the same number of tosses. Bob has exactly two ways to win: either he is ahead before the last toss, or they are tied and Bob gets $H$ on the last throw. Thus the probability that Bob eventually wins is $$p+\frac 12 \times (1-2p)=p+\frac 12 -p =\frac 12$$

$\endgroup$
  • $\begingroup$ In your first case shouldn't it be "Bob is ahead before the last toss and he also wins the last toss"? $\endgroup$ – guest Feb 19 '16 at 14:43
  • 2
    $\begingroup$ @guest No, he is the only one to toss a last time, so if he is ahead before this last toss, he will remain first no matter what. $\endgroup$ – Jimmy R. Feb 19 '16 at 14:44
  • $\begingroup$ @guest What Jimmy R. says is exactly the point. If Bob is ahead before the last throw, he can stop. He can't lose from there. $\endgroup$ – lulu Feb 19 '16 at 14:46
  • 2
    $\begingroup$ @guest If Alice (not sure why I switched it to Ann) is ahead before Bob's last turn, then Bob is doomed. Getting $H$ might tie them up but so what? He can't end up with more Heads. So if Alice is ahead before the final toss, Bob can not win. $\endgroup$ – lulu Feb 19 '16 at 14:51
  • 1
    $\begingroup$ @guest Well, you'll notice that I did not try to compute $p$. Also, the argument I gave (and the symmetry argument sketched in your question) don't work if the coin is weighted...symmetry gives us a happy cancellation. $\endgroup$ – lulu Feb 19 '16 at 15:59
3
$\begingroup$

Get out some red paint. Paint all the heads sides on Bob's coins, and paint all the tails sides of Alice's coins. Bob wins if and only if at least $n + 1$ coins out of $2n + 1$ land red side up. By symmetry, the probability of this happening is $1/2$.

$\endgroup$
0
$\begingroup$

Firstly,$$\sum_{i=0}^n C_i^n = 2^n$$ Seondly,$$\sum_{i=0}^{k-1} C_i^n + \sum_{i=k}^n C_i^n = 2^n$$ Thirdly,$$\sum_{k=1}^{n+1} C_i^{n+1}\sum_{i=0}^{k-1} C_n^i + \sum_{k=1}^{n+1} C_i^{n+1}\sum_{i=k}^n C_n^I$$$$ = \sum_{k=1}^{n+1} C_i^{n+1}\Biggl(\sum_{i=0}^{k-1} C_i^n + \sum_{i=k}^n C_i^n\Biggl) $$$$=2^n\sum_{k=1}^{n+1} C_i^{n+1}$$$$=2^{2n} $$

$\endgroup$
0
$\begingroup$

Bob wins if: 1) Bob and Alice have equal number of heads and Bob tosses his last coin and gets head 2) Bob is ahead after tossing $10$ coins

  • Probability of the first event is $1/2 \cdot 1/2 = 1/4$
  • Probability of the second event is $1/2$
  • Probability that Bob gets more heads is $1/2 + 1/4 = 3/4$
$\endgroup$
-1
$\begingroup$

Let the summation be S. $2S = 2^{2n+1} =>$ use complementary trick of combination i.e. $nCr = nC(n-r)$ => Idea is similar to how Gauss addes 1~100. Add largest and smallest summations and divide by 2.

$\endgroup$

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.