Цепи Маркова (1121219), страница 28
Текст из файла (страница 28)
Очевидно,(x 6 0,+∞x∗∗ ,x= lnи Λ (x) =(1.15.18)x > 0.x ln − 1 + ,Здесь Λ∗ (0+) =и Λ∗ ( ) = 0. Таким образом, вновь по теореме КрамераnXдля суммы Yn =Zi н.о.р.с.в. Zi ∼ Po( ) при x > получимexp (−n(x − )).j>nxj!e −n =[nx] +1(n )e−n +o(nx)([nx] + 1)!12 ([nx] + 1)=pP (Yn > nx) =n→∞1ln Eenhn,Un i,= ( 1, . . . ,d)∈ Rd , x − [nx] −1e−n(x−(1.15.20)конечный для в окрестности начала координат = 0 и непрерывно дифференцируемый по всюду, где он конечен.
Если, как и ранее,Λ∗ обозначает преобразование Лежандра)1+O 1 nxΛ∗ (x) = sup [h , xi − Λ ( ) :∈ R d , Λ ( ) < ∞] ,Как и выше, можно записать более точную аппроксимацию, воспользовавшись тем, что Yn ∼ Po(n ):X (n ) jΛ ( ) = lim x −nxP (Yn > nx) ≈Значение теоремы Крамера состоит в том, что она служит отправнойточкой для плодотворной теории, охватывающей множество различныхситуаций. Математическим основанием является так называемая теоремаГартнера—Эллиса. В удобной для наших приложений (хотя и не самойобщей) формулировке, эта теорема утверждает следующее.Теорема 1.15.6.
Рассмотрим произвольную последовательностьвекторных с.в. Un = (U1n , . . . , Udn). Предположим, что существуетпределi=1У. Шекспир (1546–1616), английский драматург и поэтZEe... that we should... transform ourselves into beasts. (Отелло)которое представляет собой одну из серии полезных оценок для гауссовских интегралов.Пример 1.15.4. Для пуассоновской с.в. Z ∼ Po( ) мы имеем(1.15.17)aaZi , где н.о.р.с.в.Zi ∼ Exp( ), теорема Крамера дает x nhxiexp − n− 1 + o(n) .P (Yn > nx) =a+anXi=1Последняя формула следует из двухстороннего неравенстваZ ∞2211−a 2 / 2e6e−x /2 dx 6 e−a /2 ,−1и Λ∗ (x) = +∞ при x 6 0.
Таким образом, для Yn =naa n2 na2 nто остаются справедливыми неравенства (1.15.11) и (1.15.12), гдеF — замкнутое, а G — открытое подмножества в Rd :.Здесь на последнем шаге использована формула Стирлинга. Отметим, чтосомножитель x−nx подавляет экспоненту.1ln P (Un ∈ F) 6 − inf [Λ∗ (x) : x ∈ F] ,nn→∞1lim inf ln P (Un ∈ G) > − inf [Λ∗ (x) : x ∈ G] .n→∞ nlim sup(1.15.21)(1.15.22)(0)порождаются векторами(0)1ϕ1(0)(0)lϕl(0) = ... и ϕ (0) = ...
со строгоположительными компонентами i(0) , ϕi(0) > 0, i = 1, . . . , l.Если существует такое s, что pij(s) > 0 для всех i, j = 1, . . . , l,то все остальные собственные значения p 6= 0 матриц R и RTудовлетворяют неравенству | p | 6 0 (1 − ), т. е. лежат внутри(0)(0)(ϕi ) −1 rij ϕj , i, j = 1, . . . , l.0(1.15.25)e будет состоятьТогда (единственное) стационарное распределение e для Pиз вероятностейei =1h(0) ,ϕ (0) i(0) (0)i ϕi ,i = 1, . .
. , l.(1.15.26)В нашем случае неприводимой и апериодической цепи Маркова (X n),имеющей состояния 1, . . . , l и матрицу вероятностей перехода P = (p ij),рассмотрим семейство матриц R следующего вида:R = (pij eh,f(j) i), i, j = 1, . . . , l.(1.15.27)f1 (j)Здесь для любых j = 1, . . . , l вектор f(j) = ... ∈ Rl — это дейfl (j)ствительнозначный вектор размерности l, таковым является и вектор .Ясно, что матрица (1.15.27) имеет неотрицательные элементы и являетсянеприводимой и апериодической. Обозначим, как и ранее, через 0 ( )максимальное собственное значение матриц R и RT ; мы знаем, что 0 ( ) == ||R || = ||RT || и кратность собственного значения 0 равна 1. Известнотакже, что 0 ( ) — бесконечно дифференцируемая по∈ Rl функция.дятся к стационарным вероятностям j (см. теорему 1.5.2).
Доказательствовпервые появилось в статье: Duffy K. , Metcalfe A. P. The large deviationsof estimating rate functions // J. Appl. Prob. 2005. V. 42. P. 267–274.Полезным утверждением является теорема Перрона —Фробениуса длянеотрицательных матриц. Эта теорема обобщает теорему 1.12.3 и состоитв следующем.Теорема 1.15.7. Пусть R — (l × l)-матрица с неотрицательнымиэлементами rij .Предположим, что для любых i, j = 1, . . . , l существует такоеs(= s(i, j)), что rij(s) > 0, где rij(s) — элемент с индексом (i, j)-матрицыRs — s-й степени матрицы R. Тогда норма ||R|| совпадает со спектральным радиусом (R) и всегда является собственным значениемматриц R и RT . Положим ||R|| = (R) = 0 .
При этом алгебраическаяи геометрическая размерности собственного значения 0 равны 1и соответствующие собственныеR и RT пространстваматриц1n i=0eij =pгде (Xn) — неприводимая и апериодическая ц.м.д.в. с конечным множеством состояний I = {0, . . . , l}. Иными словами, U jn — это время, проведенное цепью в состоянии j ∈ I, между моментами времени 1 и n. В общемслучае эта с.в. имеет распределение сложного вида, однако известно, что−11 nPвыполняются (слабый и сильный) з.б.ч.: Компоненты1(Xi = j) схо-и апериодической, если ∃ s такое, что rij(s) > 0 ∀ i, j.Существует элегантный метод превращения неприводимой и апериодической матрицы R = (rij) с неотрицательными элементами в стохастичеe = (peij) (также неприводимую и апериодическую): нужноскую матрицу Pпросто положить(1.15.23)1(Xi = j), j = 1, .
. . , l,i=11nЕстественно назвать матрицу R неприводимой, если она удовлетворяет(s)условию: ∀ i, j ∃ s = s(i, j) такое, что rij > 0, и назвать ее неприводимойUjn =nX171замкнутого круга радиуса 0 (1 − ) < 0 с центром в начале координат в комплексной плоскости C, где 0 > 0 — спектральная щель.x1..
∈ Rl выполняетсяКроме того, для любого вектора x =.равенствоxlTxT Rn = n0 hx, ϕ (0) i (0) + O((1 − ) n) .(1.15.24)Условие (1.15.20), очевидно, выполняется, когда U n = (Z1 + . . . + Zn) /n,где Z1 , Z2 , . . . — н.о.р. случайные векторы. В общем случае условие(1.15.20) нетривиально и вычисление функций Λ и Λ ∗ — сложная задача.Согласно общепринятой терминологии говорят, что последовательность(Un) удовлетворяет принципу больших уклонений (п.б.у.), если выполняются неравенства (1.15.21), (1.15.22). В этой ситуации Λ ∗ называетсяфункцией скорости больших уклонений.Проанализируем случай, когда случайный вектор U n имеет компоненты§ 1.15. Большие уклонения для цепей Маркова с дискретным временемГлава 1. Цепи Маркова с дискретным временем170Пусть опять(0) T(0) T=(0) T— соответствующая собственная вектор-строка(0) Tматрицы R и ϕ= ϕ — соответствующая собственная вектор-строка(0)(0)Tматрицы R , а элементы матриц положительны: j , ϕj > 0, j = 1, .
. . , l.172Глава 1. Цепи Маркова с дискретным временемЛемма 1.15.8. Рассмотрим неприводимую и апериодическуюц.м.д.в. (Xn) с состояниями 1, . . . , l и вектор-строкой начальных= ( (j)). Зафиксируем набор векторов f(j) ∈ Rl ,вероятностейj = 1, .
. . , l, и образуем случайные векторы f(Xn), n = 0, 1, . . . Тогдапоследовательность сумм1nf(Xi), n = 1, 2, . . . ,1ln E enhn,Vn i= ln0(),= ( 1, . . . ,l)∈ Rl(1.15.29)limудовлетворяет п.б.у. А именно, для любогосуществует пределn→∞(1.15.28)i=1Vn =nXи из теоремы Гартнера—Эллиса следует принцип больших уклонений (п.б.у.) для (Vn).
Здесь E обозначает математическое ожидание относительно распределения ц.м.д.в. (Xn) с вектор-строкойначальных вероятностей .Следовательно, функция скорости больших уклонений — этофункция0(x ∈ Rl ,)] ,Λ∗ (x) = sup [hx, i − ln∈Rl(1.15.30)независимо от выбора начального распределения .Д о к а з а т е л ь с т в о. Чтобы проверить равенство (1.15.29), запишем математическое ожидание E enh ,Vn i как сумму по всем значениямX0 , . . . , X n :E e nh,Vn i=X,f(j1) i(j0)pj0 j1 eh.
. . pjn−1 jn eh,f(jn) ij0 ,...,jn( (R ) n) j =j=10(n) h= ( Rn 1) ==lXT, ϕ (0) i(0) T+ O((1 − ) n) .(1.15.31)Последнее равенство в формуле (1.15.31) выполнено в силу теоремы1.15.7. Теперь остается взять логарифм и разделить на n, после чегополучим соотношение (1.15.29).В случае, когда j-я компонента вектора f(j) равна 1, а все остальныекомпоненты 0, задача вычисления Λ∗ (x) облегчается благодаря следующейлемме.§ 1.15.
Большие уклонения для цепей Маркова с дискретным временем173 0 .. . Лемма 1.15.9. Предположим, что у вектора f(j) = 1 j-я ком. .. 0понента равна 1, а все остальные — нули, j = 1, . . . , l. Тогда Λ∗ (x) = x1= +∞, если только вектор x = ... не таков, что x1 , . . . xl > 0xlи x1 + . . . + xl = 1. А если x удовлетворяет указанным условиям, то u1l u XjΛ∗ (x) = sup xj ln: u = ... , u1 , .
. . , ul > 0 . (1.15.32)Tj=1(u P) julЗдесь P — это матрица перехода ц.м.д.в. (Xn).Д о к а з а т е л ь с т в о. Рассмотрим вначале множество P l ⊂ Rl вектоlPxj = 1.ров x ∈ Rl , удовлетворяющих указанным условиям, т. е. x j > 0,j=1Такое множество есть (l − 1)-мерный симплекс вероятностных векторовв Rl . Его дополнение Rl \ Pl является открытым множеством. В силу леммы 1.15.8 можно использовать п.б.у.
для последовательности случайных V1nn1Xвекторов Vn = ... , где Vjn =1(Xi = j), j = 1, . . . l. ПолучаемnVlnlim infn→∞i=11ln P (Vn 6∈ Pl) > − inf Λ∗ (x) : x ∈ Rl \ Pl .n(1.15.33)Заметим, что для любого n вероятность в левой части неравенства (1.15.33)равна 0, так как Vn принимает значения только из Pl . Следовательно,логарифм в левой части равен −∞, а значит, и правая часть тоже равна−∞. Таким образом,inf Λ∗ (x) : x ∈ Rl \ Pl = +∞,т.
е. Λ∗ (x) ≡ +∞ на Rl \ Pl .Предположим теперь, что x ∈ Pl . Для начала проверим неравенство u1lXujΛ∗ (x) > sup xj ln: u = ... , u1 , . . . , ul > 0 . (1.15.34)Tj=1(u P) jul175Напомним, что ∀ x ∈ Rl значение Λ∗ (x) равно sup [hx, i− ln 0 ( ) : ∈ Rl ] ;см. (1.15.30). Следовательно, достаточно проверить, что для любых x,∈ Rl существует такая вектор-строка uT с положительными компонентами u1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
