Approximation for expected number of distinct values

Question

When I draw n evenly distributed integer random numbers from an range of [0,m], what is the expected number of distinct values?

I am aware of this answer, but is look expensive to compute. Is there an approximation (sort of like going from binominal to poisson)?

Is there a way to generalize it to (at least some) non even distributions?

Answer 1

Let $X_i = \begin{cases} 1, &\text{if at least one i is drawn, for i = 0, 1, ..., m}\\ 0, &\text{otherwise} \end{cases} $

Then $\Pr(X_i = 1) = 1 -\left( \frac{m}{m+1} \right)^n$

so the expected number of distinct values drawn is

$E(\sum X_i) = \sum E(X_i) = (m+1)\; [1 -\left( \frac{m}{m+1} \right)^n]$

Here we have used the theorem that E(X+Y) = E(X) + E(Y). It's important to realize that this theorem holds even if X and Y are not independent. That's good for us here, because the $X_i$'s are not independent.

If value i is drawn with probability $p_i$, then $\Pr(X_i = 1) = 1 - (1-p_i)^n$.