개념 정리 AEP(Asymptotic Equipartition Property)

AEP(Asymptotic Equipartition Property) 란?

i.i.d. 확률변수 $(X_1, \dots, X_N)$를 많이 뽑으면, 긴 시퀀스 $(x_1, \dots, x_N)$의 확률 $p(x_1, \dots, x_N)$는 대체로 $2^{-NH(X)}$ 크기와 비슷해집니다.

우리가 설명하고 싶은 핵심은 다음 식의 연결입니다.

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

이 식이 왜 **“길이가 길어지면, typical한 시퀀스들은 확률이 대략 비슷해진다”**로 이어지는가? 핵심은 로그식 $\to$ 확률식으로 바꾸는 단계에 있습니다.

---

1. 한 개 사건의 surprisal

확률이 $p(x)$인 사건 $x$의 surprisal은 $-\log p(x)$입니다.

• 확률이 큰 사건: 덜 놀랍다.
• 확률이 작은 사건: 더 놀랍다.

예를 들어 $\log$ base 2이면:

• $p(x) = 1/2$ 이면 surprisal = 1 bit
• $p(x) = 1/4$ 이면 surprisal = 2 bits
• 즉, 희귀할수록 surprisal이 큽니다.

2. 엔트로피는 평균 surprisal

확률변수 $X$의 엔트로피는 $H(X) = \mathbb{E}[-\log p(X)]$입니다.

즉 엔트로피는 **“이 분포에서 샘플 하나를 뽑을 때 평균적으로 얼마나 놀라운가?”**를 나타냅니다.

3. 이제 시퀀스를 보자

$(X_1, \dots, X_N)$이 **i.i.d.**라고 합시다. 그러면 시퀀스 $X^N = (X_1, \dots, X_N)$의 확률은 독립성에 의해 곱으로 쪼개집니다.

$$p(X^N) = p(X_1, \dots, X_N) = \prod_{i=1}^N p(X_i)$$

4. 시퀀스 전체 surprisal

시퀀스 전체의 surprisal은 $-\log p(X^N)$입니다. 위의 곱 공식 때문에 다음과 같이 변합니다.

$$-\log p(X^N) = -\log \prod_{i=1}^N p(X_i) = \sum_{i=1}^N -\log p(X_i)$$

즉, 시퀀스 전체 surprisal은 각 샘플 surprisal의 합입니다.

5. $N$으로 나누면 평균 surprisal

$$-\frac{1}{N}\log p(X^N) = \frac{1}{N}\sum_{i=1}^N -\log p(X_i)$$

이건 정확히 시퀀스 한 글자당 평균 surprisal입니다. 즉 왼쪽 식은 갑자기 이상한 게 아니라, 그냥 “긴 시퀀스의 글자당 평균 정보량”입니다.

6. 큰 수의 법칙 적용

$-\log p(X_i)$들도 **i.i.d.**이므로 큰 수의 법칙에 의해 다음이 성립합니다.

$$\frac{1}{N}\sum_{i=1}^N -\log p(X_i) \to \mathbb{E}[-\log p(X)] = H(X)$$

따라서, $-\frac{1}{N}\log p(X^N) \to H(X)$가 됩니다. 이것이 AEP의 핵심 식입니다.

7. 여기까지의 뜻

지금까지 얻은 뜻은 딱 이것입니다. 긴 시퀀스를 하나 뽑으면, 그 시퀀스의 글자당 surprisal은 거의 $H(X)$입니다.

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

아직 여기서는 “시퀀스들끼리 확률이 비슷하다”는 말을 안 했습니다. 지금은 그냥 per-symbol log-probability가 $H$ 근처라는 말만 한 상태입니다.

8. 이제 양변에 $N$을 곱함

$-\frac{1}{N}\log p(X^N) \approx H(X)$ 이면 $-\log p(X^N) \approx NH(X)$ 입니다.

즉, 시퀀스 전체 surprisal은 대략 $NH(X)$입니다.

9. 이제 로그를 풀어줌 (핵심 단계)

위 식을 다시 확률에 대한 식으로 바꾸려면 지수(exponential)를 취하면 됩니다. $\log$ base 2라고 하면 다음과 같습니다.

$$p(X^N) \approx 2^{-NH(X)}$$

이게 중간에 빠지면 안 되는 핵심 단계입니다.

10. 이제 비로소 “확률이 비슷하다”가 나옴

