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

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

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

. . , Xn−1 = in−1 , Xn = i) того,что состояние в момент n + 1 есть j, при условии, что заданы состоянияi0 ,. . . , in−1 и in = i в моменты времени 0, . . . , n − 1, n:P (Xn+1 = j | X0 = i0 , . . . , Xn−1 = in−1 , Xn = i) ==не пересекаются для различных i ∈ I и их объединение равно событию{состояние j в момент 1}.Теперь используем формулу (1.1.3) и напомним правила алгебры матриц:XXP (X0 = i, X1 = j) =i pij = ( P) j .i∈Iб) более общим образом, ∀ n и i0 , . .

. , in ∈ I вероятность P (X0 = i0 ,X1 = i1 , . . . , Xn = in) того, что система находится в состояниях i0 , i1 , . . .. . . , in в моменты времени 0, 1, . . . , n записывается как произведениеP (X0 = i0 , X1 = i1 , . . . , Xn = in) ={состояние i в момент 0, состояние j в момент 1}P (X0 = i0 , . . . , Xn−1 = in−1 , Xn = i, Xn+1 = j)=P (X0 = i0 , . . . , Xn−1 = in−1 , Xn = i)i pi i . . . pin−1 i pij= pij .= 0 01i0 pi0 i1 . .

. pin−1 i(1.1.4)i∈IПутем прямых вычислений эту формулу можно распространить на общие значения n:XP (X0 = i0 , . . . , Xn−1 = in−1 , Xn = j) =P (Xn = j) =Xi0 ,...,in−1n=(1.1.5)i0 pi0 i1 . . . pin−1 j = ( P ) j ,i0 ,...,in−1где P — n-я степень матрицы P. Таким образом, стохастический вектор,описывающий распределение величины Xn , можно получить, применивматрицу Pn к начальному стохастическому вектору .Затем аналогично предыдущемуXP (X0 = i0 , . . .

, Xn−1 = in−1 , Xn = i, Xn+1 = j) =P (Xn = i, Xn+1 = j) =i0 ,...,in−1Xn=i0 pi0 i1 . . . pin−1 i pij = ( P ) i pij ,ni0 ,...,in−116Глава 1. Цепи Маркова с дискретным временемоткуда следует, что§ 1.1. Марковское свойство и немедленные следствия из негоОкончательно обобщает соотношение (1.1.3) формулаP (Xn+1 = j|Xn = i) =( Pn) i pijP (Xn = i, Xn+1 = j)== pij .P (Xn = i)( Pn) i(1.1.6)Иными словами, элемент pij равен условной вероятности того, что в следующий момент состояние будет j, если в данный момент оно есть i.Более того,XP (X0 = i, Xn = j) =P (X0 = i, X1 = i1 , .

. . , Xn−1 = in−1 , Xn = j) =Xi1 ,...,in−1n=i pii1 . . . pin−1 j = i (P ) iji1 ,...,in−1иP (Xn = j | X0 = i) =P (X0 = i, Xn = j)=P (X0 = i)i (Pni) ij= (Pn) ij .(1.1.7)Значит, элемент (Pn) ij матрицы Pn дает вероятность перехода за n шаговиз состояния i в состояние j. Иногда мы будем обозначать эту вероятность pij(n) .В общем случаеP (Xk1 = i1 , Xk2 = i2 , . . . , Xkn = in) == ( Pk1) i1 (Pk2 −k1) i1 i2 .

. . (Pkn −kn−1) in−1 in ,P (Xn+1 = j | X0 = i0 , . . . , Xn−1 = in−1 , Xn = i)и( Pk) i (Pn) ijP (Xk = i, Xk+n = j)== (Pn) ij .P (Xk+n = j | Xk = i) =P (Xk = i)( Pk) i(1.1.8)Как следствие, любая степень P n стохастической матрицы вновь стоP (n)pij = 1 ∀ i ∈ I. Конечно, этот факт можнохастическая матрица, т. е.j∈Iпроверить с помощью непосредственных вычислений:X (n)XXXpij =pii1 . . . pin−1 j =pii1 . .

.pin−1 j = 1,i1 ,...,in−1 ,ji1jPпоскольку на каждом шаге (начиная с) сумма равна единице в силуjсоотношений (1.1.2).Другое следствие состоит в том, что применяя к стохастическому вектору стохастическую матрицу (P или в общем случае P n), мы вновь получимстохастический вектор. Этот факт также подтверждается прямыми вычислениями с использованием (1.1.1):XXX XXn( Pn) j =(Pn) ij =i (P ) ij =ii = 1.ji,jij(1.1.9)верная для всех моментов 0 6 k1 < k2 < . . . < kn и состояний i1 , .

