In probability theory, the birthday problem asks for the probability that, in a set of n randomly chosen people, at least two will share a birthday. The birthday paradox refers to 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, far more than half the number of days in a year.

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".^[1][2] The first publication of a version of the birthday problem was by Richard von Mises in 1939.^[3]

Calculating the probability

From a permutations perspective, let the event A be the probability of finding a group of 23 people without any repeated birthdays. Where the event B is the probability of finding a group of 23 people with at least two people sharing same birthday, P(B) = 1 − P(A). P(A) is the ratio of the total number of birthdays, ${\displaystyle V_{nr}}$, without repetitions and order matters (e.g. for a group of 2 people, mm/dd birthday format, one possible outcome is ${\displaystyle \left\{\left\{01/02,05/20\right\},\left\{05/20,01/02\right\},\left\{10/02,08/04\right\},...\right\}}$) divided by the total number of birthdays with repetition and order matters, ${\displaystyle V_{t}}$, as it is the total space of outcomes from the experiment (e.g. 2 people, one possible outcome is ${\displaystyle \left\{\left\{01/02,01/02\right\},\left\{10/02,08/04\right\},...\right\}}$). Therefore ${\displaystyle V_{nr}}$ and ${\displaystyle V_{t}}$ are permutations.

${\displaystyle {\begin{aligned}V_{nr}&={\frac {n!}{(n-k)!}}={\frac {365!}{(365-23)!}}\\V_{t}&=n^{k}=365^{23}\\P(A)&={\frac {V_{nr}}{V_{t}}}\approx 0.492703\\P(B)&=1-P(A)\approx 1-0.492703\approx 0.507297\quad (50.7297\%)\end{aligned}}}$

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^[4] 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.^[5][6] 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.^[7]

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′).

Here is the calculation of P(B) for 23 people. Let the 23 people be numbered 1 to 23. The event that all 23 people have different birthdays is the same as the event that person 2 does not have the same birthday as person 1, and that person 3 does not have the same birthday as either person 1 or person 2, and so on, and finally that person 23 does not have the same birthday as any of persons 1 through 22. Let these events be called Event 2, Event 3, and so on. Event 1 is the event of person 1 having a birthday, which occurs with probability 1. This conjunction of events may be computed using conditional probability: the probability of Event 2 is 364/365, as person 2 may have any birthday other than the birthday of person 1. Similarly, the probability of Event 3 given that Event 2 occurred is 363/365, as person 3 may have any of the birthdays not already taken by persons 1 and 2. This continues until finally the probability of Event 23 given that all preceding events occurred is 343/365. Finally, the principle of conditional probability implies that P(A′) is equal to the product of these individual probabilities:

${\displaystyle P(A')={\frac {365}{365}}\times {\frac {364}{365}}\times {\frac {363}{365}}\times {\frac {362}{365}}\times \cdots \times {\frac {343}{365}}}$

(1)

The terms of equation (1) can be collected to arrive at:

${\displaystyle P(A')=\left({\frac {1}{365}}\right)^{23}\times (365\times 364\times 363\times \cdots \times 343)}$

(2)

Evaluating equation (2) gives P(A′) ≈ 0.492703

Therefore, P(B) ≈ 1 − 0.492703 = 0.507297 (50.7297%).

This process can be generalized to a group of n people, where p(n) is the probability of at least two of the n people sharing a birthday. It is easier to first calculate the probability p(n) that all n birthdays are different. According to the pigeonhole principle, p(n) is zero when n > 365. When n ≤ 365:

Zdroj:https://en.wikipedia.org?pojem=Birthday_paradox
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---