수렴이란 무엇인가 — LLN, CLT, 그리고 Monte Carlo까지

ML 논문에서 “수렴”이라는 단어는 아무 맥락 없이 쓰인다. SGD가 수렴한다, MLE가 수렴한다, Monte Carlo 추정이 수렴한다. 그런데 이 수렴들은 모두 다른 의미다. $X_n \to X$라는 기호 하나에 최소 네 가지 다른 정의가 들어 있고, 그 강도 차이가 알고리즘 보장의 강도를 결정한다. 어느 의미의 수렴을 주장하고 있는가?

수렴의 네 가지 얼굴

네 종류의 수렴은 강도 순으로 다음과 같이 정리된다.

$$\text{a.s.} \;\Rightarrow\; \text{in prob} \;\Rightarrow\; \text{in dist} \qquad\text{and}\qquad L^p \;\Rightarrow\; \text{in prob}$$

거의확실수렴(a.s.): $\mathbb{P}(\lim_{n\to\infty} X_n(\omega) = X(\omega)) = 1$. 거의 모든 표본경로 $\omega$가 수렴한다. 가장 강하다.

확률수렴(in probability): 모든 $\varepsilon > 0$에 대해 $\lim_n \mathbb{P}(|X_n - X| > \varepsilon) = 0$. “큰 차이가 생기는 사건의 확률이 0으로 간다”는 진술이지, 각 경로가 수렴한다는 진술이 아니다.

$L^p$ 수렴: $\mathbb{E}[|X_n - X|^p] \to 0$. Markov 부등식으로 바로 in probability를 함의한다.

분포수렴(in distribution): $F_X$의 연속점 $x$에서 $F_{X_n}(x) \to F_X(x)$. 분포만 비교하며 확률변수 자체는 비교하지 않는다. 가장 약하다.

역이 성립하지 않는 반례들

역이 일반적으로 성립하지 않는다는 것이 핵심이다. Typewriter sequence는 in probability이지만 a.s.가 아니다: $X_n = \mathbf{1}_{[j/2^k,\, (j+1)/2^k]}$ (여기서 $n = 2^k + j$)는 $\mathbb{P}(X_n = 1) = 1/2^k \to 0$이므로 in probability로 0에 수렴하지만, 임의의 $\omega \in (0,1)$에서 $X_n(\omega) = 1$이 무한 번 발생한다. Spike sequence $X_n = n \cdot \mathbf{1}_{[0, 1/n]}$은 a.s. 0에 수렴하지만 $\mathbb{E}[|X_n|] = 1$로 $L^1$ 수렴하지 않는다. a.s.와 $L^p$는 서로를 함의하지 않으며 이 두 반례가 그 사실을 보여 준다.

Slutsky 정리는 약한 수렴에서 강한 결론을 끌어내는 도구다. $X_n \xrightarrow{d} X$이고 $Y_n \xrightarrow{p} c$ (상수)이면 $X_n + Y_n \xrightarrow{d} X + c$. MLE 점근 분석에서 표준오차 추정량 $\hat\sigma_n \xrightarrow{p} \sigma$를 알면 $\sqrt{n}(\hat\theta - \theta_0)/\hat\sigma_n \xrightarrow{d} \mathcal{N}(0,1)$이 된다. 분포 수렴만으로는 이 결론에 도달할 수 없고 추가 조건인 확률 수렴이 필요하다.

약법칙과 강법칙 — 같은 결론, 다른 강도

대수의 법칙(LLN)은 두 형태가 있다.

약법칙(WLLN): $\{X_i\}$ i.i.d., $\mathbb{E}[X_i] = \mu$, $\text{Var}(X_i) = \sigma^2 < \infty$이면 $\bar X_n \xrightarrow{p} \mu$. 증명은 Chebyshev 부등식 한 줄이다.

$$\mathbb{P}(|\bar X_n - \mu| \geq \varepsilon) \leq \frac{\text{Var}(\bar X_n)}{\varepsilon^2} = \frac{\sigma^2}{n\varepsilon^2} \to 0$$

