Deterministic formula for average number of unique items picked

Question

I am curious how to formulate a deterministic answer to a problem I have in mind. I have computed it stochastically, but am unsure of how to frame and compute the problem deterministically. My prob & stats classes are a few decades behind me...

Let's say that we have 100 people, and each person is asked to choose a number between 1 and 100 (inclusive). Maybe everyone chooses the same number, but this is unlikely. It is also unlikely that everyone chooses a different unique number. How many of the numbers from 1 to 100 will get picked?

Stochastically, it seems that somewhere between 59 and 67 of the numbers will be picked (10th percentile and 90th percentile respectively) with a median example resulting in 63 of the numbers being chosen.

Is there a deterministic way calculate this? What concepts are relevant? How does the formula vary for a different number of people? And for a different number of numbers to choose?

Update: I'll include the Python script I ran to clarify what I meant by "Stochastically, it seems...":

import random
import statistics

trials = 10000
n = 100
m = 100

lens = []
for j in range(trials):
    k = []
    for x in range(n):
        k.append(random.randint(1,m))
    lens.append(len(list(set(k))))

print(statistics.median(lens), statistics.quantiles(lens, n=10))

Answer 1

For greater generality, let's say that there are $n$ people and $m$ values to choose from. If you are given the chosen values $U_1,...,U_n$ then the deterministic formula for the number of values that were chosen is:

$$K \equiv \sum_{k=1}^m \mathbb{I}(Y_k > 0) \quad \quad \quad \quad \quad Y_k \equiv \sum_{i=1}^n \mathbb{I}(X_i = k).$$

The value $K$ is called the occupancy statistic and it is the number of unique values that were chosen out of the $m$ values (so it has range $1 \leqslant K \leqslant \min(n,m)$). This value is a deterministic function of the underlying values that were chosen. In a statistical context, if we assume that the values are chosen independently and are uniform over the possible choices then we have $U_1,...,U_n \sim \text{U} \{ 1,...,m \}$ and the value $K$ is then a random variable that follows the classical occupancy distribution (see e.g., O'Neill 2020 for details). This distribution has probability mass function:

$$\mathbb{P}(K=k) = \frac{(m)_k \cdot S(n,k)}{m^n} \quad \quad \quad \quad \quad \text{for } 1 \leqslant k \leqslant \min(n,m),$$

where $(m)_k \equiv \prod_{i=0}^{k-1} (m-i)$ are the falling factorials and $S(n,k)$ are the Stirling numbers of the second kind.

You can find a great deal of information about this distribution in the linked paper, including the main moments of this distribution, asymptotic results when the parameters are large, and approximation and computation results. You may also be interested to note that the various probability functions for this distribution (mass function, cumulative distribution function, quantile function, random generation function) are available in R using the functions docc, pocc, qocc and rocc in the occupancy package. These functions can quickly compute the distribution for any computationally feasible value of $n$ and $m$.

Answer 2

Let $X_i \sim U[\{1, \ldots, n\}]$ for $ 1 \leq i \leq n $ meaning that $X_i$ are random variables representing the numbers picked by your $n$ individuals, each of whom picks with uniform probability (i.e. probability $\frac{1}{n}$. Then, you can write down a random variable $Y$ which captures the number of unique values in the realization of the collection $\{X_i\}_{i=1}^n$. That is $$ Y = 1 + \sum_{i=2}^n \mathbb{1}\{X_i \neq X_j, j < i\}.$$

Taking expectations, we have that $$ \begin{align*} \mathbb{E}[Y] &= 1 + \sum_{i=2}^n \mathbb{P}(X_i \neq X_j, j < i) \\ &= 1 + \sum_{i=2}^n\prod_{j=1}^{i-1}\mathbb{P}(X_i \neq X_j) \\ &= 1 + \sum_{i=2}^n \left(1-\frac{1}{n}\right)^{i-1} \\ &= \sum_{i=1}^n\left(1-\frac{1}{n}\right)^{i-1} \\ &= n - n\left(1-\frac{1}{n}\right)^n \end{align*} $$ where we have used independence of the choices that individuals made in the second equality and the geometric partial sum formula to get a closed form in the last equality.

EDIT: I plugged this in python to see if I can verify what you did

 def calc_exp_y(n):
...     x = 0
...     for i in range(n):
...             x = x + (1-1/n)**i
...     return x
... 
>>> calc_exp_y(100)
63.396765872677015

Answer 3

If you assume that $s$ numbers are chosen independently and uniformly from $1$ to $n$, i.e. with replacement, then the expected number of distinct numbers chosen is, using linearity of expectation, $$n\left(1-\left(1-\frac1n\right)^s\right).$$

The probability exactly $u$ distinct numbers are chosen is $$\dfrac{u!S_2(s,u)}{n^s}$$ where $S_2(s,u)$ represents a Stirling number of the second kind. If you call this $p_{n}(u,s)$ then you have the recurrence $$p_{n}(u,s) = \dfrac{n-u+1}{n}p_{n}(u-1,s-1) + \dfrac{u}{n}p_{n}(u,s-1)$$ starting with $p_n(0,0)=1$ and $p_n(u,0)=0$ for $u \not=0$.

In the case $n=s=100$, you get the expected number of distinct values to be just under $63.4$, not far from $100(1-e^{-1})$. As you say, the $10\%$ quantile is at $59$ (the probability of that value or less is about $0.1053$), the median is at $63$ (the probability of that value or less is about $0.5124$) and the $90\%$ quantile is at $67$ (the probability of that value or less is about $0.9068$). The mode is also $63$ (the probability of that value exactly is about $0.1265$).