Do two databases share an ID?

Question

Database A holds 1000 records, each with a random 6-digit ID (uniform over 1000000 values). Database B independently holds another 1000 records with random IDs from the same range. What is the probability that at least one ID appears in both databases?

Accepted Answer

This is a cross collision: we look for an A record and a B record that share an ID, ignoring any duplicates within a single database. Count the cross pairs: each of A's 1000 records against each of B's 1000 records, 1000 	imes 1000 = 1000000 	ext{ cross pairs}. Each cross pair matches with probability 1/1000000. The chance of no shared ID is approximately P(	ext{no shared ID}) \approx e^{-1000000/1000000} = e^{-1} \approx 0.368. Therefore P(	ext{at least one shared ID}) \approx 1 - 0.368 \approx 0.632, about 63\%. The clean number 1 - 1/e appears because the number of cross pairs (10^6) e…

Do two databases share an ID?

Your answer

Discussion

Learn the concepts

Related questions