§ 1.9. Эргодические дискретные источники

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

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

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

Пусть

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

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

Рассмотрим теперь отрезки сообщений длины на выходе какого-нибудь одного источника (или отрезки длины одной реализации). Каждому отрезку можно поставить в соответствие число

— условную собственную информацию сообщения Среднее арифметическое этих информаций

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

при достаточно больших Если бы (1.9.6) действительно выполнялось, то

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

Это рассмотрение можно обобщить, если на ансамбле рассматривать произвольные функции и определять для них среднее по множеству источников аналогично (1.9.2) и среднее по одной реализации аналогично (1.9.5). Класс источников, для которых оба этих средних в вероятностном смысле близки независимо от выбора и функции носит название класса эргодических источников. Поэтому предположение (1.9.6) для эргодических источников выполняется.

Теперь дадим более строгое определение эргодических источников.

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

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

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

Пример 1.9.1. Если выбрать то в случае дискретного эргодического источника предположение (1.9.6) будет выполняться.

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

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

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

Теорема 1.9.1. Всякий дискретный стационарный источник без памяти является эргодическим.

Доказательство. Зафиксируем и некоторую функцию заданную на положим

и рассмотрим сумму

где

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

Используя можно получить следующие соотношения:

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

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

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

Полезно разобрать пример стационарного иеэргодического источника с тем, чтобы на этом примере более детально познакомиться с природой эргодичности.

Пример 1.9.3. Пусть имеются две урны. В первой урне лежат два белых и один черный шар. Во второй урне лежат два черных и один белый шар. Производится следующий эксперимент. Пусть случайно выбирается одна из двух причем первая выбирается с вероятностью Затем из выбранной урны осуществляется последовательное извлечение шаров с возвращением. Экспериментатор подсчитывает число извлечений белого шара. Если в начале эксперимента выбрана первая урна, то частота появлений белого шара, зарегистрированная экслериментатором, будет равна 3/3, в противном случае — 1/3, Если имеется независимо работающих экспериментаторов, то примерно пр из них зарегистрируют частоту 2/3, а примерно из них — частоту 1/3. Частота появления белого шара в среднем по множеству всех экспериментаторов равна

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

Структуру неэргодического источника примера 1.9.3 можно представить себе следующим образом (см. рис. 1.9.1). Имеются два эргодических (в данном примере — не имеющих памяти) источника и переключатель 77, который может находиться в одном из двух положений. Переключатель случайно устанавливается в одно из положений при включении источника и остается в этом положении на протяжении всей работы. Экспериментатор имеет дело с одной реализацией на выходе источника, которой может соответствовать только одно положение переключателя.

Рис. 1.9.1. Неэргодический источник с двумя эргодическими компонентами.

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

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

На первый взгляд может показаться, что (1.9.16) прямо следует из определения эргодического источника. Однако это не так.

Информацию на сообщение можно представить следующим образом:

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

неравенство (1.9.16) справедливо для любого эргодического источника при достаточно большом Этот факт устанавливается в так называемой лемме Мак-Миллана.

Лемма 1.9.1 (Мак-Миллан). Для любого дискретного эргодического источника любых, положительных и найдется такое, что всех выполняется неравенство (1.9.16).

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

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

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

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

которое следует из того, что если , то либо либо Заметим также, что

Так как для всех то согласно предположению об эргодичности для любых найдется такое, что для всех

где первое неравенство — следствие неравенства (1.9.20), а второе — следствие эргодичности и того, что принимает ограниченные значения с вероятностью 1. Таким образом, утверждение, связанное с неравенством (1.9.19), доказано.

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

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

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

Неравенство (1.9.24) легко проверяется посредством отдельного рассмотрения случаев Отсюда следует, что

и из (1.9.23) вытекает, что

Из теорем 1.5.1, 1.5.2 следует, что при любых фиксированных при достаточно большом, но фиксированном правая часть неравенства (1.9.25) стремится к нулю при Поэтому найдется такое, что при всех будет выполняться неравенство

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

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

Тогда из утверждений, связанных с неравенствами (1.9.19) и (1.9.22), будет следовать, что

Лемма доказана.

Из леммы Мак-Миллана может быть легко выведена теорема о высоковероятных множествах, а также прямая и обратная теоремы кодирования при равномерном кодировании дискретного эргодического источника.

Теорема 1.9.2 (теорема о высоковероятных множествах). Пусть дискретный эргодический источник и ансамбли последовательностей длины на его выходе. Пусть энтропия на сообщение и некоторое положительное число. Пусть подмножество множества определенное для каждого следующим образом:

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

Доказательство этой теоремы в точности повторяет доказательство теоремы 1.7.1 и поэтому опускается.

Теорема 1.9.3 (прямая теорема кодирования). Пусть тогда для любого положительного существует код со скоростью который кодирует дискретный эргодический источник с вероятностью ошибки, не превышающей

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

где вероятность ошибки для кода, кодирующего отрезки сообщений длины

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

Из этих теорем следует, что скорость создания информации дискретным эргодическим источником при равномерном кодировании равна его энтропии на сообщение Это утверждение позволяет дать такое же толкование энтропии на сообщение Для эргодических источников, как энтропии для постоянных

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