Birthday and Collision Problems, introduction to probability lesson

Four users each receive one of ten labels, independently and with all labels equally likely. Users 1 and 2 match with probability $1/10$ , which sounds small, yet the probability that some pair of users matches is almost one half. The difference comes from the six pairs among four users and from the fact that the matching pair is not named in advance. This lesson computes such collision probabilities through the complement, states the model that makes the counting valid, and shows what changes when there are more users than labels or when the labels are not equally likely.

Key terms

Collision

Definition Suppose each of $n$ individuals receives one of $m$ categories, such as labels or birthdays. A collision is the event that at least two individuals receive the same category. The matching individuals are not specified in advance, and a collision includes outcomes in which several pairs match at once. The complement of a collision is the event that the $n$ individuals all receive different categories, called no collision, so by The Complement Rule, $P(\text{collision}) = 1 - P(\text{no collision})$ .

In plain words A collision asks whether any two individuals match, not whether one particular pair does. Many pairs can match in one outcome, so it is easier to count the outcomes with no match at all.

Example Four users receive labels from $1$ to $10$ , and the outcome lists the labels of users 1 to 4 in order. The outcome $(3, 7, 3, 1)$ is a collision, since users 1 and 3 match. The outcome $(5, 5, 5, 2)$ is also a single collision outcome, even though three pairs match in it. The outcome $(4, 10, 8, 6)$ has no collision.

No-collision probability

Definition Assume that each of $n$ individuals receives one of $m$ categories independently, with probability $1/m$ for each category, and record the outcome as the ordered list of the $n$ categories. The list is ordered because its positions identify the individuals. Under these assumptions the $m^n$ ordered records are equally likely. By the product rule, the number of records with all categories different is

m(m - 1) \cdots (m - n + 1),

since each new individual must avoid the categories already used. Dividing by $m^n$ gives

\begin{aligned} &P(\text{no collision}) \\[0.4em] &\quad = \prod_{j=0}^{n-1} \left(1 - \frac{j}{m}\right). \end{aligned}

The formula holds for every whole number $n \ge 0$ . For $n = 0$ and $n = 1$ the product equals $1$ , since there is no pair that could match, and for $n > m$ it contains the factor $1 - m/m = 0$ .

In plain words Assign the categories one individual at a time. The first can take any category, and in a record with no collision each later one avoids all categories already taken, so the number of allowed choices drops by one each time. The total number of records stays $m^n$ , because the assignment itself still allows every category for every individual.

Example For four users and ten labels there are $10^4 = 10000$ records, and $10 \cdot 9 \cdot 8 \cdot 7 = 5040$ of them have four different labels. So

\begin{aligned} &P(\text{no collision}) \\[0.4em] &\quad = \frac{5040}{10^4} = 0.504, \end{aligned}

and the probability of a collision is $1 - 0.504 = 0.496$ .

Birthday problem

Definition The birthday problem asks for the probability that at least two of $n$ people share a birthday. The standard model ignores February 29, gives each of the $365$ remaining days probability $1/365$ , and treats the birthdays of different people as independent. Under these assumptions it is the collision problem with $m = 365$ , so

\begin{aligned} &P(\text{shared birthday}) \\[0.4em] &\quad = 1 - \prod_{j=0}^{n-1} \left(1 - \frac{j}{365}\right). \end{aligned}

The model is an idealization. Actual birth dates are not spread exactly evenly over the year, and a group that contains twins does not have independent birthdays.

In plain words The question concerns any two people in the group, not a match with one particular person. Even a group of moderate size contains many pairs, and each pair is another chance for a match.

Example For $23$ people the model gives a shared birthday with probability about $0.507297$ , computed from the exact product. For $22$ people it is about $0.4757$ , so $23$ is the smallest group for which the model probability exceeds one half. The $23$ people form $\binom{23}{2} = 253$ pairs, and that large number of pairs explains why a match is likely.

Match of a specified pair

Definition A specified-pair match is the event that two individuals named in advance, for example users 1 and 2, receive the same category. Under the uniform independent model its probability is $1/m$ , whatever the number of other individuals, because whatever category user 1 receives, user 2 receives the same one with probability $1/m$ . A collision is the union of the $\binom{n}{2}$ specified-pair events. When $n \ge 3$ these events can occur together, so their probabilities cannot simply be added. For every $n$ their sum gives the union bound

P(\text{collision}) \le \binom{n}{2} \frac{1}{m}.

In plain words One named pair has one chance to match. A collision collects the chances of every pair, so it is at least as likely, and with many pairs and many categories it can be far more likely. The chances overlap, so adding them overstates the answer whenever several pairs can match at once.

Example For four users and ten labels, users 1 and 2 match with probability $1/10$ . There are $\binom{4}{2} = 6$ pairs, and $6 \cdot 1/10 = 0.6$ is an upper bound for a collision. The exact value $0.496$ is smaller because records such as $(5, 5, 5, 2)$ make several pair events happen at once. Of the $10000$ records, $640$ make two or more pairs match, and each of them is counted more than once in the sum. For $23$ birthdays the bound $253/365 \approx 0.693$ is likewise larger than the exact value, about $0.507297$ .

