Follow @ProbabilityPuz

Q: An urn contains 20 uniquely identifiable balls. How many draws with replacement needs to be done before you are \(95\%\) sure that you have seen all of them?

A Book on Statistical Inference

A: A benign looking question, but its closed form solution is fairly complex and quite unlike a typical counting puzzle. First lets learn a useful tool:

$$

S(3,2) = 3

$$

The generic expression for \(S(k,n)\) is given by

$$

S(k,n) = \frac{1}{n!}\sum_{i=0}^{n}(-1)^{i}{{n}\choose{i}}(n-i)^{n}

$$

The present problem is similar to starting with \(k\) balls, dropping then in…

Q: An urn contains 20 uniquely identifiable balls. How many draws with replacement needs to be done before you are \(95\%\) sure that you have seen all of them?

A Book on Statistical Inference

A: A benign looking question, but its closed form solution is fairly complex and quite unlike a typical counting puzzle. First lets learn a useful tool:

*Stirling numbers of the second kind*. It is a complete name and they all go together. It takes in two arguments say \((k,n)\). This is represented as \(S(k,n)\) or also as \({k\brace n }\). It represents the number of subsets of a set of size \(k\) which has a size of \(n\). For example, if a set is given as \({a,b,c}\) then the number of sets of size 2 is \(\{\{a,b\},\{b,c\},\{a,c\}\}\). So we phrase this as$$

S(3,2) = 3

$$

The generic expression for \(S(k,n)\) is given by

$$

S(k,n) = \frac{1}{n!}\sum_{i=0}^{n}(-1)^{i}{{n}\choose{i}}(n-i)^{n}

$$

The present problem is similar to starting with \(k\) balls, dropping then in…