분산이 $\sigma^2/n$으로 감소한다는 관찰이 전부다. Khintchine의 WLLN은 분산 가정조차 제거한다 — $L^1$만으로 충분하다. 특성함수 $\varphi(t/n)^n \to e^{i\mu t}$이고 Lévy 연속정리로 분포 수렴이 나오며, 상수로의 분포 수렴은 확률 수렴을 함의한다.

강법칙(SLLN): 같은 결론 $\bar X_n \to \mu$이지만 in probability가 아니라 a.s.다.

WLLN: 특정 n에서 P(|X̄_n - μ| > ε) → 0
      (각 n마다 오차가 클 확률이 작아짐)

SLLN: P({ω : X̄_n(ω) → μ}) = 1
      (한 번 추출된 경로 전체가 수렴)

Kolmogorov 0-1 법칙은 $\{\bar X_n \to \mu\}$가 tail event임을 보장하므로 이 사건의 확률은 0 또는 1이다. SLLN은 그것이 1임을 확정한다. Glivenko-Cantelli 정리는 이를 균등 수렴으로 강화한다.

$$\sup_{x \in \mathbb{R}} |\hat F_n(x) - F(x)| \xrightarrow{a.s.} 0$$

PAC learning의 generalization 보장은 여기서 시작한다.

중심극한정리 — 수렴의 모양

LLN은 $\bar X_n$이 $\mu$로 수렴한다고 말한다. CLT는 그 수렴의 속도와 형태를 명시한다.

증명의 핵심은 세 단계다: 합의 특성함수가 곱으로 분해되고, Taylor 전개로 각 인수를 근사하며, 극한이 알려진 특성함수로 수렴한다. Lindeberg-Feller 일반화는 i.i.d. 가정을 제거한다 — “어떤 단일 항도 합 전체를 지배하지 않는다”는 Lindeberg 조건만으로 충분하다. Berry-Esseen 정리는 수렴 속도를 정량화한다.

$$\sup_x |F_{Z_n}(x) - \Phi(x)| \leq \frac{C\rho}{\sigma^3 \sqrt{n}}$$

$O(1/\sqrt{n})$ 균등 수렴이다. MLE의 점근 정규성 $\sqrt{n}(\hat\theta - \theta_0) \xrightarrow{d} \mathcal{N}(0, I^{-1})$, 신뢰구간, A/B 테스트의 정규 근사 — 전부 이 정리의 응용이다.

Monte Carlo — 차원의 저주 없는 수렴

Monte Carlo 적분은 LLN과 CLT가 만나는 지점이다. 목표: $I = \mathbb{E}_p[f(X)]$. 추정량: $\hat I_n = \frac{1}{n} \sum f(X_i)$.

• 일관성 (SLLN): $\hat I_n \xrightarrow{a.s.} I$
• 오차 분포 (CLT): $\sqrt{n}(\hat I_n - I) \xrightarrow{d} \mathcal{N}(0, \sigma_f^2)$
• 표준오차: $\sigma_f / \sqrt{n}$ — 차원 $d$에 무관

격자 적분(Riemann)은 $d$차원에서 정확도 $O(n^{-k/d})$를 얻는다. 차원이 늘수록 같은 정확도에 지수적으로 많은 점이 필요하다. Monte Carlo는 $O(1/\sqrt{n})$ 수렴률이 차원과 독립이다. Importance Sampling은 분산을 줄인다. $w(x) = p(x)/q(x)$로 가중하면

$$\hat I_n^{\text{IS}} = \frac{1}{n}\sum w(X_i) f(X_i) \xrightarrow{a.s.} I$$

최적 제안 분포 $q^*(x) \propto |f(x)| p(x)$에서 분산이 0이 된다. VAE의 ELBO 추정, policy gradient, MCMC 사후 추정 모두 이 틀 안에 있다.

정리

• 수렴 종류는 강도가 다르다: a.s. $\Rightarrow$ in prob $\Rightarrow$ in dist, $L^p$ $\Rightarrow