PART IV — 확률
앞 챕터들에서 우리는 표본공간 위에서 사건(event)의 확률을 계산했어요. 그런데 막상 문제를 풀다 보면 "어느 사건이 일어났는가"보다 "어떤 수치가 나왔는가"가 더 궁금할 때가 많습니다. 주사위 두 개의 합, 동전 \(n\)번 던졌을 때 앞면의 개수, 랜덤 알고리즘의 비교 횟수 — 모두 표본공간 위에 정의된 "수치 함수"입니다. 이 함수가 바로 확률변수예요. 이 챕터에서는 확률변수와 그 분포를 정의하고, 기댓값이라는 강력한 도구, 그리고 거의 마법처럼 작동하는 기댓값의 선형성을 다룹니다.
표본공간 \(S\)가 정해졌다고 합시다. 우리는 결과 \(\omega \in S\) 하나하나에 어떤 실수를 대응시키고 싶어요. 예를 들어 동전 세 번을 던지는 실험이라면 결과는 HHT, THH 같은 문자열인데, 우리가 정말 알고 싶은 건 "앞면이 몇 번 나왔는가"라는 숫자입니다. 그러니 결과를 숫자로 보내주는 함수가 필요합니다.
정의 19.1.1 (확률변수)
표본공간 \(S\) 위의 확률변수(random variable)는 함수 \(X : S \to \mathbb{R}\) 입니다. 즉 각 결과 \(\omega \in S\)에 실수 \(X(\omega)\)를 대응시키는 함수예요.
이름은 "변수"지만, 실체는 함수입니다. 이게 처음 헷갈리는 부분이에요. 보통 변수라 하면 \(x = 3\) 같은 정해진 값이 떠오르지만, 확률변수 \(X\)는 "결과에 따라 다른 값을 내놓는 규칙"입니다. 결과 \(\omega\)가 정해지면 \(X(\omega)\)도 정해져요. 결과가 무작위니까 \(X\)의 값도 무작위가 됩니다.
예제 19.1.2 (주사위 두 개의 합)
공정한 6면체 주사위 두 개를 던집니다. 표본공간은 \(S = \{(i,j) : 1 \le i, j \le 6\}\), 크기 36이고 각 결과의 확률은 \(1/36\)입니다. 확률변수 \(T(\omega) = i + j\) 를 "두 주사위 눈의 합"으로 정의해요. 그러면 \(T\)는 2부터 12까지의 값을 갖습니다. 예컨대 \(\omega = (3,4)\)이면 \(T(\omega) = 7\), \(\omega = (6,6)\)이면 \(T(\omega) = 12\)입니다. \(T = 7\)이 되는 결과는 \((1,6), (2,5), (3,4), (4,3), (5,2), (6,1)\)로 6가지이니, \(\Pr[T=7] = 6/36 = 1/6\) 입니다.
예제 19.1.3 (동전 던지기의 앞면 수)
공정한 동전을 \(n\)번 독립적으로 던집니다. 표본공간 \(S = \{H, T\}^n\), 각 결과의 확률은 \(1/2^n\)입니다. 확률변수 \(H_n(\omega)\)를 "결과 \(\omega\)에 들어 있는 H의 개수"로 정의하면, \(H_n\)은 0부터 \(n\)까지의 값을 가져요. \(\Pr[H_n = k] = \binom{n}{k}/2^n\) 입니다.
한 가지 더 짚어둘 게 있어요. 같은 표본공간 위에 여러 확률변수를 동시에 정의할 수 있습니다. 주사위 두 개의 예에서 \(T\)는 합, \(D(\omega) = |i - j|\)는 차이의 절댓값, \(M(\omega) = \max(i,j)\)는 최댓값 — 이런 식으로 얼마든지요. 모두 같은 \(\omega\)에서 동시에 평가될 수 있고, 그래서 \(T\)와 \(M\)이 함께 어떻게 움직이는지(공분산 같은 것)를 따질 수 있게 됩니다.
노트 (인디케이터 변수)
특별히 자주 쓰는 확률변수가 인디케이터(indicator) 확률변수입니다. 사건 \(A \subseteq S\)에 대해 \(I_A(\omega) = 1\) (만약 \(\omega \in A\)), \(0\) (그렇지 않으면). 0/1 값만 갖는 확률변수예요. 매우 단순해 보이지만, 19.5절의 마법은 사실상 이 인디케이터 트릭에서 옵니다.
사건의 독립은 이미 봤어요: \(\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]\). 확률변수의 독립은 이것의 자연스러운 확장입니다. 두 확률변수가 독립이라는 건, 한쪽 값을 알아도 다른 쪽 값에 대한 우리 예측이 바뀌지 않는다는 뜻이에요.
정의 19.2.1 (확률변수의 독립)
확률변수 \(X, Y\)가 독립이라는 것은 \(X, Y\)가 가질 수 있는 임의의 값 \(x, y\)에 대해 \[\Pr[X = x \text{ 그리고 } Y = y] = \Pr[X = x] \cdot \Pr[Y = y]\] 가 성립한다는 뜻입니다. 더 일반적으로 \(X_1, \ldots, X_n\)이 (상호) 독립이라는 것은 임의의 값 \(x_1, \ldots, x_n\)에 대해 \(\Pr[X_1 = x_1, \ldots, X_n = x_n] = \prod_{i=1}^{n} \Pr[X_i = x_i]\) 입니다.
예제 19.2.2 (독립인 경우와 아닌 경우)
주사위 두 개를 던질 때, \(X_1\)을 첫 번째 눈, \(X_2\)를 두 번째 눈이라 하면 \(X_1, X_2\)는 독립입니다. 어떤 \(a, b \in \{1,\ldots,6\}\)에 대해서도 \(\Pr[X_1 = a, X_2 = b] = 1/36 = (1/6)(1/6)\)이니까요. 반면 같은 실험에서 \(T = X_1 + X_2\)와 \(X_1\)은 독립이 아닙니다. 예를 들어 \(X_1 = 1\)이라는 정보를 얻으면 \(T\)는 절대 12가 될 수 없잖아요. 사전엔 \(\Pr[T=12] = 1/36\)이지만 \(X_1=1\)을 안 뒤엔 0으로 바뀝니다.
독립은 좋은 성질이에요. 독립이면 결합 확률을 분해할 수 있고, 분산이 합으로 분리되고(20장에서 확인), 큰 수의 법칙·중심극한정리 같은 것이 깔끔하게 작동합니다. 그런데 한 가지 큰 사실: 기댓값의 선형성은 독립을 요구하지 않아요. 19.5절에서 다시 말씀드릴게요.
확률변수 \(X\)에 대해 우리가 알고 싶은 모든 정보는 결국 "\(X\)가 어떤 값을 얼마의 확률로 갖는가"로 요약됩니다. 이 정보를 담는 함수가 분포(distribution)예요. 이산확률변수에서는 두 가지 방식이 표준입니다.
정의 19.3.1 (PMF, CDF)
이산확률변수 \(X\)의 확률질량함수(probability mass function, PMF)는 \(p_X(x) = \Pr[X = x]\) 입니다. 누적분포함수(cumulative distribution function, CDF)는 \(F_X(x) = \Pr[X \le x]\) 입니다. 두 함수는 서로의 정보를 모두 담고 있어요: \(p_X(x) = F_X(x) - F_X(x^-)\), \(F_X(x) = \sum_{y \le x} p_X(y)\).
PMF는 항상 \(\sum_x p_X(x) = 1\)을 만족하고 \(0 \le p_X(x) \le 1\)이어야 합니다. CDF는 비감소 함수이며 \(\lim_{x \to -\infty} F_X(x) = 0\), \(\lim_{x \to \infty} F_X(x) = 1\) 입니다. 자주 만나는 분포들을 정리해 둘게요.
정의 19.3.2 (베르누이 분포)
모수 \(p \in [0,1]\)의 베르누이 분포는 \(\Pr[X=1] = p, \Pr[X=0] = 1-p\) 인 분포입니다. "한 번의 동전 던지기" 같은, 0/1 결과의 가장 단순한 모형이에요. 표기는 \(X \sim \mathrm{Bern}(p)\).
정의 19.3.3 (이항 분포)
모수 \(n, p\)의 이항 분포는 독립적인 베르누이 \(p\) 시행 \(n\)번에서 성공 횟수의 분포입니다. PMF는 \[\Pr[X = k] = \binom{n}{k} p^k (1-p)^{n-k}, \quad k = 0, 1, \ldots, n.\] 표기는 \(X \sim \mathrm{Bin}(n, p)\). 동전 \(n\)번 던졌을 때 앞면 수 \(H_n\)은 \(\mathrm{Bin}(n, 1/2)\)예요.
정의 19.3.4 (기하 분포)
모수 \(p \in (0,1]\)의 기하 분포는 독립적인 베르누이 \(p\) 시행에서 첫 성공이 나올 때까지의 시행 횟수입니다. PMF는 \[\Pr[X = k] = (1-p)^{k-1} p, \quad k = 1, 2, 3, \ldots\] 표기는 \(X \sim \mathrm{Geo}(p)\). "버그가 나오기까지 몇 번째 빌드?" 같은 질문에 자연스러운 모형이에요.
정의 19.3.5 (이산 균등 분포)
유한 집합 \(\{a_1, \ldots, a_n\}\) 위의 균등 분포는 모든 값을 똑같이 \(1/n\)의 확률로 가집니다. 주사위 한 번 던지기는 \(\{1, \ldots, 6\}\) 위의 균등 분포예요.
예제 19.3.6 (이항 PMF 작은 예)
\(X \sim \mathrm{Bin}(4, 1/2)\)일 때 PMF를 계산해 봅시다. 분모가 \(2^4 = 16\)이고 분자가 \(\binom{4}{k}\)예요.
| \(k\) | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| \(\Pr[X=k]\) | 1/16 | 4/16 | 6/16 | 4/16 | 1/16 |
합쳐 보면 \(1/16 + 4/16 + 6/16 + 4/16 + 1/16 = 16/16 = 1\)이고, 가운데인 \(k=2\)에서 가장 큽니다. 이항계수의 종 모양이 그대로 보이죠.
노트 (결합 분포)
두 확률변수 \(X, Y\)에 대한 정보를 함께 담으려면 결합 PMF \(p_{X,Y}(x,y) = \Pr[X=x, Y=y]\)를 봅니다. 결합 분포에서 \(y\)에 대해 합치면 주변 분포 \(p_X(x) = \sum_y p_{X,Y}(x,y)\)가 나오고요. 19.2절의 독립 조건은 정확히 \(p_{X,Y}(x,y) = p_X(x) p_Y(y)\)와 같은 말입니다.
분포 전체를 볼 수 있다면 좋겠지만, 보통 우리는 그 분포를 한두 개의 숫자로 요약하고 싶어요. 그중 가장 중요한 게 기댓값(expected value), 즉 평균입니다. "이 확률변수의 값은 평균적으로 얼마쯤 될까?"에 답하는 양이에요.
정의 19.4.1 (기댓값)
이산확률변수 \(X\)의 기댓값은 \[\mathrm{E}[X] = \sum_{x} x \cdot \Pr[X = x] = \sum_{\omega \in S} X(\omega) \cdot \Pr[\omega]\] 로 정의됩니다(합이 절대수렴할 때). 두 표현은 같은 값을 줘요. 첫 번째는 "값 × 확률을 그 값을 갖는 결과들로 묶어 합산"이고, 두 번째는 "결과별 기여를 그대로 합산"입니다.
예제 19.4.2 (공정한 주사위)
\(X\)를 공정한 6면체 주사위의 눈이라 하면 \[\mathrm{E}[X] = 1 \cdot \tfrac{1}{6} + 2 \cdot \tfrac{1}{6} + \cdots + 6 \cdot \tfrac{1}{6} = \tfrac{1+2+3+4+5+6}{6} = \tfrac{21}{6} = 3.5\] 입니다. 주사위에는 3.5라는 눈이 없지만, "평균"은 그 사이 어딘가에 있어도 괜찮아요.
예제 19.4.3 (인디케이터 트릭)
인디케이터 변수 \(I_A\)의 기댓값을 봅시다. \(I_A\)는 1 (\(\omega \in A\))과 0 (\(\omega \notin A\)) 두 값만 갖죠. \[\mathrm{E}[I_A] = 1 \cdot \Pr[A] + 0 \cdot \Pr[A^c] = \Pr[A].\] 그러니까 인디케이터의 기댓값은 그냥 사건의 확률입니다. 단순한 사실이지만, 이게 19.5절에서 보여드릴 마법의 핵심 재료예요.
예제 19.4.4 (기하 분포의 기댓값)
\(X \sim \mathrm{Geo}(p)\)일 때 \(\mathrm{E}[X]\)는 얼마일까요? 정의대로 쓰면 \[\mathrm{E}[X] = \sum_{k=1}^{\infty} k (1-p)^{k-1} p.\] 이 합은 미분 트릭으로 처리할 수 있어요. \(\sum_{k=0}^{\infty} q^k = \frac{1}{1-q}\)를 \(q\)로 미분하면 \(\sum_{k=1}^{\infty} k q^{k-1} = \frac{1}{(1-q)^2}\). 따라서 \(\mathrm{E}[X] = p \cdot \frac{1}{(1-(1-p))^2} = p \cdot \frac{1}{p^2} = \frac{1}{p}\) 입니다. "성공 확률이 \(1/6\)이면 평균 6번 만에 성공" — 직관과 잘 맞죠.
기댓값은 결과별 가중평균이라는 점에서 무게중심으로 비유하면 좋아요. PMF를 막대그래프로 그렸을 때, 그 막대들의 균형점이 \(\mathrm{E}[X]\)입니다. 그래서 분포가 한쪽으로 치우치면 기댓값도 그쪽으로 끌려가요.
정의 19.4.5 (조건부 기댓값)
사건 \(A\) (\(\Pr[A] > 0\))가 주어졌을 때 \(X\)의 조건부 기댓값은 \[\mathrm{E}[X \mid A] = \sum_{x} x \cdot \Pr[X = x \mid A]\] 로 정의합니다. 이건 "\(A\)가 일어났다는 조건 하에서의 평균"이에요. 표본공간을 사건들로 분할하면 전체 기댓값 법칙이 성립합니다: \(S = A_1 \sqcup \cdots \sqcup A_k\)일 때 \(\mathrm{E}[X] = \sum_i \mathrm{E}[X \mid A_i] \Pr[A_i]\).
전체 기댓값 법칙은 "어떤 분기마다 평균이 얼마인지를 알면, 분기 확률로 가중해서 전체 평균을 얻는다"는, 매우 자연스러운 사실입니다. 어려운 기댓값을 작은 케이스로 쪼개 푸는 표준 도구예요.
이제 이 챕터에서 가장 강력한 정리, 그리고 거의 마법처럼 작동하는 도구를 소개합니다.
정리 19.5.1 (기댓값의 선형성)
표본공간 \(S\) 위의 어떤 확률변수 \(X, Y\)와 임의의 상수 \(a, b\)에 대해서도 \[\mathrm{E}[aX + bY] = a\, \mathrm{E}[X] + b\, \mathrm{E}[Y].\] 더 일반적으로 \(\mathrm{E}\!\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} \mathrm{E}[X_i]\). 이 등식은 \(X_i\)들이 독립이든 아니든 항상 성립합니다.
증명
두 변수 \(X, Y\)에 대한 식만 보일게요. 기댓값을 결과별 표현으로 쓰면 \[\mathrm{E}[aX + bY] = \sum_{\omega \in S} (aX(\omega) + bY(\omega)) \Pr[\omega] = a \sum_\omega X(\omega) \Pr[\omega] + b \sum_\omega Y(\omega) \Pr[\omega] = a \mathrm{E}[X] + b \mathrm{E}[Y].\] 합이 선형이라는, 거의 자명한 사실에서 곧장 따라옵니다. 독립성은 어디에도 쓰지 않았다는 점에 주목하세요.
∎
증명은 한 줄짜리예요. 그런데 응용은 정말 풍성합니다. 핵심 패턴은 이래요: 복잡해 보이는 확률변수 \(X\)를 단순한 인디케이터들의 합 \(X = I_1 + I_2 + \cdots + I_n\)으로 쓸 수 있으면, 선형성으로 \(\mathrm{E}[X] = \sum_i \mathrm{E}[I_i] = \sum_i \Pr[A_i]\)가 됩니다. 분포 전체를 알 필요 없이 각 사건의 확률만 알면 평균이 나오는 거예요.
예제 19.5.2 (이항 분포의 평균)
\(X \sim \mathrm{Bin}(n, p)\)의 평균을 PMF로부터 직접 계산하면 \(\sum_k k \binom{n}{k} p^k (1-p)^{n-k}\) — 끈질긴 이항계수 조작이 필요해요. 그런데 \(X = X_1 + \cdots + X_n\)으로 쓰고, \(X_i\)는 \(i\)번째 시행의 인디케이터(\(\mathrm{Bern}(p)\))라 하면 \[\mathrm{E}[X] = \sum_{i=1}^{n} \mathrm{E}[X_i] = \sum_{i=1}^{n} p = np.\] 한 줄에 끝납니다. 그리고 \(X_i\)들이 독립인 게 아니라도 이 등식은 통해요.
예제 19.5.3 (랜덤 순열의 고정점)
\(\{1, 2, \ldots, n\}\)의 랜덤 순열 \(\pi\)에서 고정점은 \(\pi(i) = i\)인 \(i\)의 개수입니다. \(F\)를 고정점의 수라 하면 \(\mathrm{E}[F]\)는 얼마일까요?
인디케이터 트릭. \(X_i = 1\) (\(\pi(i) = i\)일 때), \(0\) (아닐 때). 그러면 \(F = \sum_{i=1}^{n} X_i\)이고 \[\mathrm{E}[X_i] = \Pr[\pi(i) = i] = \frac{(n-1)!}{n!} = \frac{1}{n}.\] 따라서 \(\mathrm{E}[F] = \sum_{i=1}^{n} \frac{1}{n} = 1\). \(n\)이 100이든 백만이든, 평균 고정점 수는 항상 1개예요. 멋지죠.
여기서 \(X_i\)들은 절대 독립이 아닙니다(이미 \(n-1\)개가 고정점이면 마지막도 무조건 고정점). 그래도 선형성은 통합니다.
예제 19.5.4 (쿠폰 수집가 문제)
가챠 게임에서 \(n\)종류의 캐릭터를 모두 모으려면 평균 몇 번 뽑아야 할까요? 매번 \(n\)개 중 하나가 균등 확률로 나오고 독립이라 합시다.
\(T\)를 모두 모을 때까지의 총 횟수, \(T_k\)를 정확히 \(k-1\)종을 모은 상태에서 새로운 종을 처음 얻기까지 걸리는 횟수라 합시다. 그러면 \(T = T_1 + T_2 + \cdots + T_n\) 이에요.
\(k-1\)종을 모은 시점에서 새로운 종이 나올 확률은 \(p_k = (n - (k-1))/n = (n-k+1)/n\). 그래서 \(T_k \sim \mathrm{Geo}(p_k)\)이고 \(\mathrm{E}[T_k] = 1/p_k = n/(n-k+1)\). 선형성으로 \[\mathrm{E}[T] = \sum_{k=1}^{n} \frac{n}{n-k+1} = n \sum_{j=1}^{n} \frac{1}{j} = n H_n\] 입니다. 여기서 \(H_n\)은 \(n\)번째 조화수예요. \(H_n \approx \ln n + \gamma\) 이니까 \(\mathrm{E}[T] \approx n \ln n\). \(n=100\)이면 약 \(518\)번, \(n=1000\)이면 약 \(7485\)번 — 가챠가 왜 그렇게 잔인한지 수학적으로 보이는 결과입니다.
노트 (선형성 vs. 곱의 기댓값)
\(\mathrm{E}[X+Y] = \mathrm{E}[X] + \mathrm{E}[Y]\)는 항상 옳지만, \(\mathrm{E}[XY] = \mathrm{E}[X] \mathrm{E}[Y]\)는 일반적으로 거짓입니다. 단, \(X, Y\)가 독립이면 곱도 분리돼요. 분산이 합으로 분해되려면 독립(또는 적어도 무상관)이 필요한데, 평균이 합으로 분해되는 데에는 그게 필요 없다 — 이 비대칭이 선형성의 힘입니다.
기댓값이 늘 단순한 가중평균처럼 행동하는 건 아니에요. 합이 무한급수가 되거나, 음·양의 값이 섞이거나, 조건부로 다시 쓸 때 미묘한 일들이 벌어집니다. 이 절에서는 그런 두 가지 사례를 다뤄볼게요.
예제 19.6.1 (조건부 기댓값으로 풀기)
다시 기하 분포 \(X \sim \mathrm{Geo}(p)\)의 평균을 보겠습니다. 이번엔 무한급수 대신 조건부 기댓값으로요. 첫 시행이 성공이면 \(X = 1\); 실패면 처음 시행 한 번이 헛수고이고 그 뒤로는 같은 분포가 다시 시작됩니다(메모리리스 성질).
\(A\)를 "첫 시행 성공" 사건이라 하면 \(\Pr[A] = p\), \(\mathrm{E}[X \mid A] = 1\), \(\mathrm{E}[X \mid A^c] = 1 + \mathrm{E}[X]\) 입니다. 전체 기댓값 법칙으로 \[\mathrm{E}[X] = p \cdot 1 + (1-p)(1 + \mathrm{E}[X]).\] 정리하면 \(\mathrm{E}[X] = 1 + (1-p) \mathrm{E}[X]\), 따라서 \(\mathrm{E}[X] = 1/p\). 19.4절에서 미분 트릭으로 얻은 결과와 같지만, 한 줄짜리 자기참조 방정식으로 끝났어요. 무한급수를 다루지 않고도 무한 시행의 평균을 구할 수 있다는 게 조건부 기댓값의 힘입니다.
예제 19.6.2 (성트페테르부르크 역설 — 무한 기댓값)
도박 한 판을 생각해 봅시다. 동전을 앞면이 나올 때까지 던지는데, 처음으로 \(k\)번째 던지기에서 앞면이 나오면 \(2^k\)원을 받습니다. \(X\)를 받는 금액이라 하면 \[\mathrm{E}[X] = \sum_{k=1}^{\infty} 2^k \cdot \Pr[\text{첫 앞면이 } k \text{번째}] = \sum_{k=1}^{\infty} 2^k \cdot \frac{1}{2^k} = \sum_{k=1}^{\infty} 1 = \infty.\] 평균 상금이 무한대! 그러면 이 게임에 참가하기 위해 얼마든 — 백만 원이라도 — 내야 한다는 뜻일까요? 실제로 사람들은 그렇게 행동하지 않습니다. 이게 18세기 베르누이 형제가 제기한 성트페테르부르크 역설이에요. 기댓값이 무한이면 "평균"이라는 직관 자체가 깨질 수 있다는 경고입니다.
노트 (기댓값이 정의되지 않을 수 있다)
이산확률변수의 기댓값 정의 \(\mathrm{E}[X] = \sum_x x \Pr[X=x]\)는 합이 절대수렴할 때만 의미 있어요. 양과 음이 섞여 조건부수렴만 한다면, 합의 순서에 따라 값이 바뀝니다(리만 재배열 정리). 그래서 엄밀히는 \(\mathrm{E}[|X|] = \infty\)인 경우 "기댓값이 존재하지 않는다"고 표현해요. 알고리즘이나 시뮬레이션에서 평균을 다룰 땐 이런 가능성을 잊지 마세요.
그럼에도 불구하고 기댓값과 그 선형성은 조합론, 알고리즘, 그리고 일상의 의사결정에 끊임없이 등장하는 도구입니다. 인디케이터 트릭은 한 번 익숙해지면 거의 모든 "평균 ~ 의 개수" 문제에 통하는 만능 열쇠예요. 다음 챕터에서는 평균만으로는 부족할 때 — 즉, 평균에서 얼마나 벗어나는지를 측정하는 분산과 편차 부등식들 — 을 다루겠습니다.
정리하며
이 챕터에서 챙겨야 할 것: (1) 확률변수는 표본공간에서 \(\mathbb{R}\)로 가는 함수다. (2) 분포는 PMF/CDF로 표현된다. 베르누이·이항·기하·균등을 손에 익혀라. (3) 기댓값은 가중평균이고, 인디케이터의 기댓값은 사건의 확률이다. (4) 기댓값의 선형성은 항상 성립한다 — 독립 없어도. 이게 거의 마법이다. (5) 무한 기댓값처럼 미묘한 경우가 존재하니, 합의 수렴은 늘 의식하라.