N People Picking
As of the 23rd May 2022 this website is archived and will receive no further updates.
understandinguncertainty.org was produced by the Winton programme for the public understanding of risk based in the Statistical Laboratory in the University of Cambridge. The aim was to help improve the way that uncertainty and risk are discussed in society, and show how probability and statistics can be both useful and entertaining.
Many of the animations were produced using Flash and will no longer work.
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:
| $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% |
