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

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

1. ### Andy WuGuest

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

2. ### Bastian ErdnuessGuest

What are the Aj?

Cheers
Bastian

Bastian Erdnuess, Jun 29, 2010

3. ### Andy WuGuest

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
4. ### Bastian ErdnuessGuest

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
5. ### HenryGuest

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
6. ### HenryGuest

I think that with k=5 and Ni=10 this gives
P(5,14) = 0.8778... and P(5,15) = 0.9113...

Henry, Jul 1, 2010
7. ### Bastian ErdnuessGuest

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
8. ### Andy WuGuest

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
9. ### Bastian ErdnuessGuest

How is PIE stated in your book? How do you have tried to apply it?

Cheers
Bastian

Bastian Erdnuess, Jul 5, 2010
10. ### Andy WuGuest

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. ### Andy WuGuest

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
12. ### Bastian ErdnuessGuest

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
13. ### Andy WuGuest

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
14. ### Bastian ErdnuessGuest

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
15. ### Andy WuGuest

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
16. ### Andy WuGuest

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
17. ### Bastian ErdnuessGuest

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
18. ### Andy WuGuest

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