개념 정리 : typical set

1. typical set은 왜 등장하나요?

AEP가 말한 핵심은 다음과 같았습니다.

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

즉 긴 시퀀스 $X^N$을 하나 뽑으면, 높은 확률로 $-\frac{1}{N}\log p(X^N) \approx H(X)$가 됩니다. 여기서 자연스럽게 이런 생각을 하게 됩니다.

“그럼 실제로 자주 나오는 시퀀스들은 $-\frac{1}{N}\log p(x^N)$가 $H(X)$ 근처인 애들 아니냐?”

이런 시퀀스들만 따로 모은 집합이 바로 typical set입니다.

---

2. 정의

보통 $\varepsilon > 0$를 하나 정하고, 길이 $N$에 대한 typical set을 다음과 같이 정의합니다.

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

뜻은 다음과 같습니다.

• 시퀀스 $x^N$의 per-symbol surprisal(즉 $-\frac{1}{N}\log p(x^N)$)이 엔트로피 $H(X)$와 거의 같은 시퀀스들만 모아둔 집합입니다.

---

3. 말로 바꾸면

이 정의를 말로 바꾸면 **“전형적인 시퀀스들의 모임”**입니다. 왜 전형적이냐면, AEP에 따르면 실제로 랜덤하게 시퀀스를 뽑았을 때 높은 확률로 이런 조건을 만족하기 때문입니다. 즉 실제로 자주 관측되는 쪽이 이 집합 안에 몰립니다.

---

4. 이 정의가 왜 중요한가요?

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

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

양변에 $N$을 곱하면:

$$N(H(X) - \varepsilon) < -\log p(x^N) < N(H(X) + \varepsilon)$$

이제 로그를 풀면:

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

즉, typical set 안에 있는 시퀀스들은 전부 확률이 거의 비슷한 크기를 가집니다. 바로 이 점 때문에 typical set이 강력합니다.

---

5. AEP가 typical set에 대해 주는 핵심 결론

AEP 때문에 큰 $N$에서는 다음이 성립합니다.

(1) 확률질량이 대부분 typical set에 있다

$$P(X^N \in A_\varepsilon^{(N)}) \to 1$$

즉 길이가 충분히 길면, 랜덤하게 뽑은 시퀀스는 거의 항상 typical set 안에 들어갑니다. 가능한 모든 시퀀스가 중요한 게 아니라, 실제로는 typical set이 확률질량을 거의 다 차지합니다.

(2) typical set 안의 각 시퀀스 확률은 대략 같다

방금 본 것처럼 $p(x^N) \approx 2^{-NH(X)}$입니다.

(3) 그래서 typical set 크기는 대략 $2^{NH(X)}$

왜냐하면:

• typical set 전체 확률 $\approx$ 1
• 각 원소 확률 $\approx$ $2^{-NH}$
• 그러면 원소 개수는 대략 $\frac{1}{2^{-NH}} = 2^{NH}$ 정도여야 합니다. 이 성질은 정보이론에서 엄청나게 중요한 결론입니다.

5.5 좀 더 직관적으로

여기서 “typical set이 중요하다”는 말은 가능한 시퀀스 개수의 대부분을 차지한다는 뜻이 아닙니다. 정확한 뜻은, 랜덤하게 시퀀스를 생성했을 때 그 결과가 typical set 안에 들어갈 확률이 거의 1에 가깝다는 것입니다. 즉 중요한 것은 원소 수(count)가 아니라 확률질량(probability mass)입니다.

이 직관은 정규분포의 중앙 영역을 떠올리면 이해하기 쉽습니다. 정규분포에서는 전체 실수축이 매우 넓지만, 실제 확률의 대부분은 평균 근처의 중앙부에 집중되어 있고 양쪽 꼬리에는 확률이 거의 없습니다. typical set도 이와 비슷하게, 가능한 모든 시퀀스 중 일부분이지만 실제로 관측될 가능성의 대부분이 집중된 전형적인 시퀀스들의 집합이라고 이해하면 됩니다.

“중앙부분에 확률이 몰리는 그림과 비슷한 직관이다”

---

6. 여기서 조심할 점

많이 헷갈리는 부분인데, “most sequences”와 “most probability”는 다릅니다. 가능한 길이 $N$ 시퀀스 개수는 엄청 많습니다. 예를 들어 이진 시퀀스면 총 $2^N$개입니다. 그런데 그중 대부분의 확률질량은 typical set에 몰립니다.

즉:

• 개수로 모든 시퀀스가 비슷한 건 아님
• 하지만 실제로 생성될 가능성은 typical set 쪽에 집중됨
• 이게 핵심입니다.

