yeolyi.com성열의 컴퓨터공학

생일 같은 친구가 흔한 이유

확률

프로그램에도 운이 끼어듭니다. 무작위로 만든 ID 두 개가 우연히 같을 수 있고, 같은 선형 탐색도 찾는 값이 어디 있느냐에 따라 일찍 끝나기도 늦게 끝나기도 합니다. 미리 알 수는 없어도 경우의 수를 세면 얼마나 자주 겹칠지, 평균 몇 번이면 끝날지 수로 말할 수 있습니다.

확률

주사위를 던져 짝수가 나올 가능성은 6가지 중 3가지라 3 / 6 = 1 / 2입니다. 이처럼 모든 경우가 똑같이 일어날 법할 때, 원하는 경우의 수를 전체 경우의 수로 나눈 값을 확률(probability)이라 합니다. 0은 절대 일어나지 않음, 1은 반드시 일어남입니다.

주사위 두 개를 던지면 곱의 법칙으로 6 × 6 = 36가지입니다.

두 눈의 합 7
모든 경우 6 × 6 = 36가지
합이 7인 경우 6가지 6/36 = 16.7%

두 주사위가 모두 6일 확률은 36가지 중 1가지라 1 / 36이고, 이는 1 / 6 × 1 / 6과 같습니다. 첫 주사위의 눈이 둘째 주사위의 눈이 나올 확률을 바꾸지 않기 때문입니다. 이런 두 일을 독립(independent)이라 하고, 독립인 일들이 모두 일어날 확률은 곱으로 구합니다.

생일 문제

몇 명이 모여야 생일이 같은 두 사람이 있을 확률이 50%를 넘을까요? 생일은 365일 중 아무 날이나 똑같은 확률로 나온다고 합시다.

같은 생일이 한 쌍이라도 있는 경우는 여러 가지라 세기 어렵습니다. 그런데 “한 쌍이라도 겹침”과 “모두 다름”은 둘 중 꼭 하나만 일어나니 두 확률의 합이 1입니다. 그래서 모두 다를 확률을 구해 1에서 뺍니다. 두 번째 사람은 첫 사람과 다른 날이어야 하니 364 / 365, 세 번째는 363 / 365입니다. 각자의 생일은 독립이니 모두 곱하면 됩니다.

사람 수 23
같은 생일이 있을 확률 50.7%모두 다를 확률 365/365 × 364/365 × … × 343/365 = 49.3%

23명이면 이미 50%가 넘습니다. 사람이 아니라 쌍을 세어야 하기 때문입니다. 23명이면 쌍이 23 × 22 / 2 = 253개이고, 한 쌍만 겹쳐도 됩니다. 무작위 ID를 만들 때도 같아서, 겹침은 가짓수에 비해 생각보다 훨씬 일찍 일어납니다.

기댓값

주사위를 던지면 평균적으로 얼마가 나올까요? 각 눈에 그 확률을 곱해 모두 더합니다.

1 × 1/6 + 2 × 1/6 + 3 × 1/6 + 4 × 1/6 + 5 × 1/6 + 6 × 1/6 = 3.5

이 값을 기댓값(expected value)이라 합니다. 3.5라는 눈은 없지만 여러 번 던질수록 평균이 이 값에 다가갑니다.

던진 횟수 0지금까지의 평균 - · 기댓값 3.5
가로: 던진 횟수 · 세로: 평균 (1~6) · 점선: 기댓값
  1. “10번”을 몇 번 눌러 봅시다.
  2. “1,000번”을 눌러 봅시다.

횟수가 많아질수록 평균이 기댓값에 가까워지는 성질을 큰 수의 법칙(law of large numbers)이라 합니다. 한 번 한 번은 알 수 없어도 평균은 예측할 수 있습니다.

선형 탐색도 같습니다. 찾는 값이 n칸 중 어디에나 똑같은 확률로 있다면, i번째 칸에 있을 때 i번 확인하니 기댓값은 다음과 같습니다.

(1 + 2 + … + n) × 1/n = (n + 1) / 2

평균으로는 절반쯤 확인하면 찾습니다.

도전 문제

주사위를 한 번 던진 뒤, 나온 눈을 점수로 가질지 한 번 더 던질지 고릅니다. 다시 던지면 두 번째 눈이 점수가 되고 더는 바꿀 수 없습니다. 점수의 기댓값이 가장 커지게 고를 때, 그 기댓값은 얼마일까요? 소수나 기약분수로 답하세요.