3
$\begingroup$

If you take $N$ independent uniform random selections from a discrete space with $M$ possibilities (with replacements), then what proportion of the possibilities will have been selected?


Formally, this problem can be stated as follows. Let $X_1, ..., X_N \sim \text{IID U} \{ 1, ..., M \}$ and let $\mathcal{S} \subseteq \{ 1, ..., M \}$ be the subset of categories having at least one value in this sample. Find the expected value $\mathbb{E}(|S|/M)$ which is the expected proportion of categories hit by the random variables.

$\endgroup$
0
$\begingroup$

As pointed out in the answer by @Ben, this is not the coupon collector problem, but an associated problem, the classical occupancy problem. See for instance an interesting blog post or https://math.stackexchange.com/questions/631487/asymptotics-of-the-classical-occupancy-problem

Old Answer below:  

What you have is a version of the famous coupon collectors problem, see https://en.wikipedia.org/wiki/Coupon_collector%27s_problem and on this site https://stats.stackexchange.com/search?q=coupon+collector. You will find answer to your question there. There is also a lot of information on the web.

$\endgroup$
  • $\begingroup$ Although this sounds like the Coupon Collector problem, and clearly is related to it, it is not the same. The CC problem asks for the distribution of the random variable $N$ given by the number of selections required to fill the space completely. $\endgroup$ – whuber Dec 27 '18 at 13:56
2
$\begingroup$

Contrary to the answer by kjetil, this is actually the "classical occupancy problem" (which is related to the coupon collector's problem, but is not quite the same problem). The random variable $|S|$ has a classical occupancy distribution with mass function given by:

$$\mathbb{P} \big( |S| = s \big| n, m \big) = \frac{(m)_s \cdot S(n,s)}{m^n} \quad \quad \quad \text{for all } 1 \leqslant s \leqslant \min (n,m),$$

where $(m)_s = \prod_{i=0}^{s-1} (m-i)$ are the falling factorials and $S(n,s)$ are the Stirling numbers of the second kind. The properties of this distribution are well-known (see e.g., Johnson and Kotz 1977). The expected value of this random variable is:

$$\mathbb{E} \big( |S| \big) = m \Big( 1 - \frac{1}{m} \Big)^n.$$

Dividing through by the number of categories gives $\mathbb{E} ( |S|/m ) = ( 1 - \tfrac{1}{m} )^n \rightarrow \exp(-n/m)$, where the latter asymptotic form holds as $n \rightarrow \infty$.


Johnson, N.L. and Kotz, S. (1977) Urn Models and their Applications. John Wiley and Sons: New York.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.