Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Ре, 1 = Рг [w (у) ^ 01 передано сообщение 1]. (5.4.4)
Отыскание эффективных границ для вероятности того, что сумма
независимых случайных величин превосходит некоторое заданное число, является задачей общей как для теории информации, так и те-
142
ории вероятности, и поэтому она заслуживает более общего рассмотрения.
Предположим вначале, что t — случайная величина, принимающая только неотрицательные значения. Простейшей формой неравенства Чебышева является утверждение, что при любом б > О
Рг(/>б)<4> (5.4.5)
О
где t — среднее значение t. Для того чтобы доказать это, предположим, что t является дискретной случайной величиной с распределе-
нием вероятности Р (t). Тогда
Рг(/>6)= 2 Р(0< 2 PW-T-
оа />б о
Это неравенство возникает потому, что t/8 ^ 1 в области суммирования. Так как t/8 является неотрицательным при всех t, то можно ограничить далее это выражение сверху, суммируя по всем /; в результате получим (5.4.5). В точности такое же доказательство лишь с небольшими изменениями в обозначениях, очевидно, применимо к случаю недискретной случайной величины. Эквивалентная запись неравенства (5.4.5) получается при замене б It на а. Имеем
Рг(/^а7)^ 1/а. (5.4.6)
Чтобы показать на примере, насколько малоэффективно это неравенство, предположим, что t — рост случайно выбранного человека. Если /=152,5 см, то (5.4.5) утверждает, что вероятность того, что выбранный человек окажется выше чем 3 м 5 см, не больше 1/2, а вероятность того, что] выбранный человек окажется выше чем 15 м 25 см не больше 1/10."
Предположим теперь, что w является произвольной случайной величиной со средним значением w и дисперсией а2. Если положить в (5.4.5) t = (w — w)2, то получим
Рг[(ш—w)2 > б] ^о2/б. (5.4.7)
Обозначая е = б, это неравенство можно переписать в Биде, в котором обычно представляется неравенство Чебышева,
Pr [| w—w | ^ е] ^ а2/г2. (5.4.8)
Можно получить большое число других неравенств, называемых обобщенными неравенствами Чебышева, если положить /, равным другим функциям от w. Здесь будет особенно интересно неравенство, которое обычно называется границей Чернова; оно получается, если положить t = esw, где s — произвольное действительное число. В результате получим
Рг[е5да>б]^е™/б. (5.4.9)
143
Математическое ожидание esttl является производящей функцией моментов случайной величины w:
gw (s) — e$w = 2 P (w)eSW• (5-4.10)
W
Пусть б в (5.4.9) равно es/4, где A —произвольное действительное число. При s > 0 неравенство esw ^ esA эквивалентно неравенству w^A, так что (5.4.9) принимает вид
Pr [w > A] s^e~sAgw (s) при любом s> 0. (5.4.11)
Аналогично, если s С 0, то неравенство est" ^ esA эквивалентно неравенству w ^ А, что дает
Pr [w^ А] ^e~sAgw (s), s<0. (5.4.12)
Зависимость функции e~sAgw (s) от s изображена на рис. 5.4.1. Она принимает значение 1 при s = 0, и ее первая процзводная при s = 0
Рис. 5.4.1. Вид границы Чернова.
равна w — А. Вторая производная всегда положительна, что следует из равенства е~5Л?ш (s) = ехр [s (w — А)\. Поэтому, если А > w, то граница, устанавливаемая (5.4.12), больше чем 1 при всех s< 0 и, следовательно, является бесполезной. Аналогично, если А < w, то бесполезной является граница в (5.4.11). Другими словами, (5.4.11) и (5.4.12) могут быть использованы только при оценивании «хвостов» распределения.
В силу того, что e~sA gw (s) является функцией выпуклой ^ по s, то наиболее точную границу можно получить, найдя стационарную точку этой функции. Имеем
АЛЛЕЯМ; {в)ш (5.4.13)
as
Для большинства применений более удобно оставить s свободным параметром, чем считать, что s является решением (5.4.13).
Границы (5.4.11) и (5.4.12) полезны в основном тогда, когда w является суммой статистически независимых случайных величин:
N
w = 2 2«-
я= 1
144
13 этом случае производящая функция моментов случайной величины л/ может быть выражена через производящие функции моментов случайных величин zn следующим образом. Имеем
/ N \ N
gw (s) = exp s 2 zn j = П exp (szj.
\ n = I j n = 1
