PINs generated until the first duplicate

Question

A generator produces random 4-digit PINs, each uniform over 10000 codes, independently, one after another. It stops the moment it produces a PIN it has already produced. On average, how many PINs does it generate before the first duplicate?

Accepted Answer

Let T count the PINs generated up to and including the first repeat. The chance of no repeat so far follows the birthday-problem product, and the expected wait for a pool of N items is E[T] \approx \sqrt{\frac{\pi N}{2}} = 1.253\sqrt{N}. With N = 10000: E[T] \approx 1.253\sqrt{10000} = 1.253 	imes 100 \approx 125. So about 125 PINs on average, not the tens of thousands you might expect. The square-root law strikes again: because \binom{125}{2} \approx 7750 pairs each risk a 1/10000 collision, a repeat is essentially guaranteed by then. Takeaway. Expected wait to the first repeat is about 1.2…

PINs generated until the first duplicate

Your answer

Discussion

Learn the concepts

Related questions