· 5 min read
The Birthday Paradox: Why Random Codes Collide Sooner Than Expected
Short random codes are everywhere: booking references (PNRs), game room codes, discount codes, short links. When a 6-character code has hundreds of millions of possible values, two codes coming out the same seems impossible. It isn't. This post is about how the birthday paradox showed up in two of my projects: in my airline reservation system, the code that builds the sample data was almost certain to collide, and in my game Casus a test failed for no visible reason about once every seventy runs.
The paradox
How many people need to be in a room before the chance that two of them share a birthday passes 50%? Intuition says 183, half a year. The right answer is 23.
Intuition goes wrong because the question is not "was someone born on my birthday?" but "do any two people share a birthday?". 23 people make 253 different pairs, and every pair is another chance of a match.
The same maths applies to codes. When you draw n random codes from a space of N possible values:
- Expected number of colliding pairs: λ ≈ n² / 2N
- Chance of at least one collision: 1 − e^(−λ)
- That chance reaches 50% at about 1.18 × √N codes.
The last line is the one that matters: collisions start not at N but at the square root of N.
The codes
Both projects use the same format: 6 characters from a 31-letter alphabet.
/** No look-alike characters (0/O, 1/I/L), so a code read out over the phone is not misheard. */
public static final String PNR_ALPHABET = "ABCDEFGHJKMNPQRSTUVWXYZ23456789";
public static final int PNR_LENGTH = 6;
31⁶ = 887,503,681, about 887 million values. Its square root is about 29,800. So with around 35 thousand codes, the chance that two of them match is 50%.
Airline: the sample data was almost certain to collide
My airline reservation system generates sample data on first launch so the app looks real: past and future flights, occupied seats, cancellations. That means about 75 thousand bookings, each with a random PNR.
The numbers:
| Codes | Expected colliding pairs | At least one collision |
|---|---|---|
| 5,000 | 0.014 | 1.4% |
| 35,000 | 0.69 | 50% |
| 75,000 | 3.17 | 95.8% |
The pnr column has a UNIQUE constraint. So if the codes had been generated blindly, setup would very likely have stopped halfway and the app would have failed on first launch. Looking at 887 million values it was easy to say "they won't collide"; doing the maths turned that around.
The fix lives in two places. While generating sample data, the codes already used are kept in memory and a repeated code is drawn again:
private static String unique(Set<String> used, Supplier<String> generator) {
String code;
do {
code = generator.get();
} while (!used.add(code));
return code;
}
For a new booking while the app is running, the code is looked up in the database and redrawn if it exists:
for (int attempt = 0; attempt < 20; attempt++) {
final String code = pnr ? Codes.pnr(airline.random()) : Codes.ticketNumber(airline.random());
try (PreparedStatement ps = c.prepareStatement(existsSql)) {
ps.setString(1, code);
if (!ps.executeQuery().next())
return code;
}
}
throw new IllegalStateException("Benzersiz kod üretilemedi"); // could not generate a unique code
The UNIQUE constraint stays: if anything goes wrong between the check and the insert, the database has the last word.
Casus: a test that failed once every seventy runs
In Casus, creating a room generates a 6-character room code, and friends join with it. To test the generator I had written: generate 5,000 codes, all of them must be different.
The test passed most of the time and failed now and then. The code had no bug; the test's expectation was wrong. The first row of the table above is exactly this case: with 5,000 codes the chance of at least one collision is 1.4%, roughly once every 70 runs. A test that fails at random does more harm than one that never fails: after a while nobody believes the red.
I rewrote the test around the statistics:
// Birthday paradox: among 5,000 codes from 887 million, a single repeat happens about 1.4%
// of the time (creating a room then just draws again). A broken generator repeats far more.
var codes = Enumerable.Range(0, 5000).Select(_ => RoomCode.Generate(random)).ToHashSet();
Assert.True(codes.Count >= 4997, $"{5000 - codes.Count} repeats");
Up to 3 repeats are allowed. With 0.014 repeats expected, the chance of 4 or more is about 1.6 in a billion, so the test no longer fails for nothing. But if the generator breaks, say it never uses half of the alphabet or always starts from the same seed, repeats are counted in the hundreds and the test goes red immediately.
In the running system a collision is not an error, just a normal case. A room is saved to Redis with a "write only if the key does not exist" rule, and a taken code means another try:
public Task<bool> CreateAsync(Room room) =>
Db.StringSetAsync(StoreKeys.Room(room.Code), GameJson.Write(room), StoreKeys.RoomLifetime, When.NotExists);
for (var attempt = 0; attempt < MaxCodeAttempts; attempt++)
{
var room = RoomEngine.Create(RoomCode.Generate(random), /* ... */);
if (await rooms.CreateAsync(room)) return (null, room.Code);
}
return ("try_again", null); // ten taken codes in a row: practically never
I used one atomic operation instead of "check, then write" so that two rooms created at the same moment cannot get the same code. With a separate check and write, both could see the code as free and both could write it.
Why I didn't make the codes longer
A longer code means fewer collisions, but people read these codes on a phone, say them out loud and type them by hand. 6 characters is comfortable; 10 is not. Handling collisions with retries and a uniqueness rule is cheaper than handling them with length.
Collisions and guessability are also separate problems. A collision is "two codes come out the same"; guessing is "someone finds another person's code". The defence against guessing is a secure random source (SecureRandom in Java, a cryptographic generator in C#), codes that are not sequential, and a limit on attempts. In the airline app a PNR alone is not enough: it is asked together with the passenger's surname, and failed attempts trigger a wait.
What I took away
- Random codes start colliding around √N. For 887 million values that is about 30 thousand. If the number of codes will get anywhere near that, a collision is not a possibility but an expected event.
- Uniqueness should rest on a rule, not on randomness:
UNIQUEin the database, "write if absent" in Redis, and a retry when the code is taken. - Tests involving randomness are written with statistics. Instead of "no repeats at all", compute the expected value and set a bound that catches a broken generator without ever failing a healthy one by accident.