1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A problem in probability (complex)
  1. Probability problem (Replies: 3)

  2. Probability Problem (Replies: 7)

  3. Probability problem (Replies: 13)

Loading...