4
$\begingroup$

I have a stack of $n$ distinct cards. I randomly draw $N$ cards from the stack with replacement. Assume that $N \ge n$.

What is the probability that I observe all cards at least once?

I got this far:

The probability that the multiplicities of the states in the sample are $m_1, \dots, m_n$ is:

$$\frac{1}{n^{N}}\frac{N!}{m_1! \dots m_n!}$$

Therefore, the probability we want is found by evaluating the sum:

$$\frac{1}{n^{N}}\sum_{\begin{subarray}{c} m_{1}+\dots+m_{n}=N\\ m_{k}\ge1 \end{subarray}}\frac{N!}{m_{1}!\dots m_{n}!}$$

However, I'm stuck since I'm not sure how to evaluate this. I tried a change of variables $r_k = m_k - 1$, but this messes the factorials in the denominator.

Update: I found this paper, which contains a solution:

Kullback, Solomon. 1937. “On Certain Distributions Derived From the Multinomial Distribution.” The Annals of Mathematical Statistics 8(3): 127–44. http://projecteuclid.org/euclid.aoms/1177732409.

$\endgroup$
9
  • $\begingroup$ Is it a homework? $\endgroup$ – Tim Dec 12 '16 at 11:14
  • $\begingroup$ @Tim No, it isin't. $\endgroup$ – becko Dec 12 '16 at 11:16
  • $\begingroup$ you may want to take a look at the multinomial distribution. $\endgroup$ – EliKa Dec 12 '16 at 11:24
  • $\begingroup$ @EliKa See edit. $\endgroup$ – becko Dec 12 '16 at 11:29
  • 1
    $\begingroup$ @Paparazzi Because I am drawing with replacement. $\endgroup$ – becko Jan 4 '17 at 13:13