1. 개요
생일 문제( 生 日 問 題 / birthday problem, birthday paradox)는 비둘기 집의 원리의 확률 버전이라 볼 수 있는 개념이다. 366명(윤년인 경우 367명)이 모여 있는 경우 반드시 생일이 같은 쌍이 나오나, 실제로는 그보다 훨씬 적은 수로도 생일이 같은 쌍이 매우 높은 확률로 나와 발생하는 문제, 혹은 이런 '문제'가 발생할 가능성 자체를 구하는 문제를 말한다. 인간의 직감과 수학적 사실이 일치하지 않아 모순으로 인식되기도 하기에 '생일 역설'이라고도 한다.2. 방법
비둘기 집의 원리에 의하면, 어떤 집단에 367명(윤년의 2월 29일도 고려해야 하기 때문)이 있으면 생일이 같은 사람이 반드시 1쌍 이상 존재한다.[1] 물론, 비둘기 집의 원리는 100% 확률을 전제하는 것이므로, 실제로는 이보다 훨씬 적은 수로도 가능하다.사람이 n명 있을 때 생일이 같은 사람이 한 쌍이라도 있을 확률은 1에서 그 사람들이 모두 생일이 다를 확률을 빼면 된다. 계산을 단순화하기 위해 윤년은 고려하지 않는다 치면, 해당 확률은 1-(364/365)×(363/365)×…×(365-n+1/365)이다. 계산해보면 알겠지만 23명만 넘어가도 그 확률은 50%를 넘기 시작하고, 30명은 약 70%, 50명은 약 97%, 70명 쯤에서 이미 99.9%쯤 된다.
이를 일반화시켜 가능한 경우의 수가 n이고 시행 횟수가 k일 때, 생일 문제가 발생할 확률(=비둘기 집의 원리에 걸릴 확률)은 [math(1 - ({_{n}\textrm{P}_{k}}/{{n}^{k}}))]이다. 이 과정에서 [math({_{n}\textrm{P}_{k}})]가 [math({n}^{k})]를 따라잡지 못해 생일 문제가 발생하는 것이다. 실제로 [math({_{10}\textrm{P}_{10}})]은 3,628,800에 불과하지만, 10의 10제곱은 10,000,000,000이다. 충분히 큰 숫자를 넣지 않았는데도 자릿수에서 크게 차이가 나는 것이다.
3. 원인
이러한 수학적 사실이 '모순'으로 인식되는 원인은 확증편향에 있다. 즉, 확률을 평가할 때에는 (편향을 고려하지 않는) 수학적 사실만으로 접근해야 하는데, 알게 모르게 '자기 중심'으로 평가하는 성향 때문에 '모순'이 발생한 것처럼 보이는 것뿐이다. 즉, 사람들의 통념으로는 n명이 모였을 때 생일 문제를 따지는 횟수(경우의 수)는 [math(n-1)], 다시 말해 [math(\mathcal{O}({n}))]이라 착각하기 쉬운 것이다.물론 n명이 모였을 때 "자신"이라는 1명의 사람과 다른 사람들의 생일이 같은 확률은 [math({(n-1)}/{366})]인지라 얼핏 보면 그럴싸한 논리이긴 하지만, 이건 '나머지 사람들 중에 생일이 서로 같은 자가 나오질 않았을 때'에나 성립하는 조건부확률이다. 다시 말해, 실제로는 그 '나머지 사람들'을 감안해 경우의 수를 [math(_{n}\textrm{C}_{2})] 또는 [math(\mathcal{O}({n}^{2}))]으로 계산해야 한다.[2] 이 때문에 자신의 생일을 미처 따지기도 전에 나머지 사람들 사이에서 생일이 겹칠 가능성이 큰 것이고, 이에 따라 자신의 경우를 따지기도 전에 부질없는 일로 전락하게 된다.
뿐만 아니라 규모 n의 집단에서 나올 수 있는 경우의 수가 [math(\mathcal{O}({n}^{k}))]인 문제에 대해, k > 1인 경우에는 무조건 생일 문제가 적용된다. 단지 k = 2인 1:1 비교의 사례가 많은 것뿐이며, k ≤ 1이어야만 생일 문제가 적용되지 않는다 말할 수 있다. 같은 이유로 [math(\mathcal{O}({2}^{n}))]인 문제에는 생일 문제가 적용되며, 반대로 [math(\mathcal{O}(\log{n}))]에는 생일 문제가 적용되지 않는다.
4. 확률 문제로 확장
[math({{(n - k)}/{n}})]는 [math(1 - {k}{n}^{-1})]로 쓸 수 있으며, 이는 다시 [math(1 - _{k}\textrm{C}_{1}{n}^{-1})] 꼴로 바꿀 수 있다. 또한 이 값은 [math(1 - _{k}\textrm{C}_{1}{n}^{-1} + \mathcal{O}({n}^{-2}))]보다는 작기에, [math(n)]이 충분히 크면 [math({(1 - {n}^{-1})}^{k})]로 근사하는 것도 가능하다. 따라서 생일 문제는 [math({(1 - p)}^{k})] 꼴로 바뀌는 확률 문제로도 환원된다. 근사시킨 쪽이 오히려 더 크기에, 생일 문제가 일어날 확률의 하한을 구하는 데에도 적합하다.이에 따라, 2명이 모였을 때 생일 문제에 걸릴 확률을 [math(p)]로 가정했을 때, [math(n)]명이 모였을 때 생일 문제에 걸리지 않을 확률은 [math((1-p))]를 0회, 1회, 2회, …, [math((n-1))]회 곱하는 식으로 계산해도 된다.[3] 즉, [math(n)]명이 모였을 때 생일 문제에 걸릴 확률은 대강 [math(1 - {(1 - p)}^{_{n}\textrm{C}_{2}})]가 된다.
또한 위 식의 값을 [math(x)]놓고 보면 [math(1 - x = {(1 - p)}^{_{n}\textrm{C}_{2}})] 꼴이 되는데, [math({_{n}\textrm{C}_{2}} = \textrm{log}{(1 - x)} / \textrm{log}{(1 - p)})]으로 유도할 수 있다. [math({_{n}\textrm{C}_{2}})]는 대강 [math({{n}^{2}}/{2})]이니 이를 다시 풀면 [math(n = \sqrt{{2}\times\textrm{log}{(1 - x)} / \textrm{log}{(1 - p)}})] 꼴이 되며, 이를 이용해 발생 확률을 토대로 최소 인원을 구하는 것도 가능하다.
5. 예시
아래에서 다루는 예시는 보다 정확하게는 복잡계 이론의 예시에 가깝다. 그러나 '특정 사건이 일어날 확률'을 중점에 두어 생일 문제로 환원할 수는 있다.5.1. 대전 격투 게임의 밸런싱
대전 격투 게임의 밸런스 조정이 복잡한 것도 이 생일 문제와 연관이 있다. MMORPG, AOS와는 달리 유래가 깊은 장르인데다 이미 90년대에 대다수 제작사들이 제작에 뛰어들다 도로 철수한 바 있기 때문이다. 대한민국 아케이드 게임 제작사들이 잘해봐야 슈팅 게임을 제작했던 것도, 빅콤이 겨우 왕중왕으로 승부를 본 것도 이 때문이었다.실제로 캐릭터가 8명 정도로 얼마 안 되는 경우는 미러전을 제외한 밸런스 경우의 수가 28개로 얼마 되지 않지만, 이게 12명만 되어도 66개가 되어 복잡도가 1.5배가 아닌 최소 2.25배로 증가한다. 또한 캐릭터간 상성을 맞추기 위해서는 테스트를 거쳐야 했는데, 복잡도가 걷잡을 수 없이 증가하니 점점 밸런스를 맞추기 어려워진다. 때문에 대다수 격투 게임들은 비인기 캐릭터를 불참시키면서라도 어떻게든 밸런스를 맞춰야 했다. 스트리트 파이터 시리즈가 대표적으로 이런 사례에 해당하는데, 넘버링이 바뀌면 우선 소수 캐릭터로 시작하여 밸런스를 다지고, 그 이후 캐릭터를 점차 추가하는 방식을 취하고 있다.
또 다른 대표적인 사례로 KOF 94는 24명(+ 선택 불가 1명)의 캐릭터가 있었는데도 3인 1팀 구성을 통해 8팀으로 압축하여 밸런스를 맞출 수 있었으나, 이게 풀린 KOF 95부터는 만성적인 밸런싱 실패에 시달리고 말았으며, 급기야 KOF XII에 와서는 캐릭터 수가 20명으로 줄어들기도 했다. 반면 슈퍼 스매시브라더스 얼티밋은 캐릭터 수가 85명이나 되는데도 밸런스를 어느정도 맞췄다는 점에서 호평을 받았다.
MMORPG, AOS 역시 생일 문제에 따른 밸런스 조정이 복잡한 장르이며, 그래서 이들 게임의 운용 역시 어려운 편에 속한다. 특히 오랫동안 서비스되는 게임들에서 이러한 문제가 두드러지는데, 지속적으로 밸런스를 맞춰 여전한 인기를 얻고 있는 게임이 있는 반면, 밸런스 조정에서 사실상 손을 놓아 막장 운영으로 치달은 게임도 있다.
5.2. 암호학에서
암호학에서도 생일 문제는 중요한 문제로 작용한다. 특히 해시 알고리즘에서 중요하게 다루고 있는데, 365 대신 해시 알고리즘의 결과 값으로 나올 수 있는 경우의 수를 넣어 주면 된다. 출력이 n비트인 해시 함수는 그 경우의 수가 [math(2^n)]이 되는데, 실제로는 그보다 훨씬 적은 [math(\mathcal{O}({2}^{n/2}))] 선에서 충분히 해시 충돌을 찾을 수 있다.[4] 이를 생일 공격( 生 日 攻 擊, birthday attack)이라고 한다.이러한 문제는 엉뚱하게도 채굴기 때문에 부각되고 있는데, 비트코인을 비롯한 다수 블록체인이 해시 함수를 온갖 증명에 이용하고 있기 때문이다. 즉, 채굴기의 성능이 좋아지거나 채굴기를 여러대 두는 식으로 해시 고갈 속도가 빨라지면, 그에 비례해 해시 충돌 가능성이 높아지게 된다. 물론 순수하게 브루트 포스로 깨는 것이긴 하지만, 채굴기 물량을 생각하면 결코 만만하게 볼 일이 아니다.
5.3. 사회적 거리두기
사회적 거리두기, 그중에서도 사회적 거품(5인 이상 집합 금지 등)이 필요한 이유를 이 논리로 설명할 수 있다. 집단 감염 문제 역시 사람들의 통념과 수학적 사실이 일치하지 않기 때문이다. n명이 집합했을 때 전파 가능한 경우의 수는 [math(\mathcal{O}({n}))]이라 착각하기 쉽지만, 이 역시 실제로는 [math(\mathcal{O}({n}^{2}))]이다. 때문에 집단 감염 문제 역시 생일 문제로 환원된다.2021년 3월 24일의 대한민국의 코로나-19 누적 확진률 1.40%(약 1/70) 기준으로, 4명이 집합했을 때 집단 감염이 발생할 확률은 8.11%에 불과하지만, 1명만 추가되어도 확률은 5%p 넘게 뛰며(13.15%) 11명이 모인 경우에는 50%를, 27명이 집합했을 때에는 99%를 초과한다. 게다가 일단 전파가 시작되면 의도치 않게 p 값 자체가 상승해 재전파 가능성 역시 커지게 되며, 결국 해당 모임 전체가 집단 감염될 수 있다. 구체적으로는 아래와 같은데, 예상보다 훨씬 적은 인원으로도 충분히 집단 감염이 발생할 수 있음을 알 수 있다.
| 전파 확률 | 0% | 50% | 99% | 6-나인[5] | 1/확률 밀집 시 n- 나인 | 비고 (2021년 3월 24일 기준) | |
| 1.400% | 약 70명 중 1명 | 1명 | 11명 | 27명 | 45명 | 15 나인 | 누적 검사수 대비 확진률 |
| 0.261% | 약 383명 중 1명 | 24명 | 60명 | 103명 | 83 나인 | 수도권 무증상 확진률 | |
| 0.020% | 약 5,000명 중 1명 | 84명 | 215명 | 372명 | 1,085 나인 | 전체 인구수 대비 확진률 | |
| 0.012% | 약 8,300명 중 1명 | 108명 | 278명 | 480명 | 1,809 나인 | 전체 인구수 대비 실질 확진자 비율 | |
이는 마스크 착용이나 손씻기, 집합 시간, 환자 완치 등을 고려하지 않은 단순 계산일 뿐이지만, 같은 조건 하에서는 밀집도를 줄이는 것이 바람직하다는 것을 의미한다.[6] 3밀(밀폐·밀집·밀접) 환경에서 집단 감염이 빈번하게 발생하는 것도 이 때문이고, 밀폐·밀접은 아니지만 밀집 환경인 지하철에서 감염될 우려가 제기되었던 것도, 대중교통 이용 시 마스크 착용이 의무화됐던 것도 이 때문이다. 또한 혼자 있는 경우나 비대면 진행인 경우에는 [math({_{1}\textrm{C}_{2}})]의 값 자체가 0이기 때문에 (환경 자체가 바이러스에 오염되어 있지 않은 한) 가장 안전하다.
6. 관련 문서
- 비둘기 집의 원리
-
로또 조작설 - 인간의 편향과 수학적 사실이 일치하지 않아 '모순'으로 인식되는 또 다른 사례.
내가 로또에 당첨 될 가능성이 현저히 낮기 때문에 타인이 로또에 당첨될 시 의심하게 되는 사례로,
'나'를 기준으로 생각하는 성향과 수학적인 확률이 맞아 떨어지지 않기 때문에 발생함.
[1]
반대로 1년 중에서 하루도 빠짐없이 모든 날짜에 생일자가 있을 경우는 확률이 0%가 아니다.
[2]
앞서 23명의 예를 들면, 사람의 통념으로는 22번 비교하면 된다 생각하기 쉽지만 실제로는 253번을 비교해야 한다. 여기서 1명만 늘어도 비교 횟수는 23회 늘어난다.
[3]
혼자 있을 때엔 생일 문제 자체가 성립하지 않으므로, 1 ~ n 범위가 아닌 0 ~ (n-1) 범위로 곱해야 한다. 당장 위에서도 1에서 시작했듯이 말이다.
[4]
[math({2}^{n/2})]개 입력에서는 약 36.7%, [math({2}^{n/2+1})]개 입력에서는 약 60.0%의 확률로 충돌이 발생한다.
[5]
집단 감염이 발생하지 않을 확률이 1백만 분의 1 이하임을 의미, 방역 활동 없이는 전파가 확정적으로 일어난다는 의미이다.
[6]
더불어 백신 접종과 방역 수칙 준수는 1:1 전파 확률 자체를 줄여준다.