Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
________________ Г./-1Г-К-1
ехР [1/2 (у[ —Vi)] = S l/=o
ГК- 1 "|| v (J- 1 ГХ- 1 “|2l V
X 2 Q(k')VP(i I*') = 21
_k'=0 JJ l/=0
2 Q(k)YP(i\k) k= 0
X
K- 1
2 Q{k)VP(i\k)
k=0
= exp [— vE0 (1, Q)].
Аналогично имеем
(6Б.9)
exp(1/2v;) = {Q (•x\a)) P(y\a)\x<f))Q(x’i^) x
a = 1
X
P(y\a)\x'Sa))
CO
(6Б.10)
Вспоминая что со (y\a^) = 2 Q Р {у\°^ \ xj-a*)’ это выРажение приводим к виду
(J— 1 К — 1 'v
2 S QWaU^Piilk)1' _1=0k=0
exp(l/2 y'i)
Применяя к сумме по / неравенство Коши, получаем
Уг е-В/ 2
(6Б.11)
ехр (Ч*У1)< [/2«(/) I 2[|Q(*)l/P(/|/2)l2e-B/2]V =
1
= ехр
[?0(1.Q) + B] •
(6Б.12)
______При ограничении В < ?0(1> Q) можно также оценить сверху величину
exp[V2(Y(' •— Vi)]! входящую в (6Б.9), величиной ехр{ — (v/2) [?0(1, Q) + В]}. Подставляя эту границу и (6Б.12) в (6Б.7) с s = V2, получаем, что при п < I
Рг [Tm(t) >Тп+ а] < ехр | — [?о(1. Q) +B]J- (6Б.13)
Далее следует найти верхнюю границу второго члена в (6Б.5), Рг[Гт(г) ^ ^ Г;-f rnin ГП1;-fa]. Напомним, что
2 Vi i=i +1
при п > I и что yi — независимые одинаково распределенные случайные величины. Последовательность Tn,i при п = I, I + 1, ... называется случайным
329
блужданием. Приведенная ниже лемма является хорошо известным результатом теории случайных блужданий** и часто используется в теории информации. Мы сформулируем ее и затем воспользуемся, результатом здесь, а докажем ее в следующем разделе настоящего приложения.
Лемма 6Б.1. Пусть zlt z2, ... — последовательность независимых одинаково распределенных дискретных случайных величин. Пусть S0 = 0 и при любом п > О
Положим
Sn= 2г;-i = i
Sjnin — inf Sn. n> 0
Тогда при любом г < О, таком, что ехр (гг;) < 1, и при любом и
Pr [Smin <«]<е~™.
(6Б.14)
Применительно к нашему случаю Zj = yi+i, 1, так, что Smi-n = min Г„,г. Теперь покажем, что ехр [ — (1/г)Тг]< 1> откуда следует согласно (6Б.14), что
Pr [min Г„,г < и] <еи/2.
Аналогично (6Б.10)—(6Б.12) имеем v
(6Б.15)
ехр ( VI) = 2 П (<г wn)) р {у\а) I х\а))
Р (у\а) | *ja)) ч>(у\а))
Ч,
рВ/2
2 Q(k)Va(i)P(i\k)eB/2
А = 0 / = О
<ехр^-у[?0(1, Q)-B][. (6Б.16)
На последнем шаге мы воспользовались неравенством Коши аналогично тому, как это сделано в (6Б.11) и (6Б.12). Так как по предположению В < ?0(1, Q), то ехр (—1/2'Vi) < 1 и (6Б.15) справедливо.
Случайная величина Г/ •— Гг — а статистически независима от случайной величины min Гп, г и, следовательно,
Рг [Г/—Г; — а — min Г„,г >0] = Рг [Г/ — Г; —а =«] Pr [min Г„,г<и], (6Б.17)
и
где суммирование по и проводится по всем дискретным значениям, принимаемым случайной величиной Г/ — Г; — а. Ограничивая сверху (6Б.17) с помощью (6Б.15), имеем
Рг [Г/ — Гг — a—min Г„,г ^>0] < 2рг [Г/ — Гг — а— и] еи/2 =
= ехр [*/2 (Г/ — Гг— а) =
= ехр
1
2(v;-V/)-a < = 1
(6Б.18)
(6Б.19)
ехр
V/-V,
(6Б.20
*> См., например, книгу Кокса и Миллера (1965).
330
= ехр — у—y?e(l.Q)j< (6Б.21)
<елр j-y—у[?0(1, Q) + B]j. (6Б.22)
При выводе (6Б.20) использована статистическая независимость у/ — у*' при различных значениях i, в (6Б.21) использовалось соотношение (6Б.9), а в (6Б.22) — предположение, что В < ЯоО, Q)- Наконец, подставляя (6Б.22) и (6Б.13) в (6Б.5), имеем
Рг[Г;(0 >Гтгп + а]<(г + 1)ехр|-|—у-[?'о(1. Q) + B]}. (6Б.23)
что завершает доказательство леммы 6.9.3. |
Случайные блуждания и доказательство леммы 6Б.1
Последовательность случайных величин S0 = 0, Sj, S2, ... называется случайным блужданием, если при любом целом п > 0 можно представить Sn в виде
П
2 гг, i = i
где гг, гг, ... — последовательность независимых одинаково распределенных случайных величин. Пусть g(r) = ехр (г, Z;) — производящая функция моментов каждой из величин z-t и пусть P(z) ¦— распределение вероятностей этих случайных величин. Для простоты записи будем предполагать, что Zj — дискретные случайные величины, но результаты можно легко распространить на произвольные случайные величины, для которых g(r) существует в окрестности г = 0.