생일 역설

역설

사람들에게 파티에 손님이 몇 명 있어야 생일이 같은 두 사람이 있을 가능성이 높은지 물으면, 대부분 365의 절반인 180명쯤이라고 답합니다. 진짜 답은 23명이고, 이때 확률은 50.7%입니다. 손님이 57명이면 99%입니다. 이것을 역설이라고 부르는 것은 모순이어서가 아니라, 우리의 직관과 너무나 크게 어긋나기 때문입니다.

직관이 틀리는 이유

방 안에서 우리는 무의식적으로 자신을 기준으로 생각합니다. 나와 생일이 같은 사람이 있을 확률은 얼마일까? 1년이 365일이니 그 확률은 작습니다. 하지만 이 역설은 특정한 한 사람과 일치하는지가 아니라 방 안에서 만들 수 있는 모든 쌍에 관한 것입니다. A와 B, B와 C, A와 C 등입니다. 23명이면 서로 다른 쌍을 253개 만들 수 있고, 어느 쌍이든 생일이 같을 수 있습니다.

쌍은 제곱으로 늘어난다

n명은 n × (n − 1) / 2쌍을 이룹니다. 10명은 45쌍, 23명은 253쌍, 57명은 1,596쌍, 100명은 4,950쌍입니다. 각 쌍의 생일이 같을 확률은 1/365이므로, 253쌍이면 생일이 같은 쌍이 평균 253/365 ≈ 0.69쌍입니다. 인원을 두 배로 늘리면 쌍은 대략 네 배가 되고, 그래서 생일이 같을 확률이 급격히 올라갑니다.

단계별 계산

가장 쉬운 방법은 아무도 생일이 같지 않을 확률을 구해 100%에서 빼는 것입니다. 첫 번째 사람은 아무 날이나 차지합니다. 두 번째 사람이 첫 번째 사람과 생일이 같지 않을 확률은 364/365입니다. 세 번째 사람이 앞의 두 사람과 다를 확률은 363/365이고, 이런 식으로 계속됩니다. 23명이면:

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49.3%

모두의 생일이 다를 확률이 49.3%이므로, 그 여사건인 '생일이 같은 사람이 적어도 한 쌍 있음'의 확률은 100% − 49.3% = 50.7%입니다.

나와 생일이 같은 사람

누군가 여러분과 생일이 같을 확률은 다른 질문입니다. 나머지 n − 1명은 각각 364/365의 확률로 여러분의 생일을 비켜 가므로, 누군가 여러분과 생일이 같을 확률은 1 − (364/365)ⁿ⁻¹입니다. 23명이면 겨우 5.9%이고, 50%를 넘으려면 다른 사람이 253명 있어야 합니다. 23명 그룹의 253쌍 중 여러분이 포함된 쌍은 22쌍뿐입니다.

제곱근 법칙과 생일 공격

똑같이 일어날 수 있는 값이 N개라면, 약 1.2 × √N번 뽑은 뒤에 중복이 생길 가능성이 높아집니다. √365 ≈ 19이고, 1.2 × 19 ≈ 23입니다. 이것은 컴퓨터 보안에서 아주 중요합니다. 공격자는 생일 공격으로 암호학적 해시가 같은 두 입력, 즉 충돌을 찾습니다. 예를 들어 디지털 서명을 위조하기 위해서입니다. 생일 역설 덕분에 필요한 시도 횟수는 직관이 말하는 것보다 훨씬 적어서, 128비트 해시라면 2¹²⁸번이 아니라 약 2⁶⁴번입니다. 그래서 SHA-256 같은 현대 해시는 출력이 깁니다.

PictorX에서 살펴보기

생일 역설을 열면 23명의 그룹이 한 명씩 원 위에 모입니다. 새로 온 사람은 이미 있는 모든 사람과 선으로 이어지고, 설명 문구가 쌍의 수를 셉니다. 사람들의 생일은 달력 위로 떨어지고, 생일이 두 개 이상 겹친 날이 밝게 빛납니다. 아래에는 그 인원수에 대한 계산과, 테스트한 그룹 중 생일이 같은 사람이 있었던 비율이 나란히 나오고, 차트는 모든 인원수에 대해 생일이 같은 두 사람이 있을 확률과 나와 생일이 같은 사람이 있을 확률을 보여 줍니다. 사람을 한 명씩 추가하거나, 2명에서 366명까지 고르거나, 초당 최대 10,000개 속도로 최대 100,000개 그룹을 테스트하거나, 모든 인원수를 테스트하며 점들이 곡선을 그려 가는 모습을 지켜보세요.