Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 160

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 154 155 156 157 158 159 < 160 > 161 162 163 164 165 166 .. 355 >> Следующая


________________ Г./-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.
Предыдущая << 1 .. 154 155 156 157 158 159 < 160 > 161 162 163 164 165 166 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed