생일 역설 ( Brithday Paradox )

생일 역설 혹은 생일 문제 ( Link ) 로 알려진 유명한 문제에 대한 고찰을 해보려고 한다. 나도 꽤 옛날에 접했던 문제였음에 불구하고 당시엔 대수롭지 않게 넘겼었다. 이 내용이 전산학에서도 쓰일 수 있단걸 오늘에서야 깨달았다. 반성해야지...

...

반성 끝. 이제 글을 쓰자.

---

우선 생일 역설에 대한 해설을 잠깐 쓰겠다. 우리가 살다보면 생일이 같은 사람을 꽤 자주 마주치게 된다. 2/29 를 제외하고서 365일이나 되는 날들 중에 하필 생일이 같은 사람을 마주치면 네잎클로버를 본 듯 기분 좋은 하루가 되기도 한다. 단순히 생각해보면 굉장히 낮은 확률로 마주칠 것 같은데 살면서 꽤 자주 목격하는 일이 되는 이 현상을 설명하기 위해 글을 쓰게 되었다.

문제에서 잠깐 벗어나서 잠시 생각해보자. 생일이 동일한 사람이 한 쌍 이상 존재하기 위해 최소한 몇 명이 필요한가? 비둘기 집의 원리 ( Link ) 를 안다면 아주 쉽다. 365일, 하루하루를 비둘기 집으로 생각해서 하나씩 끼워맞추다보면 366마리의 비둘기가 있을때 적어도 한 집 안에 두 마리의 비둘기가 들어간다. 즉 366명이 있다면 무조건, 100% 한 쌍 이상은 생일이 같아진다.

다시 생일 역설 문제로 돌아와서, 몇 명이 모이면 생일이 동일한 사람이 나올 확률이 50%를 넘어갈까? 그냥 느낌상, 100%였을때가 366명이니까 한 183명 정도 있으면 50%가 될 것 같다. 실상은 그렇게 많이도 필요없다. 23명만 있으면 된다. 심지어 50명이 모이면 97%를 넘어간다.

23명 이상 모이면 생일이 같은 사람이 존재할 확률이 1/2을 넘어간다

어떻게 이런 일이 일어날 수 있는지 수학적으로 확률 계산을 해보면 쉽게 납득할 수 있다. 어떤 사건이 일어날 확률을 p라고 하면 그 사건이 일어나지 않을 확률은 1-p 이다. 이와같이 여사건 ( 원하는 사건의 반대 ) 이 일어날 확률을 계산해서 1에서 빼는 식으로 접근하면 이번 문제를 손쉽게 정복할 수 있다. 생일이 같은 사람이 있을 확률을 구하는 과정이기에 여사건은 생일이 모두 다른 사람으로 이루어진 그룹이 존재해야하는 것이다.

만약 2명만 있는 그룹에서 생일이 서로 다를 확률은 어떻게 될까? 첫 번째 사람이 임의의 하루를 생일로 가지고 있을테니 두 번째 사람은 그 날만 제외하고 나머지 날을 생일로 가지면 된다. 즉 두 번째 사람은 365일 중에 364일이 선택 가능한 날짜가 된다. 365*364/(365^2)인 것이다. 3명이 있는 그룹도 생각해보자. 첫 번째 사람이 이미 고른 날짜를 두 번째 사람은 고르면 안되고, 세 번째 사람은 앞선 두 명과 겹치면 안된다. 즉 세번째 사람은 365일 중 363일을 선택할 수 있어서 365*364*363 / (365^3) 이다. n명이 있는 그룹으로 확장할 수 있다. 365일 중에 n일의 서로 다른 날짜를 순서대로 고르면 된다. 365*364*363*362*...*(365-n) / (365^n) 이다. 이를 프로그래밍 코드로 옮겨서 확인해보자.

---

def prob( n ):
    q = 1.0
    for i in xrange( 366-n, 366 ):
        q *= i/365.0
    return 1-q

prob라는 함수를 만들어서 n명 그룹에서 생일이 동일한 사람이 있을 확률을 계산시켰다. 4줄의 나눗셈 오차가 누적되는 것이 불안하긴 하지만 다행히 유효숫자 4자리 정도까진 크게 틀리지 않더라. n에 따라서 확률이 어떻게 변하는지 아래에 덧붙인다. 직관적인 것과는 달리 굉장히 빠르게 100%로 접근하는 것을 볼 수 있다.

무튼 위 결과에서도 볼 수 있듯, 23명이 모이면 50%를 넘게 된다.

---

이러한 생일 역설은 통계학 공부에도 자주 등장하지만 전산학에서는 해시 충돌 검사에서 쓰인다고 한다. 해시 테이블을 직접 짜본 적이 없어서 해시 함수들의 구체적인 연산이 어떻게 이뤄졌었는지 다 까먹은 관계로 자세한 것은 더 공부하면서 익히도록 하고 이번 포스팅은 이쯤에서 마치겠다.