1.7. Высоковероятные множества постоянного дискретного источника

Вероятность любой n-последовательности символов для дискретного стационарного источника без памяти, вы­бирающего сообщения из множества А, записывается в виде так что количество собственной информации в последовательности определяется величиной

(1.12)

Используя для энтропии ансамбля принятое обозначение Н(А), можно сформулировать следующую теорему о высоковероятных множествах дискретного источника без памяти:

Для любых положительных чисел и найдется такое N, что для всех с вероятностью, большей, чем , выполняется не­равенство

(1.13)

Доказательство теоремы следует непосредственно из выполне­ния закона больших чисел. Действительно, совокупность представляет собой последовательность независимых одина­ково распределенных случайных величин с математическим ожиданием , принимающих ограниченные значения. К последовательности таких случайных величин применим закон больших чисел в форме Чебышева (см. приложение 2):

(1.14)

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

(1.15)

Вероятность любого элемента этого подмножества удовлетворяет неравенствам

(1.16)

Суммируя обе части левого неравенства в (1.16) по всем элементам подмножества получим

(1.17)

Аналогичный результат может быть получен и при анализе правой стороны неравенства (1.16).

(1.18)

Отсюда следует, что число элементов подмножества с точностью определяемой значениями и , оказывается приближенно равным . Таким образом, все последовательности, выдаваемые постоянным источником, при достаточно большой величине могут быть разделены на две группы. Первая группа отличается тем, что суммарная вероятность всех элементов этого подмножества близка к единице, и вероятности всех элементов его приближенно одинаковы [см. (1.15)]. Последовательности этой группы носят названия типичных. Вторая группа нетипичных последовательностей является дополнением первой до множества . Нетрудно убедиться, что при неравномерном распределении на множестве А число типичных последовательностей для больших n составляет лишь очень незначительную долю от общего числа всех последовательностей. Действительно, при заданном числе М элементов в множестве А возможное числи всех n-последовательностей составляет . Тогда в отношении числа типичных последовательностей ко всем возможным при большом значении n будет определяться очень малой величиной

(1.19)

Приведем пример. Пусть двоичный источник без памяти вы­бирает сообщения из множества , причем 1 появляется с вероятностью . Для такого источника энтропия С другой стороны, обозначая черезtдолю единиц в некоторой n-последовательности , для вероятности ее появления имеем: , так что среднее зна­чение собственной информации на символ в сообщении может быть записано в виде , где введено обозначение .

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

или ,

где Отсюда следует, что в типичных последовательностях число единиц близко к np.

Например, если р = 0,2, то . Типичное множество со­стоит из последовательностей, число единиц в котором близко к 0,2n. Доля типичных последовательностей относительно всего множества n-последовательностей 2ⁿ близка к . Так, приn = 200 это число равно примерно 10^-16,7.

В заключение отметим, что утверждение о возможности деления множества n-последовательностей, создаваемых стационарными ис­точниками без памяти, на типичные и нетипичные является справедливым и для пар последовательностей {AB},{ },{ }, так что