Birthday paradox - Ciallo Wiki

1 Intuition and Statement of the Problem

1.1 What “the paradox” refers to

The “birthday paradox” names a situation where a common intuition underestimates how quickly the probability of a shared birthday grows as group size increases. For relatively small groups, the chance that two people share the same day and month can already be substantial, despite there being hundreds of possible calendar days. The “paradox” is therefore a mismatch between intuition and the combinatorial structure of pairwise comparisons.

1.2 Defining the event: at least one shared birthday

The central event is: in a group of \(n\) people, at least two individuals have birthdays that fall on the same day of the year (or, in the common simplification, the same day and month, ignoring the year). This event can be treated as a match among the \(n\) recorded “birthday categories.”

1.3 The role of pairings among people

A key driver is the number of unordered pairs among \(n\) people. The number of pairs grows on the order of \(n^2\), so even if each pair has only a small chance of matching, the sheer volume of pairwise comparisons makes a match likely. This perspective turns the problem from “one person matching another” into a question about many potential collisions at once.

2 Mathematical Formulation

2.1 Modeling assumptions (uniform birthdays, independence)

A standard model assumes:

Each person’s birthday is independent of others.
Birthdays are uniformly distributed across \(N\) equally likely days, where typically \(N=365\) (or \(N=366\) for some contexts).
The year is ignored, so only day-of-year matters.

These assumptions create a clean categorical probability model with no seasonal weighting or dependencies.

2.2 Probability of no shared birthdays

2.2.1 Counting combinations of distinct birthdays

To have no shared birthdays among \(n\) people, their birthdays must all fall on distinct days. Under the uniform model, the first person can have any of \(N\) days. The second must avoid the first’s day, giving \(N-1\) choices, and so on. For \(n \le N\), the number of favorable ordered assignments is \[ N(N-1)(N-2)\cdots (N-n+1). \] The total number of ordered assignments is \(N^n\), since each person independently chooses a day.

2.2.2 Converting to the final probability expression

Thus the probability of no shared birthdays is \[ P(\text{none})=\frac{N(N-1)\cdots (N-n+1)}{N^n} =\prod_{k=0}^{n-1}\left(1-\frac{k}{N}\right). \] If \(n>N\), then distinctness is impossible, and \(P(\text{none})=0\).

2.3 Probability of at least one match

2.3.1 Complement rule: P(shared)=1−P(none)

The desired probability uses the complement: \[ P(\text{shared}) = 1 - P(\text{none}). \] So, for \(n \le N\), \[ P(\text{shared}) = 1-\prod_{k=0}^{n-1}\left(1-\frac{k}{N}\right). \]

2.3.2 Simplified notation and general forms

With \(N\) as the number of categories, the result is often written as \[ P(\text{shared}) = 1-\prod_{k=0}^{n-1}\left(1-\frac{k}{N}\right). \] This same expression applies whenever birthdays are modeled as independent draws from \(N\) equiprobable categories.

3 Approximations and Scaling

3.1 Exponential approximation

3.1.1 Deriving the common e^(−k) style expression

For moderate \(n\) relative to \(N\), each factor \(\left(1-\frac{k}{N}\right)\) can be approximated using the logarithm expansion: \[ \ln\left(1-\frac{k}{N}\right)\approx -\frac{k}{N} \quad \text{(when } k/N \text{ is small)}. \] Then \[ \ln P(\text{none})=\sum_{k=0}^{n-1}\ln\left(1-\frac{k}{N}\right) \approx -\sum_{k=0}^{n-1}\frac{k}{N} = -\frac{n(n-1)}{2N}. \] Exponentiating yields the familiar approximation: \[ P(\text{none})\approx \exp\!\left(-\frac{n(n-1)}{2N}\right), \] and therefore \[ P(\text{shared})\approx 1-\exp\!\left(-\frac{n(n-1)}{2N}\right). \]

3.2 Estimating threshold group sizes

3.2.1 The “50% chance” group size milestone

A commonly quoted benchmark is the smallest \(n\) such that \(P(\text{shared}) \ge 0.5\). Using the exponential approximation, \[ 1-\exp\!\left(-\frac{n(n-1)}{2N}\right)\approx 0.5 \] so \[ \exp\!\left(-\frac{n(n-1)}{2N}\right)\approx 0.5, \quad \frac{n(n-1)}{2N}\approx \ln 2. \] For \(N=365\), this produces a value near \(n\approx 23\), reflecting that the probability crosses one-half at a surprisingly small group size.

3.2.2 Other common probability targets

The same approach generalizes. For a target probability \(p\), \[ p \approx 1-\exp\!\left(-\frac{n(n-1)}{2N}\right), \] which rearranges to \[ n(n-1)\approx -2N\ln(1-p). \] This gives a quick way to estimate how many people are needed for \(p=0.1,0.9,\) or other thresholds.

3.3 Asymptotic behavior for large groups

As \(n\) grows, \(P(\text{shared})\) approaches 1, because collisions become nearly unavoidable once \(n\) is on the order of \(\sqrt{N}\) and beyond. In particular, the approximation suggests that the transition from “unlikely” to “likely” occurs when \(n^2/(2N)\) is around a constant determined by the desired probability level. The scaling therefore depends primarily on \(\frac{n^2}{N}\), not on \(n\) alone.

4 Variants and Extensions

4.1 Different numbers of days (e.g., leap years, restricted calendars)

