Why does this not seem to be random?

Solution 1:

Suppose that $n$ guesses are made. For $i=1$ to $100$, let $X_i=1$ if $i$ is not guessed, and let $X_i=0$ otherwise. If $$Y=X_1+X_2+\cdots +X_{100},$$ then $Y$ is the number of numbers not guessed.

By the linearity of expectation, we have $$E(Y)=E(X_1)+E(X_2)+\cdots+E(X_{100}).$$ The probability that $i$ is not chosen in a particular trial is $\frac{99}{100}$, and therefore the probability it is not chosen $n$ times in a row is $\left(\frac{99}{100}\right)^n$. Thus $$E(Y)=100 \left(\frac{99}{100}\right)^n.$$

In particular, let $n=100$. Note that $\left(1-\frac{1}{100}\right)^{100}\approx \frac{1}{e}$, so the expected number not guessed is approximately $\frac{100}{e}$. Thus the expected number guessed is approximately $63.2$, a result very much in line with your simulation.

In general, if $N$ people choose independently and uniformly from a set of $N$ numbers, then the expected number of distinct numbers not chosen is $$N\left(1-\frac{1}{N}\right)^N.$$ Unless $N$ is very tiny, this is approximately $\frac{N}{e}$, and therefore the expected number of distinct numbers chosen is approximately $N-\frac{N}{e}$. Note that the expected proportion of the numbers chosen is almost independent of $N$.

Solution 2:

In your 1 to 10 example, it's not true in general that the third chooser has an 80% chance on choosing a new number. It's only the case if the second one has guessed a different number than the first one.

Solution 3:

This is an example of the Birthday Paradox / Birthday Problem.

Birthday problem - Wikipedia, the free encyclopedia

I was just looking at my Online Cryptography class video lecture today on this very problem.

Coursera.org: crypto-009

There is an apparent paradox that there is more duplication of numbers than expected when the random numbers are supposedly independent.

But the Birthday Paradox is just one example of when our intuitive statistical sense is dead wrong.