Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
г Р(у)х) у
P(z)x)
Р(с/\х)
К задаче 2.9
К задаче 2.10
(Заметьте, что эту передачу можно было бы рассматривать как передачу по одному каналу с выходом уг.)
Найти Н(Х), H(Y), H(Z), H(YZ), /(X; Y), I(X; Z), /(X; Y\Z), /(X; YZ).
Дать толкование этим выражениям взаимной информации.
2.10. Двоичный стирающий канал, который изображен выше, является каналом с «шумом» особенно простого типа, при котором переданные символы могут быть «стерты», но никогда не могут быть приняты ошибочно.
(а) Пусть Рх(0) = р = \ -г- Рх( 1). Выразить I(X\ Y) через р и найти значение р, которое максимизирует I(X; Y). Для этого максимизирующего р найти 1(х', у) во всех точках ансамбля ХК, а также найти /(X; Y).
(б) Предположим, что последовательность статистически независимых и равновероятных двоичных символов требуется передать по двоичному стирающему каналу. Предположим далее, что имеется бесшумный канал обратной связи от приемника, по которому отправитель узнает, как был принят каждый символ. Рассмотреть следующую стратегию передачи последовательности с абсолютной
519
надежностью. Посылать символы по порядку по каналу, повторяя каждый символ, если он был стерт, до тех пор, пока он не будет правильно принят. Найти среднее число переданных символов при одном использовании канала.
Замечание. Интуитивно ясно, что рассмотренная здесь схема передачи приводит к оптимальному использованию канала. Заметьте фундаментальную роль, которую играет I(X;'Y).
2.11. Пусть л; = ах означает событие, состоящее в том, что шар при игре в рулетку останавливается в «красной» лунке, а х — а2 аналогично означает, что шар останавливается в «черной». Предположим, что игорный дом не берет налог, т. е. что пари, заключенное на один доллар, относительно того, будет ли лунка красной или черной, приносит один дополнительный доллар в случае успеха. Будем считать, что Рх(ах) = Р х.(а2) = 1/%-
Крупье рулетки разработал план для обмана игорного дома. После многих лет терпеливого изучения он научился частично предсказывать цвет, наблюдая путь шара вплоть до самого последнего момента, когда пари может быть еще заключено. Сообщая эти сведения сообщнику, крупье рассчитывает использовать свое провидение, чтобы получить кругленькую сумму ко времени, когда он уйдет в отставку.
Пусть;/ означает сигнал крупье; покашливание, у = Ъх означает предсказание красного, а подмигивание, у = Ь2, означает предсказание черного. Предположим, что Рх \у{ах\Ьх) = Рх | у{а21 Ь2) = 3/4 и что последовательные вращения независимы.
(а) Найти I(X; Y).
(б) Сообщник имеет некоторый начальный капитал С0. Он решил ставить фиксированную долю 1 — q его текущего капитала на предсказываемый цвет при каждом последовательном пари и долю q на другой цвет (заметьте, что это эквивалентно ставке доли 1 — 2 q на предсказываемый цвет и отказу ставить 2q).
Показать, что после N игр капитал сообщника является случайной величиной
N
Сд, = С0 П [2(l-q)fn[2q] Ч
п— 1
где zn = \г если предсказание правильно, и 0 в противном случае. Определим скорость роста:
1 CN NEN
en=~ i°g2 —; C„=c0 2 .
Найти значения q, которые максимизируют математические ожидания CN и EN, Сравните максимальное значение математического ожидания скорости роста Еы с I(X; Y).
(в) Если бы вы были сообщником, какое бы значение q вы использовали и почему?
Указание: применим ли закон больших чисел к ЕN или СN при N -> оо ? См. Дж. Л. Келли (195G) для знакомства с детальным анализом такого типа задач.
2.12. Выборочное пространство ансамбля X состоит из неотрицательных целых чисел. Найти вероятности Рх(п), я = 0, 1, ..., которые максимизируют Н(Х) при условии, что среднее значение X
СО
' 2 пРх («)
« = о
равно заданному значению А. Вычислить максимальное значение Н(Х).
2.13. Запись погоды в некотором городе дается в приводимой ниже таблице; числа указывают относительную частоту соответствующих событий.
520
На самом деле
Предсказание Дождь Нет
дождя
Дождь V. 3/16
Нет дождя Vie 10/1в
Умный студент заметил, что составитель прогноза прав только в 12/16 случаев, но мог бы быть правым в 13/16 случаев, предсказывая всегда отсутствие дождя. Студент объяснил ситуацию и написал заявление о приеме на работу в бюро прогнозов, но начальник бюро прогнозов, который был специалистом по теории информации, отклонил его заявление. Почему?
2.14. Пусть X —ансамбль, состоящий из М точек аъ ..., ам, и пусть Рх(ам) ~ а¦ Показать, что