1

I generated 1.000.000 random integers in the range from 0 to 1.000.000 (using rand() in c++ and random.randrange() in python) and both code got approximately 632000 unique numbers.

I noticed $1 - e^{-1} = 0.6321$.

Does $e$ involve in this? If so, why?

Unique number | Total numbers in array
632413           1000000

632088           1000000


631594           1000000


6305             10000


6319             10000
JMoravitz
  • 79,518
Era
  • 43
  • I don't think so. The probability of an event with $p = 1/n$ happen at least 1 time in n trials is (similar to the linked thread): $1-(1-1/n)^n$

    But i failed to see the correlation between the number of unique numbers in a randomly generated array and the probability mentioned above.

    Can you show me the similarity?

     – Era Aug 05 '21 at 12:13
  • 1
    I'll post something explaining the connection. – lulu Aug 05 '21 at 12:14
  • Additional reading: Probability of repeatedly selecting object in group where I additionally show that the number of numbers selected $k$ times was $\frac{1}{e\cdot k!}$ (note that $0! = 1$), so the numbers selected zero times occurred with probability $\frac{1}{e}$, once with probability $\frac{1}{e}$, twice with $\frac{1}{2e}$, three times with $\frac{1}{6e}$ etc... – JMoravitz Aug 05 '21 at 12:14
  • 2
    To emphasize, the behavior you witnessed was not a result of python or programming limitations, but is indeed the expected theoretical result. – JMoravitz Aug 05 '21 at 12:15
  • Related: https://math.stackexchange.com/questions/1087950/calculating-probability-of-getting-m-unique-numbers-when-choosing-n-times-fr –  Aug 05 '21 at 12:46

1 Answers1

1

Let $N$ be a large number (in your case, $N=10^6$).

By linearity of expectation, we define an indicator for each number from $1$ to $N$ according to whether or not it appears.

The probability that a number appears is $$1-\left(\frac {N-1}{N}\right)^{N}$$

Hence your expectation is $$N\left(1-\left(\frac {N-1}{N}\right)^{N}\right)$$

Now, $$\lim_{N\to \infty} \left(\frac {N-1}N\right)^N=1-e^{-1}$$

So your expectation is approximately $$N\times (1-e^{-1})$$ as desired.

lulu
  • 70,402
  • You mean $\frac1e$ in both places you have $e$. – saulspatz Aug 05 '21 at 12:28
  • @saulspatz Right, thanks. – lulu Aug 05 '21 at 12:32
  • @amWhy I was the one who first voted to close this as a duplicate (indeed, I was the one who answered the duplicate question). The OP wasn't capable of seeing how the duplicate answered the question, so I agreed to post the specific calculation. – lulu Aug 06 '21 at 20:49
  • Thanks for the explanation. I understand, @lulu. – amWhy Aug 06 '21 at 21:42