Average number of distinct values

Question

Let $q$ such that $q < n$. I pick at random $n$ values in $\mathbb{F}_q$.

What is the average number of distinct values ?

Thank you

Answer 1

Each value in $\mathbb F_q$ is not drawn with probability $(1-q^{-1})^n$ hence the average number of distinct values in a sample of size $n$ is $q\cdot(1-(1-q^{-1})^n)$.

For example, when $q\to\infty$, the average number of distinct values in a sample of size $c\cdot q$ is approximately $(1-\mathrm e^{-c})\cdot q$.

Answer 2

Imagine that the picking is done one at a time, with replacement. Define random variable $X_i$ by $X_i=1$ if the object chosen at stage $i$ is different from all the objects chosen at stages $\lt i$. Let $X_i=0$ otherwise.

Then the number of distinct objects is $\sum_1^n X_i$. So our mean is $\sum E(X_i)$.

For $E(X_i)$, the probability that $X_i=1$, this does not depend on the object picked at stage $i$. Let it be $1$. We want the probability that none of the objects chosen in stages $1$ to $i-1$ is equal to $1$. The probability of this is $\left(1-\frac{1}{q}\right)^{i-1}$. Now add up the geometric series, $i=1$ to $n$.