Типичные последовательности и AEP

Почему 1000 подбрасываний монеты почти всегда дают 480-520 орлов? AEP - математический ответ, но за ним стоит глубокая идея: вселенная типичных событий намного меньше пространства всех возможностей, и именно там мы живём.

• **Сжатие без потерь**: типичных последовательностей ≈ 2^{nH}, поэтому нужно ровно nH бит для их кодирования - вот откуда граница Шеннона.
• **Статистическая физика**: энтропия в термодинамике - это AEP для физических систем. Типичные микросостояния = термодинамическое равновесие.
• **ML generalization**: PAC-Bayes теория использует идеи, очень похожие на AEP, для оценки обобщающей способности нейросетей.

Предварительные знания

• KL-Divergence and Cross-Entropy

Типичное множество

Подбросьте монету 1000 раз. Почти наверняка получите около 500 орлов - не ровно 500, но близко. Последовательности с ~500 орлами и ~500 решками называются «типичными». Важный факт: хотя их много, они составляют ничтожную долю всех 2^1000 возможных последовательностей, но почти всю вероятность. Это и есть суть AEP.

**Типичное ε-множество T_ε^(n):** множество последовательностей x^n таких, что |−(1/n) log p(x^n) − H(X)| ≤ ε. Свойства: 1. P(T_ε^(n)) → 1 при n→∞ 2. |T_ε^(n)| ≤ 2^{n(H+ε)} 3. |T_ε^(n)| ≥ (1−ε)·2^{n(H−ε)}. Размер типичного множества ≈ 2^{nH(X)}.

AEP: Asymptotic Equipartition Property

AEP - теорема о законе больших чисел для информации. Если X₁, X₂, ..., Xₙ - независимые одинаково распределённые случайные величины, то −(1/n) log p(X₁,...,Xₙ) сходится по вероятности к H(X). Иначе говоря: почти все длинные последовательности имеют вероятность примерно 2^{−nH}. Это делает всех типичных «равновероятными» в асимптотическом смысле.

**AEP (Теорема):** Если X_i ~ i.i.d. p(x), то (1/n) log(1/p(X^n)) → H(X) по вероятности (LLN для −log p). Следствие: для любого ε > 0 при достаточно большом n: Pr[|−(1/n)log p(X^n) − H(X)| > ε] → 0.

Совместная типичность

Совместная типичность - расширение AEP на два связанных источника. Пара последовательностей (x^n, y^n) совместно типична, если эмпирическая совместная энтропия близка к H(X,Y). Ключевой результат: если X и Y независимы, то случайная пара (X^n, Y^n) совместно типична с вероятностью ≈ 2^{-nI(X;Y)}. Это центрально для доказательства теоремы о кодировании канала.

**Множество совместно типичных пар:** A_ε^(n) = {(x^n, y^n): |−(1/n)log p(x^n) − H(X)| ≤ ε, |−(1/n)log p(y^n) − H(Y)| ≤ ε, |−(1/n)log p(x^n,y^n) − H(X,Y)| ≤ ε}. Размер ≈ 2^{nH(X,Y)}. Вероятность совместно типичной пары при независимых X,Y: ≈ 2^{-nI(X;Y)}.

Случайное кодирование

Доказательство теоремы Шеннона использует элегантный приём: выбрать кодовую книгу случайно и показать, что в среднем она хороша. Генерируем 2^{nR} кодовых слов случайно из p(x). Декодер ищет единственное кодовое слово, совместно типичное с полученным y^n. При R < C вероятность ошибки стремится к нулю по n → ∞.

**Схема случайного кодирования:** 1. Генерируем M=2^{nR} кодовых слов из p^n(x). 2. Для сообщения m отправляем X^n(m). 3. Декодер ищет m̂: X^n(m̂) совместно типично с Y^n. Анализ ошибок: P(ошибка для m) ≤ P(нет сов.тип.) + ∑_{m≠m̂} P(сов.тип.) ≤ ε + 2^{n(R-I+3ε)} → 0 при R < I(X;Y) = C.

Ключевые идеи

• **Типичное множество** T_ε: последовательности с эмпирической энтропией ≈ H(X). Несёт почти всю вероятность, но занимает ≈ 2^{nH} элементов.
• **AEP:** −(1/n) log p(X^n) → H(X) по вероятности. Все типичные последовательности примерно равновероятны ≈ 2^{−nH}.
• **Совместная типичность:** (x^n, y^n) типичны совместно. Вероятность случайного попадания независимой пары ≈ 2^{−nI(X;Y)}.
• **Случайное кодирование:** доказательство теоремы Шеннона через усреднение по случайным кодовым книгам.

Связанные темы

AEP - математическое сердце теории информации, связывающее все разделы:

• Канал связи и теорема Шеннона — AEP используется в доказательстве теоремы о кодировании канала
• Network Information Theory — Многопользовательские теоремы доказываются аналогичными методами
• Information Theory в Deep Learning — PAC-Bayes и обобщающая способность используют идеи близкие к AEP

Вопросы для размышления

• AEP говорит: «почти все длинные последовательности типичны». Что происходит с нетипичными - насколько они вероятны и что с ними делать?
• Случайное кодирование доказывает существование хорошего кода. Почему этого недостаточно для практики? Какие дополнительные свойства нужны реальным кодам?
• Связь между AEP и законом больших чисел: в чём сходство и в чём отличие?

Связанные уроки

• prob-22-concentration