AEP는 높은 확률로 뽑힌 시퀀스 $X^N$에 대해 $p(X^N) \approx 2^{-NH(X)}$라고 말합니다.

그러면 이런 시퀀스들은 다들 확률이 대략 같은 크기입니다.

• 어떤 typical한 시퀀스도 대략 $2^{-NH}$
• 다른 typical한 시퀀스도 대략 $2^{-NH}$
• 이므로, typical한 시퀀스들끼리는 확률이 대략 비슷하다가 됩니다. 이건 갑자기 튀어나온 말이 아니라, 바로 직전 식에서 나온 결론입니다.

---

11. 그런데 “모든 시퀀스”가 아니다

여기가 중요합니다. AEP가 말하는 건 모든 길이 $N$ 시퀀스의 확률이 비슷해진다가 아닙니다. 정확히는 확률적으로 실제 자주 관측되는 typical한 시퀀스들의 확률이 $2^{-NH}$ 근처로 몰린다는 것입니다. 즉 “비슷한 확률”은 공간 전체가 아니라 typical set 안에서 성립합니다.

12. typical set을 식으로 쓰면

typical set $A_\varepsilon^{(N)}$를 다음과 같이 정의합니다.

$$A_\varepsilon^{(N)} = \left\{ x^N : \left| -\frac{1}{N}\log p(x^N) - H(X) \right| < \varepsilon \right\}$$

이 정의를 조금 바꾸면 다음과 같습니다.

$$H(X) - \varepsilon < -\frac{1}{N}\log p(x^N) < H(X) + \varepsilon$$

여기에 $N$을 곱하고 로그를 풀면:

$$2^{-N(H(X) + \varepsilon)} < p(x^N) < 2^{-N(H(X) - \varepsilon)}$$

이제 정말 명확합니다. typical set 안의 모든 시퀀스는 확률이 $2^{-NH(X)}$ 근처 범위 안에 있습니다.

13. 왜 equipartition이라는 이름을 쓰는가

원래 partition은 “나누다” 느낌이고, equipartition은 “거의 균등하게 나눠진다”는 느낌입니다. 하지만 AEP에서 균등하다는 말은 확률이 완전히 똑같은 균일분포라는 뜻이 아니라, 로그 스케일에서 거의 같다는 약한 의미입니다. 높은 확률을 차지하는 typical한 시퀀스들의 확률이 같은 지수적 크기($2^{-NH}$) 정도라는 뜻이죠.

14. 아주 간단한 예시: biased coin

동전을 던지는데 앞면(0.9), 뒷면(0.1)이라고 합시다. 길이 $N$ 시퀀스 중에는 별별 게 다 있지만, 실제로 자주 나오는 건 대체로 **H가 약 90%, T가 약 10%**인 시퀀스들입니다.

이런 전형적인 시퀀스들은 확률이 대략 비슷한 지수 크기를 가집니다. 즉, 너무 치우치거나 이상한 시퀀스가 아닌, 실제 분포의 평균적 성질을 반영한 시퀀스들끼리는 확률이 전부 $2^{-NH(X)}$ 근처에 모입니다.

15. 그래서 AEP의 전체 흐름은

1. i.i.d. 시퀀스의 확률: $p(X^N) = \prod p(X_i)$
2. 로그를 취하면 합: $-\log p(X^N) = \sum -\log p(X_i)$
3. $N$으로 나누면 평균: $-\frac{1}{N}\log p(X^N) = \frac{1}{N}\sum -\log p(X_i)$
4. 큰 수의 법칙: $-\frac{1}{N}\log p(X^N) \to H(X)$
5. typical한 시퀀스에 대해: $-\log p(X^N) \approx NH(X)$
6. 로그를 풀면: $p(X^N) \approx 2^{-NH(X)}$
7. 결론: typical한 시퀀스들은 대략 비슷한 확률 크기를 가진다.

16. 한 줄로 다시 요약

느끼신 비약을 메우는 핵심은 이것 하나입니다.

$$-\frac{1}{N}\log p(X^N) \approx H \quad \Longrightarrow \quad p(X^N) \approx 2^{-NH}$$

즉 AEP 식은 직접적으로는 평균 log-probability에 대한 말이고, 거기서 한 번 지수화를 해야 비로소 typical한 시퀀스들의 확률이 서로 비슷하다는 말이 나옵니다.