Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
—??(Р. Q
k,i
Q(k)
-[?' (р, Q)]2.
(6)
Як} J
Так как последнее выражение отрицательно, то оно может быть отброшено и в результате получим
Q(k)\2
-?J(p, a>jqhj I ln
к, j \ qk}
(7)
Заметим, что —[?q (1> Q)l2 всегда можно вновь поместить в окончательную границу для —Е1, если возникает необходимость иметь более сложную, но более точную границу.
4
Далее используем то, что (In х)г х ПРИ х > 1. Это можно показать,
замечая, что выражение (1п х)21х в области х > 1 достигает максимума, равного 4/е2. Таким образом,
е k,j чь.} k,}\ \ ЧЬ) !
QW!qhJ< 1
623
Используя также (4), получаем Q(k)
9hj
in
P(j\ fe)1/(1+p)
;(1па,-)2,
(9)
где последнее неравенство справедливо при Q (k)lqkj <С 1 в силу того, что в этом случае отрицательная величина внутри квадратных скобок уменьшается. Из (4) и (2) имеем
1па‘. + Р = —1—
1 1+Р
Сочетая (8)—(10), получаем
к, /:
[In со,—?0(р, Q)].
lncoj —?0(р, Q) 1+р
(10)
Q(k)/qkj< 1
lno)j- —?0(р, Q)~I2
1 + Р
Можно произвести дальнейшую оценку этого выражения, максимизируя его по со < при условии, что = 1- Отметим, что максимум достигается при соу = 1/У, давая
-Е'о (p, QX — +
ez
In J+?„(p, Q)
1+Р
(И)
Заметим, наконец, что ?0(Р. Q) ^ рС р In/. Подстаьляя в (11), лолу-4
чаем — Е„ (р, Q) «^—+(1пУ)2. Используя это неравенство для оценки а в (1)
и замечая, что С—R ^ а для всех R, 0 получаем
(C—R)2_____
Er(R Q)>
(12)
- + 2 (ln J)2
Отметим, что эта граница немного точнее того результата, который следовало доказать.
5.24. В силу того, что Ех (Р, Q) — неубывающая функция р, и так как Eex(R, Q) = sup [?х (p,Q) — P-R], получим Eex(R, Q) < Hm.E^p, Q) при всех R.
р ^ 1 р оо
Кроме того, если lim Е* (р, Q) конечен, то при любом s > 0 можно выбрать р
р — СО
так, чтобы Ех(р, Q) > lim?a;(p,Q) — s/2 и поэтому при R, достаточно малом,
р —* ОО
Ех (р, Q) — pR > 1 im Ех (р, Q)— s. Следовательно, при всех достаточно малых
р -> ОО
R > 0 имеем
lim Ех (р, Q) > Eex(R, Q) > lim Ех(р, Q) — s
р -г* ОО Р ->• ОО
и
Пт?еж(#, Q) = lim?x(p, Q).
R -*¦ 0 р оо
Положив 6=1/р, получим
-In 2 QWQ(i) [S/P(/|A)P(/I0]e
?*(i/б, Q)= ________ill________________________________L...
624
Замечая, что сумма по / является строго положительной rfpn всех I, к (см. стр. 171), можно найти предел при 6 ->- 0 по правилу Лопиталя; в результате получим
lim Ех (1/6, Q) = — 2 Q(k)Q(i) In 2 VP~(i W P(i U)-k, i j
5.25. Так как <fh,i — 1 при 2 У P (i I k) P (Ц /) > 0 и фА, t-= 0 во всех остальных случаях, то фй,г = фг, Также ф1>1 = Фо,о= 1- Следовательно,
^Q(k)Qd) 4>fc,{ = Q3 (0) + 2Q (0) Q (I) + Q2 (1) + k, i
K-l 1 1 K-l
+ 22 QWQ(i)4k,t+ 2 2 в(*)?(<')Фи,| +
к =2 /= О A = 0 « = 2
+ 2 2 Q(*)<?(0<Pft.J= [Q(0) + Q(1)13 + к 2 < 2
K-l
+ 2 2 Q(0[Q(0)q>e,«+Q(l)q>i,i]+ 2 2 Q(*)Q(0<Pft,i-
i =2 ft>2 i>2
Если (? (2)....(К — 1) зафиксированы, a Q (0) и Q (1) варьируются при
постоянной их сумме (так, что ? Q (6) = 1), то заметим, что написанная выше функция является линейной при этой вариации. Поэтому минимум при Q (0) >0, Q (1) > 0 достигается либо при Q (0) = 0, либо при Q (1) = 0. Отсюда видно, что для любого вектора вероятностей Q можно уменьшить (или не изменить) (к) Q (t) фй.г с помощью последовательного пересмотра каждой пары г, k (( ф k), для которой ф= 1, и замены либо Q (к), либо Q (г) на 0. В конце этой процедуры множество i (обозначим его через /), для которых Q (i) > 0, удовлетворяет условию ф&,г = 0 при всех к ? /, г ? /, i ф к. Для такого множества /
