wu :: forums - Print Page


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

        riddles >> easy >> k-sided die rolled n times
        
(Message started by: jarls on May 1^st, 2009, 1:20am)

Title: k-sided die rolled n times
Post by jarls on May 1^st, 2009, 1:20am

is the probability of all sides showing up at least once for a k-sided die which is rolled n times

k!/k^n?

Title: Re: k-sided die rolled n times
Post by towr on May 1^st, 2009, 2:59am

No, because the probability of all sides showing at least once goes to 1 as n increases, whereas k!/k^n goes to 0.

I'll need a few moments to figure out what the correct formula is, because I know I tend to get it wrong; even though by now I should remember it.

Title: Re: k-sided die rolled n times
Post by SMQ on May 1^st, 2009, 5:59am

[hide]One approach is to reverse the probability and use inclusion/exclusion.

P(all sides rolled)
= 1 - P(at least one side not rolled)
= 1 - [_kC₁ (k-1]ⁿ - _kC₂ (k-2]ⁿ + _kC₃ (k-3]ⁿ - ... ] / kⁿ
= Sum over i from 0 to k of (-1)ⁱ _kC_i [(k-i)/k]ⁿ
[/hide]
But that's where I get stuck, as I don't know if there's a way to find a closed-form representation of that sum.

--SMQ

Title: Re: k-sided die rolled n times
Post by towr on May 1^st, 2009, 6:24am

http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
[hide]k!/kⁿ * S(n,k)[/hide]

Title: Re: k-sided die rolled n times
Post by jarls on May 1^st, 2009, 8:27pm

This is a riddle found in the 'relatively hard' section.
Why did you move it to the 'easy' section of the forum?

Title: Re: k-sided die rolled n times
Post by JohanC on May 2^nd, 2009, 1:34am

Hi, Towr,
Jaris is referring to every die face (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#everyDieFace) in Williams hard section.

Hi, Jaris,
I suppose Towr moved it because he had an easy answer to the question as it was formulated in this thread.

Title: Re: k-sided die rolled n times
Post by towr on May 2^nd, 2009, 9:36am

on 05/01/09 at 20:27:20, jarls wrote:

This is a riddle found in the 'relatively hard' section.

Ah sorry, I didn't know that.

Quote:

Why did you move it to the 'easy' section of the forum?

The rating between the riddle site and the forum has diverged a bit over time. I didn't feel it was appropriate for the hard section; although if I had known it was classified as such on the riddle site I'd have left it.
As for why then easy rather than medium, that's because I thought I remembered it having an easier answer. There are a number of variations on the theme of what is equivalent to a "putting N balls in K bins", which vary in how easy they are to solve.
If my memory had served me better I'd have gone with medium in retrospect.