[확률] 생일문제

반응형

$n$명의 사람들 중에서 적어도 한 쌍(두 명)의 생일이 같을 확률을 구하는 문제이다. 문제를 간단히 하여 1년에 365일만 있다고 하자.

한번에 생각을 떠올리기 힘드니 작은 문제부터 확장해보자.

1. $n=2$ 일 때

두 명의 생일이 같은 사건은 $A = \{(1, 1), (2,2), \dots, (365, 365)\}$이고 표본공간 $S = \{ (1, 1), (1, 2), \dots, (365, 364), (365, 365) \}$이므로 확률을 계산하면 $P(A) = \cfrac{365}{365^2} = \cfrac{1}{365}$ 이다.

 

2. $n$명의 생일이 모두 같을 확률

$|A| = 365$이고 $|S| = 365^n$이므로 $P(A) = \cfrac{1}{365^{n-1}}$ 이다.

 

3. $n$명의 생일이 모두 다를 확률

사건 $A$의 모든 경우를 계산해도 되겠지만, 순열(permutation)의 관점에서 생각해보자.

첫번째 사람이 가능한 날짜의 수는 $365$, 두번째 사람이 가능한 날짜의 수는 $365-1$, ..., $n$번째 사람이 가능한 날짜의 수는 $365-(n -1)$이므로 $|A| = \cfrac{365!}{(365-n)!}$

따라서 $P(A) = \cfrac{365!}{365^n (365-n)!}$

 

4. $n$명의 생일 중 적어도 2명의 생일이 같을 확률

3)의 여사건이므로 $P(A) = 1 - P(A^C)$를 이용하자. 여기서 $A^C$는 3의 확률이다.

따라서 $P(A) = 1 - \cfrac{365!}{365^n (365-n)!}$

이를 사람수에 따라 그래프로 나타내면 아래와 같다.

 

$n=23$만 되어도 적어도 두 사람의 생일이 같을 확률은 50%가 넘는다.

 

테일러 급수로 근삿값 구하기

테일러 급수를 이용하면 $e^x$는 아래와 같다.

\[ e^x = 1 + x + \cfrac{x^2}{2!} + \cdots \]

first-order approximation을 이용하면 $x \ll 1$에서 $e^x \approx 1 + x$로 근사할 수 있다. 즉

\[ e^{-\cfrac{1}{365}} \approx 1 - \cfrac{1}{365} \]

\[ P(A^C) \approx 1 \cdot e^{-\cfrac{1}{365}} \cdot e^{-\cfrac{2}{365}} \cdots e^{-\cfrac{n-1}{365}} = e^{-\cfrac{n(n-1)}{730}} \]

따라서 생일문제의 확률은

\[ P(A) \approx 1 - e^{-\cfrac{n^2}{730}} \]

 

이를 더 일반화하여 $n$명의 사람이 $d$일동안 적어도 한 쌍의 생일이 같을 확률은 

\[ p(n, d) \approx 1 - e^{-\cfrac{n^2}{2d}}\]

단 $n \ll d$ 이다.