3.5. ДИСКРЕТНЫЕ СТАЦИОНАРНЫЕ ИСТОЧНИКИ

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

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

Дискретный источник называется стационарным, если вероятностное описание не зависит от начала отсчета времени. Точнее, источник называется стационарным, если

для всех длин целых чисел и последовательностей Это означает, что вероятность того, что источник производит

последовательность и на интервале от 1 до равна вероятности того, изводится в точности такая же последовательность на интервале до

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

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

Теперь можно было бы определить энтропию на букву источника как предел при При втором подходе следует определить условную энтропию буквы в последовательности при условии, что заданы первые букв, и затем определить энтропию на букву источника как

Следующая теорема утверждает, в частности, что оба этих предела существуют и равны друг другу.

Теорема 3.5.1. Для дискретного стационарного источника с имеем

Доказательство. Используя вначале то, что наложение условия не может увеличить энтропию (2.3.13), а также используя стационарность источника, получаем при

Это доказывает утверждение (a).

Используем цепное равенство (2.2.30) для разложения

Согласно утверждению последнее слагаемое в (3.5.6) является границей снизу каждого из слагаемых. Применяя эту границу, получаем утверждение

Согласно определению имеем

После простых преобразований получаем устанавливая справедливость утверждения

Так как являются неотрицательными и невозрастающими с то оба предела существуют. Обозначим через . Используя опять цепное равенство, получаем

Здесь было использовано то, что первое слагаемое в квадратных скобках является верхней границей для каждого из остальных слагаемых. Переходя в (3.5.8) к пределу при получаем

Так как (3.5.9) справедлива при всех то будем иметь

Неравенства (3.5.10) и (3.5.3) устанавливают справедливость (3.5.4), что завершает доказательство теоремы.

Теорема 3.5.2. (Теорема кодирования для источника неравномерным кодом.) Пусть энтропия на букву в последовательности длины дискретного источника с алфавитом объема При заданном кодовом алфавите с символами можно так закодировать последовательности из букв источника префиксным кодом, что среднее число кодовых букв на букву источника будет удовлетворять неравенствам

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

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

и левое неравенство для никогда не нарушается для однозначно декодируемого кода.

Доказательство. Доказательство (3.5.11) аналогично доказательству соответствующего условия в теореме 3.3.2, за исключением того, что энтропия последовательности букв источника равна а не При переходе к пределу в (3.5.11) при стремится к стремится к 0, что доказывает (3.5.12)

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

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

Аналогично, если — множество бесконечных последовательностей букв источника, то обозначает то же самое множество, сдвинутое на I позиций, т. е. если то и принадлежит множеству тогда и только тогда, когда и принадлежит Множество последовательностей называется инвариантным, если Легко можно заметить, что множество всех последовательностей дискретного

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

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

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

Доказательство эквивалентности этих определений эргодичности содержится у Хинчина (1956); Вольфовиц (1961), лемма 10.3.1, рассмотрел другое определение и доказал его эквивалентность приведенным здесь.

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

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

кодовых букв на букву источника равно

В задаче 3.21 приведен пример эргодического источника, в котором это среднее, рассматриваемое как случайная величина, принимает различные значения с ненулевыми вероятностями. Трудность состоит в том, что (3.5.15) представляет собой среднее по времени в ином смысле, чем (3.5.13), так как оно определено с помощью сдвигов на букв сразу, а не сдвигов на одну букву.

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

Теорема 3.5.3. [Макмиллан (1953).] Пусть для дискретного стационарного эргодического источника

Для произвольных существует целое число (которое зависит от источника), такое, что при всех

До того как доказать теорему, введем некоторые необходимые обозначения и докажем две леммы. Заметим, что

Отметим, что правая часть (3.5.17) очень похожа на среднее по времени, задаваемое (3.5.13). Отличие состоит в том, что каждое слагаемое в (3.5.17), являющееся собственной информацией, зависит от разного числа предыдущих букв источника. Центральным местом доказательства является установление того, что эта зависимость убывает достаточно быстро, когда стремится к бесконечности. Пусть обозначает вероятность последовательности букв источника; определим для любого целого числа величину как

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

Это можно показать суммированием вначале по затем по и так далее и, наконец, по

Лемма 1. Для дискретного стационарного эргодического источника с и для произвольного

с вероятностью 1.

Доказательство. Из (3.5.18) следует, что

Так как не зависит от и принимает конечные значения с вероятностью 1, то

с вероятностью 1. Аналогично, так как является функцией последовательности букв и имеет конечное математическое ожидание — а также в силу того, что источник является эргодическим, (3.5.13) приводит к равенству

с вероятностью 1. И, наконец, так как фиксировано, то предел в (3.5.22) не меняется при замене на Теперь на основании равенств получаем (3.5.19).

Лемма 2. Для дискретного стационарного эргодического источника с для произвольных для достаточно большого и для любого

Доказательство. Имеем:

где было использовано неравенство Чебышева для неотрицательной случайной величины

Пусть теперь для любого числа у выражение обозначет «положительную часть» у, т. е.

Рис. 3.5.1.

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

Пользуясь рис. 3 5.1, можно также заметить, что для у О

Из (3 5.26) и (3 5 27) следует, что

Для выражения, стоящего в правой части в (3 5 28), имеем

Подставляя выражения (3 5.28)-(3.5 30) в (3 5 24), получим

Заметим, наконец, что из теоремы 3.5.1 следует, что выражение, стоящее в квадратных скобках в правой части (3.5.31), при стремится к нулю при возрастании равномерно по Таким образом, для любого фиксированного правая часть неравенства будет меньше, чем для достаточно больших

Доказательство теоремы. Для заданных выберем достаточно большим так, чтобы правая часть (3.5.31) была меньше, чем для всех и

Выберем затем достаточно большое так, чтобы для всех

Это возможно сделать на основании леммы 1. Из неравенств для имеем

Для того чтобы увидеть это, следует заметить, что, еслй не имеют места ни событие в левой части (3.5.31), ни событие в левой части (3.5.33), то тогда не может произойти событие в (3.5.34). Следовательно, вероятность события в (3.5.34) не больше, чем сумма вероятностей событий в (3.5.31) и (3.5.33). В силу произвольности это эквивалентно (3.5.16), что завершает доказательство теоремы.

Теорема 3.1.1 с заменой на доказывается теперь, как и раньше при если использовать теорему 3.5.3 вместо (3.1.7).