. . , in ∈ I.Наступило время подвести итоги наших изысканий. Предположим, что= ( i) — стохастический вектор и P = (pij) — матрица перехода на I.Случайное состояние Xn в момент n рассматривается как случайная величина со значениями I.Определение 1.1.3. Говорят, что последовательность случайных величин Xn со значениями в конечном или счетном множестве I образуетцепь Маркова с дискретным временем (ц.м.д.в.), или, коротко, цепьМаркова, с начальным распределением и матрицей перехода P, если∀ i0 , .

. . , in ∈ I совместное распределение P (X0 = i0 , . . . , Xn = in) задаетсяформулой (1.1.3). В этом случае мы говорим, что (X n) — цепь Марковас параметрами ( , P), или ( , P) — цепь Маркова.Теорема 1.1.4. Если (Xn) — цепь Маркова с параметрами ( , P), тоа) Условная вероятностьP (Xk = i, Xn+k = j) = ( Pk) i (Pn) ijj∈I17iравна условной вероятности P (Xn+1 = j | Xn = i) и совпадаетс pij . Эквивалентно, условное распределение Xn+1 при условии X0 == i0 , . . . , Xn−1 = in−1 , Xn = i не зависит от i0 , . .

. , in−1 и совпадаетс (pij , j ∈ I), т. е. с i-й строкой матрицы P.б) Вероятность P (Xn = i) того, что состояние в момент n есть i,равна ( Pn) i .(n)в) Элемент pij матрицы Pn совпадает с условной вероятностьюP (Xk+n = j | Xk = i), т. е. задает вероятность перехода из i в j за nшагов.г) Вероятность общего видаP (Xk1 = i1 , Xk2 = i2 , . . . , Xkn = in)задается формулой (1.1.9).Dial M for Markov 2(Из серии «Фильмы, которые не вышли на большой экран».)2 Ср.с названием фильма «Dial M for Murder»откуда с очевидностью следует, что+(1 −(n)++p00 =1,01000010............00.01. Элементы Pn можно найти с помощью непосредственного(n)(n−1)+ (1 − − )p00.(n−1)− ) + (1 − p00) ===(n−1)p00 (1(n−1)(1 − ) + p01(n−1)p00 = p00вычисления. Действительно, P n = Pn−1 P, откуда для элемента p00 получаем равенство(n)= 0.=.(n)0100 2 /3 1 /31 /3 0 2 /3P=(n).Ее собственные числа являются решениями характеристического уравнения:−10 2 /3 −1/3001 /32 /3 −=−3!=+432−49откуда получаем0= 1,1−1−> 0,Элемент p11 можно получить, меняя и местами, а элементы p01 и p10 —как дополнения до 1.Пример 1.1.8.

В общем случае для вычисления элементов P n можно использовать собственные числа и собственные векторы матрицы P.Рассмотрим пример с матрицей 3 × 3:!detВ этом случае любая степень P n вновь равна единичной матрице. Значит,в силу соотношения (1.1.4) мы получаем, P (Xn = i) = i , т. е. распределение случайной величины (с.в.) Xn такое же, как и у X0 . Другими словами,начальное распределение сохраняется во времени.1.1.7. Для ц.м.д.в.

с двумя состояниями матрица P равна Пример если++1= − ( − 1)9√1±i 3.± =62−13Следовательно, (Xn) — последовательность независимых одинаково распределенных (или, коротко, н.о.р.с.в.).Пример 1.1.6. Если P — диагональная матрица, то она должна совпадать с единичной матрицей, у которой строка с номером i задаетсястохастическим вектором i :еслиP (X0 = i0 , X1 = i1 , . . . , Xn = in) = P (X0 = i0) P (X1 = i1) . . . P (Xn = in).10I=00(n)− ) n,Таким образом,pi pj = p j .i∈Ii∈IX(n)pi pij =XP (Xn = j) = ( Pn) j =pl = 1.

