#문제

$n$명으로 이루어진 집단에서 두 사람의 생일이 같을 확률은 얼마입니까.

#직관

어떤 사람의 생일이 $x - \frac{1}{365}$일 확률, 그렇다면 두 사람을 골랐을 때 생일이 일치할 확률은 $\frac{1}{365^2}$이고, 쌍의 수는 $\frac{n \cdot (n - 1)}{2}$이므로, 50명에 대한 확률은 1퍼센트를 조금 넘습니다

#올바른 직관

그룹 내 임의의 두 사람의 생일이 일치할 확률을 고려하므로, 이 확률은 $n$명으로 만들 수 있는 사람 쌍의 개수에 의해 결정됩니다. 쌍에서 사람의 순서는 중요하지 않으므로, 이러한 쌍의 총 개수는 $n$개에서 2개를 고르는 조합의 수와 같으며, 23명만 되어도 이미 $\frac{23 \cdot 22}{2} = 253$쌍이 됩니다. 이 수를 보면, 253쌍의 사람을 고려할 때 적어도 한 쌍의 생일이 일치할 확률이 상당히 높으리라는 것을 쉽게 이해할 수 있습니다.

여기서 핵심은 생일 역설의 명제가 바로 집단 내 임의의 두 구성원의 생일이 일치하는 경우를 말한다는 점입니다. 흔한 오해 중 하나는 이 경우를 언뜻 보기에 비슷한 다른 경우, 즉 집단에서 한 사람을 고른 뒤 다른 구성원 중 누군가의 생일이 고른 사람의 생일과 일치할 확률을 구하는 경우와 혼동하는 것입니다. 후자의 경우에는 생일이 일치할 확률이 훨씬 낮습니다.

#풀이

먼저 $n$명으로 이루어진 집단에서 모든 사람의 생일이 서로 다를 확률 $p(n)$을 계산해 봅시다. $n > 365$이면 비둘기집 원리에 의해 확률은 0입니다. $n \le 365$인 경우에는 다음과 같이 추론합니다. 집단에서 임의로 한 사람을 골라 그 사람의 생일을 기억해 둡니다. 다음으로 임의로 두 번째 사람을 고르는데, 이 사람의 생일이 첫 번째 사람의 생일과 일치하지 않을 확률은 $1 — \frac{1}{365}$입니다. 다음으로 세 번째 사람을 고르는데, 이 사람의 생일이 앞의 두 사람의 생일과 일치하지 않을 확률은 $1 — \frac{2}{365}$입니다. 같은 방식으로 추론하면 마지막 사람에 이르게 되며, 이 사람의 생일이 앞선 모든 사람의 생일과 일치하지 않을 확률은 $1 — \frac{n - 1}{365}$입니다. 이 확률들을 모두 곱하면 집단 내 모든 생일이 서로 다를 확률을 얻습니다.

$p(n) = 1 \cdot (1 − \frac{1}{365}) \cdot (1 − \frac{1}{365}) \dots (1 - \frac{n - 1}{365}) = \frac{365 \cdot 364 \dots (365 − n + 1)}{365^n}=\frac{365!}{365^n \cdot (365−n)!}$이므로, 우리가 구하려는 확률은 $1 - p(n)$이며, 23명만 되어도 이 확률은 50퍼센트를 넘습니다.

#일반적인 정식화

$n$개의 객체를 $M$개의 바구니에 균등하게 무작위로 배치할 때 $n \geq \sqrt{M}$이면, $\geq \frac{1}{2}$의 확률로 어떤 2개의 객체가 같은 바구니에 들어갑니다.