[확률론] (3) Birthday Problem, Properties of Probability

우리의 직관에 반하는 예시인 Birthday Problem을 살펴보면서 확률의 특성에 대해 알아보자.

만약 k명의 사람들이 존재할 때, 그 중 적어도 2명의 생일이 서로 같을 확률은 얼마일까? 이 문제의 가정은 i.i.d라는 점이다. 가령 k명의 사람이 모인 집단이 무작위적으로 추출된 것이 아니라 특정 일자를 생일로 가질 확률이 확률적으로 높은 집단이라면 이 문제는 무효가 된다. 따라서 생일의 확률은 identically distributed된 경우라고 가정한다. 

이 문제를 풀기 위한 과정은 다음과 같다. 

첫째, 만약 k > 365라면 확률은 1이 된다. k=366이라면 매우 운이 없는 경우 365명 모두의 생일이 다르더라도 적어도 한 명의 생일은 누군가와 겹치게 되니 P(k)=1, k>365가 된다. 

둘째, 만약 k <= 365라면 그 누구도 서로 생일이 겹치지 않을 확률은 위 식이 된다. 모두가 independent하고 identically distributed된 생일 분포의 확률을 갖고, 이들이 서로 겹치지 않는 경우의 수만을 따지면 위 식이 도출되는 것이다. 참고로 이 때 누가 언제 생일인지는 중요한 이슈기 때문에 순서는 고려의 대상이 된다. 

 

위에서 구한 "그 누구도 서로 생일이 겹치지 않을 사건"의 확률을 1에서 빼주게 되면, 단 한명이라도 매칭되는 사건의 확률이 도출된다. 이 식을 풀면 k=23일때 확률은 50.7%, k=50일때 97%가 된다. 일반적으로 우리는 200명 이상의 k를 guess하는데 k=50이면 97%의 확률로 생일이 겹치니 이는 상당히 반-직관적인 결과다. 

 

이전 글에서 확률의 non-naive한 정의를 살펴봤다. 

우측하단의 도식처럼 P(확률)은 experiment를 통해 도출된 특정 event를 input으로 받고, 그 event가 전사건 중 차지하는 면적을 0과 1 사이의 숫자로 치환하여 반환하는 일종의 함수다.

 

이런 확률에는 다음과 같은 특성이 있다.

첫째, event A의 여집합의 확률은 전사건에서 P(event A)를 차감한 것과 같다. 

둘째, 만약 A가 B의 부분집합일 경우, P(A) <= P(B)이다. 

셋째, P(A or B) = P(A)+P(B)-P(A and B)다. 

증명은 중학교 수준이라 생략한다. 

 

위 특성을 활용한 것 중에 가장 중요한 것이 Inclusion-Exclusion, 즉 포함 배제의 원리다. 

event A,B,C가 위 벤다이어그램과 같은 관계에 놓여있다고 가정하자. P(A or B or C)는 다음과 같이 계산할 수 있다. 

P(A or B or C) = P(A) + P(B) + P(C) - P(A and B) - P(A and C) - P(B and C) + P(A and B and C)

 

이 원리는 위 식과 같다. 모든 event를 독립적으로 다 더하고, 두 개의 event간의 교집합을 차감한다. 그리고 세 개의 event간의 교집합을 더하고, 네 개의 교집합은 차감하고... 이 과정을 끝까지 반복하는 것이다. 

 

포함 배제의 원리를 활용한 문제 중 유명한 것은 de Montmort's Problem이 있다. 

1,2,...,n까지 숫자가 기입된 n개의 카드가 존재한다고 가정하자. event Aj를 정렬된 카드 중 j번째 카드에 숫자 j가 있는 경우라고 정의할 때, 카드가 아무것도 매칭되지 않을 확률은 얼마인가?

P(no match)=1-P(at least one card matched)임을 활용해서 풀어보자. 최소 한 카드가 매칭될 확률은 A1, A2, A3, ... , An의 합집합이다. 따라서 우리는 이 합집합을 포함 배제의 원리를 활용해 계산해주면 된다. 

우선 P(Aj) = 1/n 이다. 카드가 일렬로 정렬되어있고 j번째 카드에 j가 적혀 있을 확률은 n개의 숫자 중 j가 거기 있을 확률이니 1/n인 것이다. 이런 j가 n개 있는 것이니 nC1을 확률에 곱해주면 된다. 

그리고 포함 배제의 원리대로 Aj와 Am이 동시에 발생할 확률을 차감하고, Aj와 Am, Ap가 동시에 매칭될 확률을 더하고... 이 작업을 P(A1 and A2 and ... An)까지 반복해주면 된다. 그 결과로 나온 값은 독특하게도 테일러급수를 따르기에 P(at least one card matched) = 1 - 1/e 임을 우리는 알 수 있다. 따라서 P(no match) = 1/e다.