§ 1.7. Теорема о высоковероятных множествах дискретного источника без памяти

Рассмотрим дискретный источник без памяти, выбирающий сообщения из конечного множества Согласно определению источника без памяти вероятность каждой последовательности сообщений на его выходе может быть записана в виде

где распределение вероятностей на множестве Будем полагать, что для всех . В противном случае всегда можно перейти к рассмотрению суженного множества, для которого это предположение верно.

Пусть энтропия ансамбля некоторое положительное число. Определим подмножество множества следующим образом:

где собственная информация последовательности

Теорема 1.7.1. Для любых положительных чисел и 6 найдется такое, что для всех выполняются следующие неравенства:

где число элементов в множестве

Доказательство. В силу отсутствия памяти у источника

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

применить закон больших чисел, из которого следует, что при любых найдется такое, что при всех

или

Нетрудно увидеть, что вероятность равна левой части неравенства (1.7.7) и, следовательно, неравенство (1.7.3) справедливо.

С другой стороны, из определения множества следует, что для всякой последовательности

Суммируя обе части левого неравенства по всем элементам получим следующую цепочку неравенств:

откуда следует правое неравенство в (1.7.4). Суммируя теперь обе части правого неравенства в (1.7.8) по всем элементам получим, что для достаточно больших

что дает левое неравенство в (1.7.4). Теорема доказана.

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

Если т. е. если энтропия источника строго меньше, чем достаточно мало, то а убывает к нулю при увеличении как

Эти свойства множества позволяют называть его множеством типичных последовательностей или высоковероятным множеством дискретного источника без памяти.

Следующие примеры показывают структуру высоковероятных множеств для двух двоичных источников.

Пример 1.7.1. Рассмотрим двоичный источник сообщений о результатах подбрасывания симметричной монеты. Вероятности сообщений одинаковы и равны Энтропия такого ансамбля Вероятность любой последовательности сообщений длины не зависит от последовательности и равна Отсюда следует, что т. е. все последовательности из принадлежат множеству при любом Другими словами, для этого источника и высоковероятное множество совпадает с множеством всех последовательностей.

Пример 1.7.2. Пусть двоичный источник без памяти выбирает сообщения из множества причем 1 появляется с вероятностью Для такого источника

где количество единиц в последовательности х. Обозначая — получим

и, следовательно,

где Таким образом, высоковероятное множество для рассматриваемого источника состоит из таких последовательностей число единиц в которых близко к . Например, если , то . Высоковероятное множество состоит из последовательностей, число единиц в которых близко к Количество последовательностей в этом множестве близко к Доля множества близка к Так, при это число примерно равно