생일 문제

생일 문제는 무작위로 뽑은 값들이 언제부터 서로 겹치기 시작하는지를 알려 줍니다. 한 해는 365일인데 사람 스물세 명만 모이면 생일이 같은 두 사람이 있을 확률이 절반을 넘습니다. 겹침이 직관보다 훨씬 이르게 온다는 뜻이라 생일 역설이라고도 부릅니다.

상세

동창회에 스물세 명이 모였다고 해 봅시다. 사회자가 "제 생일과 같은 분 계세요" 하고 물으면 대개 아무도 손을 안 듭니다. 그런데 "여기 생일이 같은 두 분이 계신가요"로 질문을 바꾸면 절반이 넘는 확률로 손이 올라옵니다. 두 질문은 비슷하게 들리는데 답은 여덟 배 넘게 벌어집니다. 생일 문제는 이 벌어짐이 어디서 오는지를 다룹니다.

무엇을 묻는 문제인가

생일 문제는 가짓수가 N인 값에서 k개를 무작위로 뽑았을 때 그중 같은 값이 두 개 이상 나올 확률을 묻습니다. 생일이라면 가짓수 N은 365이고, 방에 있는 사람 수가 k입니다. 가짓수 365에 사람 23명을 넣은 답이 0.5073입니다.

전제가 둘 붙습니다. 사람마다 생일을 서로 상관없이 고른다는 것, 그리고 365일에 고르게 흩어져 있다는 것입니다. 이 전제가 깨지면 답이 어떻게 움직이는지는 아래 「전제가 깨질 때」에서 봅니다.

세는 법과 실제 값

겹칠 확률을 바로 세면 경우가 너무 많이 갈립니다. 그래서 반대쪽인 "아무도 안 겹칠 확률"을 먼저 구하고 1에서 뺍니다. 첫 사람은 아무 날이나 골라도 되고, 둘째 사람은 앞사람과 다른 364일 가운데 골라야 하고, 셋째 사람은 363일 가운데 골라야 합니다.

p(k) = 1 − (365/365) × (364/365) × (363/365) × … × (365−k+1)/365

이 식을 그대로 돌린 값입니다.

절반을 넘는 경계가 스물세 명입니다. 스물두 명까지는 0.4757로 절반에 못 미치고, 한 사람이 더 들어오는 순간 0.5073이 됩니다.

왜 역설이라 부르나

직관은 대개 이렇게 답합니다. 생일이 놓일 칸이 365개니까 절반쯤 채우려면 180명은 있어야 하지 않겠느냐고요. 여기서 말하는 칸은 앞에서 쓴 가짓수 N을 하나씩 센 것이라 둘은 같은 말입니다. 실제로 180명을 모으면 겹칠 확률은 절반이 아니라 사실상 1입니다. 절반이 되는 지점은 그 여덟 분의 일에 가까운 스물세 명입니다.

이 어긋남은 계산이 이상해서 생기는 것이 아닙니다. 사람들이 머릿속에서 다른 질문에 답하기 때문입니다. 먼저 떠오르는 질문은 "나와 생일이 같은 사람이 있는가"입니다. 그 질문의 답은 실제로 낮습니다. 스물세 명 방에서 나와 생일이 같은 사람이 있을 확률은 0.0586이고, 이 확률이 절반을 넘으려면 나 말고 253명이 더 있어야 합니다.

생일 문제가 묻는 것은 "아무 두 사람의 생일이 같은가"입니다. 기준이 되는 사람이 따로 없고, 방 안의 모든 짝을 다 봅니다. 나를 기준으로 스물두 번 맞춰 보는 일과, 짝을 지어 253번 맞춰 보는 일은 애초에 크기가 다른 일입니다.

위 두 문단에 나온 253명과 253쌍이 같은 수인 것은 우연이 아닙니다. 확률 1/365짜리 맞춰 보기를 몇 번 하면 "한 번은 맞는다"가 절반을 넘는가, 그 답이 253번입니다. 앞의 질문은 그 맞춰 보기가 사람 수만큼 있고, 뒤의 질문은 짝 수만큼 있습니다. 같은 253번을 사람으로 채우느냐 짝으로 채우느냐가 두 질문의 차이입니다.

flowchart TD
    S1["질문 하나 · 나와 생일이 같은 사람이 있나"]
    S1 --> A["나를 기준으로 세운다"]
    A --> B["나머지 22명과 하나씩 맞춰 본다"]
    B --> C["맞춰 보는 횟수 22"]
    S2["질문 둘 · 아무 두 사람의 생일이 같나"]
    S2 --> D["기준이 되는 사람이 없다"]
    D --> E["스물세 명을 두 명씩 짝지어 맞춰 본다"]
    E --> F["맞춰 보는 횟수 253"]

