Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Prfl-ft принятый символ = 0| передавался хх]
2.7. (а) /х. у (x1;0)=log— ------ ---------------;—1---- -------------=
’ 1 Рг [1-й принятии символ = 0]
==log-- — = tog [2 (I — е)].
/ 2
Здесь был использован результат, который очевиден из-за симметрии и который также легко вывести: если входами двоичного симметричного канала являются символы 0 или 1 с равными вероятностями, то выходами также являются символы 0 или 1 с равными вероятностями.
(в) Заметим, что первые три входных символа для канала являются статистически независимыми равновероятными двоичными символами. Так как канал является каналом без памяти, то легко получить, что первые три выхода также статистически независимы и равновероятны. Следовательно,
^х;У21 у, (¦*!> 0 I 0) =/х. у, | у, у, (*1> 0 I 0,0) = log [2 (1 е)].
Усредняя, наконец, по всем кодовым словам, найдем, что вероятность приема у = (0, 0, 0, 0) равна V8 [(1 — е)4 + 6 (1 — е)2 е2 + е4]. Поэтому
РУ4|У.У,У. (01 0,0,0) =(1-е)4+6 (1-е)2е2+е4
и
1—е
/ у . v iv v v (xj_; 010,0,0) = log— -— — — — .
Х'У«П»У»У» (1—е)4 + 6(1—е)2е2-)-е4
2.8. Первые N — 1 двоичных символов статистически не зависят друг от друга, a N-й определяется первыми N — 1, так что
[ 0 при n<N,
1{Хп-,Хп_1\Х1 ,...,хп-г =
[ 1 бит при n — N.
Заметим, что это рассуждение не зависит от порядка символов в последовательности. Другими словами, никакое множество из N — 2 символов не дает никакой информации относительно xN, хотя при любом заданном множестве из N — 2 символов оставшийся символ разрешает всю неопределенность относительно xN,
2.9. Н (X) = 3/2 бит, / (Х;К) = 1/2 бит,
Н (Y) = 1 бит, / (X; Z) = 1 бит,
H(Z) = 1 бит, / (X;F|Z) = 1/2 6ht,
H(YZ)= 2 бит, I(X;YZ)= 3/2 бит.
Выражение I (X; Y \ Z) истолковывается как средняя взаимная информация, содержащаяся в Y относительно X после того, как становится известным Z. В этом примере условие, что задано Z, является несущественным.
2.10. (а) С помощью прямых вычислений и упрощения полученного выражения будем иметь
I(X-Y) =(1-8)
р log---------+ (1— р) log-
р 1 —р.
Либо выполняя непосредственную оптимизацию по р, либо используя теорему 2.3 1, можно найти, что р = 1/2 максимизирует I (X; К). При р = 1/а имеем I (X; Y) = (1 — е) бит и
/Х;у (0; 0) = /х. у (1; 1) = 1 бит; /х.у (х; ?) = 0.
(б) Для данной стратегии передача символа источника заканчивается каждый раз, когда в канале не возникают стирания. Поэтому среднее число символов источника, переданных при одном использовании канала, равно (1 — е). Согласно закону больших чисел при большом числе использований канала N с высокой вероятностью (близкой к 1) число переданных символов источника близко к (1 — 8) N.
578
2. И. (а)/ (X; У) = 1 + */4 log % + 1/i log i/4 = 0,189 би*.
(б) Капитал в конце п-й игры Сп равен удвоенной ставке на выигравший цвет, т. е. Сп =Cn-i [2 (1— q)]2n [2q\x~zn.
Решая это рекуррентное соотношение, получаем
N
CN=C0 П [2(1 -?)]2П [2<7]‘-гп,
п= 1
EN= — ^ [г„ log [2 (1 —(?)] + (1 — z„) log 2q].
N п = 1
Так как zn = 1 с вероятностью 3U и 0 с вероятностью V4 и так как математическое ожидание произведения независимых случайных величин равно произведению математических ожиданий, то
N
+ ~Т" %q\ =Cq
2М ' 4
EN=-^-i°g [2 (1— ?)]+-“ log (2q).
T~q
Из рассмотрения выражения для CN находим, что CN максимизируется
при 9 = 0. Дифференцируя Еп по q, получим, что единственный максимум имеет место при q — 1/4. Поэтому
/ 3 _ 3 3 1 1
maxCN =С0 — , max EN = 1 + —— log —— + —- log —— =?/ (X; Y).
(в) Заметим, что при любом заданном q значение EN является выборочным средним множества N одинаково распределенных независимых случайных величин 2л log [2 (1 — (?)] + (1 — zn) log 2q. Поэтому, в силу закона больших чисел lim Pr [ | EN — EN | > е] = 0 при любом е > 0. В обозначениях CN это
N-rOO
результат утверждает, что
lim Рг { С0 2"^“®] < CN < С0 2N [?Д'+е1\ = 1.
N->¦00 I J
Другими словами, значение EN определяет те близкие пределы, в которых как CN, так и ЕN при больших N находятся с высокой вероятностью. Игрок, который использует q = 1/4 (которое максимизирует EN), будет с подавляющей вероятностью иметь больший капитал после достаточно большого числа игр, чем игрок, который использует какое-либо другое значение q. Дополнительное проникновение в эту своеобразную ситуацию может быть получено с помощью рассмотрения того, что случится при <7=0 (которое максимизирует CN). В этом случае весь капитал ставится каждый раз на предсказанный цвет и любое появле-ние другого цвета уменьшает капитал до 0. Таким образом, после N игр капитал равен С02м с вероятностью (3/4)w. При увеличении N вероятность выигрыша экспоненциально убывает, однако выигрыши столь велики, когда они возникают, что математическое ожидание CN велико. Это является примером экстремальной ситуации, в которой математический термин «ожидание» не имеет смысла, обычно вкладываемого в него в русском языке.
