N People Picking

In Pick a Number - Level 2 we calculated the probability of a group of 20 people all picking different numbers between 1 and 100. Here we derive a general algebraic approximation.

Suppose $N$ people pick a number at random between 1 and $T$. Imagine them in a line picking numbers one at a time (without consulting each other). Let the probability that they all pick different numbers be $p(N,T)$. For this event to occur, the second picks a different number from the first, the third picks a different number from the first 2, and so on, so
$$p(N,T) = \left(1-\frac{1}{T}\right)\left(1-\frac{2}{T}\right)....\left(1-\frac{N-1}{T}\right),$$
which may be easily calculated.

Now provided $N$ is reasonably small compared to $T$, then $\left(1-\frac{k}{N}\right) \approx e^{-k/T}$ for $k = 1,2,...,N-1$, and so the probability they all choose different numbers is
$$p(N,T) = e^{-\frac{1}{T}[1+2+...+(N-1)]} = e^{-\frac{1}{T}N(N-1)/2}$$
using the fact that the sum of the first $N-1$ integers is $N(N-1)/2$. For reasonably large $N$ this can be approximated by $e^{-\frac{N^2}{2T}}$. So we can complete the Table:

Chance that no matches occur, when choosing $N$ numbers at random between $1$ and $T$
$T$ $N^2T/2$ = expected number of matches $p(N,T)$ % chance that all different
$N^2/2$ $1$ $e^{-1}$ 37%
$N^2/4$ $2$ $e^{-2}$ 13%
$N^2/6$ $3$ $e^{-3}$ 5%
$N^2/8$ $4$ $e^{-4}$ 2%
$N^2/10$ $5$ $e^{-5}$ 1%
Free tags:
Levels: