Expected duplicate-code pairs among a thousand users

Question

Each of 1000 users is assigned a random 6-digit code, uniform over 1000000 codes, independently. On average, how many pairs of users end up with the same code?

Accepted Answer

Use linearity of expectation, adding the per-pair chances. Number of pairs of users: \binom{1000}{2} = \frac{1000 \cdot 999}{2} = 499500 	ext{ pairs}. Each pair shares a code with probability 1/1000000. Therefore E[	ext{duplicate pairs}] = 499500 	imes \frac{1}{1000000} = 0.4995, about half a duplicate pair expected. Because this expected count is roughly 	frac12, the chance of at least one duplicate is about 1 - e^{-0.5} \approx 0.39, so a clash is possible but a bit less likely than not. Takeaway. Expected collisions are \binom{n}{2}/d \approx 0.5 here. When the expected count sits near…

Expected duplicate-code pairs among a thousand users

Your answer

Discussion

Learn the concepts

Related questions