논리에 모순이 있는 것이 아니라 직관 쪽이 틀린 것뿐입니다. 여기서 "역설"은 계산이 이상하다는 뜻이 아니라 답이 직관과 어긋난다는 뜻입니다.

짝의 개수가 제곱으로 는다

사람이 n명이면 두 사람의 짝은 n(n−1)/2개입니다. 사람 하나가 늘 때 짝은 그 자리에 이미 있던 사람 수만큼 늘어나므로, 사람은 한 줄로 느는 동안 짝은 제곱에 가깝게 붙습니다. 스물세 명이면 짝은 253쌍입니다.

짝 하나가 겹칠 확률은 1/365입니다. 짝이 253개면 겹치는 짝의 기대 개수는 253/365, 곧 0.6932가 됩니다. 여기서 기대값은 "평균 몇 쌍이 겹치겠는가"를 뜻합니다.

기대 개수는 아직 확률이 아닙니다. 평균 0.6932쌍이 겹친다는 말과 겹칠 확률이 얼마라는 말은 다른 말이라, 사이에 한 걸음이 더 필요합니다. 짝 하나가 안 겹칠 확률은 1 − 1/N이고, 짝이 m개면 아무 짝도 안 겹칠 확률은 그 값을 m번 곱한 것입니다. N이 크면 이 곱은 e^(−m/N)에 가까워집니다. e는 자연로그의 밑으로 쓰는 상수로 대략 2.718이고, 아주 작은 확률을 아주 여러 번 되풀이하는 자리에서 이런 꼴로 나타납니다. 짝끼리 완전히 서로 무관한 것은 아니라서 이 값은 어림값입니다만, N이 크면 어긋남이 작습니다.

짝의 개수              m = k(k−1)/2
겹치는 짝의 기대 개수    m/N = k(k−1)/(2N)
아무 짝도 안 겹칠 확률   ≈ e^(−k(k−1)/(2N))
적어도 한 쌍이 겹칠 확률  p ≈ 1 − e^(−k(k−1)/(2N))

e의 지수 자리에 들어간 것이 곧 기대 개수라는 점이 이 식의 전부입니다. 기대 개수가 0.6931쯤이면 e^(−0.6931)이 0.5000이 되고, 겹칠 확률도 0.5000이 됩니다. 스물세 명의 기대 개수 0.6932가 바로 그 자리라 확률이 절반을 갓 넘습니다. 식에 넣으면 1 − e^(−0.6932) = 0.5000이 나오고, 앞에서 하나씩 곱해 정확히 센 0.5073과 소수 첫째 자리까지 맞습니다.

제곱근 규칙

어림식을 보면 위험해지는 지점이 어디인지가 드러납니다. e의 지수에 든 것이 대략 k²/2N이므로, k가 N의 제곱근 근처가 되면 지수가 1/2 근처가 됩니다.

flowchart TD
    A["가짓수 N 에서 k 개를 뽑는다"] --> B["맞춰 볼 짝의 개수 = k(k−1)/2"]
    B --> C["짝 하나가 겹칠 확률 = 1/N"]
    C --> D["겹치는 짝의 기대 개수 = k²/2N"]
    D --> E["k 가 N 의 제곱근이면 기대 개수 = 1/2"]
    E --> F["겹칠 확률 = 1 − e^(−1/2) = 0.3935"]

k가 N의 제곱근과 같으면 확률은 1 − e^(−1/2), 곧 0.3935입니다. 가짓수의 제곱근만큼만 뽑아도 겹칠 확률이 이미 열에 넷이라는 뜻입니다. 확률이 정확히 절반이 되는 지점은 그보다 조금 뒤인 k ≈ 1.1774 × √N 입니다. 가짓수 365를 넣으면 22.49가 나오고, 사람은 정수로만 세니 스물세 명이 됩니다. 위 표에서 경계로 잡힌 것과 같은 지점입니다.

그래서 이 문제의 결론은 한 줄로 줄어듭니다. 첫 겹침은 전체 가짓수 N이 아니라 대략 √N 근처에서 나옵니다.

칸보다 많이 뽑으면 반드시 겹친다는 것은 비둘기집 원리입니다. 그건 N+1개를 뽑았을 때의 이야기입니다. 생일 문제는 그 훨씬 앞, 칸이 아직 거의 비어 있을 때 이미 겹치기 시작한다는 것을 말합니다.

해시에서 나타나는 자리

해시 함수는 길이가 제각각인 입력을 받아 정해진 길이의 값 하나로 줄이는 함수입니다. 서로 다른 두 입력이 같은 출력으로 줄어드는 것을 해시 충돌이라고 부릅니다. 출력이 n비트면 나올 수 있는 값은 2^n가지이고, 그 값들을 뽑는 일에 생일 문제가 그대로 얹힙니다.

