A problem in probability (complex)

[quasar987]

The question is simple, but the solution is a monster (or at least mine is). It says,

A player A posesses n+1 normal coins, and a player B posesses n coins of the same kind. Each player throws all of his coins. Show that the probability of A having thrown tails (T) more often than B is ½.

To do this, condition according to wheter A or B has T more often than the other when both players have thrown n coins. (there are 3 possibilities)

Solution:

I identified the fondamental set as $\Omega$: The result of n throwing of a coin for the two players A and B."

$$\Omega=\left\{((x_1^A,x_2^A,...,x_{n+1}^A),(x_1^B,x_2^B,...,x_{n}^B)): x_i^A,x_i^B\in \left\{T,H\right\}\right\}$$

#$$\Omega=2^{n+1}2^n = 2^{2n+1}$$

I then define the event of interest as E: Player A has thrown more T than H after all players have thrown all their coins. And I partition the fondamental set like so,

$F_1$: Player A has more T than player B after n throws.

$F_2$: Player A has less T than player B after n throws.

$F_3$: Player A and player B both have the same amount of T after n throws.

According to the "total probability formula", then,

$$P(E) = \sum_{i=1}^3P(E\vert F_i)P(F_i) = \sum_{i=1}^3P(E F_i)= \sum_{i=1}^3 \frac{\mbox{card}(EF_i)}{\mbox{card}(\Omega)}$$

So if I find the cardinality of the $EF_i$, I will have won.

Obviously, #$EF_2$=0, for even if B only has one more T than A after the nth thrown and A gets T at his n+1th thrown, A and B are only at equality. So A cannot win in this case, hence the intersection is empty.

To find #$EF_3$, I said, suppose k is the number of T each player has thrown after their nth thrown. There are $\binom{n}{k}$ ways for each player to thrown k T in n thrown. So there are $\binom{n}{k}^2$ ways for the both of them combined. And, for each of these ways to realize the event "each player throwns k T", there is only one way that A can win, and it is by throwing a T at his n+1th thrown. And since k can be any value btw 0 and n, we must sum on k from 0 to n:

$$\mbox{card}(EF_3)=1\cdot\sum_{k=0}^n\binom{n}{k}^2$$

For #$EF_1$, we first note that for each ways to realize $F_1$, there are two ways to realize E, since player A can either thrown a T or a H at his n+1th thrown and still win (hence the factor 2 in the final expression for #$EF_1$). To find the number of ways $F_1$ can be realized, we proceed similarly to above. We say, suppose k is the number of T thrown by A after n thrown. There are $\binom{n}{k}$ ways that this can happen. And for each of them, there are

$$\sum_{j=0}^{k-1}\binom{k-1}{j}$$

ways for B to throw less than k T. So,

$$\mbox{card}(EF_1) = 2\cdot\sum_{k=1}^n\sum_{j=0}^{k-1}\binom{n}{k}\binom{k-1}{j}$$

All this together yields,

$$P(E)=\frac{1}{2^{2n+1}}\left[2\sum_{k=1}^n\sum_{j=0}^{k-1}\binom{n}{k}\binom{k-1}{j}+\sum_{k=0}^n\binom{n}{k}^2 \right]$$

This is not equivalent to ½ as can be seen by computing it for n=1. It give P(E) = 2/8=1/4.

 

[shmoe]

I didn't read all that, it looks excessively complicated.

Just look at the 3 cases from their hint. After n throws each, let's say the probability of the same number of tails is x. The probability they don't have the same number of tails is then 1-x, with each equally likely to be in the lead. Calculate the probability A has more tails after the next flip in terms of x before you try to work out what x actually is.


Alternatively, notice that after all the coins have been flipped, A has either more tails than B or more heads than B but not both (why?).

 

[quasar987]

Ok, well basically, you start the problem in the same way I do (See my partition in F_1, F_2, F_3 in the OP) but you set P(F_3)=x. Then P(F_1 u F_2) = 1-x <==> P(F_1) = 1-x-P(F_2). Also as in my post, the next step is to say

P(E) = P(F_1)P(E|F_1)+P(F_2)P(E|F_2)+P(F_3)P(E|F_3)

But P(E|F_2)=0, P(E|F_3)=1/2 and P(F_1) = 1-x-P(F_2), so

P(E) = (1-x-P(F_2))P(E|F_1)+x/2

Also, P(E|F_1)=1. So,

P(E) = 1-x/2-P(F_2)

I have a feeling this isn't right.

 

[shmoe]

That's right, but notice P(F_1)=P(F_2). Find P(F_2) in terms of x.

 

[quasar987]

Oh, I have seen an error in my OP (two actually, but they are of the same nature):

$$\mbox{card}(EF_3)=\frac{1}{2}\cdot\sum_{k=0}^n\binom{n}{k}^2$$

#EF_3 is only half of F_3 because only for half of the elements of F_3 is $x_{n+1}^A$=T. For the other half, it is equal to H, which does make make A win.

Similarly,
$$\mbox{card}(EF_1) = \mbox{card}(F_1) =\sum_{k=1}^n\sum_{j=0}^{k-1}\binom{n}{k}\binom{k-1}{j}$$

because every element of F_1 make A win.

Unfortunately, this agravates the situation. I need more fuel in the numerator, not less!

 

[quasar987]

P(F_1)+P(F_2)+P(F_3)=1
2P(F_2)+x=1
P(F_2) = (1-x)/2

==>P(E) = 1-x/2-(1-x)/2 = 1/2

beh :P

Still I'm not going to sleep well until I find what's wrong with my solution in the OP...

 

[shmoe]

To find the number of ways $F_1$ can be realized, we proceed similarly to above. We say, suppose k is the number of T thrown by A after n thrown. There are $\binom{n}{k}$ ways that this can happen. And for each of them, there are

$$\sum_{j=0}^{k-1}\binom{k-1}{j}$$

ways for B to throw less than k T.

This appears to be the culprit in your OP. The sum should be:

$$\sum_{j=0}^{k-1}\binom{n}{j}$$

as you are picking j of the n coins to be tails (or heads, I forget which). The rest looks fine, even the part you said was wrong in a later post. The F_i events are after n tosses, so the cardinality of EF_3 is equal to the cardinality of F_3 (likewise you have F_3 losers corresponding to a tie, then a head on the n+1 coin).You didn't mention my 'alternate' approach, I think it's simpler. To make it clearer, I am saying that after all coins have been tossed, the events "A has more heads than B" and "A has more tails than B" form a partition of your sample space, i.e. they are disjoint and their union is the entire space. By symmetry they have the same cardinality.

 

[quasar987]

Thanks a lot shmoe for reading through my monster solution, I did not expect an answer!

I will check your alternate solution tomorrow morning.

 

[quasar987]

P.S. Got any quick idea for a trick one could use to prove that

$$\frac{1}{2}=\frac{1}{2^{2n+1}}\left[2\sum_{k=1}^n\sum_{j=0}^{k-1}\binom{n}{k}\binom{n}{j}+\sum_{k=0}^n\binom{n}{k}^2 \right]$$

??

 

[shmoe]

P.S. Got any quick idea for a trick one could use to prove that

You already have, you've shown the big summation is the probability you are after. In another way, you've shown this probability is 1/2.

A combinatorial argument can be so much nicer than an algebraic one.