wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Drawing With Replacement
        
(Message started by: william wu on Oct 13^th, 2003, 1:34am)

Title: Drawing With Replacement
Post by william wu on Oct 13^th, 2003, 1:34am

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?

Title: Re: Drawing With Replacement
Post by Dudidu on Oct 13^th, 2003, 2:07am

Could it be...
[hide]
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)ⁱ(^k_i)((k-i)[smiley=diagup.gif]k) ⁿ [/hide] ???

Title: Re: Drawing With Replacement
Post by william wu on Oct 13^th, 2003, 2:09am

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.

Title: Re: Drawing With Replacement
Post by william wu on Oct 13^th, 2003, 2:13am

on 10/13/03 at 02:07:45, Dudidu wrote:

Could it be...

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

[hide]
Take out the (-1)^i ... not sure why that was there ...
[/hide]

Title: Re: Drawing With Replacement
Post by william wu on Oct 13^th, 2003, 2:22am

Another error:

[hide]
Change the upper limit of the summation from k to k-1
[/hide]

Title: Re: Drawing With Replacement
Post by Dudidu on Oct 13^th, 2003, 2:26am

For my opinion the
[hide] (-1)^i ought to be there since the (^k_i)((k-i)\k)ⁿ 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).[/hide]

Do you agree with me ???

Title: Re: Drawing With Replacement
Post by Dudidu on Oct 13^th, 2003, 2:31am

Changing [hide] 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).[/hide]

Title: Re: Drawing With Replacement
Post by william wu on Oct 13^th, 2003, 3:27am

on 10/13/03 at 02:26:15, Dudidu wrote:

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)ⁿ~~ (-1)ⁱ 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 10/13/03 at 02:31:37, Dudidu wrote:

Changing [hide] 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).[/hide]

true, the probability that all colors are missing is zero

Title: Re: Drawing With Replacement
Post by Dudidu on Oct 13^th, 2003, 3:41am

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

Hope this helps.

Title: Re: Drawing With Replacement
Post by william wu on Oct 13^th, 2003, 3:52am

yea i meant to say (-1)ⁱ

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

http://www.ocf.berkeley.edu/~wwu/images/riddles/inclusion-exclusion.gif

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

Title: Re: Drawing With Replacement
Post by Dudidu on Oct 13^th, 2003, 5:38am

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=1^k (-1)^k+1 (_i^k) (k-i)ⁿ) / kⁿ.

Does it work now ? :)

p.s - If explanation is needed, just indicate it.

Title: Re: Drawing With Replacement
Post by THUDandBLUNDER on Oct 13^th, 2003, 6:26am

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

http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html