개념 정리 : Method of Types : Large Deviations for Empirical Distributions : Sanov’s Theorem

**Typical Set의 정량화: Method of Types와 KL Divergence**

**Empirical Distribution, Method of Types, and Large Deviations**

**Large Deviations of Empirical Distributions (Sanov-type view)**

 

 

먼저 큰 흐름

전체 흐름은 이렇게 이어집니다.

1. AEP: 긴 시퀀스의 평균 surprisal이 entropy로 갑니다.
2. Typical Set: 그래서 실제로 자주 나오는 시퀀스들은 per-symbol log-probability가 $H$ 근처에 몰립니다.
3. Method of Types / Large Deviations: 왜 그런 시퀀스들만 자주 나오고, 원래 분포에서 많이 벗어난 시퀀스는 드문지를 **경험적 분포(empirical distribution)**와 KL divergence로 정량화합니다.

즉 이건 완전히 새로운 이야기가 아니라, **“typical set을 더 세밀하게 설명하는 단계”**라고 보시면 됩니다.

---

1. AEP에서는 무엇을 봤는가

AEP에서는 i.i.d. 시퀀스 $X^N$에 대해 다음과 같은 식을 봅니다.

$$-\frac{1}{N}\log p(X^N) \to H(X)$$

뜻은, 긴 시퀀스를 하나 뽑으면 높은 확률로 그 시퀀스의 per-symbol surprisal이 entropy에 가까워진다는 것입니다. 그래서 typical set이라는 개념이 자연스럽게 나옵니다.

2. Typical set에서는 무엇을 말하는가

Typical set은 대략 $-\frac{1}{N}\log p(x^N) \approx H(X)$를 만족하는 시퀀스들의 집합입니다. 즉:

• 실제로 자주 나오는 시퀀스들
• 확률이 대략 $2^{-NH(X)}$ 규모인 시퀀스들
• 원래 분포의 평균적인 성질을 반영하는 시퀀스들
• 을 모아놓은 집합입니다.

3. 여기서 자연스럽게 생기는 다음 질문

Typical set을 이해한 다음에는 이런 질문이 생깁니다.

“어떤 시퀀스가 전형적이고, 어떤 시퀀스가 비전형적인가? 그 차이를 더 구체적으로 설명할 수는 없을까?”

이 질문에 답하는 방식이 바로 경험적 분포를 보는 관점입니다.

4. 경험적 분포(empirical distribution)란 무엇인가

길이 $N$짜리 시퀀스를 하나 관측했다고 합시다. 예를 들어 2개 상태만 있는 경우, 상태 1이 $N_1$번, 상태 2가 $N_2$번 나왔다면 이 시퀀스가 보여준 실제 비율은 다음과 같습니다.

$$q = \left( \frac{N_1}{N}, \frac{N_2}{N} \right)$$

이 $q$를 경험적 분포(empirical distribution) 또는 type이라고 부릅니다.

• $P$: 원래 샘플을 만들어내는 진짜 분포
• $q$: 이번에 관측된 시퀀스가 보여준 빈도 비율

5. 왜 경험적 분포를 보는가

시퀀스가 typical한지 아닌지는 결국 **“그 시퀀스가 원래 분포의 통계적 성질을 얼마나 잘 반영하고 있는가”**와 연결됩니다. 예를 들어 biased coin에서 $P(H) = 0.9, P(T) = 0.1$이라면:

• H가 대략 90%, T가 대략 10% 나온 시퀀스는 전형적이고
• H와 T가 반반 나온 시퀀스는 비전형적입니다.

즉 typicality는 그 시퀀스의 경험적 분포 $q$가 진짜 분포 $P$와 얼마나 가까운가로 볼 수 있습니다.

6. 그 “가까움”을 재는 것이 KL divergence

그 차이를 재는 대표적인 양이 $D(q\|P)$, 즉 KL divergence입니다. 직관적으로는 다음과 같습니다.

• $q$가 $P$와 비슷하면 KL이 작고
• $q$가 $P$와 다르면 KL이 큽니다.

즉 KL은 관측된 경험적 분포가 진짜 분포에서 얼마나 벗어났는가를 재는 양입니다.

7. 핵심 식의 의미

이제 핵심 식은 대략 이렇게 씁니다.

$$P(\hat{P}_N \approx q) \approx e^{-ND(q\|P)}$$

또는 2상태의 경우에는 $P(N_1, N_2) \approx e^{-ND(q|P)}$처럼 쓸 수 있습니다. 뜻은 아주 간단합니다. 길이 $N$ 샘플에서 경험적 분포가 $q$처럼 보일 확률은 $q$가 $P$에서 멀어질수록 지수적으로 작아진다는 것입니다.

