Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(9.4.12)
Рассмотрим функцию
F(p,P,f)= ^Q(k)P(j\k) ln
pg\k)
k* i
SQ(i)P(/IO
475
Отделяя третье выражение в (9.4.13) от первых двух н суммируя по /, получаем
F (р, Р, f) == R0 (р, Р) — 2 СЩ In -А- = R0 (р, Р) -
k Ч. \&)
~H(U)~^Q(k)\nfh. (9.4.14)
к
Покажем теперь, что F (р, Р, f) неотрицательна, используя обычное неравенство In х ^ х— 1. Из (9.4.13) имеем
-F(pM) = 2Q{k)P(j\k) in
k,i
LP(i\k)Q(k)
<2 ю (/)/* e"^*1 Л-2 Q(*)P(/1 A:). (9.4.16)
k,j k,j
Суммируя сначала no k и используя затем ограничение (9.4.9), получаем
— F(p, Р, f)< !>(/) —2со(/) = 0. (9.4.17)
/ i
Из (9.4.17) и (9.4.14) выводим (9.4.12).
Неравенство (9.4.12) переходит в равенство тогда и только тогда, когда оба неравенства, ведущие от (9.4.15) к (9.4.17), переходят в равенства, или тогда и только тогда, когда
_?Шл_е-Р*<*;/) = 1 для всех р(у |/г)>0, (9.4.18)
P(j\k)Q(k)
^fke~pd <"> = 1 для всех и(/)>0. (9.4.19)
k
Если обе части (9.4.18) умножить на Р (j\k) и просуммировать по /, то получим (9.4.7), так что условия теоремы необходимы для равенства в (9.4.12). Аналогично, если неотрицательные числа ю (0), ..., ю (/ — —1) удовлетворяют (9.4.7) и если (9.4.19) удовлетворяется, то, как было уже показано ранее, Р (/1 k), заданные формулой (9.4.5), являются переходными вероятностями с выходными вероятностями ев (/). В соответствии с (9.4.5) выбранные значения удовлетворяют (9.4.18), так что условия теоремы достаточны для равенства в (9.4.12).
Для завершения доказательства следует показать существование Р и f, удовлетворяющих заданным ограничениям и удовлетворяющих
(9.4.12) с равенством. Пусть Р минимизирует*' R0 (р, Р) в допустимой области, в которой Р — множество переходных вероятностей. Для каждого k выберем некоторое /, скажем / (k), для которого Р (/1 k) >
> 0, и определим fh равенством
111 + Pd i W)-ln 7^7 = 0• (9-4 -2°)
“[/(*)] Q(k)
*) Такое P должно существовать, так как область, по которой проводится минимизация, замкнута и ограничена, и R0 непрерывна по Р в этой области.
476
В оставшейся части доказательства будем считать это f = (/„, /к-i)
фиксированным. Рассмотрим функцию F (р, Р, f), определенную в
(9.4.13), и заметим, что из (9.4.14) следует, что так как рассматриваемое Р минимизирует R0 (р, Р), то Р минимизирует также F (р, Р, f). Для любых k, j с со (/) > 0 и d (k; j) < оо имеем
dF (р, Р, f) dP(j\k)
ln
P(i \k) w O')
¦ pd (k; j) — ln
fh
Q(*)J
Q(k). (9.4.21)
Если это выражение отрицательно (положительно) для каких-либо k, j (с to (/) >0, d (/г, /) < ро), то приращение, увеличивающее (уменьшающее) это Р (/ | k), и приращение, уменьшающее (увеличивающее) Р (/ (k) \ k) (для которого dF/dP [/ (k) \ k\ = 0), будет приводить к убыванию F (р, Р, f) в противоречии с предположением, что Р минимизирует F (р, f, Р). Отсюда следует, что для минимизирующих Р
P(ilk) + pd(k; j) — ln^^-^0 (9.4.22)
In-
w(y') .......... Q(k)
для всех k, j с со (j) > 0, d (k\ j) < оо. Также P (j | k) = 0, если или w (/) = 0, или d (k; j) = оо. Следовательно, для рассматриваемых P, f (9.4.5) удовлетворяется для всех k, j. Умножая (9.4.5) на Q (k) и суммируя по k, видим, что (9.4.9) удовлетворяется с равенством для /, таких, что со (/) >0. Таким образом, Р и f удовлетворяют достаточным условиям для равенства в (9.4.12). Доказательство еще не закончено, так как следует показать, что f лежит в области, соответствующей заданным ограничениям, т. е. что (9.4.9) также удовлетворяется для /, таких, что со (j) = 0. Предположим, что со (/') = 0 для заданного /', и определим Р' через минимизирующее Р следующими равенствами:
fh Р d(k-i)
для всех k,
Q(k)
’ (j (k) | k) = P (/ (k)\k) — P' (/' | k) для всех k, P' (j | k) = P{j j k) для всех других /, k.
(9.4.23)
(9.4.24)
(9.4.25)
Для достаточно малых е > 0 вектор Р' представляет собой множество переходных вероятностей. Пусть Fj (р, Р, f) задается равенством
/\,-(р, Р, f) = 2Q(A:)P(/| k)
k
In + pd (k; j) — ln -A-
co(i) Q(k)
Тогда
F(p, P', t)-F(p, P, f) = /v(P, P'- f) + + S p'> p. f)l-
M/'
(9.4.26)
