$f(n, d)$를 $n$명으로 이루어진 집단에서 생일이 같은 사람이 아무도 없을 확률이라고 합시다. 생일은 $1$부터 $d$까지의 구간에서 독립적이고 균등하게 분포한다고 가정하겠습니다.
$$
f(n, d) = (1-\frac{1}{d}) \times (1-\frac{2}{d}) \times ... \times (1-\frac{n-1}{d})
$$
$f$를 추정해 봅시다:
$$
\begin{aligned}
e^x & = 1 + x + \frac{x^2}{2!} + \ldots & \text{(ряд Тейлора для экспоненты)}
\\\ & \simeq 1 + x & \text{(аппроксимация для $|x| \ll 1$)}
\\\ e^{-\frac{n}{d}} & \simeq 1 - \frac{n}{d} & \text{(подставим $\frac{n}{d} \ll 1$)}
\\\ f(n, d) & \simeq e^{-\frac{1}{d}} \times e^{-\frac{2}{d}} \times \ldots \times e^{-\frac{n-1}{d}} &
\\\ & = e^{-\frac{n(n-1)}{2d}} &
\\\ & \simeq e^{-\frac{n^2}{2d}} &
\end{aligned}
$$식에서 확률 $\frac{1}{2}$은 $n \approx \sqrt{d}$에서 도달하며, 이 지점에서 빠르게 변한다는 것을 알 수 있습니다.
따름정리. 어떤 두 수가 일치하려면 멀티셋에 1부터 $n$까지의 무작위 수를 $O(\sqrt{n})$개 추가해야 합니다.