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

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?

 

What are the Aj?

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

Cheers
Bastian

 

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.

 

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

 

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

 

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

 

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

 

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.

 

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

Cheers
Bastian

 

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,

 

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,

 

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

 

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?

 

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

 

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?

 

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).

 

That's why I ask how you get the P(A1) in there. It's not supposed to
be.

Cheers
Bastian

 

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

Thanks man.