wu :: forums
« wu :: forums - Drawing With Replacement »

Welcome, Guest. Please Login or Register.
Feb 22nd, 2024, 4:07pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: william wu, towr, Grimbal, Icarus, SMQ, ThudnBlunder, Eigenray)
   Drawing With Replacement
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Drawing With Replacement  (Read 2042 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Drawing With Replacement  
« on: Oct 13th, 2003, 1:34am »
Quote Quote Modify 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 Quote Modify 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
  Huh
« Last Edit: Oct 13th, 2003, 2:12am by Dudidu » IP Logged
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Drawing With Replacement  
« Reply #2 on: Oct 13th, 2003, 2:09am »
Quote Quote Modify 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
*****





   
WWW

Gender: male
Posts: 1291
Re: Drawing With Replacement  
« Reply #3 on: Oct 13th, 2003, 2:13am »
Quote Quote Modify 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
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Drawing With Replacement  
« Reply #4 on: Oct 13th, 2003, 2:22am »
Quote Quote Modify 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 Quote Modify 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 Huh
IP Logged
Dudidu
Full Member
***





   


Posts: 227
Re: Drawing With Replacement  
« Reply #6 on: Oct 13th, 2003, 2:31am »
Quote Quote Modify 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
*****





   
WWW

Gender: male
Posts: 1291
Re: Drawing With Replacement  
« Reply #7 on: Oct 13th, 2003, 3:27am »
Quote Quote Modify 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 Huh    

 
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 Quote Modify Modify

We use the Inclusion Exclusion principle but...  
you might have replaced the (-1)i with (-1)n (being tired  ? Wink)
 
Hope this helps.
IP Logged
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Drawing With Replacement  
« Reply #9 on: Oct 13th, 2003, 3:52am »
Quote Quote Modify 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 Quote Modify 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 ?  Smiley  
 
p.s - If explanation is needed, just indicate it.
IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Drawing With Replacement  
« Reply #11 on: Oct 13th, 2003, 6:26am »
Quote Quote Modify 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board