In probability theory, the birthday problem asks for the probability that, in a set of n randomly chosen people, at least two will share the same birthday. The birthday paradox is the counterintuitive fact that only 23 people are needed for that probability to exceed 50%.

The birthday paradox is a veridical paradox: it seems wrong at first glance but is, in fact, true. While it may seem surprising that only 23 individuals are required to reach a 50% probability of a shared birthday, this result is made more intuitive by considering that the birthday comparisons will be made between every possible pair of individuals. With 23 individuals, there are ⁠23 × 22/2⁠ = 253 pairs to consider.

Real-world applications for the birthday problem include a cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of finding a collision for a hash function, as well as calculating the approximate risk of a hash collision existing within the hashes of a given size of population.

The problem is generally attributed to Harold Davenport in about 1927, though he did not publish it at the time. Davenport did not claim to be its discoverer "because he could not believe that it had not been stated earlier". The first publication of a version of the birthday problem was by Richard von Mises in 1939.

Consider the event A that a group of k people does not have any repeated birthdays, and let the complementary event B be that of a group of k people contains at least two people who share a birthday. Then the probabilities P(A) and P(B) of the two events are related by the equation P(B) = 1 − P(A). The probability P(A) can be computed using the perspective of permutations, as follows. Let ${\displaystyle V_{nr}}$ be the total number of ways that k can have distinct birthdays, and let ${\displaystyle V_{t}}$ be the total number of ways k people can have birthdays arranged, including possibly repeated birthdays. The probability P(A) is the ratio of these two quantities, ${\displaystyle V_{nr}}$ divided by ${\displaystyle V_{t}}$. When ${\displaystyle k=23}$, the two counts are given by $${\displaystyle V_{nr}=365\cdot 364\cdot 363\cdots (365-22)={\frac {365!}{(365-23)!}}}$$ and $${\displaystyle V_{t}=365\cdot 365\cdot 365\cdots 365=365^{23},}$$ their ratio is ${\displaystyle P(A)={\frac {V_{nr}}{V_{t}}}\approx 0.492703}$, and so $${\displaystyle P(B)=1-P(A)\approx 1-0.492703=0.507297\quad (50.7297\%).}$$

Another way the birthday problem can be solved is by asking for an approximate probability that in a group of n people at least two have the same birthday. For simplicity, leap years, twins, selection bias, and seasonal and weekly variations in birth rates are generally disregarded, and instead it is assumed that there are 365 possible birthdays, and that each person's birthday is equally likely to be any of these days, independent of the other people in the group.

For independent birthdays, a uniform distribution of birthdays minimizes the probability of two people in a group having the same birthday. Any unevenness increases the likelihood of two people sharing a birthday. However real-world birthdays are not sufficiently uneven to make much change: the real-world group size necessary to have a greater than 50% chance of a shared birthday is 23, as in the theoretical uniform distribution.

The goal is to compute P(B), the probability that at least two people in the room have the same birthday. However, it is simpler to calculate P(A′), the probability that no two people in the room have the same birthday. Then, because B and A′ are the only two possibilities and are also mutually exclusive, P(B) = 1 − P(A′).