Pigeonhole principle

Definition If $n$ objects are placed into $m$ boxes and $n > m$ , then at least one box contains at least two objects. More generally, some box contains at least $\lceil n/m \rceil$ objects. In collision terms, if $n > m$ individuals each receive one of $m$ categories, a collision is certain, so $P(\text{collision}) = 1$ , whatever the category probabilities and whether or not the assignments are independent. Under the uniform model the no-collision product agrees, since it contains a zero factor when $n > m$ .

In plain words With more individuals than categories there is no way to give everyone a different category, and no probability calculation is needed.

Example Seven users with six labels must produce a collision, and in the $365$ -day birthday model any $366$ people include two with the same birthday. With six users and six equally likely labels a collision is not certain, but it is very likely, since

\begin{aligned} 1 - \frac{6!}{6^6} &= 1 - \frac{720}{46656} \\[0.4em] &= \frac{319}{324}, \end{aligned}

which is about $0.985$ .

Nonuniform categories

Definition Suppose each individual receives category $i$ with probability $p_i$ , where $p_1 + \cdots + p_m = 1$ . When the $p_i$ are not all equal, the ordered records are no longer equally likely, and the ratio of counts behind the no-collision formula no longer applies. Probabilities must then be computed from the actual $p_i$ . For two individuals who choose independently with these probabilities, the events that both receive category $i$ are disjoint for different $i$ , so

P(\text{match}) = \sum_{i=1}^{m} p_i^2.

This sum is always at least $1/m$ , with equality exactly when every $p_i = 1/m$ . More generally, for any number of individuals who choose independently with the same category probabilities, the collision probability is never smaller than it is when all $m$ categories are equally likely. For birthdays this means that, as long as people are independent and share one distribution over $365$ days, unequal birth frequencies cannot lower the chance of a shared birthday below the uniform value.

In plain words Unequal probabilities make some categories popular, and independent individuals tend to meet in them. So with independent choices a match is never less likely than with equally likely categories.

Example Two independent choices from four labels with probabilities $0.7$ , $0.1$ , $0.1$ and $0.1$ match with probability

\begin{aligned} &0.7^2 + 3 \cdot 0.1^2 \\[0.4em] &\quad = 0.49 + 0.03 = 0.52, \end{aligned}

compared with $4 \cdot (1/4)^2 = 0.25$ when the four labels are equally likely. Counting $4$ matching records among $16$ would give $0.25$ for both models, which is wrong for the unequal one, because the record $(1, 1)$ has probability $0.49$ while the record $(2, 3)$ has probability $0.01$ .

Check yourself

Three users independently receive one of six equally likely labels. Find the probability of a collision and the probability that users 1 and 2 match. What is the probability of a collision for seven users and six labels?

Show the answer

There are $6^3 = 216$ equally likely ordered records, and $6 \cdot 5 \cdot 4 = 120$ of them have three different labels. So

\begin{aligned} P(\text{collision}) &= 1 - \frac{120}{216} \\[0.4em] &= \frac{4}{9}, \end{aligned}

which is about $0.444$ . Users 1 and 2 match with probability $1/6$ . The collision probability is larger because it also includes matches that involve user 3, while an outcome with several matches is still counted once. With seven users and six labels a collision is certain by the pigeonhole principle, so its probability is $1$ .

In the $365$ -day birthday model with $23$ people, one person computes the probability that someone else in the group shares her birthday as $1 - (364/365)^{22} \approx 0.0586$ . She concludes that the value $0.507$ for the birthday problem must be wrong. Explain the discrepancy.

Show the answer

Her calculation is correct for a different event, a match with one specified person. Given her birthday, each of the other $22$ people independently misses it with probability $364/365$ , which gives

1 - \left(\frac{364}{365}\right)^{22} \approx 0.0586.

The birthday problem asks about all $253$ pairs in the group, including the $231$ pairs that do not involve her. Both numbers are right for their own events, and the collision event contains hers and is much more likely.

Two people independently choose one of three labels with probabilities $1/2$ , $1/4$ and $1/4$ . A classmate lists the $9$ ordered records, finds $3$ with matching labels and answers $3/9 = 1/3$ . Find the correct probability of a match and explain the error.

Show the answer

The match events for the three labels are disjoint, so

\begin{aligned} P(\text{match}) &= \frac{1}{4} + \frac{1}{16} + \frac{1}{16} \\[0.4em] &= \frac{3}{8}. \end{aligned}

The classmate treated the $9$ records as equally likely, but they are not. The record $(1, 1)$ has probability $1/4$ , while $(2, 3)$ has probability $1/16$ . A ratio of record counts gives the probability of every event exactly when the records are equally likely. As expected for unequal label probabilities, the answer $3/8$ is larger than the uniform value $1/3$ .

Birthday and Collision Problems

Key terms

Collision

No-collision probability

Birthday problem

Match of a specified pair

Pigeonhole principle

Nonuniform categories

Check yourself

How this lesson connects

Builds on

Used later in