# If I generate 100 random integer, each sampled from 1 to 100 with equal probability, how many unique numbers do I expect to get?

If I generate 100 random integer, each sampled from 1 to 100 with equal probability, how many unique numbers do I expect to get?

I simulated on Python, run 1E6 experiments and it seems that they result is around 63.39.

I just want an analytical solution to this problem. Thanks

• Looks like $100(1-e^{-1})$ to me. Commented Mar 1, 2018 at 3:30
• @DilipSarwate how did you get this? My answer matches with the simulation (which is posted below)...
– TYZ
Commented Mar 1, 2018 at 3:49
• @YilunZhang it was guess :) Commented Mar 1, 2018 at 3:56
• @YilunZhang As you found, the probability is $$1-\left(\frac{99}{100}\right)^{100} = 1 - \left(1-\frac{1}{100}\right)^{100} \approx 1 - \lim_{n\to\infty}\left(1-\frac{1}{n}\right)^{n} = 1-e^{-1}$$ Commented Mar 1, 2018 at 4:49
• @DilipSarwate Aha, good point, now it makes sense to me. :)
– TYZ
Commented Mar 1, 2018 at 4:50

Let $S$ be the set of samples you get from your process. Let $I_i = \begin{cases}1 & i \in S \\ 0 & o.w. \end{cases}$. Then, $S = \{I_1,\cdots,I_{100}\}$, and your question "on average, how many unique integers are selected" can be translated to $$\mathbb{E}\left[\sum_{i=1}^{100} I_i\right] = \sum_{i=1}^{100} P(I_i = 1)$$ Since the sample is equal probability, we can easily get: $$P(I_i = 1) = 1 - P(I_i = 0) = 1 - \left(\frac{99}{100}\right)^{100} \approx 0.633967$$ and this holds for all $i=1,\cdots,100$. Thus, the answer is $100\times 0.633967 \approx 63.3967$, which matches with your simulation.