Lesson 3

Theorem. If there are \(d\) days in a year and there are at least \(\sqrt{2d}\) people in the room, then the probability that two of them have the same birthday is approximately equal to \(1-1/e \approx 0.632\).

It is called a paradox because intuitively it seems that for such a high probability, a much larger number of people is needed (for example, \(d/2\)). At the same time, there is also an intuitive explanation for this effect: if there are \(n\) people, there are \(\binom{n}{2}\) pairs of people who may have the same birthday.

Proof. Let \(p(n)\) be the probability that at least two of the randomly chosen \(n\) people have the same birthday. Then \(q(n)=1-p(n)\) is the probability that the birthdays of randomly chosen \(n\) people fall on (pairwise) different days. It will be more convenient for us to estimate exactly \(q(n)\): \[\begin{align*}q(n)&=\frac{d(d-1)(d-2)\dotsb(d-(n-1))}{d^n}=\\&=\frac{d}{d}\cdot \frac{d-1}{d}\cdot \frac{d-2}{d}\dotsb \frac{d-(n-1)}{d}=\\&=\left(1-\frac{0}{d}\right) \cdot \left(1-\frac{1}{d}\right) \dotsc \left(1-\frac{n-1}{d}\right)<\\&<e^{0}\cdot e^{-1/d}\cdot e^{-2/d}\dotsb e^{-(n-1)/d}=\\&=e^{-n(n-1)/2d}\ .\end{align*}\] It remains to notice that \(\frac{\sqrt{2d}(\sqrt{2d}-1)}{2d}\to 1\) as \(d \to \infty\).◼