Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
При любом заданном г определим перекошенные распределения вероятностей Qr(z) с помощью равенств
Qr (z)= P{gjpjZ ¦ (6Б.24)
Пусть гг, Г; i = 1,2...— последовательность статистически независимых слу-
чайных величин, каждая из которых принимает значения с вероятностями Qr(z), и рассмотрим «перекошенное» случайное блуждание, для которого S0, г — 0 и
П
^п,г= 2’г
i=i
при п > 0.
Нас интересует вероятность того, что при таком перекошенном случайном блуждании первый переход ниже некоторой точки и < 0 произойдет при данном целом п, и определим вероятность />, п(и, v) при s^uc помощью равенства
/г, и (и, f) = Pr[S;,r > и; 1 </ < п— 1; Sn,r = u]. (6Б.25)
ОО
Заметим, что 2/г, п(и, v) является вероятностью того, что при перекошенном блуж-данни первое достижение значения, меньшего или равного и, произойдет в
оо
момент п. Следовательно, 2 2/V, п(и, v) является вероятностью того, что при
п= 1 v^.u
перекошенном случайном блуждании когда-нибудь будет достигнуто значение,
331
меньшее или равное и. Наконец, при г = О эти вероятности относятся к первоначальному случайному блужданию.
Теперь предположим, что аи ..., ап являются последовательностью значений, которые могут принимать случайные величины z2.......zn. Из (6Б.24) получим
Рг [г1,г— ai> ••• > гп,г — ап Следовательно,
Рг
Pr [Z1 = a1,...,zn = ап] ехр ( г = lS(r)]n
•i>) < = 1 /
(6Б.26)
а*
г = 1
ехр
V г — 1
[г ('')]"
(6Б.27)
Рис._6Б.1. График функции g(r) = ехр(лг{) для Zi>0, где zj принимает как положительные, так и отрицательные значения.
Если просуммировать (6Б.27) по всем последовательностям ап, для кото-
i = v, то, по
/о, л (и, v)er
рых 2 ai >и ПРИ * <1<П—1 И 2аг=у’ Т0' получим, что г = 1 /=1
fr,n(u< v)----"
le(r)]n
(6Б.28)
Предположим теперь, что г выбрано так, что Z;,r < 0. Тогда, используя закон больших чисел, получаем
lim Pr [Sn,r<u] = l
п ->оо
и с вероятностью 1 перекошенное случайное блуждание в конце концов достигает значений, меньших или равных любому и < 0. Поэтому, суммируя обе части (6Б.28) по v < и и по п, получаем
1=2 2/о,я(и.«)е"’[*(/¦)Г
п = 1 V и
(6Б.29)
Этот результат известен как тождество Вальда для блужданий с одним барьером ч (величина и называется барьером, так как в теории случайных блужданий часто заканчивают блуждание после первого пересечения данного значения).
Здесь мы хотим использовать этот результат для вывода границы сверху величины
ОО
Рг [Sm;n ^ и] = 2 У fn.n (и, v) ¦
л= 1
332
Предположим, что z; > 0, в противном случае Pr[5m,-n < и] ¦= 1. Также предположим, что Z; принимает по меньшей мере одно отрицательное значение с отличной от нуля вероятностью, в противном случае Pr[Sm!-n < и) = 0. График функции g(r) представлен на рис. 6Б.1.В частности, функция g(r) выпукла kj и стремится к бесконечности как при г оо, так и при г — оо. Поэтому уравнение g(r) = 1 имеет два решения: одно при г = 0 и одно при г = г0, где /¦„ <0. Так как
—________1 dg(r)
^i,r—¦ . . . »
g (г) dr
то отсюда видно, что z;,r < 0 при г = /¦„; применяя (6Б.29), получаем
(6Б.30
(6Б.31)
Pr[5min<U]<e-r»“. (6Б.32)
Так как g(r) <1 лишь при г0 </¦ <0, то можно далее получить границу сверху в (6Б.32) вида е~~ги для любых г < 0, таких, что g(r) < 1. Наконец, заметив, что Pr[5m;n < и] < ехр (— г и.) также при и > 0, завершим доказательство леммы 6Б.1. Граница (6Б.32) является довольно точной. Чтобы увидеть это, предположим, что существует минимальное значение, например zmin, которое может принимать случайная величина г. Тогда v в (6Б.30) должна удовлетворять неравенствам и — zm/n < v < и и поэтому Pr[Smm < и] можно ограничить снизу с помощью неравенства
