1. ## urn problem

each of two players A and B toss N fair coins. let Pi be the probability that i coins of N coins player A (equivalently player B) tossed show heads.

a) what is the probability the two players have the same number of heads?

b) if the game is modified so that player A tosses N+1 coins ( player B still tosses N ) show that the probability taht player A has more heads than player B is 0.5.

2. Originally Posted by farukcan
each of two players A and B toss N fair coins. let Pi be the probability that i coins of N coins player A (equivalently player B) tossed show heads.

a) what is the probability the two players have the same number of heads?

b) if the game is modified so that player A tosses N+1 coins ( player B still tosses N ) show that the probability taht player A has more heads than player B is 0.5.
a) Suppose the players toss N fair coins. Let X be the number of heads tossed by A and Y be the number of heads tossed by B. Then both X and Y have Binomial(N, 1/2) distributions, so

$P(X = Y) = \sum_{i=0}^N P(X=i) \; P(Y=i) =\sum_{i=0}^N \left( \binom{N}{i} (1/2)^N \right) ^2$
$= \sum_{i=0}^N \binom{N}{i}^2 (1/2)^{2N}$
$=(1/2)^{2N} \sum_{i=0}^N \binom{N}{i}^2$
$=\binom{2N}{N} (1/2)^{2N}$

where we have used a well-known identity, $\sum_{i=0}^N \binom{N}{i}^2 = \binom{2N}{N}$.

b) First, let's continue a) by finding $P(X > Y)$ and $P(X \geq Y)$.
By symmetry, $P(X < Y) = P(Y < X)$. Then
$1 = P(X < Y) + P(X=Y) + P(X >Y) = P(X=Y) + 2 P(X>Y)$
so
$P(X>Y) = (1/2) [1 - P(X=Y)] = (1/2) \left(1 - \binom{2N}{N} (1/2)^{2N} \right)$ .....(1)
and
$P(X \geq Y) = P(X>Y) + P(X=Y) = (1/2) \left( 1 - \binom{2N}{N} (1/2)^{2N} \right) + \binom{2N}{N} (1/2)^{2N}$
$= 1/2 + \binom{2N}{N} (1/2)^{2N+1}$ ....(2)

Now consider the case where A has N+1 coin tosses. As before, let X = the number of heads in the first N tosses, and let's say Z is the total number of heads in all N+1 tosses.

We find $P(Z > Y)$ by conditioning on A's last toss. If A's last toss is a tail, then $Z > Y$ if and only if $X > Y$. If A's last toss is a head, then $Z > Y$ if and only if $X \geq Y$. So

$P(Z > Y) = (1/2) P(X > Y) + (1/2) P(X \geq Y)$.

I think that if you substitute the expressions for $P(X > Y)$ from (1) and $P(X \geq Y)$ from (2) in the above equation and do a little algebra, you will find that $P(Z > Y)$ reduces to 1/2.

3. ## Simplification

Originally Posted by awkward
a) Suppose the players toss N fair coins. Let X be the number of heads tossed by A and Y be the number of heads tossed by B. Then both X and Y have Binomial(N, 1/2) distributions, so

$P(X = Y) = \sum_{i=0}^N P(X=i) \; P(Y=i) =\sum_{i=0}^N \left( \binom{N}{i} (1/2)^N \right) ^2$
$= \sum_{i=0}^N \binom{N}{i}^2 (1/2)^{2N}$
$=(1/2)^{2N} \sum_{i=0}^N \binom{N}{i}^2$
$=\binom{2N}{N} (1/2)^{2N}$

where we have used a well-known identity, $\sum_{i=0}^N \binom{N}{i}^2 = \binom{2N}{N}$.

b) First, let's continue a) by finding $P(X > Y)$ and $P(X \geq Y)$.
By symmetry, $P(X < Y) = P(Y < X)$. Then
$1 = P(X < Y) + P(X=Y) + P(X >Y) = P(X=Y) + 2 P(X>Y)$
so
$P(X>Y) = (1/2) [1 - P(X=Y)] = (1/2) \left(1 - \binom{2N}{N} (1/2)^{2N} \right)$ .....(1)
and
$P(X \geq Y) = P(X>Y) + P(X=Y) = (1/2) \left( 1 - \binom{2N}{N} (1/2)^{2N} \right) + \binom{2N}{N} (1/2)^{2N}$
$= 1/2 + \binom{2N}{N} (1/2)^{2N+1}$ ....(2)

Now consider the case where A has N+1 coin tosses. As before, let X = the number of heads in the first N tosses, and let's say Z is the total number of heads in all N+1 tosses.

We find $P(Z > Y)$ by conditioning on A's last toss. If A's last toss is a tail, then $Z > Y$ if and only if $X > Y$. If A's last toss is a head, then $Z > Y$ if and only if $X \geq Y$. So

$P(Z > Y) = (1/2) P(X > Y) + (1/2) P(X \geq Y)$.

I think that if you substitute the expressions for $P(X > Y)$ from (1) and $P(X \geq Y)$ from (2) in the above equation and do a little algebra, you will find that $P(Z > Y)$ reduces to 1/2.
I now see (and should have seen earlier) that the answer in part b) can be obtained more simply without using the result of a) at all.

As before, we know
$1 = P(X < Y) + P(X=Y) + P(X >Y) = P(X=Y) + 2 P(X>Y)$
so
$P(X>Y) + (1/2) \; P(X=Y) = 1/2$.

And
$P(Z > Y) = (1/2) \; P(X > Y) + (1/2) \; P(X \geq Y)$
$= (1/2) \; P(X >Y) + (1/2) \; [P(X>Y) + P(X=Y)]$
$= P(X > Y) + (1/2) \; P(X=Y)$
$= 1/2$