Связь между энтропией и числом сообщений (фундаментальная теорема)

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

Пусть имеет место алфавит из M букв, а источником выдается последовательность из N букв.

Возможное число различных последовательностей – M ^N. Вероятности появления каждой из них при неравной вероятности букв, из которых они состоят, различны.

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

«Как бы ни были малы два числа ε > 0 и δ > 0 при достаточно большом N все последовательности могут быть разбиты на две группы.

Первая группа включает подавляющее число (большинство) таких последовательностей, каждая из которых будет иметь настолько ничтожную вероятность, что даже суммарная вероятность всех таких последовательностей очень мала и при достаточно большом N будет меньше сколь угодно малого числа ε > 0. Эти последовательности называются нетипичными.

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

где – энтропия на целую последовательность;

H – энтропия источника с учетом статистических связей и неравновероятности букв.

Другими словами, почти достоверно, что весьма близко к H, когда N – велико – это свойство ассимптотической равновероятности достаточно длинных последовательностей (N > 1000).

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

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

где δ – сколь угодно мало).

Доказательство сложно. Для простейшего случая отсутствия статистических связей теорема является следствием закона больших чисел, который можно изменить так: с вероятностью близкой к 1 в длинной последовательности из N элементов будет N·p₁ – элементов первого алфавита, N·p₂ – второго и т.д. (частота встречаемости стремится к вероятности при числе испытаний стремящихся к бесконечности). http://peredacha-informacii.ru/ Следовательно, для типичной последовательности вероятность её появления будет равна:

откуда

и

Типичные последовательности составляют лишь незначительную часть всех возможных последовательностей. Число всех возможных последовательностей длиной в N-букв равно:

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

Следовательно,

Доля нетипичных последовательностей велика.

Решим такую задачу.

Какова вероятность того, что обезьяна путём случайных нажатий на клавиатуре пишушей машинки, имеющей всего 32 клавиши (буквы и пропуск), наберет типичное сообщение длиною N = 20 букв?

Решение

Вероятность того, что случайно набранное сообщение будет типичным равна:

.

Эта вероятность бесконечно мала.