wu :: forums « wu :: forums - Drawing With Replacement » Welcome, Guest. Please Login or Register. Feb 22nd, 2024, 4:07pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: william wu, towr, Grimbal, Icarus, SMQ, ThudnBlunder, Eigenray)    Drawing With Replacement « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Drawing With Replacement  (Read 2042 times)
william wu

Gender:
Posts: 1291
 Drawing With Replacement   « on: Oct 13th, 2003, 1:34am » Quote Modify

You make n draws with replacement from a uniformly distributed set of k objects, where n,k[in][bbz]+, n[ge]k. What is the probability that after n draws, every object will have been drawn at least once?
 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Dudidu
Full Member

Posts: 227
 Re: Drawing With Replacement   « Reply #1 on: Oct 13th, 2003, 2:07am » Quote Modify

Could it be...

Pr(every element is chosen at least once) =
1 - Pr(There is at least one element that ain't chosen) =
1 -  [sum]i=1[smiley=supk.gif](-1)i(ki)((k-i)[smiley=diagup.gif]k) n

 « Last Edit: Oct 13th, 2003, 2:12am by Dudidu » IP Logged
william wu

Gender:
Posts: 1291
 Re: Drawing With Replacement   « Reply #2 on: Oct 13th, 2003, 2:09am » Quote Modify

OK I figured out what I was doing wrong (I was baffled forever) and got an empirically-verified solution, so the problem isn't necessarily as interesting as I thought it was. But I'll leave it here in case someone alreaady looked at it and was intending to reply to it.
 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
william wu

Gender:
Posts: 1291
 Re: Drawing With Replacement   « Reply #3 on: Oct 13th, 2003, 2:13am » Quote Modify

on Oct 13th, 2003, 2:07am, Dudidu wrote:
 Could it be...

Hehe speak of the devil (dudidu posted right before i did). It's very close:

Take out the (-1)^i ... not sure why that was there ...
 « Last Edit: Oct 13th, 2003, 2:16am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
william wu

Gender:
Posts: 1291
 Re: Drawing With Replacement   « Reply #4 on: Oct 13th, 2003, 2:22am » Quote Modify

Another error:

Change the upper limit of the summation from k to k-1
 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Dudidu
Full Member

Posts: 227
 Re: Drawing With Replacement   « Reply #5 on: Oct 13th, 2003, 2:26am » Quote Modify

For my opinion the
(-1)^i  ought to be there since the (ki)((k-i)\k)n describes the probability that at least i elements are not chosen, but it doesn't say that at least (k-i) elements are chosen (thus, the (-1)^i acts as a "balancer" for duplicate cases).

Do you agree with me
 IP Logged
Dudidu
Full Member

Posts: 227
 Re: Drawing With Replacement   « Reply #6 on: Oct 13th, 2003, 2:31am » Quote Modify

Changing the upper limit of the summation from k to k-1 is not obligatory since in the [sum] the k-th element equals 0 (so it doesn't matter).
 IP Logged
william wu

Gender:
Posts: 1291
 Re: Drawing With Replacement   « Reply #7 on: Oct 13th, 2003, 3:27am » Quote Modify

on Oct 13th, 2003, 2:26am, Dudidu wrote:
 For my opinion the   (-1)^i  ought to be there since the (ki)((k-i)\k)n describes the probability that at least i elements are not chosen, but it doesn't say that at least (k-i) elements are chosen (thus, the (-1)^i acts as a "balancer" for duplicate cases).   Do you agree with me

Darn. You're right! I'm overcounting again. The empirical results were close but apparently I didn't test enough ... by playing with different possible values for n and k, I eventually discovered that my formula yields ridiculous numbers.

(-1)n (-1)i is not entirely the correct expression for the balancer; plugging in n=10, k=4 using your formula produces 1.2194 > 1, which cannot be a probability.

We may have to use the Inclusion Exclusion principle, which I hoped to not have to use by by considering the complement of the desired event, but alas here we are again ...

Might want to check out
http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html

i must go to bed now

note: edited a typo

addition: on Oct 13th, 2003, 2:31am, Dudidu wrote:
 Changing the upper limit of the summation from k to k-1 is not obligatory since in the [sum] the k-th element equals 0 (so it doesn't matter).

true, the probability that all colors are missing is zero
 « Last Edit: Oct 13th, 2003, 3:54am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Dudidu
Full Member

Posts: 227
 Re: Drawing With Replacement   « Reply #8 on: Oct 13th, 2003, 3:41am » Quote Modify

We use the Inclusion Exclusion principle but...
you might have replaced the (-1)i with (-1)n (being tired  ? )

Hope this helps.
 IP Logged
william wu

Gender:
Posts: 1291
 Re: Drawing With Replacement   « Reply #9 on: Oct 13th, 2003, 3:52am » Quote Modify

yea i meant to say (-1)i

i didn't type it wrongly when computing your formula though -- it returns 1.9641 > 1 when n=40 and k=20

let Ei be the event that at least i colors are missing. then we want

Pr(E1 U ... U Ek)

so to compute this, the inclusion exclusion principle tells us to first add up all those expressions:

[sum]i=1 to k Pr(Ei)

then we subtract

- [sum]1<=i,j<=k Pr(Ei [cap] Ej) = [sum]1<=i,j<=k Pr(Ex) where x = max(i,j)

+ [sum]1<=i,j,p<=k Pr(Ei [cap] Ej [cap] Ep) = [sum]1<=i,j,p<=k Pr(Ex) where x = max(i,j,p)

etc ...

i'm probably speaking gibberish, i really should go to bed now
 « Last Edit: Oct 13th, 2003, 4:02am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Dudidu
Full Member

Posts: 227
 Re: Drawing With Replacement   « Reply #10 on: Oct 13th, 2003, 5:38am » Quote Modify

It's seems that I made few mistakes, I hope that the following equation deals with all the bugs (Inclusion Exclusion principle):
1 - ([sum]i=1k (-1)k+1 (ik) (k-i)n) / kn.

Does it work now ?

p.s - If explanation is needed, just indicate it.
 IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: Drawing With Replacement   « Reply #11 on: Oct 13th, 2003, 6:26am » Quote Modify

William, the solution can be expressed in terms of Stirling Numbers of the Second Kind.

http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
 « Last Edit: Oct 13th, 2003, 6:27am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »