Author |
Topic: Drawing With Replacement (Read 2060 times) |
|
william wu
wu::riddles Administrator
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
wu::riddles Administrator
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
wu::riddles Administrator
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:
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
|
|
|
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
wu::riddles Administrator
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
wu::riddles Administrator
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)
then add
+ [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.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print