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

Типичные последовательности — это класс случайных последовательностей, обладающих свойствами, которые проявляются с вероятностью, близкой к единице, при достаточно большой длине. Понятие широко используется в теории информации, статистической физике, теории кодирования и алгоритмической теории сложности. Типичные последовательности противопоставляются нетипичным, которые встречаются крайне редко и не вносят существенного вклада в средние характеристики источника данных.

¶Определение и основные свойства

В теории информации типичные последовательности определяются в контексте стационарного источника с дискретным временем и конечным алфавитом. Пусть \(X_1, X_2, \dots, X_n\) — независимые одинаково распределённые случайные величины с распределением \(P\) на алфавите \(\mathcal{A}\). Для последовательности \(x^n = (x_1, \dots, x_n)\) определена эмпирическая энтропия:

\[ H_{\text{emp}}(x^n) = -\frac{1}{n} \log_2 P(x^n) = -\frac{1}{n} \sum_{i=1}^n \log_2 P(x_i). \]

Последовательность \(x^n\) называется типичной (в смысле Шеннона — Макмиллана — Бремана), если её эмпирическая энтропия близка к истинной энтропии источника \(H(X)\):

\[ \left| -\frac{1}{n} \log_2 P(x^n) - H(X) \right| \le \varepsilon, \]

где \(\varepsilon > 0\) — произвольно малая константа. Множество всех таких последовательностей длины \(n\) обозначается \(A_\varepsilon^{(n)}\) и называется типичным множеством.

¶Ключевые свойства типичного множества

1. Вероятность близка к единице: для любого \(\varepsilon > 0\) при достаточно больших \(n\) выполняется \(P(A_\varepsilon^{(n)}) > 1 - \varepsilon\). Это прямое следствие закона больших чисел для эмпирической энтропии.
2. Мощность ограничена: число типичных последовательностей не превышает \(2^{n(H(X) + \varepsilon)}\). При этом для достаточно больших \(n\) оно не меньше \((1 - \varepsilon) 2^{n(H(X) - \varepsilon)}\).
3. Все типичные последовательности приблизительно равновероятны: для любой \(x^n \in A_\varepsilon^{(n)}\) выполняется \(2^{-n(H(X) + \varepsilon)} \le P(x^n) \le 2^{-n(H(X) - \varepsilon)}\).

¶Теорема Шеннона — Макмиллана — Бремана

Фундаментальным результатом, обосновывающим существование типичных последовательностей, является теорема Шеннона — Макмиллана — Бремана (также известная как асимптотическое свойство равнораспределения). Она утверждает, что для стационарного эргодического источника последовательность эмпирических энтропий сходится по вероятности к энтропии источника:

\[ -\frac{1}{n} \log_2 P(X^n) \xrightarrow{P} H(X). \]

Для независимых одинаково распределённых источников это сводится к закону больших чисел. Следствием теоремы является то, что при больших \(n\) почти вся вероятность сосредоточена на типичном множестве, размер которого экспоненциально близок к \(2^{nH(X)}\).

¶Виды типичных последовательностей

В зависимости от контекста и используемого критерия различают несколько видов типичности:

¶Типичность по Шеннону (слабая типичность)

Определяется через близость эмпирической энтропии к истинной. Применима к независимым одинаково распределённым источникам. Является основой для доказательства теоремы Шеннона о кодировании источника без потерь.

¶Типичность по Макмиллану — Бреману (сильная типичность)

Требует, чтобы эмпирические частоты каждого символа в последовательности были близки к теоретическим вероятностям. Для независимых одинаково распределённых источников сильная типичность влечёт слабую, но не наоборот. Сильная типичность удобна при доказательстве теорем для каналов с помехами.

¶Алгоритмическая типичность (колмогоровская сложность)

В алгоритмической теории информации последовательность называется типичной, если её колмогоровская сложность близка к длине. Такие последовательности не имеют регулярной структуры и не могут быть сжаты. Понятие введено Андреем Николаевичем Колмогоровым и развито Леонидом Левиным. Алгоритмически типичные последовательности являются случайными в смысле Мартина-Лёфа.

¶Применение

¶Теория кодирования

Типичные последовательности лежат в основе доказательства теоремы Шеннона о кодировании источника без потерь (сжатие данных). Идея состоит в том, чтобы кодировать только типичные последовательности, а нетипичные — специальным образом (например, с помощью префикса и дополнительного кода). Поскольку вероятность нетипичных последовательностей мала, средняя длина кода стремится к энтропии.

¶Теория информации и связь

В задачах передачи информации по каналу с помехами типичные последовательности используются для построения кодов, исправляющих ошибки. Кодовые слова выбираются из типичного множества, и декодер ищет ближайшую типичную последовательность к принятому сигналу.

¶Статистическая физика

В термодинамике и статистической механике типичные последовательности соответствуют микросостояниям, которые реализуются с подавляющей вероятностью. Энтропия Больцмана \(S = k \ln W\) связана с числом типичных микросостояний \(W \approx 2^{nH}\).

¶Криптография

В криптографии понятие типичных последовательностей используется для анализа случайности генераторов псевдослучайных чисел. Последовательность, которая не является алгоритмически типичной, может быть предсказуема и непригодна для криптографических целей.

¶Примеры

¶Пример 1: Бернуллиевский источник

Рассмотрим источник, выдающий независимые биты с вероятностью \(p\) для единицы и \(1-p\) для нуля. Энтропия источника равна \(H(p) = -p \log_2 p - (1-p) \log_2 (1-p)\). Для \(n=1000\) и \(p=0.5\) типичное множество содержит примерно \(2^{1000}\) последовательностей, но все они имеют почти одинаковое число единиц (около 500). Нетипичные последовательности, например, состоящие из 1000 нулей, имеют ничтожную вероятность \(2^{-1000}\).

¶Пример 2: Текстовый источник

Для русского языка энтропия оценивается примерно в 4.5 бита на символ (для буквенного алфавита). Типичные тексты длиной 1000 символов имеют эмпирическую энтропию, близкую к этому значению. Текст, состоящий из повторяющихся букв, будет нетипичным.

¶Критика и ограничения

Понятие типичных последовательностей имеет ряд ограничений:

• Зависимость от длины: для конечных \(n\) граница \(\varepsilon\) остаётся произвольной, и множество типичных последовательностей не является единственным. Разные авторы могут выбирать разные \(\varepsilon\).
• Неприменимость к коротким последовательностям: для малых \(n\) типичное множество может быть пустым или содержать последовательности, которые интуитивно не кажутся «типичными».
• Алгоритмическая сложность: определение алгоритмической типичности неконструктивно — нельзя алгоритмически проверить, является ли последовательность типичной, из-за неразрешимости проблемы остановки.

¶Источники

1. Шеннон К. «Математическая теория связи» (1948).
2. Макмиллан Б. «Теорема об асимптотическом равнораспределении» (1953).
3. Колмогоров А. Н. «Три подхода к определению понятия «количество информации»» (1965).
4. Ковер Т., Томас Дж. «Элементы теории информации» (2006, русский перевод).
5. Лидский В. В. «Теория информации» (учебное пособие, МФТИ, 2018).