3
$\begingroup$

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

$\endgroup$
7
  • 2
    $\begingroup$ Looks like $100(1-e^{-1})$ to me. $\endgroup$ Commented Mar 1, 2018 at 3:30
  • $\begingroup$ @DilipSarwate how did you get this? My answer matches with the simulation (which is posted below)... $\endgroup$
    – TYZ
    Commented Mar 1, 2018 at 3:49
  • $\begingroup$ @YilunZhang it was guess :) $\endgroup$
    – Aksakal
    Commented Mar 1, 2018 at 3:56
  • $\begingroup$ @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}$$ $\endgroup$ Commented Mar 1, 2018 at 4:49
  • $\begingroup$ @DilipSarwate Aha, good point, now it makes sense to me. :) $\endgroup$
    – TYZ
    Commented Mar 1, 2018 at 4:50

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I think you need to put an expectation operator around that first sum. $\endgroup$
    – Ben
    Commented Mar 1, 2018 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.