Нахождение R(d) в некоторых простых случаях

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

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

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

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

Здесь X — параметр, изменяющийся от 0 до со и определяющий значение величины Для этого минимизирующего значения величины и выражаются через параметр X:

Легко видеть, что когда , то . Если то где — число равных

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

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

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

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

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

так как все буквы алфавита теперь равновероятны и

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

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