TITLE: Approximation for expected number of distinct values
QUESTION [0 upvotes]: 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?

REPLY [4 votes]: 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$.
{"set_name": "stack_exchange", "score": 0, "question_id": 444443}