§ 47. Энтропия неограниченных случайных последовательностей

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

последовательностей является энтропия, которая определяет некоторые важные асимптотические свойства случайных последовательностей. В предыдущей главе мы уже встречались с последовательностями случайных величин и, в частности, с последовательностями независимых случайных величин как с простейшим видом случайных последовательностей. Однако для приложений недостаточно рассматривать только последовательности независимых случайных величин. В самом деле, легко понять, что вероятность появления той или иной буквы или цифры при передаче очередного знака телеграфного сообщения никак нельзя считать совершенно независимой от того, какие буквы или цифры предшествуют данной: например, вероятность появления буквы «а» после буквы «п» довольно велика, в то время как вероятность появления буквы «а» после буквы «ы» практически равна нулю. Во многих случаях практики оказывается возможным считать случайную последовательность простой цепью Маркова. Последовательность прерывных случайных величин имеющих одни и те же возможные значения называется простой цепью Маркова, если условные вероятности значений для каждой последующей случайной величины зависят только от значения непосредственно предшествующей случайной величины и не зависят от значений, которые принимают другие предшествующие случайные величины частности, случайные величины могут представлять собой значения одной и той же случайной Величины X в ряде опытов. В этом случае говорят, что рассматриваемая последовательность опытов представляет собой простую цепь Маркова.

Пусть условная вероятность того, что случайная величина примет значение при условии, что величина принимает значение Если рассматриваемая последовательность случайных величин представляет собой последовательность значений одной и той же случайной величины в ряде опытов, то представляет собой вероятность появления значения случайной величины при условии, что в результате предшествующего опыта она принимает значение Иными словами, есть вероятность перехода от значения к значению в следующем опыте. Цепь Маркова вполне определяется вероятностями перехода

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

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

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

Энтропией цепи Маркова называется средняя условная энтропия случайной величины X в каждом данном опыте. Согласно определению средней условной энтропии (43.17) и изложенному в начале § 43 способу перехода от непрерывной случайной величины к прерывной энтропия цепи Маркова выразится формулой

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

Заметим теперь, что из неравенств

вытекают неравенства:

При совместном выполнении обоих неравенств (47.5), очевидно, выполняется также неравенство

Невыполнение этого неравенства возможно только в том случае, если не выполняется хотя бы одно из неравенств (47.5). Но первое неравенство (47.5) может нарушиться только в том случае, если нарушится первое неравенство (47.4), а второе неравенство (47.5) может нарушиться только в том случае, если нарушится второе неравенство (47.4). Следовательно, для нарушения неравенства (47.6) необходимо нарушение хотя бы одного из неравенств (47.4).

Вероятности невыполнения каждого из неравенств (47.4), согласно (47.2) и (47.3), меньше произвольно малого числа 8, если достаточно велико. А так как вероятность появления хотя бы одного из нескольких событий не может быть больше суммы вероятностей этих событий, то вероятность нарушения неравенства (47.6) при достаточно большом будет не больше 28:

Оценим теперь вероятность того, что неравенство (47.6) нарушится хотя бы для одной пары значений индексов у. Эта вероятность на основании только что сделанного замечания не больше суммы вероятностей невыполнения неравенства (47.6) для всех возможных пар индексов Но, по доказанному, вероятность невыполнения неравенства (47.6) для каждой данной пары индексов меньше, чем 28, если достаточно велико. Следовательно, вероятность невыполнения неравенства (47.6) хотя бы для одной пары значений меньше, чем

А так как 8 произвольно мало при достаточно большом то неравенство (47.6) с вероятностью, как угодно близкой к единице, будет выполнено для всех значений если число опытов достаточно велико. Доказанное предложение можно написать в виде формулы

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

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

как случайную величину. В формуле (47.10) это отражено тем, что номер К значения величины X в первом опыте и числа переходов являются случайными величинами. Положим:

Подставляя это выражение в (47.10), получим после логарифмирования:

или

Подставляя выражение (47.11) в неравенство (47.6), приведем его к виду:

Из (47.13) следует, что при совместном выполнении всех неравенств (47.6) и равноценных им неравенств (47.14) имеет место неравенство

При достаточно большом и достаточно малом правая часть неравенства (47.15) будет меньше произвольного числа . А так как при произвольно малом вероятность совместного выполнения всех неравенств (47.6), а следовательно и всех неравенств (47.14), согласно (47.9), как угодно близка к единице, если достаточно велико, то и вероятность того, что левая часть неравенства (47.15) будет меньше произвольно малого числа как угодно близка к единице при достаточно большом и

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

где а — основание логарифмов.

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

Отсюда находим:

и

С другой стороны, так как сумма вероятностей всех последовательностей, вероятности которых не удовлетворяют неравенствам (47.17), меньше произвольно малого числа о, то сумма вероятностей последовательностей, вероятности которых удовлетворяют неравенствам (47.17), больше . А так как вероятность каждой из этих последовательностей меньше то

Отсюда находим:

и

Неравенства (47.20) и (47.23) доказывают, что

Так как произвольно мало при достаточно большом

Формула (47.24) показывает, что, каково бы ни было число как бы мало ни было положительное число наименьшее число наиболее вероятных последовательностей имеющих суммарную вероятность, не меньшую чем удовлетворяет неравенствам:

если достаточно велико.

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

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

и

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

Доказанные результаты легко обобщаются на более общие случайные последовательности, представляющие собой сложные цепи Маркова. Приведенный вывод асимптотических свойств цепей Маркова и их применение к решению задачи об оптимальном кодировании в нижеследующем примере принадлежат в основном А. Я. Хинчину [821.

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

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

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

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

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

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

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

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

быть переданы меньшим, чем числом знакоз каждое, не превосходит Но, согласно (47.25), как бы мало ни было 5, число сообщений, имеющих суммарную вероятность, не меньшую 5, всегда больще Следовательно, с вероятностью, большей придется передать одно из сообщений, кодированных последовательностями с большим, чем числом знаков каждая. Следовательно, коэффициент сжатия текста (т. е. математическое ожидание отношения числа знаков кодированного текста к числу знаков первоначального текста) не может быть меньше, чем

А так как при достаточно большом величины могут быть сколь угодно малыми, то коэффициент сжатия текста не может быть меньше чем и завершается доказательство.