Типичные последовательности¶
Типичные последовательности — это класс случайных последовательностей, обладающих свойствами, которые проявляются с вероятностью, близкой к единице, при достаточно большой длине. Понятие широко используется в теории информации, статистической физике, теории кодирования и алгоритмической теории сложности. Типичные последовательности противопоставляются нетипичным, которые встречаются крайне редко и не вносят существенного вклада в средние характеристики источника данных.
¶Определение и основные свойства
В теории информации типичные последовательности определяются в контексте стационарного источника с дискретным временем и конечным алфавитом. Пусть \(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)}\) и называется типичным множеством.
¶Ключевые свойства типичного множества
- Вероятность близка к единице: для любого \(\varepsilon > 0\) при достаточно больших \(n\) выполняется \(P(A_\varepsilon^{(n)}) > 1 - \varepsilon\). Это прямое следствие закона больших чисел для эмпирической энтропии.
- Мощность ограничена: число типичных последовательностей не превышает \(2^{n(H(X) + \varepsilon)}\). При этом для достаточно больших \(n\) оно не меньше \((1 - \varepsilon) 2^{n(H(X) - \varepsilon)}\).
- Все типичные последовательности приблизительно равновероятны: для любой \(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\) типичное множество может быть пустым или содержать последовательности, которые интуитивно не кажутся «типичными».
- Алгоритмическая сложность: определение алгоритмической типичности неконструктивно — нельзя алгоритмически проверить, является ли последовательность типичной, из-за неразрешимости проблемы остановки.
¶Источники
- Шеннон К. «Математическая теория связи» (1948).
- Макмиллан Б. «Теорема об асимптотическом равнораспределении» (1953).
- Колмогоров А. Н. «Три подхода к определению понятия «количество информации»» (1965).
- Ковер Т., Томас Дж. «Элементы теории информации» (2006, русский перевод).
- Лидский В. В. «Теория информации» (учебное пособие, МФТИ, 2018).