Цепи Маркова (1121219), страница 11
Текст из файла (страница 11)
а) См. рис. 1.22. Если ki = E i T и hi = P i (XT YT = 0),то с учетом первого шага в силу марковского свойства и симметрии мыполучаемk (0,0) = 1 + k (−1,0) ,h (0,0) = h (−1,0) ,k (0,0)k (−1,−1)+,42h (0,0)h (−1,−1)1= ++,442k (−1,0) = 1 +h (−1,0)k (−1,1) = 1 +h (−1,−1)k (−1,0),2h (−1,0)=.2§ 1.6. Возвратность и невозвратность: случайные блуждания на кубических решеткахТогдаE i (Vi) =∞XP (Vi > k) =k>1С другой стороны,E i Vi = E i∞X∞Xfik .k=01(Xn = i) =n=0∞X(n)pii .n=0Следовательно, fi = 1 тогда и только тогда, когда∞Pn=0(n)pii = ∞.Пусть теперь (Xn) — это простое симметричное случайное блуждание в Z2 .
Оно неприводимо, следовательно, достаточно проверить, что∞P(n)pii = ∞ для одного состояния i ∈ Z2 , скажем начала координат (0, 0).n=0Обозначим символом (Xn±) проекцию (Xn) на диагональ {x = ±y} в Z2 .Тогда (Xn±) — это независимые простые симметричные случайные блуж12дания на √ Z, и возвращение в (0, 0) цепи (Xn) означает одновременноевозвращение в 0 для каждой из цепей (Xn±).
Далее,±P 0 (X2k= 0) = Ck2kи1,22k(2k)+−p00= P 0 (X2k= 0) P 0 (X2k= 0).(2k)Формула Стирлинга задает для p00 приближение √2 (2k) 2k 1 21≈ √= , при k → ∞.2k2k2 k k92ET = k (0,0) = ,Следовательно,12h (0,0) = .В силу симметрии,∞Xn=01418P (XT = 2 и YT = 0) = h (0,0) = .б) Состояние i возвратно, если fi = P (Ti < ∞) = 1, где Ti = inf{n > 1 :Xn = i}. Если Vi — это суммарное (общее) время, проведенное в состоянии i, то P i (Vi > k + 1) равноP i (Vi > k) P i (Vi > k + 1|Vk > k) = P i (Vi > k)fi = . . .
= fik+1 .2(n)p00=Рис. 1.22Следовательно,67∞Xk=0k(2k)p00= ∞.Pi(n)i pij= ( Pn) j , вектор= ( i) являетсяинвариантным вектором матрицы P (т. е. собственным вектором, соответствующим собственному значению 1): P = .Обозначим стационарное распределение= ( i) и будем подразумевать выполнение равенства P = без дополнительных напоминаний.Конечно, вектор удовлетворяет еще двум дополнительным условиям: а)он лежит в Pнеотрицательном ортанте ( i > 0 ∀ i ∈ I) и б) он лежит в гиперплоскостиi = 1. Если условие б) не выполняется, будем использоватьiб) если =антным.1 0+,=> 0, то матрица имеет единственное инвариантное+Тогда: а) еслираспределение1−обозначение вместо и назовем инвариантной мерой: = ( i), P = ,i > 0 для любого состояния i.Следует различать два уравнения: P = (уравнение инвариантности)и Ph = h (уравнение времени достижения).Пример 1.7.2. Рассмотрим (2 × 2)-матрицу перехода1−.P=+,= 0, то P = 0 1 и любой вектор (x, y) является инвари-= n(b − (N − n)).Cin Cb(N−i),CNa+bi = 0, 1, .
. . , N.Инвариантное распределение может оказаться не единственным, еслицепь имеет более чем один замкнутый сообщающийся класс. Она можетиметь стационарные распределения, заданные на разных замкнутых классах; см. рис. 1.8.Стационарное распределение не может быть задано на открытом сообщающемся классе, поскольку i всегда равно нулю для состояний i,принадлежащих открытым классам.Неединственность инвариантного распределения возникает тольков случае, когда число замкнутых сообщающихся классов превышает 1,так как неприводимая матрица имеет не более одного стационарногораспределения (т. е.
либо одно, либо ни одного). Конечная неприводимаяматрица P всегда имеет единственное стационарное распределение.Если матрица P является (счетной) неприводимой и невозвратной, тодля нее не существует инвариантного распределения.Если матрица P неприводима и возвратна, то возможны два случая:1. Матрица P имеет (единственное) стационарное распределение . Тогда все вероятности i положительны. В этом случае говорят, что матрицаP положительно возвратна (имеет положительную возвратность).2.
Для P не существует стационарного распределения. В этом случаеговорят, что P имеет нулевую возвратность.Более точно, каждая неприводимая возвратная матрица P имеет инвариантную меру , для которой P = и все компоненты i положительны.Однако сумма компонент может быть как конечной, так и бесконечной,и в определении 1.7.6 мы будем разделять эти случаи:XiXiПоскольку P (Xn = j) =(1.7.1)∀ j ∈ I.n= P (X0 = j) = P (X1 = j) = .
. . = P (Xn = j) = . . .=jiПусть (Xn) — это ц.м.д.в. с матрицей вероятностей перехода P.Определение 1.7.1. Начальное распределение вероятностей называется инвариантным (или стационарным), если оно сохраняется во времени.Это означает, что= (N − n) (a − n),Проверьте, что инвариантное распределение является гипергеометрическим.i< ∞ : P имеет положительную возвратность,i= ∞ : P имеет нулевую возвратность.Марк Аврелий Антоний (121–180), римский императорnВремя — это река событий, и сильно ее течение;чуть что-то показалось на горизонте, оно уже унесено течением,и ему на место приходит что-то другое, которое тоже пройдет.69Пример 1.7.3.
Пусть a, b > N, a, b, N ∈ Z. Рассмотрим м.ц.д.в.с состояниями n = 0, 1, . . . , N и переходами в соседние состояния (т. е.рождением и гибелью) с вероятностями pn и qn = 1 − pn переходов в n + 1и n−1 из n, заданными соотношениями pn = n / ( n + n), qn = n / ( n + n),где§ 1.7. Инвариантные распределения:определения и основные факты. Положительнаяи нулевая возвратность. I§ 1.7. Инвариантные распределения. Положительная и нулевая возвратность. IГлава 1.
Цепи Маркова с дискретным временем68инвариантным, т. е. k = k P, тогда и только тогда, когда состояние k возвратно.3. Если матрица P неприводима и возвратна, то710<ki< ∞ ∀ i, k ∈ I.Отметим одну из особенностей. Решения уравнения P = при сложении и умножении на постоянную вновь являются решениями: ( 1 + 2)P == 1 P +. 2 P и (c )P = c( P). Следовательно, можно выполнить нормиPPровку ij = i , чтобы получить равенствоj = 1 (при условии,jjPчтоj < ∞). Мы видим, что для неприводимой цепи все инвариантные§ 1.7.
Инвариантные распределения. Положительная и нулевая возвратность. IГлава 1. Цепи Маркова с дискретным временем70иP k (Tk > m − 1, Xm−1 = i)pik = P k (Tk = m, Xm−1 = i).1(Xn = i) =E k (ожидаемое число попаданий в i до возвращения в k),=если i 6= k (для 1 6 n < Tk),если i = k (начиная с n = 0).1,Тогда при j 6= k имеем(1.7.2)kjX= Ek1(Xn = j) =06n6Tk −1== 1 + E k (Tk − 1) = E k Tk .( P) k :=Xki pik61=kиXkk(субинвариантность).(1.7.6)X26n<∞ i : i6=kkk pkj+2. Соотношение ( k P) k = 1 выполняется тогда и только тогда,когда состояние k возвратно. Следовательно, вектор k являетсяXXE k 1(Tk > n, Xn = i)pij = ( k P) j .i : i6=k 16n<∞Далее, при i = k имеем( k P) k =Xki pik=kk pkki∈I= pkk ++XXi : i6=ki : i6=ki∈IP k (Tk > n − 1, Xn−1 = i, Xn = j),P k (Tk > n − 1, Xn−1 = i)pij ==i∈IXXа это выражение в силу соотношения (1.7.7) равно(1.7.4)Теорема 1.7.4.
1. Для любого состояния k выполняются соотношенияXkk( k P) j :=(инвариантность),(1.7.5)i pij = j , j 6= kP k (Xn = j, Tk > n) =26n<∞ i : i6=kpkj +E k (число посещений i до возвращения в k) =i∈I : i6=ki∈I= pkj +=1+X= ( ki , i ∈ I), зависящие отX16n<∞kiXkE k 1(Xn = j, Tk > n) =16n<∞Здесь, как и в соотношении (1.5.4), Tk есть время возвращения в состояние k:Tk = inf [n > 1 : Xn = k] .(1.7.3)Тогда 0 6 ki 6 ∞. Рассмотрим векторыпараметра k ∈ I.
Заметим, чтоX(1.7.8)n=0EkTXk −1= EkP k (Tk > m − 1, Xm−1 = i)pij = P k (Tk > m − 1, Xm−1 = i, Xm = j) (1.7.7)kiСледовательно, для неприводимой и возвратной матрицы P вектор k является «истинно» инвариантным вектором со строгоположительными и конечными компонентами.Д о к а з а т е л ь с т в о. 1. В силу марковского свойства для любогоm > 2 и состояний i 6= k и j 6= k выполняются соотношениямерыпропорциональны друг другу:= c . В частности, для всехинвариантных мер все i положительны для любого i ∈ I.Перейдем к доказательствам приведенных выше утверждений. Ключевым утверждением, которое позволяет доказать вышеперечисленныесвойства, является теорема 1.7.4. Положим0jki pikX=1(Xn = i) pik =16n<R (k)= pkk +XXi : i6=k 16n<∞E k 1(Tk > n, Xn = i)pik ,Глава 1.
Цепи Маркова с дискретным временема это выражение в силу (1.7.8) равноX XXP k (Tk = n + 1, Xn = i) = pkk +P k (Tk = n) =pkk +k (m)l plk>k (n)i pik ,т. е.6(n)i6=kpki pij + . . . +pki pij +Xi1 ,...in−1 6=k= pkj +i6=kXX=k,(1.7.9)i, k ∈ I.Заключаем теперь, что для неприводимой возвратной цепи возможныдва случая: а) все ненулевые инвариантные меры таковы, чтоX(1.7.10)i < ∞,i6=k l6=kpki1 . .
. pin−1 j += ... =Xl,i1 ,...,in−1 6=kи б) все ненулевые инвариантные меры таковы, чтоXi = ∞.ll pli piji∈I= 1 сле-(1.7.11)i∈Ii : i6=kXkД о к а з а т е л ь с т в о. 1) Из инвариантности и равенствадует, что для любых j ∈ I и n > 1 выполняется равенствоXXXXj =i pij = 1 · pkj +i pij = pkj +l pli pij =i(i)∀ i ∈ I;kiki2) для неприводимой и возвратной матрицы P выполнено равенствоki = i ∀ i ∈ I.i6=kОтсюда следует, что все ненулевые инвариантные меры связаны отношением пропорциональности 0 = c и все их компоненты конечны и строгоположительны. В частности, все векторы k пропорциональны:>i1)= pkj +.Теорема 1.7.5. Предположим, что = ( i) — инвариантная мера:P = и i > 0 ∀ i ∈ I. Дополнительно предположим, что k = 1 длянекоторого состояния k.
ТогдаX1piklkiX=kk1=С другой стороны,получаем, что e i = 0. Следовательно, e = 0 и = k .Мы видим, что для неприводимой возвратной цепи условие k = 1определяет все ее поведение. Более точно, если — ненулевая инвариантная мера, т. е. P = , i > 0 и k > 0 для некоторого состояния k,то= k k.llОтметим, что в вышеприведенных рассуждениях возвратность не использовалась.2. Из последнего соотношения следует, что ( k P) k = 1 тогда и толькотогда, когда fk = 1, т.