아래쪽처럼 겹치는 한 쌍을 찾아내는 것을 생일 공격이라고 부릅니다. 찾는 쪽은 특정한 값을 맞힐 필요가 없고 자기가 만든 값들끼리 겹치기만 하면 되므로, 방 안의 모든 짝을 세는 쪽 계산을 씁니다.

"충돌 저항이 b비트다"라는 말은 충돌 한 쌍을 찾는 데 2^b번쯤 시도해야 한다는 뜻입니다. 그래서 출력이 n비트인 해시 함수의 충돌 저항은 n비트가 아니라 n/2비트입니다. 출력이 128비트여도 충돌을 찾는 데 드는 시도는 2^128이 아니라 2^64 근처라는 말입니다. 서명이나 무결성 검사처럼 아무 두 개가 겹치기만 해도 곤란한 자리에서는 이 절반 값을 기준으로 자릿수를 잡습니다.

자릿수를 정하는 근거

무작위 값을 여러 개 뽑아 이름표로 쓰는 설계는 전부 이 계산으로 자릿수를 정합니다. 기준은 값의 가짓수가 아니라 그 제곱근입니다.

솔트가 그런 자리입니다. 사용자마다 무작위 값을 하나씩 뽑아 붙여 두는 물건이라, 두 사용자의 솔트가 같아지면 그 둘에 대해서는 솔트를 붙인 뜻이 옅어집니다. 솔트가 64비트라면 안심할 수 있는 구간은 2^64명이 아니라 2^32명입니다.

UUID(Universally Unique Identifier, 범용 고유 식별자)처럼 무작위로 뽑아 붙이는 식별자도 같습니다. "고유"라는 이름은 겹치지 않도록 자릿수를 크게 잡았다는 뜻이지 겹치지 않는다는 뜻이 아닙니다.

짧은 주소를 만들 때 해시값의 앞 몇 글자만 잘라 쓰는 방식도 여기 걸립니다. 16진수 여섯 자를 쓰면 가짓수는 16,777,216입니다. 그 제곱근은 4,096이고, 5,000개만 넣어도 어느 두 개가 겹칠 확률이 0.5253입니다. 넣은 5,000개는 칸 16,777,216개를 3,355로 나눈 만큼이니, 칸이 3,355개에 하나꼴로만 찼는데 겹칠 확률은 이미 절반을 넘는 셈입니다.

겹침을 다루는 길은 둘입니다. 하나는 자릿수를 늘리는 것입니다. 무작위 비트를 두 배로 늘리면 걱정 없이 뽑을 수 있는 개수는 제곱이 됩니다. 다른 하나는 겹쳤을 때 알아채는 장치를 두는 것입니다. 넣기 전에 이미 있는 값인지 조회하거나, 저장소에 유일 제약을 걸어 두 번째 값이 들어올 때 오류가 나게 합니다. 확인 없이 그냥 넣으면 겹친 값이 앞의 것을 소리 없이 덮어씁니다.

전제가 깨질 때

이 계산은 값이 고르게 흩어져 있고 한 번 뽑는 것이 다른 뽑기에 영향을 주지 않는다는 전제 위에 섭니다. 실제 생일은 고르게 흩어져 있지 않아서 어느 날에 몰립니다. 몰림이 있으면 겹칠 확률은 오히려 올라갑니다.

무작위 값도 마찬가지입니다. 난수 발생기가 좁은 범위만 내놓거나 같은 상태에서 다시 출발하면 겹침은 √N보다 훨씬 이르게 옵니다. 고른 분포를 전제로 계산한 값은 그래서 가장 낙관적인 쪽의 값이고, 실제 겹침은 그보다 이르면 일렀지 늦지 않습니다.

관련 항목

생일 문제가 자릿수 근거가 되는 설계 요소

솔트 · UUID · 세션 식별자 · 액세스 토큰 · 기본 키 · 캐시 키 · URL 단축기

겹침이 실제로 터졌을 때 나는 오류

해시 충돌 · 충돌 해소 · 유일 제약 · 중복 키 · 데이터 유실

제곱근 규칙을 파고드는 공격과 그 대상

생일 공격 · 해시 함수 · 충돌 저항성 · 전자 서명 · 메시지 인증 코드 · 무차별 대입 공격 · 레인보우 테이블

이 확률을 세울 때 쓰는 수학 도구

비둘기집 원리 · 기대값 · 여사건 · 조합 · 균등 분포 · 독립 시행

겹칠 값을 뽑아 주는 무작위 장치

난수 발생기 · 유사난수 함수 · 엔트로피 · 암호학적 난수 발생기

겹침을 피하려고 무작위 대신 쓰는 발급 방식

자동 증가 · 일련번호 · 스노우플레이크 · 중앙 발급기

겹침 확률이 성능으로 드러나는 저장 구조

해시테이블 · 블룸 필터 · 인덱스 · 샤딩 · 일관성 해싱