생일 문제는 확률 이론의 유명한 예제 중 하나로, 특정 집단 내에서 적어도 두 명의 사람이 같은 생일을 가질 확률을 계산하는 문제이다. 이 문제는 직관적으로 생각했을 때 예상치 못하게 높은 확률을 보여주기 때문에 The birthday paradox 라고도 불린다.
생일 문제의 기본
생일 문제에서는 일반적으로 365 일이 있는 한 해를 가정하며, 윤년은 고려하지 않는다. 문제의 기본적인 질문은 “어떤 방에 사람들이 있을 때, 적어도 두 사람이 같은 생일일 확률은 얼마인가?” 이다.
계산방법
이 확률을 계산하는 가장 쉬운 방법은 충돌이 발생하지 않을 확률을 계산한 다음 그 값에서 1을 빼는 것이다.
예를 들어, 한 방에 사람이 n 명 있을 경우, 첫 번째 사람의 생일은 어느 날이든 될 수 있고, 두 번째 사람의 생일이 첫 번째 사람과 다른 날짜일 확률은 $\frac{364}{365}$ 이다. 세 번째 사람의 생일이 첫 번째와 두 번째 사람의 생일과 다른 날짜일 확률은 $\frac{363}{365}$ , 그리고 이런 식으로 계속 된다.
n 명이 모두 다른 생일을 가질 확률을 $NP$ (no collision) 이라고 할때, 이는 다음과 같이 계산된다.
$P(no collision)=\frac{365}{365}×\frac{364}{365}×\frac{363}{365}×⋯×\frac{365 - n + 1}{365}$
그러므로 적어도 두 명이 같은 생일을 가질 확률 $P (collision)$ 은 :
$P(collision) = 1 - P (nocollision)$
주요 결과
- 방에 23 명만 있어도, 적어도 두 사람이 같은 생일일 확률이 약 50% 이다.
- 57명이 방에 있으면 이 확률은 99% 이상으로 증가한다.
이러한 결과는 직관적으로 이해하기 어려울 수 있다. 왜냐하면 365 일 중 하루를 선택하는 경우의 수가 많기 때문에, 사람들이 생각하는 것보다 훨씬 더 빨리 충돌이 일어날 가능성이 높기 때문이다.
- 아래 예제 코드를 보면 n=23 일때 50% 확률에 근접해감을 알 수 있다.
public class Solution {
public static void main(String[] args) {
int n = 23;
double np = 1;
for (int i = 0; i < n; i++) {
np *= ((365D - i) / 365);
}
System.out.println(1 - np); // 약 50% 이 나온다.
}
}원리
생일 문제의 원리는 “생일 패러독스” 라고 불리우며, 이는 다수의 무작위 선택 사이에서 예상보다 훨씬 더 빨리 중복이 발생할 수 있다는 통계적 현상을 설명한다. 이 원리를 보다 기술적으로 정의하자면, “이산 확률 공간 내에서 충돌 확률이 높아지는 현상” 이라고 할 수 있다.
생일 문제에서 핵심적인 원리는 각 시행이 독립적이며, 결과의 범위가 제한적일 때, 결과 간의 충돌(중복) 이 상대적으로 적은 수의 시행 후에도 높은 확률로 발생한다는 것이다. 이를 수학적으로 표현하면, 충돌 확률은 시행의 수가 결과 공간의 크기의 제곱근에 접근함에 따라 급격히 증가한다.
(하지만 위의 생일 문제 예시에서 보듯이 제곱근 이상의 확률이 넘어가면 그 이후부터는 급격히 증가하진 않는다.)
위의 생일 문제에서 각 시행이 독립적이며, 결과의 범위가 제한적인 이유는 다음과 같다.
- 각 시행이 독립적인 이유
생일 문제에서 각 시행이 독립적이라는 것은 각 사람의 생일이 서로에게 영향을 미치지 않고 무작위로 결정된다는 뜻입니다. 즉, 한 사람의 생일이 특정 날짜인 것이 다른 사람의 생일 날짜에 영향을 주지 않는다. 각 사람이 생일을 갖는 사건은 다른 사람과는 관련이 없으므로, 이들 사건은 서로 독립적이다. 예를 들어, 한 방에 있는 첫 번째 사람의 생일이 1월 1일이라고 해서, 두 번째 사람의 생일도 그 날짜일 확률에는 영향을 주지 않는다.
- 결과의 범위가 제한적인 이유
생일 문제에서 결과의 범위가 제한적이라는 것은 생일을 가질 수 있는 날짜의 수가 한정되어 있기 때문이다. 일반적인 경우에는 한 해에 365일이 있으므로, 생일은 365개의 가능한 결과 중 하나가 된다. 이는 결과의 범위가 비교적 작다는 것을 의미하며, 각각의 생일이 발생할 확률은 1/365 이다.
응용
생일 문제의 원리는 컴퓨터 과학, 특히 해시 함수와 같은 데이터 구조에서의 충돌 예측, 네트워크 보안 프로토콜 설계, 확률적 알고리즘 분석 등 다양한 분야에서 응용된다. 이 문제를 통해 우리는 직관에 반하는 통계적 결과를 이해하고, 이를 실제 문제 해결에 적용할 수 있다.