Цепи Маркова (1121219), страница 27

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

1.431что ln P (Yn > n( + a)) 6 −Λ∗ ( + a), и, таким образом,nЧтобы завершить доказательство соотношения (1.15.4), проверим теперь противоположное неравенство:n→∞1ln P (Yn > n( + a)) > −Λ∗ ( + a).n(1.15.7)lim infДля этого потребуются некоторые аналитические рассуждения.В курсе алгебры равенство A = B, как правило, тривиально.В курсе анализа оно есть следствие двух противоположных неравенств,одно из которых обычно простое, а второе требует больших усилий.Рис.

1.44(Из серии «Так говорил суперлектор».)Во-первых, отметим, что для заданного x ∈ R преобразование Лежанд∗∗ра Λ∗ (x) равно − ln Ee (Z−x) = ∗ x − ln Ee Z , максимум достигается при∗e 1, Ze2, . . .(= ∗ (x)); см. рис. 1.43. Далее, перейдем к н.о.р. копиям Zeвзвешенных с.в.

Z, для которыхВ частности, при + a > z+ , т. е. при a > z+ − , вероятность P (Yn >> n( + a)) стремится к нулю для любых n и предел в формуле (1.15.4)равен −∞, что согласуется с принятыми выше предположениями. Аналоn→∞1ln P (Yn < n( − a)) равен Λ∗ ( − a).nгично предел limи запишемВсюду далее будем предполагать, что 0 < a < z+ − .

