생일 문제

30명의 사람이 있을 때, 이 중 생일 같은 사람이 최소 2명 있을 확률을 구하고 싶다. 어떻게 계산할 수 있을까? 이러한 문제를 생일 문제라 한다. 흥미로운 점은 생일 문제가 우리의 직관을 비웃는 것 같은 결과를 보인다는 것이다.

예를 들어 당신이 누군가를 만났다고 하자. 그 사람이 당신과 생일이 같을 확률은 얼마일까? 당신의 생일이 정해져 있으므로 그 사람의 생일은 365일 중 같은 날인 하루여야 한다. 이 때의 확률은 1/365로 약 0.274% 밖에 안된다. 이처럼 1년의 날 수가 365일이나 되기 때문에 생일이 같아질 확률이 매우 작아 보인다.

다시 문제로 돌아와보자. 30명의 사람이 있을 때 생일이 같은 사람이 최소 2명 있을 확률은 2명이 같을 때, 3명이 같을 때, … 30명이 모두 같을 때의 경우를 모두 찾아야 하므로 쉬운 일이 아니다. 따라서 전체 확률 공간에서 모든 사람이 생일이 다른 확률을 제외하는 식으로 찾아야 한다.

30명 중 한 명의 생일을 선택했고, 두 번째 사람의 생일이 그 사람과 다를 확률은 364/365이다. 같은 식으로 이미 채택된 생일을 제외하고 남은 날 중에 생일이 있을 확률들은 363/365, 362/365… 이다. 이 모든 경우가 동시에 발생해야 생일이 겹치는 날이 없으므로 생일이 겹치지 않은 확률의 계산은 다음과 같이 계산된다.

\displaystyle P(x) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{336}{365}

이는 조금 간단히 쓰면 \frac{365!}{(365-30+1)!365^{30}} 으로 계산할 수 있다. 이 값은 계산해보면 29.37% 정도 되므로, 30명일 때 생일이 같은 사람이 있을 확률이 거의 70%나 된다는 것을 알 수 있다. 진짜? 그렇게나 높다고?

시뮬레이션을 통해서 검증해보자. 365개 숫자 중에서 30개를 뽑아서 중복이 없는 경우의 횟수를 센다. 이걸 10,000 회 반복해서 겹치지 않는 경우에 대한 통계적 확률을 뽑아보자.

from random import randint

def f(k=10000):
  r = 0
  for _ in range(k):
    s = set()
    for _ in range(30):
      s.add(randint(1, 365))
    r += 1 if len(s) == 30 else 0
  return r / k

for _ in range(10):
  print(f'p={f():.2%}')
------------------------
p=29.34%
p=28.91%
p=28.82%
p=29.00%
p=29.83%
p=29.52%
p=29.49%
p=29.34%
p=29.54%
p=28.83%

얼추 29% 언저리에 나오는 것을 볼 수 있다. 이번에는 인원수에 따라서 생일이 같은 사람이 있을 확률을 계산하는 코드를 작성해서 인원수에 따라서 이 확률이 어떻게 변하는지 알아보자. 셈을 간단히 하기 위해 리스트에 있는 모든 값을 곱하는 product 함수를 정의하고 이를 계산식에 사용한다.

from functools import reduce

product = lambda xs: reduce(lambda x, y: x * y, xs, 1)

def p_same_birthday(n=30):
  return 1 - product((x+1)/365 for x in range (365-n, 365))

결과는 놀랍다. 비둘기집 원리에 따르면 366명이 있을 때 생일이 같을 확률이 100%가 된다. 하지만 실질적으로는 20명 정도만 되어도 이미 확률이 절반가까이 되며 100명이 되면 99.99997%가 된다. 이론적으로 완전한 100%는 366명째일 것이나 사실상 100명이 되면 생일이 같은 사람이 거의 있을 것이라 볼 수 있다. 200명이 되면 이 확률이99.9999999999999999999999999998%에 달한다. (아이고 의미 없다.)

# 소수점 6째자리에서 반올림
  2 ->    0.27397%
  3 ->    0.82042%
  4 ->    1.63559%
  5 ->    2.71356%
...
 10 ->   11.69482%
 20 ->   41.14384%
 30 ->   70.63162%
 40 ->   89.12318%
 50 ->   97.03736%
 60 ->   99.41227%
 70 ->   99.91596%
 80 ->   99.99143%
 90 ->   99.99938%
100 ->   99.99997%
110 ->  100.00000%

다만 이것이 ‘우리반이 30명일 때 나와 생일이 같은 친구가 있을 확률’을 말하는 것은 아니다. 이 때에는 비교되는 날짜의 내 생일 하루로 고정되므로 1 - (\frac{364}{365})^{29} 가 되어 약 7.64% 정도가 된다.

참고로 생일이 겹치는 것과 비슷하게 해시값이 같은 두 입력값이 있을 확률 역시 입력값의 개수가 많아질 수록 비슷하게 매우 빠르게 증가하기 때문에 모든 입력값에 대해 계산하지 않고도 해시 충돌을 찾을 수 있다고 한다. (참고)