ПРИЛОЖЕНИЕ 1А. ВЫПУКЛЫЕ ФУНКЦИИ

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

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

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

Функцию называют выпуклой если неравенство (1 А. 1) меняется на обратное для всех указанных и 0. Если при всех неравенство или обратное ему выполняется строго, мы называем функцию строго выпуклой или строго выпуклой

Рис. 1А.1. Выпуклая функция

На рис. приведен типичный случай выпуклой функции, выраженной при фиксированных как функция 0. Из рисунка ясно, почему мы пользуемся здесь обозначением Аналогичное замечание приложимо и к выпуклым функциям. В действительности, поскольку выпуклая функция есть взятая с минусом выпуклая функция, нам нужно исследовать только свойства выпуклых функций. Часто встречаются выпуклые функции на интервале Выпуклые функции включают при Функциями, одновременно выпуклыми и выпуклыми , будут линейные функции вида

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

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

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

Объединив эти соотношения для любого получим

Выбрав теперь из видим, что неравенство

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

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

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

Функция называется строго выпуклой если всякий раз, когда приведенное неравенство строгое. Если неравенство противоположное, функцию называют выпуклой

Для выпуклых функций векторного аргумента справедливы два важных свойства:

1. Если суть выпуклые функции, а положительные числа, то функция

выпукла причем строго, если хотя бы одна из строго выпукла Это вытекает из определения

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

где символ математического ожидания. Это весьма полезное неравенство известно как неравенство Иенсена и доказано в приложении

Энтропия

представляет собой выпуклую функцию на области определенной в Чтобы доказать это, положим

Воспользовавшись леммой убеждаемся в том, что каждая функция выпукла Л- Тогда с учетом свойства 1 мы имеем, что также

выпуклая функция. Другое доказательство можно получить непосредственно из неравенства (1.1.8) (см. задачу 1.12).

Рассмотрим, наконец, ДКБП с входным и выходным алфавитами и переходными вероятностями для Для входного распределения вероятностей при мы определили среднюю взаимную информацию (см. равенство 1.2.7). Чтобы подчеркнуть зависимость от переходных вероятностей, которые мы обозначим через и от входного распределения вероятностей, обозначаемого через перепишем равенство 1.2.7:

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

где через обозначено распределение вероятностей и для любых переходных вероятностей и всех выполняется неравенство

где через обозначена переходная вероятность для В неравенстве означает любую переходную вероятность, а в неравенстве означает любое входное распределение вероятностей .

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

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

где энтропия выходного алфавита. Первое слагаемое в соотношении линейно по следовательно, выпукло по Второе слагаемое выпукло по что было установлено в рассуждениях, следующих за соотношением (1 А. 10). Но поскольку линейно по то оно также и выпукло по Из свойства 1 следует, что выпукла по при фиксированном Р. Этим доказано неравенство

Для доказательства неравенства положим

и

Тогда

Воспользовавшись затем неравенством получим

поскольку второе слагаемое суммы равно нулю. Аналогичным образом имеем

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