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.

Same birthday as you

Note that in the birthday problem, neither of the two people is chosen in advance. By way of contrast, the probability q(n;d) that someone in a room of n other people has the same birthday as a particular person (for example, you), or more generally has picked the same number between 1 and d as you, is given by

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: q(n;d) = 1 - left( rac{d-1}{d} ight)^n

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Substituting n = 22 and d = 365 gives about 5.9%, which is only slightly better than 1 chance in 17. For a greater than 50:50 chance that one person in a roomful of n people has the same birthday as you, n would need to be at least 253. Note that this number is significantly higher than 365/2 = 182.5: the reason is that there are likely some birthday matches among the people in the room.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~