9.4. ВЫЧИСЛЕНИЕ R(d)

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

по всем выборам множества переходных вероятностей где

Другие ограничения

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

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

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

при всех Удобно ввести эти множители в виде что означает, что нужно минимизировать выражение

и затем выбирать так, чтобы

для всех Дифференцируя получаем

где .

Следовательно, условия на которые приводят к стационарной точке для принимают вид (для всех

Если умножить обе части (9.4.5) на просуммировать по и сократить на

то получим

Точно так же, суммируя (9.4.5) по и используя ограничение

Равенства (9.4.6) дают линейных уравнений относительно переменных а (9.4.7) дают К линейных уравнений относительно Если то обычно эти уравнения можно решить и затем найти из (9.4.5). Так как выпукло по то также выпукло и решение дает минимум.

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

Теорема 9.4.1. Для заданного источника с энтропией и заданной меры искажения пусть

Здесь и всюду в дальнейшем сумма берется только по тем для которых Тогда для любого

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

Необходимые и достаточные условия, накладываемые на при которых достигается минимум в (9.4.8), сводятся к тому, что существует множество неотрицательных чисел удовлетворяющих (9.4.7), и что (9.4.9) удовлетворяется с равенством для каждого с Выраженный через и со вектор задаваемый (9.4.5), минимизирует

Обсуждение. Одно из следствий из (9.4.8) заключается в том, что для любого множества которое удовлетворяет (9.4.9),

Так как уже было показано, что

то это означает, что для любого и любого удовлетворяющего (9.4.9) для этого

Это соотношение задает нижнюю границу для и фактически дает если выбраны оптимально.

Попытка фактического нахождения приводит нас к ситуации, весьма похожей на ту, которая была при отыскании пропускной способности. Можно попытаться решить (9.4.9) относительно сначала угадывая множество для которых должно иметь место равенство; затем, используя полученное для решения (9.4.7) относительно и после этого, находя с помощью (9.4.5). Суммируя (9.4.5) по и используя (9.4.7), видим, что действительно являются переходными вероятностями. Умножая (9.4.5) на суммируя по и используя (9.4.9), находим, что действительно являются выходными вероятностями Хотя (9.4.8) выражает только через нужно еще решить (9.4.7), чтобы убедиться, что что (9.4.9) удовлетворяется с равенством для каждого В следующем параграфе эта процедура будет применена к важному примеру. Другой подход к нахождению в случае, если источник и мера искажения достаточно симметричны, состоит в угадывании решения и проверке, что это решение удовлетворяет условиям теоремы. И в еще одном последнем подходе используется то, что так как выпукло по то выпукло по и множества ограничений выпуклы; при этом относительно легко вычислить минимум или максимум численными методами с помощью вычислительной машины.

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

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

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

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

Рассмотрим функцию

Отделяя третье выражение в (9.4.13) от первых двух и суммируя по получаем

Покажем теперь, что неотрицательна, используя обычное неравенство Из (9.4.13) имеем

Суммируя сначала по и используя затем ограничение (9.4.9), получаем

Из (9.4.17) и (9.4.14) выводим (9.4.12).

Неравенство (9.4.12) переходит в равенство тогда и только тогда, когда оба неравенства, ведущие от (9.4.15) к (9.4.17), переходят в равенства, или тогда и только тогда, когда

Если обе части (9.4.18) умножить на и просуммировать по то получим (9.4.7), так что условия теоремы необходимы для равенства в (9.4.12). Аналогично, если неотрицательные числа удовлетворяют (9.4.7) и если (9.4.19) удовлетворяется, то, как было уже показано ранее, заданные формулой (9.4.5), являются переходными вероятностями с выходными вероятностями В соответствии с (9.4.5) выбранные значения удовлетворяют (9.4.18), так что условия теоремы достаточны для равенства в (9.4.12).

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

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

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

для всех Также если или или Следовательно, для рассматриваемых удовлетворяется для всех Умножая (9.4.5) на и суммируя видим, что (9.4.9) удовлетворяется с равенством для таких, что Таким образом, удовлетворяют достаточным условиям для равенства в (9.4.12). Доказательство еще не закончено, так как следует показать, что лежит в области, соответствующей заданным ограничениям, т. е. что (9.4.9) также удовлетворяется для таких, что Предположим, что для заданного и определим через минимизирующее следующими равенствами:

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

Тогда

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

Так как минимизирует то правая часть (9.4.28) неотрицательна, откуда следует

что завершает доказательство теоремы.

Следствие 9.4.1. Для конечной меры искажения с наклон непрерывен при и стремится к при стремящемся к 0.

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

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

Это означает, что не зависит от для всех и следовательно, как вытекает из (9.4.29), где не зависит от Следовательно,

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

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

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

Следовательно, остается только показать, что

Для этого рассмотрим новую меру искажения задаваемую равенством

Скорость как функция искажения для равна так как среднее искажение для любого равно или 0 или и является минимумом для которого среднее искажение равно 0. Следовательно, функция

для также равна при всех используя (9.4.8) для

при любом получаем

при ограничении

Взяв достаточно большим, можно аппроксимировать которое максимизирует (9.4.32) при условии (9.4.33), сколь угодно точно с помощью которое удовлетворяет

Следовательно, для любого можно выбрать достаточно большим, так что

Так как

то имеем

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

Доказательство. Для любого заданного пусть максимизирует правую часть (9.4.8) при условии (9.4.9). Из теоремы следует, что которое минимизирует может быть найдено из (9.4.5), где выходные вероятности удовлетворяют равенствам

Это является множеством К линейных уравнений с неизвестными и имеется по крайней мере одно решение . А тогда, точно так же как в следствии 3 § 4.5, доказывается, что имеется решение, для которого только К чисел Если прямая касается кривой только в одной точке, то это решение должно дать эту точку. Вместе с тем, если является касательной к на целом интервале, то для того чтобы найти которое приводит к заданному требуется дополнительное ограничение

Используя (9.4.5) и (9.4.9) с равенством при получаем

Из (9.4.37) и (9.4.36) получаем линейных уравнений с неизвестными и, как раньше, должно существовать решение, для которого только из положительны.