1년은 365일 윤년이면 366일. 다시 말해서, 길가에 나가서 아무나 붙잡았을 때 생일이 같은 사람일 확률은 대략 1/366에서 1/365. 그렇다면 아무나 붙잡아서 생일들을 기록했을 때, 얼마나 많은 사람들을 기록하면 처음으로 생일이 같은 사람들이 나올까?
이 문제는 생일 문제라고 불리는 문제로, 일단 당연한 소리지만, 367명을 기록하면 그 중에서 생일이 같은 사람은 반드시 존재하게 되어있음. 그러나 당연히, 일반적으로 그 전에 생일이 같은 사람들이 나올 것임. 여기서 놀라운 것은, 23명 정도만 되어도 그 중에서 생일이 같은 사람이 있을 확률이 50%나 되고, 40명쯤 되면 90% 확률로 존재함. 이 부분이 사람들의 직관과는 다르기 때문에, 이를 생일 역설이라고 부르기도 함.
실제로 이 확률을 계산해보면, 총 가능성이 n개 (생일 문제에서는 n=365, 366), 사람이 m명인 경우, 이 m명이 모두 다른 확률은
이 됨. 물론 진짜 현실적으로는 모든 날짜가 같은 확률인 것이 아니라서 (2월 29일은 자명하게 확률이 낮고, 그 외에도 크리스마스에 임신하는 경우가 많아서 9월에 태어날 확률이 높다든지 하는 등의 요소로), 각 n에 따라 서로 다른 확률까지 반영하면 정말 정확하게는
라는 공식으로 쓰여질 수 있는데, 사실 여기서 산술-기하 평균 부등식의 일반화인 매클로린 부등식을 적용하면
라는 식을 얻기 때문에, 확률이 서로 다르다면 오히려 다 다를 확률은 더 작아진다는 것을 알 수 있고, 우리는 지금 역설적인 상황을 검증하고자 하기 때문에 전부 같은 확률이라고 가정해도 충분함.
여기서 n=365나 366같은 식으로 고정된 경우야 m 값을 하나하나 대입해서 확률을 계산하면 끝이지만, 여기서는 더 일반적인 상황을 위해서 이를 근사적으로 계산하는 방법에 대해서도 언급할 예정임.
우선 계산에 대해서 얘기해 둬야 할 것은, 분모 분자를 정확하게 정수로 계산하려면 숫자가 너무 커지기 때문에 좋지 않고
을 통해서 실수 계산으로 하는 것이 자연스러울 것임.
그럼 이제 근사적 예측으로 가는데, 우선 가정으로 n은 m에 비해 꽤 크다는 전제 하에서 근사 계산을 하려고 함. 가장 먼저 할 수 있는 것으로는 스털링 공식을 통해 팩토리얼을 근사하는 방법이 있음. 스털링 공식은 팩토리얼이 대략
정도가 된다는 내용으로, 이를 n! / {(n-m)! n^m} 에 대입하면 확률의 근사식으로
을 얻게 됨. 여기서 추가로 근사식 처리를 하면
라는 근사식을 얻을 수 있음.
또 다른 방법으로는
라는 방법도 있음. 여기서 추가로 1 - 1/n이 e^{-1/n} 정도인 것도 이용하면 위의 근사와 굉장히 유사한 e^{-m(m-1)/2n} 을 얻게 됨
마지막으로, 기대값을 계산하는 방법이 있음. 즉, 단순히 생일이 같은 페어가 존재하느냐, 아니냐가 아니라 그런 페어가 몇 개나 있냐를 계산하는 것임. 각 페어에 대해서 그 둘이 같은 값을 얻을 확률은 모두 1 /n이고, 따라서 이 기대값은 기대값의 선현성에 의해서 단순히 (1/n) * 페어의 개수 가되므로 이 값은
이 됨. 다시 말해서, 이 값이 서로 같은 페어의 개수의 기대값이므로, 이 값이 유의미하게 크면 같은 페어가 존재할 확률 또한 유의미한 값을 가지게 됨. 여기서 주목해야할 것은 m의 경우는 제곱에 의존한다는 것이고, 이는 위의 두 근사에서도 동일하게 나타나는 현상임.
물론 이 계산 또한 더 정밀하게 할 수 있는데, 페어의 개수가 0개인 확률, 1개인 확률, 2개인 확률 등을 다 나눠서 계산하면 됨. 여기서 페어의 개수가 0개인 확률은 이미 우리가 알고 있는 값이고, 이 확률을 P라고 하면 어렵지 않은 계산으로
1개인 확률 :
2개인 확률:
3개인 확률:
같은 식으로 계산해낼 수 있음. 여기서 n이 m보다 유의미하게 크고 대략적으로 m^2 정도의 크기라고 가정하면 3개인 확률에서 두 번째는 무시할 수 있음.
여기서 m^2 / 2n을 r이라고 하고, m또한 1보다 충분히 커서 m(m-1)을 m^2으로 근사할 수 있다고 가정하면, 1개인 확률은 대략 Pr, 2개인 확률은 대략 Pr^2/2!, 3개인 확률은 대략 Pr^3/3! 으로 나가는 것을 알 수 있음.
따라서 이 확률의 합은 Pe^r이 되고, 이는 확률의 합이므로 1이 되고 이로부터 P는 대략적으로 e^{-r}이 되는 것을 알 수 있음. 즉 이 경우에도 우리는 근사식으로
라는 근사식을 얻게됨. 추가로, 여기서 실제로 이 근사를 바탕으로 기대값을 계산해보면
라는 것 또한 얻을 수 있음. 이 기대값의 참값은 m(m-1)/2n 이므로, 어떤 관점에서 보면
쪽의 근사를 얻는다고도 볼 수 있음.
이러한 결론들로부터, 365일의 경우 23이 어디서 나왔는지 또한 쉽게 알 수 있음. 즉, 365 * 2 * log 2의 루트가 22에서 23 정도의 숫자가 나오기 때문에 생일의 경우는 23명 정도면 50% 확률로 충돌이 나타나는 것임.
이 모든 방법의 귀결은 결국 m/n의 값이 확률을 결정하지 않고, m^2 / n이 확률을 결정한다는 결론으로 이어지는 것을 볼 수 있음. 생일 역설은 바로 여기서 나오는 것으로, 실제로 이렇게 계산해보지 않으면 이 숨어있는 제곱을 느끼기 어렵기 때문에 나타나는 현상이라고 할 수 있음. 참고로 보안 이론에서 해시 함수의 경우, 계산할 수 있는 정밀도의 두 배 길이여야 한다는 것 또한 이 생일 역설과 관계가 있음. 2^256까지 계산할 수 있다면 512비트 해시의 충돌을 일으킬 수 있기 때문임.
1. 23명은 요즘 기준으로 대충 한 반 정도 되니까 대략 두 반 에 한 반 꼴로 같은 반에 생일이 같은 애가 존재함
2. 이 확률은 인원의 제곱에 의해 줄어들기 때문에 인원수가 늘어남에 따라 사람들이 상상하는 것보다 빠르게 변화함
3. 가챠겜 캐릭터 생일의 경우는 랜덤이 아니라 캐릭터 성에 날짜 맞추는 경우가 많으니 실제로 이 분석이 적용되지 않는 것 또한 알 수 있음.