Why an Extra Coin Gives Bob a 50% Chance?

[Kakashi]

Homework Statement

Alice and Bob have 2n+1 coins, eahc coin with probability of heads equal to 1/2.Bob tosses n+1 coins, while Alice tosses the remaining n coins. Assuming independent coin tosses, show that the probability after all coins have been tosses, Bob will have gotten more heads than Alice is 1/2.

Relevant Equations

N/A

Whether Bob has more heads depends on both Bob and Alice outcomes. For Bob to win Alice must get fewer heads. If bob gets x heads then Alice must get 0,1,2,..,x-1 heads. The number of sequences with k heads is $$ {n} \choose {k} $$. So for a fixed x the number of Alice sequences with less than x heads is $$ \sum_{k=0}^{x-1} {{n} \choose {k}} $$. The number of bob sequences with exactly x heads is $$ {n+1} \choose {x} $$.

 

[PeroK]

I'm not sure whether you've posted an attempt or just some initial calculations.

You need to be clever. Here's a big hint. If they toss $n$ coins each, then there is a probability $p$ that Alice has more Heads; the same probability $p$ that Bob has more Heads; and, a probability $q$ that they have an equal number of Heads.

Take it from there.

 

[Kakashi]

Wow I dont know why I was overcomplicating things.

The probability that Bob wins= p+q*1/2=p+(1-2p)*1/2=1/2

My counting attempt was that every sequence with x heads for Bob can be paired with every Alice sequence having fewer than x heads. So the total number of pairs for this fixed x is $$ {{n+1} \choose {x}} \sum_{k=0}^{x-1} {{n} \choose {k}} $$
Summing over all x
$$ \sum_{x=1}^{n+1} {{n+1} \choose {x}}*\sum_{k=0}^{x-1} {{n} \choose {k}} $$
Then $$ P(\text{Bob wins})=\frac{\sum_{x=1}^{n+1} {{n+1} \choose {x}}*\sum_{k=0}^{x-1} {{n} \choose {k}}}{2^{2n+1}} $$. Since there are 2^{n+1} Bob sequences and 2^{n} Alice sequences.

 

[FactChecker]

Suppose we look at the situation after both have tossed n coins and say that they have equal probabilities for every number of heads. Then, give Bob one more coin to toss and calculate his probability of getting more heads as 1/2.

NOTE: I missed that post #2 already gave this advice.

 

[haruspex]

Suppose we look at the situation after both have tossed n coins and say that they have equal probabilities for every number of heads. Then, give Bob one more coin to toss and calculate his probability of getting more heads as 1/2.

Yes, very neat, but might not be clear to all. A bit of elaboration might help…
After n tosses each,
- A has more heads than B with probability p
- B has more heads than A with probability p
- equal counts with probability 1-2p
A's extra toss doesn’t change the outcome in the first two cases but gives A an evens chance of winning in the third.

 

[FactChecker]

Yes, very neat, but might not be clear to all. A bit of elaboration might help…
After n tosses each,
- A has more heads than B with probability p
- B has more heads than A with probability p
- equal counts with probability 1-2p
A's extra toss doesn’t change the outcome in the first two cases but gives A an evens chance of winning in the third.

Very good! I didn't clarify it because I couldn't see a clear proof. You did it. Thanks!

 

[PeroK]

Yes, very neat, but might not be clear to all. A bit of elaboration might help…
After n tosses each,
- A has more heads than B with probability p
- B has more heads than A with probability p
- equal counts with probability 1-2p
A's extra toss doesn’t change the outcome in the first two cases but gives A an evens chance of winning in the third.

This solution was already posted in posts #2 and #3.

 

[PeroK]

Very good! I didn't clarify it because I couldn't see a clear proof. You did it. Thanks!

Look at posts #2 and #3.

 

[PeroK]

Suppose we look at the situation after both have tossed n coins and say that they have equal probabilities for every number of heads. Then, give Bob one more coin to toss and calculate his probability of getting more heads as 1/2.

If this argument were valid, then it would work for any probability of Heads. But, it only works in the special case of 1/2. For the general case, where the probability of Heads is $r$ we get:
$$P(Bob) = p + r(1-2p) = r + (1-2r)p$$This only equals $r$ if $r = 1/2$ or $p =0$.

 

[FactChecker]

Look at posts #2 and #3.

Ouch! Sorry, I missed that. Maybe my posts and other's responses should be deleted.