생일 문제(생일 역설) 계산기

생일 역설 계산기 쉽게 이해하기 — 개념과 원리

생일 역설 계산기는 k명이 모인 자리에서 생일이 같은 사람이 적어도 한 쌍 있을 확률을 구합니다. 23명만 모여도 그 확률이 50%를 넘는다는 결과는 많은 사람을 놀라게 합니다. 같은 원리는 해시 함수의 충돌 위험, 무작위 ID 생성, 복원추출에서 중복이 생길 가능성을 따질 때도 쓰입니다.

계산 방법

1. 모든 사람의 생일이 다를 확률은 P(일치 없음) = (d/d) × ((d − 1)/d) × ((d − 2)/d) × … × ((d − k + 1)/d)입니다. 곧 i = 0부터 k − 1까지 (1 − i/d)를 모두 곱한 값이며, d는 1년의 날수(기본 365)입니다.
2. P(적어도 두 명 일치) = 1 − P(일치 없음)이고, 백분율로도 보여 줍니다.

사람 수가 날수보다 많으면 비둘기집 원리에 따라 반드시 겹치므로 곱이 0이 됩니다.

원리

반대 사건을 세는 편이 훨씬 쉽습니다. 첫 사람은 아무 날이나 되고, 둘째 사람은 하루를, 셋째 사람은 이틀을 피해야 합니다. 이렇게 줄어드는 확률을 모두 곱하면 모두 다를 확률이 나옵니다. 결과가 역설처럼 느껴지는 것은 사람들이 '나와 같은 생일'만 떠올리기 때문인데, 실제로는 어느 두 사람이든 겹치면 됩니다. 23명이면 짝이 23 × 22 ÷ 2 = 253쌍이고 각 쌍이 겹칠 확률은 1/365입니다. 근사식 P(일치) ≈ 1 − e^(−k(k−1)/(2d))도 자주 씁니다.

예제 풀이

1. 입력값: 23명, 365일입니다.
2. P(일치 없음) = 365/365 × 364/365 × … × 343/365 ≈ 0.49270입니다.
3. P(적어도 두 명 일치) = 1 − 0.49270 ≈ 0.5073, 곧 50.73%입니다.
4. 근사식으로 확인하면 1 − e^(−253/365) ≈ 0.500으로 정확한 값과 가깝습니다.

결과 해석

확률은 빠르게 커져 10명이면 약 11.7%, 30명이면 70.6%, 50명이면 97.0%, 70명이면 99.9%입니다. 반면 23명 가운데 누군가가 '내 생일'과 같을 확률은 약 6%에 불과합니다. 컴퓨터 분야에서는 가능한 값이 N개인 해시에서 대략 √N개쯤부터 충돌이 나타나기 시작한다는 뜻으로 해석합니다.

흔한 실수

• '아무 두 사람이 같을 확률'과 '누군가가 나와 같을 확률'을 혼동하는 경우
• 50%가 되려면 365의 절반인 183명이 필요하다고 생각하는 경우
• 결과를 '정확히 한 쌍'의 확률로 읽는 경우(적어도 한 쌍입니다)

자주 묻는 질문

99% 확률이 되려면 몇 명이 필요한가요?

57명이면 약 99.0%입니다.

2월 29일을 넣으면 결과가 달라지나요?

거의 달라지지 않습니다. 날수를 366으로 바꿔 보면 23명에서 여전히 약 50%입니다.

암호학의 생일 공격이란 무엇인가요?

같은 확률 원리를 이용해 정해진 해시 하나를 맞히는 것보다 훨씬 빨리, 해시값이 같은 두 입력을 찾아내는 공격입니다.

출처: Feller, W., An Introduction to Probability Theory and Its Applications, Vol. 1 (Wiley) · Ross, S. M., A First Course in Probability (Pearson)