생일 문제(Birthday problem)

한 반에 $n =$ 명이 있을 때 생일이 같은 두 사람이 있을 확률은 입니다. 직관보다 훨씬 큽니다. 23명이면 이미 절반을 넘고(약 50.7%), 57명이면 99%입니다. 여기서는 2월 29일을 빼고 365일이 모두 똑같이 흔하다고 가정합니다. 실제 생일은 계절에 따라 조금 몰리는데, 고르지 않으면 겹칠 확률은 오히려 더 커집니다.

"겹치는" 경우는 여러 방식이 얽혀 있어 세기 어렵습니다. 그래서 여집합⁠(complement)⁠, 곧 "모두 다를" 확률을 셉니다. 두 번째 사람은 첫 사람과 다를 확률이 364/365, 세 번째는 앞 둘과 다를 확률이 363/365, … 이를 모두 곱합니다. 각 항은 1에 가깝지만 곱해지는 항이 많아서 빠르게 작아집니다.

비밀은 짝의 수입니다. 23명 사이에는 $\binom{23}{2} = 253$쌍이 있고, 각 쌍이 겹칠 확률은 1/365입니다. 겹칠 기회가 사람 수가 아니라 쌍의 수, 곧 대략 사람 수의 제곱에 비례해 늘어나는 것입니다. 곱의 각 항에 $1 - x \approx e^{-x}$(지수함수)를 쓰면 곱이 $e^{-n(n-1)/730}$가 되어 점선과 거의 겹칩니다. 지수의 $n(n-1)/730$은 바로 쌍의 수 ÷ 365입니다. 쌍마다의 사건⁠(event)⁠이 서로 겹치므로 정확히 셈하려면 포함배제 원리⁠(inclusion–exclusion principle)⁠가 필요하지만, 여집합으로 돌아가면 그럴 필요가 없습니다.

다시 뽑기 이렇게 2000번 실험하면 겹친 비율은 계산값과 맞습니다. 사람이 366명(윤년까지 치면 367명)이면 비둘기집 원리⁠(pigeonhole principle)⁠로 확률이 정확히 1입니다. 하지만 그 훨씬 전, 칸 수의 제곱근 정도에서 겹침은 이미 흔합니다. N칸일 때 겹칠 확률이 절반이 되려면 약 $1.18\sqrt N$개만 뽑으면 됩니다(N = 365이면 22.5개). 키를 칸에 흩어 담는 해시 테이블⁠(hash table)⁠에서 두 키가 같은 칸에 떨어지는 충돌이 생각보다 훨씬 일찍 일어나는 것도 이 때문입니다.

암호에서도 중요합니다. 해시 함수⁠(hash function)⁠는 아무리 긴 데이터라도 정해진 길이(예: 256비트)의 짧은 값으로 바꾸는 함수⁠(function)⁠로, 문서의 '지문'처럼 쓰입니다. 전자 서명(RSA 서명 등)은 문서 대신 이 지문에 서명하므로, 해시값이 같은 두 문서를 찾아내면 한 문서에 받은 서명을 다른 문서에 옮겨 붙일 수 있습니다. 해시값이 b비트면 가능한 값은 $2^b$가지인데, 생일 문제 덕분에 무작위 문서를 $2^b$개가 아니라 그 제곱근인 $2^{b/2}$개쯤만 만들어 봐도 충돌하는 쌍이 약 40%의 확률로 나오고, 몇 배만 더 만들면 거의 확실해집니다. 이것이 "생일 공격⁠(birthday attack)⁠"이고, 그래서 암호에 쓰는 해시⁠(hash)⁠는 지키려는 안전성의 두 배 길이여야 합니다.

언어학에도 같은 교훈이 있습니다. 두 언어의 수많은 낱말을 짝지어 보면 우연히 소리와 뜻이 비슷한 쌍은 생각보다 많이 나옵니다. 영어 have와 라틴어 habere(가지다)는 소리도 뜻도 닮았지만 뿌리가 다른 말입니다. 그래서 두 언어가 한 조상에서 왔다고 말하려면 몇몇 닮은 낱말이 아니라, 우연으로는 설명되지 않는 규칙적인 소리 대응이 필요합니다(비교 언어학⁠, comparative linguistics⁠).