PART IV — 확률
확률은 불확실성을 다루는 수학입니다. 컴퓨터과학에서는 무작위 알고리즘을 설계하고 분석할 때, 또 평균적인 실행시간이나 데이터 구조의 기대 동작을 가늠할 때 확률이 늘 등장합니다. 이번 챕터에서는 확률이라는 모호해 보이는 개념을 어떻게 엄밀한 수학으로 길들일 수 있는지를, 유명한 문제들을 통해 차근차근 살펴봅니다. 직관이 자주 미끄러지는 영역이라 더 조심스러운 도구가 필요합니다.
1970년대 미국의 게임쇼 Let's Make a Deal에서 진행자 몬티 홀이 던진 문제는 수학자들조차 한참을 다툰 사건이었습니다. 룰은 이렇습니다. 무대 위에 문이 세 개 있고, 그중 한 문 뒤에는 자동차가, 나머지 두 문 뒤에는 염소가 들어 있습니다. 참가자가 먼저 문 하나를 고릅니다. 그러면 진행자는 남은 두 문 중에서 염소가 있는 문 하나를 열어 보여줍니다. 진행자는 어느 문에 자동차가 있는지 알고 있고, 반드시 염소가 있는 문을 고른다는 점이 중요합니다. 그리고 참가자에게 묻습니다. 고른 문을 바꾸시겠습니까, 그대로 두시겠습니까?
여기서 많은 사람의 직관은 이렇게 말합니다. 이제 문이 두 개 남았으니 자동차가 있을 확률은 절반씩이지. 바꾸든 안 바꾸든 똑같다.
하지만 이 직관은 틀렸습니다. 바꾸면 자동차를 얻을 확률이 \( \tfrac{2}{3} \)이고, 그대로 두면 \( \tfrac{1}{3} \)에 머뭅니다. 두 배 차이가 납니다.
왜 이렇게 어긋날까요? 사람들은 흔히 지금 보이는 두 문만 바라보며 대칭성을 가정해 버립니다. 그러나 진행자가 문을 여는 행위는 단순히 정보를 지운 게 아니라, 자동차가 있는 문은 절대 열지 않는다는 규칙을 통해 정보를 적극적으로 전달한 행동입니다. 이 비대칭성을 잡아내는 방법이 있어야 합니다. 다음 절에서 살펴볼 4단계 방법이 바로 그 도구입니다.
노트
이 문제는 1990년 잡지 칼럼니스트 매릴린 보스 사반트가 바꾸는 게 유리하다
고 답하자, 박사학위 소지자 수백 명이 항의 편지를 보낸 사건으로도 유명합니다. 직관이 얼마나 강하게 우리를 잘못된 답으로 끌고 가는지, 동시에 확률이 왜 형식적인 도구를 필요로 하는지를 보여주는 일화입니다.
확률 문제를 안전하게 푸는 정형화된 절차가 있습니다. 단계를 통째로 외우는 게 아니라, 매번 같은 순서로 머리속을 정리하는 습관이라고 보시면 됩니다.
정의 17.2.1 (4단계 방법)
임의의 확률 문제는 다음 네 단계로 해결할 수 있습니다.
(1) 표본공간 정의: 가능한 모든 결과의 집합 \( S \)를 명확히 적습니다. 보통 트리 다이어그램으로 그리면 한눈에 들어옵니다.
(2) 결과 확률 부여: 각 결과 \( \omega \in S \)에 대해 \( \Pr[\omega] \)를 정합니다. 합은 반드시 1이 되어야 합니다.
(3) 사건 식별: 우리가 관심 있는 사건 \( E \subseteq S \)를 결과들의 집합으로 적습니다.
(4) 사건 확률 계산: \( \Pr[E] = \sum_{\omega \in E} \Pr[\omega] \)로 합산합니다.
몬티홀에 적용해 봅시다. 자동차가 있는 문을 1, 2, 3 중 하나라 하고, 참가자가 처음 고른 문도 1, 2, 3 중 하나, 그리고 진행자가 여는 문도 1, 2, 3 중 하나입니다. 단순화를 위해 참가자는 항상 1번 문을 먼저 고른다고 합시다(대칭성 때문에 일반성을 잃지 않습니다).
1단계 — 표본공간. 두 단계 무작위 시행이 일어납니다. 첫째, 자동차가 1, 2, 3번 문 중 어디에 놓이는가. 둘째, 진행자가 어느 문을 여는가. 트리로 펼치면 결과는 다음과 같이 나옵니다.
자동차 위치 진행자가 여는 문 결과
1 (1/3) ───── 2 (1/2) ──────── (1, 2)
└─ 3 (1/2) ──────── (1, 3)
2 (1/3) ───── 3 (1) ────────── (2, 3)
3 (1/3) ───── 2 (1) ────────── (3, 2)
참가자가 1번을 고른 상태에서, 자동차가 1번에 있을 때 진행자는 2번이나 3번 중 아무 데나 열 수 있으므로 각각 \( \tfrac{1}{2} \) 확률을 부여합니다. 자동차가 2번이라면 진행자는 반드시 3번을 열어야 하고(1번은 참가자가 골랐고 2번은 자동차이므로), 자동차가 3번이라면 반드시 2번을 엽니다.
2단계 — 결과 확률. 가지의 곱으로 각 결과의 확률을 매깁니다.
\( \Pr[(1,2)] = \tfrac{1}{3} \cdot \tfrac{1}{2} = \tfrac{1}{6} \), \( \Pr[(1,3)] = \tfrac{1}{6} \), \( \Pr[(2,3)] = \tfrac{1}{3} \), \( \Pr[(3,2)] = \tfrac{1}{3} \). 합은 \( 1 \)입니다.
3단계 — 사건. 우리가 알고 싶은 건 바꾸기 전략을 쓸 때 자동차를 얻는 사건
입니다. 바꾸기 전략에선, 진행자가 연 문 말고 남은 다른 문으로 바꿉니다. 이 사건 \( W \)에 속하는 결과는 자동차가 1번이 아닐 때 모두입니다. 즉 \( W = \{(2,3), (3,2)\} \).
4단계 — 합산. \( \Pr[W] = \tfrac{1}{3} + \tfrac{1}{3} = \tfrac{2}{3} \). 끝입니다. 바꾸기 전략의 승률은 \( \tfrac{2}{3} \), 안 바꾸기 전략의 승률은 \( \tfrac{1}{3} \).
노트 — 직관 vs 계산
직관: 문 두 개 남았으니 50대 50.
계산: 처음 고른 문이 자동차일 확률은 \( \tfrac{1}{3} \)에 고정되어 있고, 진행자의 행동은 그 \( \tfrac{1}{3} \)을 흔들지 않는다. 따라서 나머지 한 문이 자동차일 확률이 \( \tfrac{2}{3} \)이다.
이런 종류의 어긋남은 확률에서 끝없이 등장하므로, 4단계 방법을 한번 몸에 익혀 두면 평생을 갑니다.
주사위 세 개 \( A, B, C \)를 만들었다고 합시다. 보통 주사위가 아니라 면마다 다른 숫자가 적힌 특별한 주사위입니다. 두 사람이 각자 주사위를 굴려 더 큰 수가 나오는 쪽이 이깁니다. 이때 \( A \)가 \( B \)를 이길 확률이 절반을 넘는다
를 \( A \succ B \)라고 적기로 합시다.
상식적으로는 이 관계가 추이적일 거라고 기대합니다. 즉 \( A \succ B \)이고 \( B \succ C \)이면 \( A \succ C \)일 거라고요. 가위바위보처럼 순환하는 일은 보통의 부등호에는 없으니까요. 그런데 잘 만든 주사위 세 개로는 \( A \succ B \succ C \succ A \)라는 가위바위보 같은 고리를 만들 수 있습니다. 이런 주사위를 비추이적 주사위라고 부릅니다.
예제 17.3.1 (에프론의 주사위)
다음 주사위를 봅시다. 모든 면은 동일한 확률 \( \tfrac{1}{6} \)로 나옵니다.
\( A = \{2, 2, 4, 4, 9, 9\} \), \( B = \{1, 1, 6, 6, 8, 8\} \), \( C = \{3, 3, 5, 5, 7, 7\} \).
\( \Pr[A > B] \)를 계산해 봅시다. \( B \)가 \( 1 \)이 나오면(확률 \( \tfrac{1}{3} \)) \( A \)는 무조건 큽니다. \( B \)가 \( 6 \)이면(확률 \( \tfrac{1}{3} \)) \( A \)는 \( 9 \)일 때만 이기므로 \( \tfrac{1}{3} \)입니다. \( B \)가 \( 8 \)이면(확률 \( \tfrac{1}{3} \)) 마찬가지로 \( A \)는 \( 9 \)일 때만 이깁니다.
\[ \Pr[A > B] = \tfrac{1}{3} \cdot 1 + \tfrac{1}{3} \cdot \tfrac{1}{3} + \tfrac{1}{3} \cdot \tfrac{1}{3} = \tfrac{1}{3} + \tfrac{2}{9} = \tfrac{5}{9}. \]
같은 식으로 \( \Pr[B > C] = \tfrac{5}{9} \), \( \Pr[C > A] = \tfrac{5}{9} \)도 나옵니다. 즉 \( A \succ B \succ C \succ A \).
왜 직관이 무너질까요? 우리는 주사위를 평균이 큰 쪽이 강한 주사위
로 자동 환산하는데, 승률은 평균이 아니라 분포의 모양 전체에 의존합니다. \( A \)는 \( 9 \) 같은 큰 수에 무게가 실리지만 \( 4 \) 이하도 자주 나오고, \( B \)는 양극단 \( 1 \)과 \( 8 \)로 갈리며, \( C \)는 중간값을 모아둔 주사위입니다. 두 분포가 만났을 때 누가 자주 이기는가 하는 문제는 단일 숫자로 환원되지 않습니다.
노트
비추이적 주사위는 단순한 잡학이 아니라, 최선의 선택이라는 개념이 어떨 때 깨지는지를 보여주는 사례입니다. 게임이론, 투표 이론, 기계학습의 손실비교 등에서 비슷한 비추이성이 등장합니다. 평균만 보고 비교하지 마라
가 교훈입니다.
강의실에 학생 23명이 모여 있다고 합시다. 같은 생일을 가진 두 사람이 있을 확률이 얼마나 될까요? 직관은 365일 중 23명이라니, 너무 적다. 한 5%쯤?
이라고 속삭이지만, 정답은 50%를 살짝 넘습니다. 학생이 23명만 모이면 이미 동률에 도달한다는 뜻입니다.
4단계 방법으로 풀어 봅시다. 표본공간은 23명 각자가 365일 중 하루를 균등하게 가질 모든 경우, 즉 \( S = [365]^{23} \)이고 결과는 길이 23인 튜플입니다. 각 결과에 동일 확률 \( 1 / 365^{23} \)을 부여합니다(단순화: 윤년·계절성 무시).
관심 사건 \( M \)은 두 명 이상이 같은 생일
인 사건입니다. 이걸 직접 세기보다 여집합 \( \overline{M} \)인 모두가 다른 생일
을 세는 게 훨씬 쉽습니다. 23명을 한 명씩 줄세워 생일을 정한다고 보면, 첫 사람은 365일 중 아무 날이나 가능, 두 번째는 364일, 셋째는 363일, ..., 23번째는 \( 365 - 22 = 343 \)일.
\[ \Pr[\overline{M}] = \frac{365 \cdot 364 \cdot 363 \cdots 343}{365^{23}} \approx 0.4927. \]
따라서 \( \Pr[M] = 1 - \Pr[\overline{M}] \approx 0.5073 \). 절반을 넘습니다.
일반화도 쉽습니다. 가능한 생일 종류가 \( N \)이고 사람이 \( n \)명일 때 충돌 확률이 \( \tfrac{1}{2} \)에 도달하는 \( n \)은 대략 \( n \approx 1.177 \sqrt{N} \)입니다. \( N = 365 \)면 \( n \approx 22.5 \), 우리가 본 23과 일치합니다. 핵심은 가능한 쌍의 수가 사람 수의 제곱으로 늘어난다는 점입니다.
정리 17.4.1 (생일 원리)
각각이 \( N \)개 가능 종류 중에서 균등하게 무작위로 뽑힌 \( n \)개의 항목이 있다고 하자. 두 항목이 일치할 확률 \( p \)는 다음과 같이 근사된다.
\[ p \approx 1 - \exp\!\left(-\frac{n(n-1)}{2N}\right). \]
특히 \( n \approx \sqrt{2N \ln 2} \approx 1.177\sqrt{N} \)일 때 \( p \approx \tfrac{1}{2} \)가 된다.
증명 스케치
모두 다를 확률은 \( \prod_{k=0}^{n-1}\!\left(1 - \tfrac{k}{N}\right) \)입니다. 각 항에 \( 1 - x \le e^{-x} \)를 적용하면 \( \prod_{k=0}^{n-1} e^{-k/N} = e^{-n(n-1)/(2N)} \)을 얻습니다. 여집합을 취하면 정리의 식이 나옵니다.
∎
노트 — CS에서의 응용
해시 함수의 충돌 분석이 정확히 이 원리입니다. 해시 출력이 \( N \)가지일 때, 약 \( \sqrt{N} \)개의 입력만 해싱해도 충돌이 거의 확실해집니다. 128비트 해시면 \( N = 2^{128} \), 충돌 임계는 \( 2^{64} \) 수준. 암호학에서 생일 공격
이라 부르며, 해시의 안전 자릿수를 두 배로 잡는 이유입니다.
지금까지 직관적으로 사용한 표본공간
과 사건
을 이제 집합론의 언어로 다시 깔끔하게 정리해 봅시다. 이게 확률공간(probability space)의 표준 정의입니다.
정의 17.5.1 (확률공간)
확률공간은 다음 두 가지로 구성됩니다.
(1) 표본공간 \( S \): 모든 가능한 결과(outcome)의 집합.
(2) 확률 함수 \( \Pr : S \to [0, 1] \): 각 결과에 0 이상 1 이하의 실수를 배정하며, \( \sum_{\omega \in S} \Pr[\omega] = 1 \).
사건은 표본공간의 부분집합 \( E \subseteq S \)이고, 그 확률은 \( \Pr[E] = \sum_{\omega \in E} \Pr[\omega] \)로 정의합니다.
이렇게 보면 사건은 곧 부분집합이고, 사건들의 연산은 그대로 집합 연산입니다. \( A \) 또는 \( B \)가 일어남
은 \( A \cup B \), 둘 다 일어남
은 \( A \cap B \), \( A \)는 일어나지 않음
은 여집합 \( \overline{A} = S \setminus A \). 집합 항등식이 곧 확률의 항등식이 되는 강력한 사전이 생기는 셈입니다.
정리 17.5.2 (확률 측도의 기본 성질)
임의의 사건 \( A, B \subseteq S \)에 대해 다음이 성립합니다.
(a) \( \Pr[\emptyset] = 0 \), \( \Pr[S] = 1 \).
(b) \( \Pr[\overline{A}] = 1 - \Pr[A] \).
(c) 합집합 경계 (Union Bound): \( \Pr[A \cup B] \le \Pr[A] + \Pr[B] \). 일반적으로 \( \Pr\!\left[\bigcup_{i} A_i\right] \le \sum_i \Pr[A_i] \).
(d) 포함–배제: \( \Pr[A \cup B] = \Pr[A] + \Pr[B] - \Pr[A \cap B] \).
(e) 단조성: \( A \subseteq B \implies \Pr[A] \le \Pr[B] \).
증명 스케치
모두 \( \Pr[E] = \sum_{\omega \in E} \Pr[\omega] \)에서 자동으로 따라옵니다. 예컨대 (b)는 \( S = A \cup \overline{A} \)에서 \( \Pr[A] + \Pr[\overline{A}] = \Pr[S] = 1 \)이고, (c)는 \( A \cup B \)의 원소 각각이 우변에서 한 번 또는 두 번 세어진다는 데서, (d)는 두 번 세어진 \( A \cap B \)를 한 번 빼주는 데서, (e)는 \( B = A \cup (B \setminus A) \)의 분해에서 나옵니다.
∎
합집합 경계는 거칠어 보여도 컴퓨터과학에서 가장 자주 등장하는 부등식 중 하나입니다. 가령 무작위 알고리즘이 \( m \)가지 나쁜 사건 중 어느 하나라도 발생하면 실패한다고 합시다. 각 나쁜 사건의 확률을 \( \tfrac{1}{m^2} \) 이하로 누를 수 있다면 합집합 경계로 전체 실패 확률은 \( \tfrac{1}{m} \)을 넘지 않습니다. 정확한 \( \Pr[A_i \cap A_j] \)을 몰라도 위쪽 경계만 잡고 안전하게 결론을 내릴 수 있는 도구입니다.
예제 17.5.3 (몬티홀 다시 보기)
17.2절에서 표본공간 \( S = \{(1,2),(1,3),(2,3),(3,2)\} \), 확률 \( \tfrac{1}{6}, \tfrac{1}{6}, \tfrac{1}{3}, \tfrac{1}{3} \), 사건 \( W = \{(2,3),(3,2)\} \)을 정했습니다. 이는 정의 17.5.1을 충족합니다(확률 합 \( = 1 \), \( W \subseteq S \)). 따라서 \( \Pr[W] = \tfrac{2}{3} \)는 단순한 트릭이 아니라 잘 정의된 확률공간 위에서의 정직한 계산입니다.
노트 — 무한 표본공간에 대해서
이번 챕터에서는 \( S \)가 유한하거나 셀 수 있는 경우만 다룹니다. 실수 구간처럼 셀 수 없는 표본공간을 엄밀히 다루려면 측도론(measure theory)이 필요해집니다. 다행히 컴퓨터과학에서 만나는 대부분의 확률 모형은 유한이라, 우리에게 필요한 도구는 사실상 다 갖춘 셈입니다.
이렇게 사건을 집합으로, 확률을 측도로 보는 시점이 자리잡으면, 다음 챕터들에서 다룰 조건부 확률·독립성·기댓값·집중 부등식이 모두 같은 언어 위에서 자연스럽게 펼쳐집니다. 확률은 더 이상 감
이 아니라, 우리가 5장과 8장에서 길러 온 집합과 합산의 도구를 그대로 다시 쓰는 분야가 되는 것입니다.