Distribution for count of unique elements

29 Views Asked by At

Consider the selection, with replacement, of $N$ elements uniformly at random from $\{1, 2,\dots, M\}$. From the selected elements, count the number of unique elements.

Does the distribution of this count have any specific name, or if not, what is a succinct way of describing it, perhaps referring to another distribution?

1

There are 1 best solutions below

0
On

I do not know whether it has a name, but I regard it as an occupancy problem, so perhaps you could call it an occupancy distribution

Some statements about it are not too difficult. For example, the probability of $x$ unique selections after $n$ draws with replacement from $m$ equally likely possibilities is

$$\mathbb P(X=x \mid n,m) = \frac{S_2(n,x) \, m!}{m^n \,(m-x)!} = \frac{m \choose x}{m^n}\sum_{j=0}^x (-1)^j {x \choose j}(x-j)^n$$ where $S_2(n,x)$ is a Stirling number of the second kind. You can also say

$$\mathbb E[X\mid n,m] = m\left(1-\left(1-\frac1m\right)^n\right)$$ and $$\text{Var}(X\mid n,m) = m\left(1-\frac1m\right)^n + m^2\left(1-\frac1m\right)\left(1-\frac2m\right)^n - m^2\left(1-\frac1m\right)^{2n}.$$