Birthday paradox

The birthday paradox states that if there are 23 people in a room then there is a chance of more than 50% that at least two of them will have the same birthday. This means that in a typically-sized school class, where the 'paradox' is often cited, an even higher probability often applies. For 60 or more people, the probability is already greater than 99%. This is not a paradox in the sense of leading to a logical contradiction; it is a paradox in the sense that it is a mathematical truth that contradicts common intuition. Most people estimate that the chance is much lower than 50:50. Calculating this probability (and related ones) is the birthday problem. The mathematics behind it has been used to devise a well-known cryptographic attack named the birthday attack.

Reverse problem

An alternate question may be:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:For a fixed probability p and number of days in a year d...

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:... find the greatest n(p;d) for which the probability p(n;d) is smaller than the given p, or

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:... find the smallest n(p;d) for which the probability p(n;d) is greater than the given p.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

An approximation for this is given by:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:n(p;d)pprox left(2dlnleft({1 over 1-p} ight) ight)^{1/2}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Example

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

approximationcomputation for d := 365

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

pn generalizedn for d := 365 n↓p(n↓)n↑p(n↑)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.010.14178 √d 2.7086420.0027430.00820

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.050.32029 √d 6.1191660.0404670.05624

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.10.45904 √d 8.7700280.0743490.09462

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.20.66805 √d12.76302120.16702130.19441

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.30.84460 √d16.13607160.28360170.31501

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.51.17741 √d22.49439220.47570230.50730

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.71.55176 √d29.64625290.68097300.70632

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.81.79412 √d34.27666340.79532350.81438

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.92.14597 √d40.99862400.89123410.90315

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.952.44775 √d46.76414460.94825470.95477

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0.993.03485 √d57.98081570.99012580.99166

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Note: some values are coloured showing that the approximation is not always exact.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~