Главная > Математика > Теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

11.2. Теорема об асимптотической равноценности различных количеств информации

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

При этом будем иметь

Запишем выражение в правой части подробнее. Поскольку область точек I, где «расстояние» с не превосходит «расстояния» с ( До любой точки из имеем

и, следовательно, также

Усредняя будем иметь

В каждом члене удобно в первую очередь произвести интегрирование по точкам не совпадающим с Если ввести функцию распределения

то после -кратного интегрирования по точкам не совпадающим с из будем иметь

Знак неравенства возник по той причине, что при с О мы несколько расширили области присоединив к ним все «спорные» точки для которых с а при с сузили эти области, отбросив все подобные точки. Нетрудно видеть также, что (11.2.4) можно записать в виде

или в силу (11.2.1)

В правой части здесь усредняется по математическое ожидание, соответствующее функции распределения

Очевидно, что

поскольку Вместо удобно ввести близкую к ней (при больших функцию распределения

Нетрудно доказать, что

В самом деле, используя неравенство

имеем

что эквивалентно (11.2.9).

Используя (11.2.7), (11.2.9), получаем, что функция (11.2.8) не превосходит функции (11.2.6):

Из последнего неравенства вытекает

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

Итак, неравенство (11.2.5) только усилится, если в правой части заменить на Следовательно, будем иметь

где определяется формулой (11.2.8) при Полученное неравенство будет использовано в § 11.3.

2. Теорема 11.1. Пусть имеются бейесовские системы являющиеся -й степенью системы причем функция штрафа ограничена сверху.

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

при Иначе говоря, имеет место асимптотическая равноценность

шенноновского и хартлиевского количеств информации. Предполагается, что входящие в (11.2.15) удельные потери конечны и функция непрерывна.

При доказательстве этой теоремы будем следовать Шеннону [4], сформулировавшему этот результат в других терминах.

Доказательство. 1) Вследствие (11.1.4) при экстремальном распределении (11.1.6) случайная информация

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

при при любом

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

Обозначим через Г множество пар ?), для которых одновременно выполняются оба неравенства

Тогда из (11.2.17) получаем

В самом деле, вероятность события противоположного события (11.2.18), а также вероятность события В, противоположного (11.2.19), не больше Поэтому для их объединения имеем

Событие же, противоположное , есть не что иное, как Г, и, следовательно, справедливо (11.2.20).

Пусть для фиксированного множество есть множество тех , которые в паре с входят в Г, другими словами, сечение множества Г. При таком определении Рассмотрим множество В тех элементов Е, для которых

Из (11.2.20) следует, что

Чтобы в этом убедиться, предположим противное, т. е., что

дополнение к Н). Вероятность дополнения к Г можно в этом случае оценить следующим образом. Воспользуемся представлением

причем разобьем этот интеграл на две части и оставим лишь один подынтеграл:

В дополнении очевидно, выполняется неравенство, противоположное (11.2.21):

т. е. при Подставляя эту оценку в (11.2.226) и учитывая (11.2.22а), находим

Это противоречит (11.2.20) и, следовательно, предположение (11.2.22а) неверно.

Неравенство (11.2.19) означает, что

т. е.

Суммируя по отсюда получаем

или, используя (11.2.21),

2) Используем теперь формулу (11.2.5). Возьмем функцию распределения

Вследствие условия ограниченности (11.2.14) функции штрафа, вероятность выполнения неравенства с ( равна нулю и из (11.2.3) получаем Вследствие (11.2.6) следует, Таким образом, функции на участке к совпадают. На участке имеем поскольку

в силу неубывающего характера функции Следовательно, неравенство справедливо при всех значениях к. Из него следует обратное неравенство для средних:

подобно тому как (11.2.12) следовало из (11.2.11). Поэтому формула

но

согласно (11.2.24). Следовательно, из (11.2.25) при учете (11.2.6) получаем

или

если учесть (11.2.10). Выполнение предполагаемого при этом неравенства обеспечивается увеличением

3) Вследствие (11.2.3) имеем

где фиксировано. Сравним эту величину с вероятностью

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

Подставляя сюда (11.2.23), получаем

Разобьем интеграл в (11.2.26) на два: интеграл по множеству Н и дополнительному множеству Е. В первом из них используем (11.2.27), а во втором заменим экспоненту на единицу. Это даст

где учтено неравенство (11.2.22). Здесь

причем целесообразно положить Тогда неравенство (11.2.28) примет вид

Подставляя последнее в (11.2.26), будем иметь

