Tokens minted until the first collision

Question

A generator mints random tokens, each uniform over 1000000 values, independently, until it produces a value it has already produced. On average, how many tokens are minted before the first collision?

Accepted Answer

Let T be the number of tokens up to and including the first collision. The chance of no collision so far follows the birthday-problem product, and the expected wait for a pool of N values is E[T] \approx \sqrt{\frac{\pi N}{2}} = 1.253\sqrt{N}. With N = 1000000: E[T] \approx 1.253\sqrt{1000000} = 1.253 	imes 1000 \approx 1253. So only about 1250 tokens on average, even though there are a million possible values. This is the heart of the "birthday attack": to force a collision in a space of size N, an attacker needs roughly \sqrt{N} tries, not N. A million-value space offers only about a thous…

Tokens minted until the first collision

Your answer

Discussion

Learn the concepts

Related questions