생일 문제(Birthday Problem)

이병헌·2021년 1월 16일
0
post-thumbnail

하버드에서 제공하는 Statistics 110: Probability 강의를 듣다 오랜만에 생일문제에 대한 이야기를 듣게 되었다.

생일문제(Birthday Problem)이란 사람이 임의로 모였을 때 최소한 두 명의 생일이 겹칠 확률을 구하는 문제이다.

교수는 강의에서 23명만 있어도 생일이 겹칠 확률이 50%가 넘고 50명이 있다면 확률은 97%에 육박한다고 한다.

생일문제에 대해서는 많이 들어보았지만 곰곰이 생각해보면 사실 단 한번도 실제로 계산해본적이 없다. 따라서 오늘은 생일문제를 직접 계산해보려 한다.

먼저 이를 간단하게 계산하기 위해서는 먼저 이 확률은 서로 독립(서로에게 영향을 주지 못한다, 쌍둥이 제외)을 가정하고 2월 29일은 존재하지 않는다고 가정하고 시작하겠다.

확장해보면 365일의 각자 다른 생일을 가지고 있는 사람들을 구하기 위해서는 365개의 구분되어있는 칸에 구슬을 어떻게 집어넣는지와 같다고 생각할 수 있다.

따라서 구슬의 수가 366을 넘어가게되면 365개의 칸에 구슬을 하나씩 넣었다 하더라도 하나를 더 넣어야 하기 때문에 두명의 생일이 겹칠 확률은 1을 넘어가게된다.

이는 비둘기집 원리라는 이름으로 증명돼있다.

365 미만의 숫자에서는 겹치지 않을 확률은 구슬을 처음 365칸 중 아무데나 넣을 수 있으니 365/365, 그 다음은 첫 구슬이 들어간 한 칸을 제외한 364/365, 그 다음 구슬은 두 칸을 제외한 363/365 ... 계속 확률의 곱법칙으로 곱해나갈 수 있다.

이를 전부 곱해주면

P(kc)=365364363(365k+1)365kP\relax(k^c) = \frac{365 * 364 * 363 * \dotsb * (365-k+1)}{365^k}

이를 약분해주면

P(kc)=365!365k(365k)!P\relax(k^c) = \frac{365!}{365^k*(365-k)!}

확률의 axiom에 의해 여사건은 전체확률 1에서 확률을 빼주는 것이니

P(k)=1365!365k(365k)!P\relax(k) = 1- \frac{365!}{365^k*(365-k)!}

이 값을 직접 계산해보면

answer = 1 - math.factorial(365)/ (pow(365, k) * math.factorial(365-k))


30명만 있어도 70퍼가 넘는 확률을 알 수 있다.

이는 우리의 1차원적인 직관에서는 많이 벗어나는 일이지만, 조금만 더 생각해보면 30명중 두 명을 뽑으면 이미 그 숫자는 435로 365보다 훨씬 높은 숫자이다.

> 문득 다른쪽으로 확장해 생각해보니 자료구조에서도 이렇게 생일문제와 비슷한 문제를 해결하려는 모습을 볼 수 잇다.

앞서 이야기했던 한정되어있는 칸에 값을 집어넣으려면 생각보다 많은 것을 고려해야한다.

365개의 칸이 있어도 30개만 원소를 집어넣으려 하면 같은 칸에 겹칠 확률이 70%가 넘어버린다.

이같은 경우를 입력값을 해시함수를 통해 해시하여 출력값을 집어넣는 자료구조인 해시그래프에서는 해시충돌이라고 부르고, 이를 해결하기 위한 여러가지 해결책을 제시한다.

사실 가장 간단한 것은 칸을 무한대로 늘려버리는 것이다. 그렇게 되면 겹칠리가 없다. 물론 기술이 하염없이 발전하더라도 메모리 문제를 해결할 수도 없지만.

> 그런 문제로 가장 널리 사용되는 것 중 하나는 Open address다. 원소가 들어갈 곳을 미리 정해놓지 말고 만약 충돌이 발생한다면 그 다음 한칸을 이동해서 저장하는 Linear probing, 한 칸이 아닌 제곱칸씩 이동하는 Quadratic probing을 제시한다.

물론 완벽한 해결책은 아니지만 꽤 괜찮은 방법이다.

> 또 생각을 확장하다 보니 비트코인으로 와버렸다.

대부분의 암호화폐에서는 해시함수로 SHA-256을 사용한다. SHA-256은 간단하게 결과가 256비트인 해시함수이다.

먼저 이야기할 수 있는 것은 SHA-256은 '충돌이 거의 발생하지 않는다'.

충돌이 전혀 없다 라고 말할 수는 없다. 2의 256승개를 전부 입력해보면 구할 수 있겠지만... 아마 양자컴퓨터가 개발되면 가능성이 있어도 현재로썬 SHA-256이 깨지긴 어렵다.

profile
all for one / Product

0개의 댓글