4.4. ВЫПУКЛЫЕ ФУНКЦИИ

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

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

Пусть является -мерным вектором с действительными компонентами, определенным в области векторного пространства. Назовем область R выпуклой, если для любого вектора а из R и любого вектора из R вектор принадлежит R при Геометрически, когда 6 изменяется от 0 до 1, 0а проходит отрезок прямой линии от до а. Таким образом, область является выпуклой, если для каждой пары точек из области отрезок прямой линии между этими точками принадлежит области (рис. 4.4.1)

Рис. 4.4.1. Примеры выпуклых областей для двумерных векторев.

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

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

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

Назовем действительную функцию векторного аргумента выпуклой (следует читать выпуклой вверх) в выпуклой области R

векторного пространства, если для всех а из из функция удовлетворяет условию

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

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

Из (4.4.3) непосредственно следует, что если выпукла то выпукла и наоборот. Поэтому мы будем иметь дело только с выпуклыми функциями, так как результаты могут быть легко применены к выпуклым функциям.

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

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

является выпуклой и выпуклость строгая, если какая-либо строго выпукла.

2) Пусть для одномерного вектора а

на всем интервале, тогда выпукла на этом интервале со строгой выпуклостью, если (4.4.4) справедливо со строгим неравенством.

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

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

Подставляя в неравенство, определяющее выпуклость (4.4.3), устанавливаем справедливость свойства 1. Свойство 2 почти очевидно геометрически (см. рис. 4.4.2) и оно доказано в задаче 4.9. Свойство 3 на геометрическом языке означает, что часть «плоскости», в которой лежат точки находится ниже (или на) поверхности, порождаемой между этими точками (см. для доказательства задачу 4.9).

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

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

Рис. 4.4.3. Вид выпуклой функции с максимумом в области который достигается при

Неравенство (4.3.16), которое мы оставили недоказанным в предыдущем параграфе, следует из (4.4.6) и выпуклости энтропии.

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

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

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

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

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

В качестве второго примера рассмотрим максимизацию выпуклой функции в области, в которой а является вектором вероятностей, т. е. в области, где компоненты а неотрицательны и в сумме равны 1. Условие позволяет использовать метод множителей Лагранжа, который означает максимизацию по области, в которой компоненты неотрицательны, и выбор Этаким образом, чтобы максимум имел место при Применяя (4.4.8) и (4.4.9) к функции будем иметь:

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

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

равен для некоторых Тогда (4.4.10) и (4.4.11) являются необходимыми и достаточными условиями того, что вектор вероятностей а максимизирует в области

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

Преобразуя (4.4.12), будем иметь

В силу того, что (4.4.13) справедливо при всех можно перейти к пределу и получить

Выполняя дифференцирование, имеем

Существование производной в (4.4.14) и эквивалентность (4.4.14) и (4.4.15) следуют из непрерывности частных производных. Эта непрерывность является следствием предположения, так как (4.4.10) и (4.4.11) исключают случай, когда Заметим теперь, что

Это следует из (4.4.10), если Если то и (4.4.16) следует из (4.4.11).

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

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

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

Разделив это выражение на 0 и переходя к пределу при будем иметь

По крайней мере одна компонента а является строго положительной, предположим для простоты обозначений, что Пусть является единичным вектором с единицей в качестве компоненты и остальными нулевыми компонентами; выберемр равным а как то является вектором вероятностей при Используя это в (4.4.20), получаем

Если то можно также выбрать отрицательным, и в этом случае неравенство в (4.4.22) изменяется на обратное, что приводит к

Выбирая, наконец, равной приходим к эквивалентности (4.4.22) и (4.4.3) условиям (4.4.10) и (4.4.11). Для завершения доказательства теоремы рассмотрим а, для которого при некотором и покажем, что такое а не может максимизировать Предположим для простоты обозначений, чтоах Будем иметь

В пределе при первое слагаемое в правой части равенства (4.4.24) остается ограниченным в силу непрерывности Второе слагаемое возрастает так, что левая часть (4.4.24) является положительной для достаточно малого Это показывает, что а не максимизирует что завершает доказательство теоремы.

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

Теорема 4.4.2. Пусть дискретный канал без памяти с К буквами на входе и буквами на выходе имеет переходные вероятности Пусть произвольное распределение вероятностей на входе канала. Тогда

является выпуклой функцией

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

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

При желании можно рассматривать и как условные вероятности при условии, что задано значение двоичной случайной величины (рис. 4.4.4), т. е.

Рис. 4.4.4.

Выберем и (как показано на рис. 4.4.4) В обозначениях этого трехмерного ансамбля имеем, что левая часть (4.4.26) равна а правая часть равна

Так же как при рассмотрении последовательных каналов в § являются независимыми при условии, что задано х. Следовательно, как и в (2.3.15),

Кроме того, так же как в (2.3.16) и (2.3.17),

Приравнивая правые части (4.4.29) и (4.4.30) и используя (4.4.28) получаем

Так как это эквивалентно (4.4.26), то доказательство теоремы закончено.

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

канала, докажем тесно связанную с ним теорему, которая полезна как при исследовании неизвестных каналов, так и в гл. 9.

Теорема 4.4.3. Рассмотрим в (4.4.25) как функцию переходных вероятностей и входного распределения При фиксированном входном распределении является выпуклой функцией переходных вероятностей (отметим, что она является выпуклой а не выпуклой как в теореме 4.4.2).

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

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

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

Так как статистически независимы, то и

Это эквивалентно (4.4.34); теорема доказана.