Значит,l∈Iin−1− ) =1− ,A + B = 1, A + B(1 −Pi2− ) n,гдеблагодаря тому чтоi1(n)p00 = A + B(1 −i1 ,...,in−1(0)Это соотношение рекуррентно по n, с начальными значениями p 00 = 1(1)и p00= 1 − . Значит,Кроме того, в этом примере Pn = P, так какXXX Xpij(n) =pi1 . .

. pin−1 pj =pi 1pi 2 . . .pin−1 pj = pj ,19Пример 1.1.5. Предположим, что все строки матрицы P одинаковы,т. е. pij = pj не зависит от i. Предположим также, что j = pj , т. е.совпадает с любой строкой матрицы P. Тогда в силу соотношения (1.1.3)получаемP (X0 = i0 , X1 = i1 , . . . , Xn = in) = pi0 pi1 . .

. pin .§ 1.1. Марковское свойство и немедленные следствия из негоГлава 1. Цепи Маркова с дискретным временем18+19= 0,Поскольку все собственные числа различны, матрицу P можно диагонализовать: существует такая обратимая матрица D, что10√1+i 30D−1 PD = 600010√0 1+i 3 −10006√  , т. е. P = D √ D .1−i 31−i 30066Глава 1. Цепи Маркова с дискретным временем(1)и=A+B 1 + i√3 26+C633+ 1 n 3=3coscosn+3n± i sin33/3e±insinnn,3+19−√ 132+= ,223+√ 1 13+= 1,3 22где = A, = B + C и = i(B − C) должны быть действительными. Снова(n)они имеют видполучаем уравнения для n = 0, 1, 2; для p12= 0,0= 1,113= ,2(n)pij = A + B 1 n3= 0.+ C · 0n .Вновь используем три начальные условия, т. е. матрицы P 0 , P и P2 (как(n)обычно, считаем, что 00 = 1).

Например, p11 ищется из соотношений13A + B + C = 1,13A+ B= ,A+ 1 2313B= ,откуда получаем A = 1/3, B = 0, C = 2/3 и p11 ≡ 1/3, n > 1. Аналогично(n)(n)p12 = 1/3 − (1/3) n и p13 = 1/3 + (1/3) n . При n → ∞ все элементы первойnстроки матрицы P стремятся к 1/3 (что на самом деле верно для всехдевяти элементов матрицы Pn).Пример 1.1.10. Сделаем ряд предварительных замечаний. Во-первых,1 — собственное число любой стохастической матрицы P. Действительно,пусть I — единичная матрица, т. е.

элементы матрицы I равны ij , i, j ∈ I.Тогда а) det( I − P) = det( I − P) T = det( I − PT), т. е. собственные числаматрицы P и транспонированной матрицы P T совпадают; и б) 1 — всегдаявляется собственным числом матрицы P T : соответствующий собственный3 1 n =pij(n) =+и собственные числа равны(n) 1 nи363Затем получаем 1 ± i√3 n23(n)33Значит, элементы pij имеют простой вид2= .3Вычисления можно упростить, если избавиться от мнимых частей (по(n)скольку элементы pij матрицы Pn действительны и неотрицательны).С этой целью сперва заметим, что ± — комплексные сопряженные корни,и запишем√√1±i 31 1±i 311== e ±i / 3 =cos ± i sin.63√√1+i 31−i 3+C=166 1 − i√3 2.Теперь характеристическое уравнение имеет вид4 211− 3+−= − ( − 1) −=0(2)p121 /3 0 2 /31 /3 2 /3 01 /3 1 /3 1 /3P=(0)p12 = A + B + C = 0, p12 = A + B9√3.7=(n)= 3/7.В частности, lim p12n→∞Пример 1.1.9.

Рассмотрим другой пример матрицы, соответствующейсистеме с тремя состояниями:!Коэффициенты A, B и C могут быть комплексными; они меняются отэлемента к элементу, а найти их можно, подставляя n = 0, 1, 2. Еслиn = 0, то P0 = I — единичная матрица (точно так же, как для скаляровp0 = 1 для всех p (включая p = 0)); для n = 1 берем матрицу P и приn = 2 возводим ее в квадрат, чтобы получить P 2 . Например, предположим,что состояния системы — это 1, 2 и 3; в этом случае элементы имеют вид(n)(n)pij , i, j = 1, 2, 3. Тогда для p12 пишем:−3,76=и любой элемент матрицы Pn имеет вид суммы√ n√ n1+i 31−i 3A+B+C.37= ,0√0n1+i 300 −1Pn = D D ,6√n 1−i 3006621откуда следует, что1Тогда§ 1.1. Марковское свойство и немедленные следствия из него20618+916223−19с собственными числами0= 1,j∈I±=0√−1 ± 17=.12Отсюда получаем уравнениепоскольку матрица P стохастическая.Следовательно, характеристический многочлен стохастической матрицы делится на − 1; в случае размера 3 × 3 частное является квадратнымтрехчленом, значит, все собственные числа можно найти явно.Во-вторых, если + — комплексное собственное число матрицы P, тосопряженное комплексное число − = + также является собственнымзначением, поскольку только это дает возможность получить действительный характеристический многочлен как произведение линейных одночленов (имеется в виду произведение ( − +) ( − −) = 2 − ( + + −) + + −с действительными коэффициентами + + − и + − = | ± |2).

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

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