a problem from Jaynes book Probability Theory: the logic of science

Discussion in 'Probability' started by Andy Wu, Jun 29, 2010.

  1. Andy Wu

    Andy Wu Guest

    exercise 3.2:

    Suppose an urn contains N = SIGMA(Ni) balls, N1 of color 1, N2 of
    color
    2, . . . , Nk of color k. We draw m balls without replacement; what is
    the probability
    that we have at least one of each color? Supposing k = 5, all Ni = 10,
    how many do
    we need to draw in order to have at least a 90% probability for
    getting a full set?

    ----

    I know P(Aj)(where 1<=j<=k) is easy to get, but I can i calculate P(A1|
    A2), P(A3|A1A2), etc. Am I going the wrong direction?

    Thanks,

    BTW, anyone know if there is there an answer list to the book?
     
    Andy Wu, Jun 29, 2010
    #1
    1. Advertisements

  2. What are the Aj?

    Does <http://www.ds.unifi.it/VL/VL_EN/urn/urn4.html> help you?

    Cheers
    Bastian
     
    Bastian Erdnuess, Jun 29, 2010
    #2
    1. Advertisements

  3. Andy Wu

    Andy Wu Guest

    apologies..A1 represents the event of color 1 being drawn for at least
    once, Aj means color j being drawn for at least once.

    Its just my way of trying to solve the problem, you may ignore.
     
    Andy Wu, Jun 30, 2010
    #3
  4. I tried it with

    P(A2|A1) = 1 - P(not A2|A1) = 1 - (39 over n-1)/(49 over n-1) .

    That means, I want to draw n balls. When I know, I've already at least
    one ball of color 1, I just need to draw n-1 random other balls. There
    are just 49 other balls left and 39 of them are not of color 2.

    Analoguous P(A3|A1,A2) would be

    1 - (38 over n-2)/(48 over n-2) .

    But that didn't lead to the right solution. The result's by the formula

    prod[k=0..4] (1 - (40-k over n-k)/(50-k over n-k))

    underestimate the probability for getting a full set of colors by
    drawing n balls slightly.

    I don't know what went wrong here but the way didn't look very trustable
    to me anyway.

    I got the right formula for the probability of getting a full set of
    colors by drawing n balls by the principle of incusion and exclusion (at
    least I think it's the right formula).

    However, maybe there is another way to get answer without knowing that
    probability for every n, too.

    Would be helpful to know what techniques are discribed in the book in
    the chapter where the question occours, to get a guess how it's supposed
    to be solved.

    Cheers
    Bastian
     
    Bastian Erdnuess, Jun 30, 2010
    #4
  5. Andy Wu

    Henry Guest

    This can be done by recursion.

    If P(x,m) is the probability of having x number of colours present in
    sample of first m balls drawn from a population of k colours each with
    equal Ni balls then you have something like

    P(x,m) =( (k - x + 1) * Ni * P(x-1,m-1) + (x*Ni - m + 1) *
    P(x,m-1) ) / (k*Ni - m + 1)

    starting with P(0,0)=1, P(0,m)=0 for m>0, and P(x,0)=0 for x>0
     
    Henry, Jul 1, 2010
    #5
  6. Andy Wu

    Henry Guest

    I think that with k=5 and Ni=10 this gives
    P(5,14) = 0.8778... and P(5,15) = 0.9113...
    so the answer is 15
     
    Henry, Jul 1, 2010
    #6
  7. That should do the job.
    And that are the same probabilities I got.

    With PIE I got the formula

    p(n) = sum[k=0..5] (-1)^k (5 over k) (10(5-k) over n) / (50 over n)

    for the probability to get a full set of colors with n drawn balls.

    Cheers,
    Bastian
     
    Bastian Erdnuess, Jul 1, 2010
    #7
  8. Andy Wu

    Andy Wu Guest

    i dont quite get your formula:

    p(n) = sum[k=0..5] (-1)^k (5 over k) (10(5-k) over n) / (50 over n)

    when i try to apply PIE, i get a much more complex formula involving a
    lot factorial calculation, where appears computer can do the job much
    better.

    but PIE seems to be the right direction to go, thanks for pointing it
    out for me.

     
    Andy Wu, Jul 5, 2010
    #8
  9. How is PIE stated in your book? How do you have tried to apply it?

    Cheers
    Bastian
     
    Bastian Erdnuess, Jul 5, 2010
    #9
  10. Andy Wu

    Andy Wu Guest

    Supposing k = 5, all Ni = 10

    Ai represents after 5 draws color i is not selected. Then the
    probability of getting a full set of colors in 5 draws is:

    1 - P(A1 + A2 + A3 + A4 + A5)

    applying PIE
    P(A1 + A2 + A3 + A4 + A5) = (5 choose 1)P(A1) - (5 choose 2)P(A1A2) +
    (5 choose 3)P(A1A2A3) - (5 choose 4)P(A1A2A3A4)

    where P(A1)=(40!45!)/(50!35!), P(A1A2)=P(A1)(30!45!)/(50!25!),
    P(A1A2A3)=P(A1A2)(20!45!)/(50!/15!), P(A1A2A3A4)=P(A1A2A3)(10!45!)/
    (50!/5!)

    so a computer program is what i came up to this problem...just dont
    see how this can be further simplified. And can you explain more about
    your solution? I'm not very confident to mine...:)

    Thanks,
     
    Andy Wu, Jul 6, 2010
    #10
  11. Andy Wu

    Andy Wu Guest

    Supposing k = 5, all Ni = 10

    Ai represents after 5 draws color i is not selected. Then the
    probability of getting a full set of colors in 5 draws is:

    1 - P(A1 + A2 + A3 + A4 + A5)

    applying PIE
    P(A1 + A2 + A3 + A4 + A5) = (5 choose 1)P(A1) - (5 choose 2)P(A1A2) +
    (5 choose 3)P(A1A2A3) - (5 choose 4)P(A1A2A3A4)

    where P(A1)=(40!45!)/(50!35!), P(A1A2)=P(A1)(30!45!)/(50!25!),
    P(A1A2A3)=P(A1A2)(20!45!)/(50!/15!), P(A1A2A3A4)=P(A1A2A3)(10!45!)/
    (50!/5!)

    so a computer program is what i came up to this problem...just dont
    see how this can be further simplified. And can you explain more about
    your solution? I'm not very confident to mine...:)

    Thanks,
     
    Andy Wu, Jul 6, 2010
    #11
  12. That's P(A1) = (40 over 5)/(50 over 5).
    That's P(A1A2) = P(A1) (30 over 5)/(50 over 5).

    But how does the P(A1) comes in here?

    Cheers,
    Bastian
     
    Bastian Erdnuess, Jul 6, 2010
    #12
  13. Andy Wu

    Andy Wu Guest

    A1 represents in color 1 does not appear in all 5 draws.

    P(A1)=(40/50)(39/49)(38/48)(37/47)(36/46)

    Isnt it?
     
    Andy Wu, Jul 7, 2010
    #13
  14. Yeah, it is. And you can check that that's just another way to write

    (40 over 5)/(50 over 5) .

    But how do you get P(A1A2)?

    Cheers
    Bastian
     
    Bastian Erdnuess, Jul 7, 2010
    #14
  15. Andy Wu

    Andy Wu Guest

    A1 represents in color 1 does not appear in all 5 draws.

    P(A1)=(40/50)(39/49)(38/48)(37/47)(36/46)

    Isnt it?
     
    Andy Wu, Jul 7, 2010
    #15
  16. Andy Wu

    Andy Wu Guest

    Arh, i didnt know your "(5 over k)" is same as my "(5 choose 1)", our
    formula is similar but not the same.

    Looks like in your formula, P(A1A2)=(30 over n)/(50 over n); while in
    my formula P(A1A2)=P(A1)(30 over n)/(50 over n).
     
    Andy Wu, Jul 7, 2010
    #16
  17. That's why I ask how you get the P(A1) in there. It's not supposed to
    be.

    Cheers
    Bastian
     
    Bastian Erdnuess, Jul 7, 2010
    #17
  18. Andy Wu

    Andy Wu Guest

    Yes, you are correct. I got the wrong formula of P(A1|A2)=(30 over n)/
    (50 over n), it shouldnt be.

    Thanks man.
     
    Andy Wu, Jul 8, 2010
    #18
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.