If the model uses \(N\) categories instead of 365, all formulas remain the same after replacing \(N\). For leap-year style counts, one might take \(N=366\), which slightly shifts threshold group sizes but does not change the qualitative behavior.

4.2 Including or excluding February 29

When leap day is included, birthdays fall into \(N=366\) categories only if the population spans time such that February 29 is genuinely a distinct possible date. If instead the model effectively treats people as belonging to a fixed non-leap-year calendar, February 29 can be removed, returning to \(N=365\). The choice affects numerical thresholds, especially for small probability targets, though the structural formula is unchanged.

4.3 Non-uniform birthday distributions

4.3.1 Seasonality and real-world effects (conceptual discussion)

Empirical birthday data often show non-uniformity due to seasonality and other demographic influences. In a non-uniform setting, categories with higher probability (certain months/days) increase the likelihood of repeated birthdays. The uniform model typically yields a baseline estimate; real-world variation can make shared-birthday probabilities either slightly larger or smaller, depending on the actual shape of the distribution.

A common extension asks for the probability that some day is shared by at least \(m\) people, not merely two. This relates to occupancy distributions: placing \(n\) balls (people) into \(N\) bins (days) and asking for a bin occupancy of size \(\ge m\). Exact computation is more involved than the \(m=2\) case, but the underlying approach remains combinatorial and depends on how many configurations produce bins with sufficient load.

4.5 Generalization to other categorical variables

The same mathematics applies to any categorical labels assigned independently and uniformly across \(N\) categories. Examples include matching colors among objects, repeated values among sampled items, or shared “hash buckets” in abstract collision models. The birthday effect is essentially a special case of collision probability in discrete systems.

5 Practical Examples and Interpretations

5.1 Interpreting probability in real group sizes

The headline numbers (such as “about 23 people for a 50% chance” under uniform assumptions) should be interpreted as model outputs rather than guaranteed outcomes in real populations. Real groups may be biased by age distribution, seasonality, or sampling procedures. Nonetheless, the magnitude of the effect is robust: the probability rises quickly because the number of pairs grows rapidly.

5.2 Relating to collision problems in computer science (conceptually)

In computer science, similar probability questions arise when mapping many inputs to a limited set of outputs. If a system assigns items to one of \(N\) bins uniformly at random, the chance of at least one collision among \(n\) items follows the same form. This conceptual link underlies the intuition behind collision resistance and sizing parameters in hashing and randomized algorithms, even though practical hash functions are not purely random in implementation details.

5.3 Common misconceptions and clarifications

A frequent misunderstanding is to treat the question as if “one person is matching a fixed birthday.” The birthday problem instead concerns whether any pair among the group matches somewhere in the calendar. Another misconception is to think year matters in a way that fundamentally changes the effect; including years effectively enlarges the category count, which shifts thresholds upward but still exhibits rapid growth behavior driven by pairings.

6 Worked Examples

6.1 Example: small group computations

Let \(N=365\) and consider \(n=10\). Using \[ P(\text{none})=\prod_{k=0}^{9}\left(1-\frac{k}{365}\right), \] one multiplies ten terms of the form \((1-k/365)\). The complement gives \(P(\text{shared})\). For small \(n\), the probability is modest, reflecting limited pairwise comparisons.

6.2 Example: solving for group size at a target probability

Suppose a target probability \(p=0.9\) is desired. Using the exponential approximation, \[ 1-\exp\!\left(-\frac{n(n-1)}{2N}\right)\approx 0.9 \] implies \[ \exp\!\left(-\frac{n(n-1)}{2N}\right)\approx 0.1, \quad \frac{n(n-1)}{2N}\approx \ln 10. \] With \(N=365\), \[ n(n-1)\approx 2\cdot 365\cdot \ln 10. \] Solving the resulting quadratic gives an estimate for \(n\), which can then be rounded and optionally verified with the exact product formula.

6.3 Example: comparing uniform vs adjusted assumptions

Consider a toy adjustment where some days are more likely than others, such that the distribution is not uniform. The exact “none” probability can be computed from the multinomial occupancy model using the bin probabilities \(p_1,\dots,p_N\), rather than the uniform product \(\prod_{k}(1-k/N)\). Comparing results shows how heterogeneity changes collision likelihood. Typically, uneven probabilities can increase the chance of repeats because high-probability bins are more likely to be hit multiple times.

7 Connections to Other Probability Topics

7.1 Relation to combinatorics

The exact formula arises from counting assignments that avoid collisions: selecting distinct categories for each person and comparing to all category assignments. This combinatorial counting perspective connects naturally to factorial expressions, permutations, and products of decreasing linear terms.

7.2 Relation to the law of large numbers (intuition)

While the law of large numbers typically concerns averages converging with increasing sample size, the birthday paradox can be seen through an “intuitive” lens: as \(n\) increases, the sample of categories becomes dense enough that repeats become typical. Although the events here are not about convergence of an average, the underlying idea—that more trials in a fixed categorical space produce more regular outcomes—aligns with broader probabilistic intuition.

7.3 Relation to occupancy and collision models

The framework is identical to classical occupancy problems: distributing \(n\) independent balls into \(N\) bins and asking about the presence of collisions. Many related quantities—expected number of occupied bins, probability of no collisions, probability of a bin reaching a certain occupancy—can be studied using occupancy methods. The birthday paradox is therefore a canonical entry point into collision modeling.