Цепи Маркова (1121219), страница 26
Текст из файла (страница 26)
. . , l.l+j )( i−j)−+i>(i=1||+ 2|| > E (+).(1.14.24)(1.14.25)−+ 2j ) .=l+)=l1 X +122+ 2( i − +|| .j ) rij > 2 (H( )) ||2(1.14.26)i,j=1ЗдесьH( ) = infh Q(S, Sc)(S)i: ∅ 6= S ⊂ S+ ( ) .(1.14.27)Чтобы доказать соотношение (1.14.26), не теряя общности, предположим, что i > 0 ∀ i = 1, . . . , l. В силу неравенства Коши—ШварцаlXi,j=1|2i−2j |rij6√2E ( )1/ 2Xl(i+j)2riji,j=1 1/ 266 23/2 E ( ) 1/2 || || .lТеперь предположим, что для некоторого > 0 выполняется следующеенеравенство:(L ) i 6 i для i ∈ S+ ( ).1/2 lPТогда норма || + || =( i ∨ 0) 2 iудовлетворяет неравенствуj)rij ,−1(i) иi= ...
получаем=++ii+i,j=1Замечание 1.14.2. В тех же обозначениях для любого вектора 1векторы ... и ... , гдеl1 X +( i − +j )(2В самом деле, последнее неравенство следует из элементарной оценкиE(Отсюда 1 6 2h. Доказательство оценки снизу в соотношении (1.14.22)является более сложным и основано на следующих двух замечаниях.Замечание 1.14.1.
Пусть задана действительная функция : i ∈∈ {1, . . . , l} 7→ (i); обозначим + (i) = max [ (i), 0] = (i) ∨ 0 и положимS+ ( ) = {i ∈ S : (i) > 0}. Предположим, что S+ ( ) 6= ∅.Благодаря соотношениям (1.14.6) и (1.14.10) можно записать E ( ) == hL , i и E ( +) = hL + , + i. Здесь опять и + обозначают l-мерные , i =и правая часть этого равенства, что довольно неожиданно, оказывается неменьшеhL + , + i = E ( +).Вновь используя соотношение (1.14.9), получимE ( S)Q(S, Sc)Q(S, Sc)=62.1 (P) 6cV ( S)(S) (S )(S)+|| > hLгде(S)iminS : 0< (S) 61/2h=1157Действительно,h 1а затем положим§ 1.14. Геометрическая алгебра цепей Маркова, III.
Границы Пуанкаре и Чигера(1.14.28)Левую часть формулы (1.14.28) можно записать в виде2lX1(j>i) (i,j=1=4(j) 2 − (i) 2)rij =lXi,j=11(j>i)rijZjit dt = 4Z∞0ti,j :Xi 6t< jrij dt.(1.14.29)(1.14.30)i,j=1для St (= St ( )) = {i :и (1.14.26), находим:i> t} ⊆ S+ ( ). Комбинируя соотношения (1.14.24)23/2 E ( ) 1/2 || || > H( )т. е. справедлива оценка>Z∞012(St)t dt = H( ) || ||2 ,1(H( )) 2 .2(1.14.31)Теперь мы готовы завершить доказательство оценки снизу в неравенстве Чигера 1 > h2 /2.
В силу соотношений (1.14.24), (1.14.26) и (1.14.27)если (L ) i 6 i ∀ i ∈ S+ ( ), то выполняется неравенство (1.14.31).Возьмем теперь= 1 , и пусть T — нормированная собственнаяTвектор-строка L , соответствующая собственному значению 1 : T LT == 1 T , т. е.
L = 1 , где || || = 1. Мы знаем, что вектор-столбцыlPи 1 являются -ортогональными, т. е. -среднее равно нулю:i i =i=1= 0. Значит, всегда можно добиться выполнения неравенства 0 << (S+ ( )) 6 1/2, а следовательно, H( ) > h. Оценка 1 > h2 /2 следуеттеперь из неравенства (1.14.31) при таком выборе значения и вектора .В конце этого параграфа мы расскажем одну поучительную историю, из которой можноизвлечь два урока.
Во-первых, хорошее владение искусством вычислений является жизненноважным (что уже отчетливо проявилось в приведенных выше доказательствах). А втораямораль (особенно для нынешних и будущих лекторов) в том, что не всегда безопасно читатьскучные лекции. Эта история из жизни знаменитого физика Игоря Тамма (1895–1971),нобелевского лауреата в области физики (1958 г.) и близкого друга Н. Бора, П.
Дирака,Р. Пайерса и многих других. Тамм был чрезвычайно популярным и уважаемым в советскоми международном сообществе физиков; ходила даже шутка о том, что если бы существовалаединица измерения честности, то называлась бы она «один тамм». Тамм родился во Владивостоке, а обучение начинал в Эдинбургском университете, где изучал математику. Вернувшисьв Россию на летние каникулы в 1914 году, он уже не смог продолжить свою учебу заграницей, так как началась Первая мировая война. Ему удалось закончить курс в Московскомуниверситете, и в течение нескольких лет он преподавал математику в нескольких учебныхзаведениях. Это был период гражданской войны в России (1918–1920), когда в стране былаострая нехватка продовольствия и одежды. Люди часто прибегали к «бартерному обмену»предметов одежды на еду и наоборот.
Однажды Тамм отправился в местность недалекоот Одессы, чтобы обменять сумку вещей на еду. Военная обстановка в этой местностибыла нестабильной, основные баталии разворачивались между красными и белыми, однакоактивные действия вели и различные другие силы, включая так называемых зеленых (которыхне следует путать с одноименным современным политическим течением). Зеленые выступали§ 1.15.
Большие уклонения для цепей Марковас дискретным временемНичего не пропускайте, постоянно следите (за своими детьми);вы не знаете, где окончится уклонение от правды.С. Джонсон (1709–1784), английский публицист и драматургТеория больших уклонений описывает редкие события, вероятностикоторых малы. Формально говоря, это асимптотическая теория, рассматривающая такие события An , что P (An) → 0 при n → ∞. Типичный примертакого события, когда случайная величина Yn принимает неограниченноубывающие значения, это {Yn > n( + a) }, EYn = n , a > 0 (переходя от Yn к −Yn , мы можем рассмотреть также неограниченно растущиеотрицательные значения).
Начнем с простейшего примера, когда Y n == Z1 +. . . +Zn есть сумма n копий н.о.р.с.в. Z. Предположив, для простоты,что с.в. Zi принимают конечное число значений z (более одного), мы можемутверждать, что если EZ = EZi = и Var Z = Var Zi = 2 > 0, то прик , слабый и строгий законыn → ∞ усредненная сумма Yn /n сходится √больших чисел (з.б.ч.), и с.в. (Yn − n ) / n имеет в пределе нормальное распределение N(0, 1) (локальная и интегральная ц.п.т.). Однако этиутверждения мало что говорят нам о вероятности P (Y n > n( + a)), гдеa > 0.
Например, неравенство Чебышёва P (Yn > n( + a)) 6 Var Z1 /na2гарантирует, что P (Yn > n( + a)) стремится к 0, но остается вопрос,с какой скоростью. Если с.в. Z1 , Z2 , . . . принимают два значения, напримерc= Q(St , St )j)rij6t<i1(и против красных, и против белых (и против других сторон), а целью их было установление«крестьянской власти» (некоторые современные историки рассматривают их как борцов заукраинскую государственность). Одним из их лозунгов был такой: «Бей красных, пока непобелеют, а белых, пока не покраснеют». Тактика зеленых состояла в том, чтобы атаковатьслабые места в тылу как белых, так и красных, быстро захватить добычу и скрыться.Тамм был схвачен во время внезапной вылазки зеленых.
Как подозрительную личностьего привели к командиру. Живописного вида командир с медвежьими ухватками был того жевозраста, что и Тамм, и носил, согласно обычаям того времени, пару маузеров на ремне, грудьего украшали перекрещенные пулеметные ленты. Его заместитель доложил, что Тамм арестован как большевистский агитатор и должен быть немедленно расстрелян. Тамм протестовал,уверяя, что он вовсе не политический активист, а профессор математики. Неожиданно командир приказал всем выйти и оставить его с Таммом наедине. Затем он сказал Тамму: «Отлично.Если вы математик, выпишите остаточный член в форме Маклорена для разложения в рядТейлора.» В одно мгновение Тамм выдал ответ, сопроводив его комментарием, что вопросбыл слишком тривиальным.
Командир был удовлетворен и немедленно приказал отпуститьТамма и позволить ему вернуться в Одессу. Как оказалось, командир зеленых был бывшимстудентом-математиком, но счел изучение математики слишком скучным занятием...lX159Теперь заметим, что§ 1.15. Большие уклонения для цепей Маркова с дискретным временемГлава 1. Цепи Маркова с дискретным временем158160Глава 1. Цепи Маркова с дискретным временем§ 1.15. Большие уклонения для цепей Маркова с дискретным временем161±1, можно попытаться использовать точную формулуP (Yn = m) = Cn(n+m) /2 p (n+m) /2 (1 − p) (n−m) /2 ,где p = P (Z1 = 1), m = 0, ±1, .
. . , ±n, но вычисления становятся громоздкими. Чтобы разобрать более или менее общий случай, необходимыдругие методы.Оказывается, ответ довольно прост. Рассмотрим производящую функцию моментовEe Yn = (Ee Z) n ; здесь п.ф.м. для каждого слагаеP (п.ф.м.)Zzмого Ee =e P (Z = z) равна конечной сумме экспонент. Любая п.ф.м.zявляется выпуклой функцией (это можно доказать, используя неравенствоd2Ed 2ZЙенсена или просто продифференцировав, например= EZ2 eZ>> 0). При сделанных предположениях Ee и Eeконечны для любых∈ R. (Очевидно, они также и положительны для любых ∈ R.) Возьмемлогарифм от Ee Yn и разделим на n:Рис.
1.42YnZ1ln Eenэкспоненты как положительных, так и отрицательных значений. Пустьz+ > 0 — максимальное, а z− < 0 — минимальное значения, которыхдостигает Z. График функции Λ ( ) имеет вид гиперболы, проходящей черезначало координат: см. рис. 1.42.= ln EeZ:= Λ ( ).(1.15.1)YnDracula’s Bloody ’s14(Из серии «Фильмы, которые не вышли на большой экран».)Далее рассмотрим так называемое преобразование Лежандра (илиЛежандра—Фенхеля, или, в контексте больших уклонений, Лежандра—Крамера):Λ∗ (x) = max [ x − Λ ( ),zzПредположим теперь, что Z принимает как положительные,так и отP zрицательные значения, так что сумма Ee Z =e P (Z = z) включаетzEezСм.
рис. 1.43.Однако для x < z− и x > z+ такой точки ∗ не существует, и для такихx положим Λ∗ (x) = +∞. При x = z− и x = z+ прямыми вычислениямиполучаем, что Λ∗ (z±) = − ln P (Z = z±). См. рис. 1.44.EeEZn e Z, n = 1, 2, ...)Ee Z=e 1 = z) = 1 Pe z P (Z = z) = 1 и E Ze n = 1 Pzn e z =P (Z1ZZPe z P (Z = z).Ee Z(При этомe 1 = z) =P (Ze 1 принимает те же значения, что и Z, но соЗдесь случайная величина Zвероятностями«взвешенными»(1.15.2)ZEZ2 e Z − (EZe Z) 2 ]e 2 − (E Ze 1) 2 = Var Ze 1 > 0.= EZ1(Ee Z) 2[Ee∈ R] = − ln(min [e− x Ee Z :∈ R]), x ∈ R.(1.15.3)Смысл этой операции состоит в том, что значение Λ ∗ (x) достигается в точке∗= ∗ (x), в которой Λ0 ( ∗) = x; в нашей ситуации Z принимает конечноечисло значений, как отрицательных, так и положительных, такая точкасуществует и единственна для z− 6 x 6 z+ (мы будем считать, что∗(z±) = ±∞) иΛ∗ (x) = ∗ x − Λ ( ∗).Вторую производную удобно записать в виде дисперсии:ZEZ2 e Z − (EZe Z) 2 ].(Ee Z) 2d2[EeΛ( ) =d 2dEZe ZΛ( ) =,dEe ZЭто опять выпуклая функция от ; самый простой способ понять этосостоит в следующем.
Рассмотрим производные14 Ср.с названием фильма «Dracula’s Bloody Teeths».162Глава 1. Цепи Маркова с дискретным временем§ 1.15. Большие уклонения для цепей Маркова с дискретным временем163− ( + a) :∈ R достигается в точкеПри a > 0 минимум поnYnh1ln EeP (Yn > n + na) 6 exp n minВ действительности, это просто неравенство Маркова для с.в. e U : P (U >> b) = P (e U > e b) 6 Ee U e b . Заменив U на Yn и минимизируя по> 0, получаем>0i.> 0. Отсюда следует,n→∞1ln P (Yn > n( + a)) 6 −Λ∗ ( + a).n(1.15.6)lim supРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
