How long until you draw the same thing twice?

Question

You repeatedly draw items uniformly at random (with replacement) from a pool of $N$ equally likely items, think of drawing random raffle numbers from $1$ to $N$ . You stop the moment you draw something you have seen before.

Roughly how many draws until the first repeat, and how does it scale with $N$ ? Give the leading behaviour and evaluate for $N = 365$ .

Accepted Answer

Let T be the number of draws until the first repeat. First, the probability of no repeat in the first k draws is the birthday-problem product: P(T k) = \left(1 - \frac{1}{N}\right)\left(1 - \frac{2}{N}\right)\cdots\left(1 - \frac{k-1}{N}\right). Each new draw must dodge all previously seen items. Using 1 - x \approx e^{-x}, the exponents add up to \frac{1 + 2 + \dots + (k-1)}{N} \approx \frac{k^2}{2N}, so P(T k) \approx e^{-k^2/(2N)}. The typical scale where this drops off is k \sim \sqrt{N}, collisions happen after about the square root of the pool size, not half of it. Summing P(T k) gives …

How long until you draw the same thing twice?

Your answer

More Probability questions