§ 2.5. Выпуклость средней взаимной информации

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

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

Определение 2.5.1. Функция называется выпуклой вверх в выпуклой области если для любого , любых неотрицательных и любых выполняется неравенство

Если в (2.5.1) имеет место противоположное неравенство, то функция называется выпуклой вниз.

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

Рис. 2.5.1. Функция, выпуклая вверх (а) и выпуклая вниз (б).

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

Пусть XV — дискретный ансамбль с совместным распределением вероятностей Средняя взаимная информация между ансамблями определяется выражением

Аналогичное выражение для непрерывного ансамбля вид

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

Теорема 2.5.1. Средняя взаимная информация является выпуклой вверх функцией в области всех безусловных распределений вероятностей (вероятностных векторов или ф. п. в.) на множестве X при условии, что условные распределения на множестве Y {условные вероятности или условные ф. п. в.) зафиксированы.

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

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

где данное условное распределение. Тогда при каждом на множестве определено условное распределение вероятностей

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

где

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

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

где использовано определение 2.1.5 средней взаимной информации относительно ансамбля . С другой стороны, из (2.5.7) следует, что есть вероятностный вектор, равный среднему с весами из вероятностных векторов Поэтому правая часть неравенства (2.5.1) есть просто Таким образом, для доказательства теоремы теперь необходимо доказать неравенство

в предположении, что справедливо (2.5.4).

Для доказательства этого неравенства рассмотрим среднюю взаимную информацию По свойству аддитивности имеем

Из (2.5.4) следует, что для всех

т. е. Поэтому

Теперь, учитывая неотрицательность средней взаимной информации, из (2.5.10) и (2.5.12) получим (2.5.9). Теорема доказана для случая дискретных ансамблей.

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

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

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

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

Следовательно, условная ф. п. в.

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

Теорема 2.5.2. Средняя взаимная информация является выпуклой вниз функцией в области всех условных распределений вероятностей (стохастических матриц или условных ф. п. в.) на множестве при условии, что безусловное распределение вероятностей на множестве X (вероятности или ф. п. в.) зафиксировано.

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

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

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

где данное безусловное распределение на Тогда при каждом на множестве задано условное распределение вероятностей

Каждому такому распределению и, следовательно, каждому элементу соответствует средняя взаимная информация определяемая по формуле (2.1.22). С другой стороны, на множестве задано безусловное распределение вероятностей:

где

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

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

где использовано определение 2.1.5. С другой стороны, из (2.5.17) следует, что является стохастической матрицей, равной средней с весами из стохастических матриц Поэтому правая часть неравенства (2.5.1) есть просто Таким образом, для доказательства теоремы теперь необходимо доказать неравенство

в предположении, что выполняется (2.5.14).

Для доказательства этого неравенства рассмотрим среднюю взаимную информацию По свойству аддитивности имеем

Из (2.5.14) следует., что для всех

т. е. и поэтому

Теперь, учитывая неотрицательность информации из (2.5.20) и (2.5.22), получим (2.5.19).

Рис. 2.5.2. Переходные вероятности двоичного симметричного канала.

Теорема доказана для случая дискретных ансамблей.

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

которая, как и в теореме 2.5.1, задает распределение смешанного типа: ансамбли непрерывны, а ансамбль дискретен. В остальном доказательство полностью сохраняется.

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

поэтому среднюю взаимную информацию можно рассматривать как функцию двух параметров а и и записывать ее как

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

Имеем

где

Второе равенство в -следствие того, что не зависит от так как набор условных вероятностен совпадает с набором условных вероятностей Таким образом, при фиксированном

где (3 определяется через а с помощью соотношения (2.5.24). Очевидно, так как при или принимает максимальное значение при Так как только в том случае, когда то принимает максимальное значение, равное в точке . Поскольку к - выпуклая вверх функция (см. задачу 2.5.5), а линейная функция то выпуклая вверх функция (см. рис. 2.5.3, а).

Рис. 2.5.3. Иллюстрация выпуклости средней взаимной информации вверх по распределениям на входе (а) и вниз по условным распределениям, задающим канал (б).

Пусть теперь зафиксировано число а, а изменяется. По-прежнему будем пользоваться соотношением (2.5.25), оценивая по отдельности каждое слагаемое. Первое слагаемое есть выпуклая вверх функция, принимающая максимальное значение, равное 1, при так как при таком значении вероятность 0 (см. (2.5.24)) равна Очевидно, функция равна нулю при выпукла вверх и принимает максимальное значение, равное 1, при На рис. 2.5.3, б показаны три функции: и Видно, что средняя взаимная информация является выпуклой вниз функцией от