Birthday Paradox

Concept Overview

The Birthday Paradox (or Birthday Problem) is a famous result in probability theory which states that in a group of just 23 randomly chosen people, there is more than a 50% chance that at least two of them share the same birthday. It is called a "paradox" not because it is logically contradictory, but because it is highly counterintuitive to human intuition, which often drastically underestimates the probability.

Mathematical Definition

To calculate the probability that at least two people in a group of n people share a birthday, it is easier to first calculate the probability of the complementary event: the probability that nobody shares a birthday. Let P(A) be the probability of a shared birthday, and P(A') be the probability that all n people have distinct birthdays.

Assuming a year has d = 365 days (ignoring leap years) and birthdays are uniformly distributed:

// Probability of unique birthdays

P(A') = (d/d) · ((d-1)/d) · ((d-2)/d) · ... · ((d-n+1)/d)

P(A') = d! / (dⁿ · (d-n)!)

// Probability of at least one shared birthday

P(A) = 1 - P(A')

Key Concepts

Pairs vs. Individuals

The intuition flaw stems from thinking about one person comparing their birthday to others (which gives n-1 comparisons). However, the true probability depends on the total number of pairs in the group. For n = 23 people, there are C(23, 2) = 23 × 22 / 2 = 253 possible pairs. With 253 chances for a match, it becomes much more believable that at least one pair will match out of 365 possible days.

Exponential Approximation

Using the Taylor series expansion for e^x ≈ 1 + x, we can approximate the probability. For n people and d days, the number of pairs is n(n-1)/2. The probability of any given pair NOT matching is 1 - 1/d.

P(A') ≈ (1 - 1/d)^n(n-1)/2 ≈ e^-n(n-1)/(2d)

P(A) ≈ 1 - e^-n²/(2d)

Historical Context

The origins of the birthday paradox are slightly ambiguous, but it is often attributed to Harold Davenport, who claimed to have invented it in the late 1920s. However, it was first published by Richard von Mises in 1939. The problem serves as a classic example in introductory statistics to demonstrate how human heuristics regarding combinatorics and exponential growth are fundamentally flawed.

Real-world Applications

Cryptography (Birthday Attack): The birthday paradox forms the basis for the "birthday attack," a type of cryptographic attack that exploits the mathematics behind the birthday problem to find collisions in hash functions. If a hash function produces outputs of size d, a collision can be expected after evaluating approximately √d inputs, rather than d/2 inputs.
Database Collision Resolution: When designing hash tables for databases, the birthday paradox helps engineers predict how many random insertions can be made before a hash collision becomes highly probable, informing the design of collision handling mechanisms.
DNA Sequencing: In computational biology, similar combinatoric principles apply when estimating the likelihood of finding matching genetic sequences or identifying the probability of random overlaps in sequence assembly.

Related Concepts

Monte Carlo Simulation — Can be used to empirically demonstrate the birthday paradox by simulating thousands of random groups.
Probability Distributions — The problem is deeply connected to uniform distributions and combinatorial probability.

Birthday Paradox