Доказательстворавенства (1.15.4) состоит в проверке выполнения двух противоположныхнеравенств. Одно из них проверяется просто при помощи неравенстваЧернова: для любых случайных величин U со значениями в R с конечнойп.ф.м. Ee U и любых > 0(1.15.4)1EeebP (U > b) 6U.(1.15.5)P (Yn > nx) =e i = z) = P (Ze = z) = eP (ZX∗zP (Z = z) Ee∗Z1(z1 + . . .

+ zn > nx) P (Z1 = z1) . . . P (Zn = zn) =z1 ,...,zn= (Ee∗Z n)Xz1 ,...,znТеперь, если x,1ln P (Yn > n( + a)) = −Λ∗ ( + a).nlimn→∞Как мы увидим, для любого a > 0 вероятность P (Yn > n( + a))экспоненциально убывает с показателем степени Λ ∗ ( + a):∗1(z1 + . . . + zn > nx)e−∗(z1 +...+zn)nYi=1e i = zi).P (Z> 0, то для любого заданного ε > 0 правая часть не164Глава 1.

Цепи Маркова с дискретным временем)z1 ,...,zn>e−n∗nX1 nx(1 + ε) >zi > nx e−x(1+ε)(z1 +...+zn)i=1∗(EeXZ n)1 nx(1 + ε) >z1 ,...,zn= e −n∗∗x(1+ε)∗(Eei=1nXzi > nxi=1e i = zi) >P (ZYni=1e i = zi) =P (Ze1 + . . . + Ze n > nx).) P (nx(1 + ε) > ZZ nЗаметим, чтоnYZe − x) = 1 ∗ E (Z − x)eE (ZEe Z∗В самом деле,d=(1.15.9)√ e + ... + Ze n − nxZεx n√6,P 0< 1eа эта величина в силу центральной предельной теоремы стремится кZ ∞211√e−y /2 dy = .220nПереходя к пределу при ε → 0, получаем11lim inf ln P Yn > x > − ∗ x + ln Een→∞n∗Zn.∗ZZ= 1 − p + pe(1.15.12)и Λ ( ) = ln(1 − p + pe ).Мы знаем, что для вычисления преобразования Лежандра необходиморешить уравнение x = Λ0 ( ∗) и вычислить x ∗ − Λ ( ∗) и что этот методвычисления работает, когда 0 6 x 6 1; здесь.nEen→∞(1.15.11)В качестве примера опять предположим, что с.в.

Z i принимают конечное число значений, и рассмотрим множество F, представляющее собой[z+ , +∞), где z+ — максимальное значение, достигаемое величинами Z i .Тогда P (Yn ∈ F) = P (Z1 = . . . = Zn = z+) = (P (Z = z+)) n и предел в левойчасти неравенства (1.15.11) равен ln P (Z = z+), что совпадает с Λ∗ (z+);см. рис. 1.44.Пример 1.15.2. Более конкретно, предположим, что Z принимает значение 0 с вероятностью q = 1 − p и значение 1 с вероятностью p. Тогда∗> 0, то для любого ε > 0,11lim inf ln P Yn > x > − ∗ x(1 + ε) + ln EeСледовательно, если x,6 − inf [Λ∗ (x) : x ∈ F] ,1Ynln P∈ G > − inf [Λ∗ (x) : x ∈ G] .nn→∞ nlim infтак как ∗ есть точка максимума для ln Ee Z − x.Далее, вероятность в правой части соотношения (1.15.8) равнаe nа для любых открытых множеств G ⊂ R выполняется неравенство= 0,∗1Ynln P∈Fnn→∞ nlim supe = x.= 0, т.

е. E Z(Z−x) e − x) = d EeE (Z(1.15.8)i=1Теорема 1.15.1. Для любых замкнутых множеств F ⊂ R выполняется неравенство(1.15.10)= lnx(1 − p)x1−xи Λ∗ = x ln + (1 − x) ln.(1 − x)pp1−p(1.15.13)Теперь из условий x > 0 и ∗ > 0 следует, что x > = EZ. Значит, можновзять x = + a, где 0 < a < z+ − , и неравенство (1.15.7) следует изнеравенства (1.15.10).В общем случае методология больших уклонений пригодна для рассмотрения замкнутых и открытых множеств. Здесь следует быть внимательным, поскольку преобразование Лежандра Λ ∗ ( ), как мы видели, не∗XZ n∗является непрерывным по ∈ R (оно может стремиться к +∞).

Тем неменее, Λ∗ является выпуклой и полунепрерывной снизу функцией, т. е.Λ∗ (qx1 + (1 − q)x2) 6 qΛ∗ (x1) + (1 − q) Λ∗ (x2) ∀ x1 , x2 ∈ R и 0 < q << 1 и если xn → x, то Λ∗ (x) > lim sup Λ∗ (xn). Аппарат теории большихуклонений всегда учитывает это свойство. Основополагающая теорема дляnPZi н.о.р.с.в. Z1 , Z2 , . . . часто называется теоремой Крамера.суммы Yn =(Ee165менее следующей величины:§ 1.15. Большие уклонения для цепей Маркова с дискретным временемДля x < 0 и x > 1 мы имеем Λ∗ (x) = +∞. Выражение (1.15.13) фигурировало в томе I (с. 83). Это относительная энтропия двухточечноговероятностного распределения (1 − p, p) на множестве {0, 1} относительнораспределения (1 − x, x); ясно, что Λ∗ (p) = 0.

Таким образом, для суммыnPZi н.о.р.с.в. Zi ∼ Z теорема Крамера утверждает следующее:Yn =i=1Глава 1. Цепи Маркова с дискретным временемчения zk , откуда можно восстановить исходную сумму: Yn =Eek=1k Zk,= ( 1, . . . ,!= E explXh ,ZiРассмотрим теперь совместную п.ф.м.l),nPlPi=1 k=1zk Ui,k .−;221 x−222=1 (x − ) 2.222x−=x−−2∗(1.15.16)Это бесконечно дифференцируемая при всех x ∈ R функция, строго возрастающая при x > и строго убывающая при x < с минимумом в точкеx = , равной среднему значению с.в.

Z.nPТогда в силу теоремы Крамера для суммы Yn =Zi гауссовскихi=12) и для любого замкнутого подмножества F ⊂ ( , ∞)н.о.р.с.в. Zi ∼N( ,можно записать11ln P Yn ∈ Fnnn→∞lim sup6−(x∗− − ) 2,2 2где x∗− — это левая крайняя точка множества F: x∗− = min [x : x ∈ F] .Аналогично для любого открытого множества G ⊂ ( , ∞) справедливонеравенство1(y∗ − ) 21lim inf ln P Yn ∈ G > − + 2 ,i=1x−, т. е.где н.о.р.с.в. Zi ∼ Z, где Z принимает конечное число (различных) значений, скажем z1 , . .

. , zl с вероятностями p1 , . . . , pl . На самом деле удобнееработать с l-мерными векторами Ui ∼ U. Здесь Ui = (Ui,1 , . . . , Ui,l) и U == (U1 , . . . , Ul), где Uk = 1, если Z = zk , и Uk = 0, если Z 6= zk ,и аналогично, Ui,k = 1, если Zi = zk , и Ui,k = 0, если Zi 6= zk . ТогдаnPсумма векторов Yn =Ui подсчитывает число появлений каждого зна-− Λ ( ∗) = x∗ 2i=1Zi ,∗+n→∞nn2Эти рассуждения можно распространить на случай суммы Y n =Λ∗ (x) = x(1.15.14)nPx = Λ0 ( ∗) =,p < x 6 1.Для вычисления преобразования Лежандра Λ (x) выпишем равенства1n max [x, 1 − x]i1−pp1+O2∗12 nx(1 − x)P (Yn > nx) = p x nx 1 − x −n(1−x) h2Точные вычисления, основанные на формуле Стирлинга, приводят к оценке1−pЗдесь Sl обозначает l-мерный симплекс стохастических векторов: Sl == {x : xj > 0, x1 + . .

. + xl = 1}. Утверждение теоремы Крамера полностьюсохраняется и приводит к векторным аналогам «скалярных» формул.Пример 1.15.3. Рассмотрим п.ф.м. гауссовской с.в. Z ∼ N( , 2):11+ 2 2 , Λ ( ) = ln Ee Z =+ 2 2.Ee Z = exp∗если G ⊆ (−∞, −1] ∪ [1, +∞),если a = infx∈G x ∈ (p, 1] ,если a = supx∈G x ∈ [0, p),если G 3 p.Аналог формулы (1.15.13) определяет относительную энтропию вероятностного распределения (pj) относительноP «контрольного» вероятностногораспределения (xj), где xj > 0 иj xj = 1. Точнее, преобразование∗Лежандра Λ будет функцией вектора x ∈ Sl :lX x ln xj , x ∈ Sl ,jpjΛ∗ (x) = j=1(1.15.15)+∞,llx∈R \S.G⊂RΛ∗ (x) = sup [h , xi − Λ ( )] .Для F = [x, ∞) и G = (x, ∞), где p < x 6 1, в силу непрерывности Λ на[0, 1] получим x nx 1 − x −n(1−x)exp(o(n max [x, 1 − x])), p < x 6 1.P (Yn > nx) =p167и ее логарифм Λ ( ) = ln Eeh ,Zi . Аналогично случаю «скалярного» преобразования Лежандра можно ввести его векторный вариант:а) для любых замкнутых множеств F ⊂ R= −∞,если F ⊆ (−∞, −1) ∪ (1, +∞),6 −Λ∗ (a), если a = min1x∈F x ∈ (p, 1] ,lim ln P (Yn ∈ F)∗nn→∞6 −Λ (a), если a = maxx∈F x ∈ [0, p),6 0,если F 3 p,б) для любых открытых множеств> −∞,> −Λ∗ (a),1lim ln P (Yn ∈ G)n→∞ n> −Λ∗ (a),0,§ 1.15.

