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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

откуда

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

и

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

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

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

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

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

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

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

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

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

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

Решение

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

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

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

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