(использовано, что в силу

Итак, мы получили, что при любых не зависящих от найдется такое что неравенство (11.2.29) будет выполняться для всех Это значит

(берется Поэтому имеем

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

Эта формула в сочетании с неравенством

вытекающим из (11.1.3) и (11.1.8), доказывает соотношение

т. е. (11.2.15). Доказательство закончено.

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

Легко понять, что при этих условиях сохранятся неравенства типа (11.2.17), принимающие теперь вид

для причем Вместо прежнего соотношения теперь будем иметь

Условие ограниченности (11.2.14) возьмем таким:

где К не зависит от В приведенном доказательстве потребуется лишь изменение способа записи формул. Соотношение (11.2.29) теперь примет вид

или

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

Предположим, что существует предел

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

Вследствие произвольности и непрерывности функции отсюда получаем

Для доказательства сходимости

остается только сравнить (11.2.34а) с неравенством

которое служит обобщением (11.2.30а).

4. В § 9.6 отмечалось, что функции ценности информации остаются инвариантными при преобразовании

функции штрафов (см. теорему 9.8). При этом остаются неизменными также разность рисков и области определенные в § 11.1, если не меняются кодовые точки и распределение с которым они выбрасываются. Между тем условия (11.2.31), (11.2.32) не остаются инвариантными при указанном преобразовании (11.2.36). Так (11.2.31) переходит в соотношение

Которое, очевидно, вообще не совпадает с

Учитывая это, можно воспользоваться свободой выбора функции в преобразовании (11.2.36), чтобы добиться выполнения условий (11.2.31), (11.2.32) в том случае, если они первоначально не выполнялись. Это расширяет круг случаев, для которых удается доказать сходимость (11.2.34), ослабляет условия асимптотической равноценности в вышеизложенной теории.

Специальным подбором функции в (11.2.36) можно вообще устранить надобность в условии (11.2.31). В самом деле, в случае экстремального распределения как видно из (9.4.21), выполняется соотношение

Пользуясь свободой выбора функции в (11.2.36), положим Тогда новое «расстояние» с совпадает с и сходимость (11.2.31) для него можно будет не оговаривать, так как она будет вытекать из условия

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

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

не зависит от и условие непрерывности по у функции (11.2.34), то имеет место сходимость (11.2.35). Условие (11.2.39), как нетрудно понять, возникло из (11.2.32),

5. Используем изложенную выше теорию для более подробного анализа измерительно-передающей системы, рассмотренной в § 9.2. Асимптотическая равноценность хартлиевской и шенноновской информации позволяет улучшить работу системы, схема которой дана на рис. 9.5, т. е. снизить средние штрафы от уровня

до уровня

определяемого ценностью шенноновской информации.

Чтобы этого достичь, нужно, приводя систему в действие многократно, заменить х на блок а и — на блок при достаточно большом В качестве штрафов должен рассматриваться суммарный штраф. После этого можно применять теорему 11.1 и конструировать блоки 1 и 2, изображенные на рис. 11.1 по тем же принципам, как это делалось в п. 3 § 9.2. Теперь, однако, зная доказательство теоремы 11.1, мы можем конкретно разобрать их действие. Не стремясь к точной оптимальности, возьмем в качестве требуемого разбиения рассмотренное выше разбиение (11.1.13). Области здесь определяются по принципу близости к случайным кодовым точкам

Рис. 11.1. Блочный вариант системы с информационным ограничением Пропускная способность канала в раз больше, чем на рис 9 5

Это разбиение является, как доказано, асимптотически оптимальным. Другими словами, система (рис. 11.1), в которой блок 1 классифицирует входной сигнал по принадлежности к областям и выдает на выходе номер области, содержащей , работает асимптотически оптимально. Легко видеть, что описанная работа блока 1 совершенно аналогична рассмотренной в гл. 7 работе декодировщика на выходе канала с помехами, только вместо «расстояния» (7.1.8) теперь учитывается «расстояние» с а также заменены на , Эта аналогия позволяет назвать блок 1 измерительным декодировщиком, блок же 2 работает как блок оптимальных оценок.

Описанная информационная система и системы несколько более общего вида рассматривались в работах Стратоновича [31, Стратоновича и Гришанина [1], Гришанина и Стратоновича [1].

Информационные ограничения типа рассмотренных ранее (рис. 9.6, 11.1) могут учитываться в различных системахоптимальной фильтрации, автоматического регулирования, динамического программирования и даже теории игр. Иногда указанные ограничения связаны с ограниченностью притока информации, иногда с ограниченностью памяти, иногда с ограничением сложности автомата или регулятора. Учет ограничений приводит к проникновению понятий и методов теории информации в упомянутые теории, к срастанию их с теорией информации. В динамическом программировании (см., например, Беллман [11) и часто в других теориях рассматривается ряд действий, совершаемых последовательно во времени. В связи с этим информационные ограничения в этом случае носят многократный характер. Это приводит к последовательностному обобщению вышеизложенных результатов. Ряд вопросов, относящихся к указанному направлению, изучается в работах Стратоновича [5, 7], Стратоновича и Гришанина [2].

<< Предыдущий параграф Следующий параграф >>
Оглавление