Большие уклонения для цепей Маркова с дискретным временем166P (Yn > n( + a)) = P (Yn > n( + a)) ≈ e−na22/2.Ee=∗=x−,x−Λ ( ) = ln EeΛ∗ (x) =xZx= ln−,,< .Λ∗ (0+) = +∞− 1 − ln ,(1.15.19)ZПри x > 0 получаем2Действительно, при Yn ∼ N(n , n ) непосредственное вычисление даетZ ∞h 1 i222211P (Yn > n( +a)) = √e−x /2 dx = √1+O √e−na /2 .√169Пример 1.15.5. Для показательной с.в. Z ∼ Exp( ) имеемгде y∗+ — это правая крайняя точка множества R \ G: y∗− = max [x : x 6∈ G] .Для F = [ + a, ∞) и G = ( + a, ∞) получаем x∗− = y∗+ = + a, откудаследует, что§ 1.15. Большие уклонения для цепей Маркова с дискретным временемГлава 1. Цепи Маркова с дискретным временем168= exp [ (e − 1)] , Λ ( ) = ln EeZ= (e − 1).Как и ранее, для заданного x нужно найти такое ∗ , что x = Λ0 ( ∗); так какΛ возрастает по , значение x должно быть положительным.

Характеристики

Список файлов лекций