Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: A problem in probability (complex)

  1. Sep 30, 2006 #1

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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 [itex]\Omega[/itex]: The result of n throwing of a coin for the two players A and B."

    [tex]\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\}[/tex]

    #[tex]\Omega=2^{n+1}2^n = 2^{2n+1}[/tex]

    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,

    [itex]F_1[/itex]: Player A has more T than player B after n throws.

    [itex]F_2[/itex]: Player A has less T than player B after n throws.

    [itex]F_3[/itex]: Player A and player B both have the same amount of T after n throws.

    According to the "total probability formula", then,

    [tex]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)}[/tex]

    So if I find the cardinality of the [itex]EF_i[/itex], I will have won.

    Obviously, #[itex]EF_2[/itex]=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 #[itex]EF_3[/itex], I said, suppose k is the number of T each player has thrown after their nth thrown. There are [itex]\binom{n}{k}[/itex] ways for each player to thrown k T in n thrown. So there are [itex]\binom{n}{k}^2[/itex] 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:

    [tex]\mbox{card}(EF_3)=1\cdot\sum_{k=0}^n\binom{n}{k}^2[/tex]

    For #[itex]EF_1[/itex], we first note that for each ways to realize [itex]F_1[/itex], there are two ways to realise 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 #[itex]EF_1[/itex]). To find the number of ways [itex]F_1[/itex] 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 [itex]\binom{n}{k}[/itex] ways that this can happen. And for each of them, there are

    [tex]\sum_{j=0}^{k-1}\binom{k-1}{j}[/tex]

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

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

    All this together yields,

    [tex]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][/tex]

    This is not equivalent to ½ as can be seen by computing it for n=1. It give P(E) = 2/8=1/4.
     
    Last edited: Sep 30, 2006
  2. jcsd
  3. Sep 30, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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 probabilty 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?).
     
  4. Sep 30, 2006 #3

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  5. Sep 30, 2006 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    That's right, but notice P(F_1)=P(F_2). Find P(F_2) in terms of x.
     
  6. Sep 30, 2006 #5

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

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

    [tex]\mbox{card}(EF_3)=\frac{1}{2}\cdot\sum_{k=0}^n\binom{n}{k}^2 [/tex]

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

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

    because every element of F_1 make A win.

    Unfortunately, this agravates the situation. I need more fuel in the numerator, not less!
     
  7. Sep 30, 2006 #6

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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 gonna sleep well until I find what's wrong with my solution in the OP...
     
  8. Sep 30, 2006 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

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

    [tex]\sum_{j=0}^{k-1}\binom{n}{j}[/tex]

    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.
     
  9. Oct 1, 2006 #8

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

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

    I will check your alternate solution tomorrow morning.
     
  10. Oct 1, 2006 #9

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

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

    [tex]\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][/tex]

    ?? :biggrin: :biggrin: :biggrin:
     
  11. Oct 1, 2006 #10

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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. :wink:
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook