생일 문제

개요

생일 문제는 확률론에서 고전적인 문제 중 하나로, 여러 사람 중 두 명 이상이 같은 생일을 가질 확률을 계산하는 문제이다. 이 문제는 직관과는 다르게, 비교적 적은 수의 사람만 있어도 같은 생일을 가질 확률이 매우 높아진다는 점에서 흥미롭다. 이러한 현상은 주로 해시 충돌이나 고유 식별자 생성 문제, 특히 UUID 충돌 확률 계산 등 다양한 컴퓨터 과학적 문제에서 응용된다.

문제 정의

생일 문제는 다음과 같이 정의할 수 있다:

• N일이 있는 달력에서, k명의 사람들이 있을 때, 이들 중 적어도 두 명 이상이 같은 생일을 가질 확률을 구한다.
• 전제 조건으로는, 각 사람이 생일을 독립적으로, 균등한 확률로 고른다는 가정이 포함된다.

기본 개념

생일 문제에서 기본적으로 다루는 두 가지 확률은 다음과 같다:

1. 적어도 두 명이 같은 생일을 가질 확률
2. 모든 사람이 서로 다른 생일을 가질 확률

후자의 경우는 비교적 쉽게 계산할 수 있다. 이를 통해, 첫 번째 확률은 다음과 같이 구할 수 있다: [math]\displaystyle{ P(\text{적어도 두 명이 같은 생일}) = 1 - P(\text{모든 사람이 다른 생일}) }[/math]

확률 계산

모든 사람이 서로 다른 생일을 가질 확률은 점진적으로 줄어든다. k명이 있을 때, 첫 번째 사람은 N일 중 어느 날을 선택하더라도 상관없고, 두 번째 사람은 첫 번째 사람이 선택하지 않은 날들 중 하나를 선택해야 한다. 이를 일반화하면 다음과 같은 식을 얻을 수 있다:

[math]\displaystyle{ P(\text{모든 사람이 다른 생일}) = \frac{N}{N} \times \frac{N-1}{N} \times \frac{N-2}{N} \times \cdots \times \frac{N-k+1}{N} = \prod_{i=0}^{k-1} \frac{N-i}{N} }[/math]

이 식을 계산하여 얻은 값에서 1을 빼면 적어도 두 명이 같은 생일을 가질 확률을 얻을 수 있다: [math]\displaystyle{ P(\text{적어도 두 명이 같은 생일}) = 1 - \prod_{i=0}^{k-1} \frac{N-i}{N} }[/math]

예시

예를 들어, 365일의 달력에서 23명이 있을 때, 적어도 두 명이 같은 생일을 가질 확률은 약 50%이다.

계산 과정

생일 문제에서 23명이라는 숫자와 50%의 확률이 나오는 이유는 확률 계산이 직관과는 다르게 작동하기 때문이다. 이는 수학적 확률 계산의 결과로, 구체적으로 설명하자면 모든 사람이 서로 다른 생일을 가질 확률을 계산한 후, 그 값을 1에서 빼서 적어도 두 명이 같은 생일을 가질 확률을 구하는 방식이다.

1. 첫 번째 사람은 365일 중 아무 날에나 태어날 수 있다. 확률은 1.
2. 두 번째 사람은 첫 번째 사람이 태어난 날을 제외한 364일 중 한 날에 태어나야 한다. 확률은 [math]\displaystyle{ \frac{364}{365} }[/math]이다.
3. 세 번째 사람은 앞의 두 사람이 태어난 날을 제외한 363일 중 한 날에 태어나야 한다. 확률은 [math]\displaystyle{ \frac{363}{365} }[/math]이다.
4. 이렇게 계속해서 계산하면, 모든 사람이 서로 다른 생일을 가질 확률은 다음과 같은 식으로 계산된다:

[math]\displaystyle{ P(\text{모든 사람이 다른 생일}) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{365-23+1}{365} }[/math]

계산을 하면, 모든 사람이 서로 다른 생일을 가질 확률은 약 49.3%이다. 따라서 적어도 두 명이 같은 생일을 가질 확률은 [math]\displaystyle{ 1 - 49.3\% = 50.7\% }[/math]가 된다.

즉, 23명이 있을 때, 적어도 두 명이 같은 생일을 가질 확률이 약 50%인 것이다. 이 결과는 직관과는 다르게 적은 인원으로도 높은 확률을 얻을 수 있다.

응용 사례

생일 문제는 단순히 생일 확률 계산에 그치지 않고, 여러 분야에서 응용된다. 대표적인 응용 사례는 다음과 같다:

• 해시 함수 충돌: 해시 테이블에서 여러 개의 입력값이 동일한 해시값을 가질 확률을 계산할 때 생일 문제가 응용된다. 이를 생일 충돌 확률이라 부르며, 특히 해시 함수의 강도 평가와 암호학에서 중요하게 다뤄진다.
• UUID 충돌 확률 계산: UUID와 같은 고유 식별자의 충돌 가능성을 평가할 때, 생일 문제의 확률 계산 방법이 자주 사용된다. 특히, 많은 개체에서 고유 식별자를 생성하는 분산 시스템에서 유용하다.
• 암호학: 생일 문제는 암호학적 공격에서 중요한 역할을 한다. 특히, '생일 공격'은 해시 함수에서 약한 충돌 저항성을 이용해 동일한 해시값을 가진 두 입력을 찾는 방식이다.