---

7. 공정한 동전 예시

공정한 동전이면:

• H 확률 (1/2)
• T 확률 (1/2)
• 엔트로피 $H(X) =$ 1

길이 $N$의 모든 시퀀스 확률이 $(1/2)^N = 2^{-N}$으로 똑같습니다. 이 경우는 사실 전체 집합 자체가 거의 typical합니다. 왜냐하면 모든 시퀀스의 per-symbol surprisal이 정확히 1이기 때문입니다. 즉 공정한 동전에서는 typical set 개념이 좀 덜 드라마틱합니다. 모든 시퀀스가 원래부터 확률이 같기 때문입니다.

---

8. biased coin 예시가 더 본질적입니다

이제 앞면(0.9), 뒷면(0.1)이라고 합시다. 이 경우 길이 $N$ 시퀀스의 확률은 전부 다릅니다.

• HHHHH...H: 확률이 큽니다.
• TTTTT...T: 확률이 매우 작습니다.
• H와 T가 반반인 것: 그렇게 자주 안 나옵니다.

그런데 실제로 자주 나오는 건 H가 약 90%, T가 약 10% 들어 있는 시퀀스들입니다. 이런 전형적인 시퀀스들이 바로 typical set 근처입니다. 즉 typical set은 대충 말해 **“분포의 평균적인 성질을 반영하는 시퀀스들의 집합”**입니다.

---

9. 왜 “전형적”이라는 말을 쓰나요?

예를 들어 $p(H) = 0.9, p(T) = 0.1$인데 길이 100의 시퀀스가 다음과 같다면:

• H 90개, T 10개쯤 있으면: 전형적
• H 50개, T 50개면: 비전형적
• T 80개면: 매우 비전형적

왜냐하면 소스의 본래 통계적 성질을 잘 반영하는 쪽이 전형적이기 때문입니다. 즉 typical set은 단순히 “확률이 큰 시퀀스 몇 개”가 아니라, **“소스가 장기적으로 보여주는 평균적 패턴을 따르는 시퀀스들의 모임”**이라고 보는 게 더 정확합니다.

---

10. typical set의 핵심 성질 3개

보통 세 가지로 요약합니다.

1. 높은 확률: $P(A_\varepsilon^{(N)}) \to 1$. 대부분의 확률질량이 여기에 있습니다.
2. 거의 같은 확률: 모든 $x^N \in A_\varepsilon^{(N)}$에 대해 $p(x^N) \approx 2^{-NH}$로 확률이 거의 같습니다.
3. 개수는 대략 $2^{NH}$: $|A_\varepsilon^{(N)}| \approx 2^{NH(X)}$.

---

11. 왜 개수가 $2^{NH}$개쯤 되나요?

직관만 쓰면 아주 간단합니다.

• typical set 전체 확률 $\approx$ 1
• 원소 하나 확률 $\approx$ $2^{-NH}$
• 그러면 원소 수는 $\approx \frac{1}{2^{-NH}} = 2^{NH}$입니다. 이것은 엄밀한 증명 전 단계 직관인데, 감을 잡기에 가장 좋습니다.

---

12. compression과의 연결

이게 왜 대단하냐면, 길이 $N$짜리 시퀀스 전체를 구분하려면 원래 경우의 수가 엄청 많습니다. 하지만 실제로 중요한 건 typical set에 있는 약 $2^{NH}$개의 시퀀스뿐입니다. 그럼 이걸 식별하려면 필요한 비트 수가 대략 다음과 같습니다.

$$\log_2(2^{NH}) = NH$$

즉 한 글자당 $H$비트가 필요합니다. 이것이 바로 엔트로피가 최적 압축률의 한계가 되는 이유입니다.

---

13. 한 문장 직관

typical set은 **“길이가 길어졌을 때 실제로 거의 항상 나오게 되는, 전형적인 시퀀스들의 집합”**입니다. 그리고 이 집합 안에서는 각 시퀀스 확률이 거의 같고, 전체 확률질량은 거의 다 여기에 있으며, 원소 수는 대략 $2^{NH}$입니다.

---

14. 아주 짧게 요약

AEP가 $-\frac{1}{N}\log p(X^N) \to H(X)$를 말해주면, 그 근처에 있는 시퀀스들만 모아서 typical set을 정의합니다. 그 결과 랜덤 시퀀스는 거의 항상 그 집합 안에 들어가고, 그 집합 안 시퀀스들은 확률이 대략 $2^{-NH}$이며, 그래서 개수는 대략 $2^{NH}$개입니다.