8. 왜 이것이 typical set의 심화판인가

Typical set은 “자주 나오는 시퀀스들은 전형적인 확률 규모를 가진다”는 이야기였습니다. Method of types는 한 단계 더 들어가서, 시퀀스를 하나하나 보는 대신 **“같은 경험적 분포를 가진 시퀀스들끼리 묶어서 본다”**는 것입니다.

그러면:

• 진짜 분포와 가까운 type은 자주 나오고
• 멀리 벗어난 type은 드물게 나옵니다.

즉 typical set은 대략 **“KL이 작은 type들에 속한 시퀀스들의 모임”**으로 이해할 수 있습니다.

9. biased coin으로 직관

예를 들어 $P(H) = 0.9, P(T) = 0.1$이라고 합시다. 그러면 경험적 분포가 $q = (0.9, 0.1)$에 가까운 것은 자연스럽습니다. 반대로 $q = (0.5, 0.5)$라면 굉장히 비전형적입니다. 원래 분포는 앞면이 90% 나오는데, 샘플에서는 반반 나왔기 때문입니다.

이런 deviation이 나올 확률은 $e^{-ND((0.5, 0.5)|(0.9, 0.1))}$처럼 줄어듭니다. 즉 $N$이 커질수록 이런 일은 지수적으로 드물어집니다.

10. large deviation이라는 이름이 왜 붙는가

큰 수의 법칙 때문에 경험적 분포는 보통 진짜 분포 쪽으로 갑니다. 그런데도 가끔은 원래 분포에서 많이 벗어난 결과가 나올 수 있습니다. 이런 **“전형적인 행동에서 크게 벗어나는 사건”**이 얼마나 드문지를 다루는 것이 large deviation theory입니다.

여기서는 그 드묾의 지수율을 KL divergence가 주고 있습니다. 그래서 $e^{-ND(q\|P)}$ 꼴이 나오는 것입니다.

11. method of types라는 이름이 왜 붙는가

여기서 type은 시퀀스의 “빈도 패턴”입니다. 예를 들어 길이 10에서 H가 9번, T가 1번 나온 모든 시퀀스는 순서는 달라도 같은 type입니다.

• HHHHHHHHHT
• HTHHHHHHHH
• THHHHHHHHH
• 는 모두 같은 경험적 분포 $q = (0.9, 0.1)$를 가집니다. Method of types는 이렇게 시퀀스를 경험적 분포별로 묶어서 그 개수와 확률을 계산하는 방법입니다.

12. Sanov’s theorem은 어디에 있는가

Sanov 정리는 이보다 더 일반적인 큰 그림입니다. 거칠게 말하면, i.i.d. 샘플의 경험적 분포가 어떤 집합 $\Gamma$ 안에 들어갈 확률은 KL divergence를 rate function으로 하여 지수적으로 감소한다는 내용입니다. 그래서 위의 식들은 Sanov 정리의 핵심 감각과 연결됩니다.

13. 전체를 한 번에 묶으면

이제 흐름을 한 번에 쓰면 이렇습니다.

• AEP: 긴 시퀀스의 per-symbol surprisal이 entropy로 갑니다.
• Typical set: 실제로 자주 나오는 시퀀스들은 per-symbol log-probability가 $H(X)$ 근처에 몰립니다.
• Method of types: 이런 전형성을 “경험적 분포가 진짜 분포와 가깝다”는 말로 더 구체화합니다.
• Large deviations / Sanov: 경험적 분포가 진짜 분포에서 벗어날 확률은 대략 $e^{-ND(q\|P)}$ 꼴로 지수적으로 줄어듭니다.

14. 한 문장으로 핵심만 압축하면

Typical set은 원래 분포와 비슷한 경험적 분포를 가진 시퀀스들의 집합이고, 원래 분포에서 멀리 벗어난 경험적 분포는 KL divergence만큼 지수적으로 드물어진다.

이 문장이 AEP, typical set, method of types, large deviations를 가장 자연스럽게 연결해줍니다.

15. 아주 짧은 요약

• 이건 typical set과 따로 노는 내용이 아니라 그걸 더 정량적으로 설명하는 단계입니다.
• 시퀀스를 경험적 분포 $q$별로 묶어 봅니다.
• $q$가 진짜 분포 $P$와 가까우면 typical하고, 멀면 atypical합니다.
• 그 드묾의 정도가 $e^{-ND(q|P)}$로 주어집니다.
• 즉, 전형적이지 않은 비율은 왜 거의 안 나오나를 KL divergence로 설명하는 내용입니다.