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

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

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

Рассмотрим уравнения инвариантности11,,0 =1 = 0+2 12 211+ i+1 , i > 2.i =2 i− 12§ 1.9. Сходимость к положению равновесия.Предельные пропорцииВремя есть образ вечности.Лаэрт Диоген (II в. н. э.), греческий писательУравнение во второй строке имеет общее решение вида i = A + Bi, i > 1.Из первой строки находим B = 0 и 0 = A/2.

Следовательно, любаяинвариантная мера имеет вид1= A, i > 1,0 = A,2Pгде A > 0. Для этой мерыi = ∞, за исключением случая, когда A = 0.iСходимость к положению равновесия означает, что с течением времениц.м.д.в. «забывает» свое начальное распределение . В частности, если == (i) , мера Дирака, сосредоточенная в состоянии i, ц.м.д.в. «забывает»о начальном состоянии i. Очевидно, такое поведение цепи связано сосвойствами n-кратной матрицы перехода P n при n → ∞.

Рассмотримсначала случай конечной цепи.Теорема 1.9.1. Предположим, что (m × m)-матрица перехода Pnпоэлементно сходится к предельной матрице Π = ( ij)i(n)lim pij =n→∞(i)Тогда а) каждая строкапределениеij(i)Далее, в силу строго марковского свойстваP 0 (N = n) = P 0 (N > 1) ×× P 1 (достичь 0 без возвращений в 1) =P=матрицы Π задает инвариантное рас(i)илиij=Xil plj .l(1)б) Если матрица P неприводима, то все ее строки= .

. . = (m) = . В этом случаеlim P (Xn = j) =1.2n(1.9.1)∀ i, j ∈ I.Таким образом, стационарное распределение не существует и цепь (W n)имеет нулевую возвратность.Следовательно, для ц.м.д.в. (Wn) выполняется равенствоi, k > 1 или i = k = 0,1,ik=== 0, k > 1,12,i/ik2,i > 1, k = 0.× (P 1 (возвращение в 1 без прохождения цепи через 0)) n−1 ×12n→∞(i)jдля любого j ∈ I и любого начального распределения .совпадают:88Глава 1. Цепи Маркова с дискретным временем§ 1.9. Сходимость к положению равновесия.

Предельные пропорции89Д о к а з а т е л ь с т в о. а) Для любого состояния j можно записать((i)XP) j ==l∈IXil plj=(n)lim pil plj = limn→∞ln→∞Xl(n)(n+1)pil plj = lim pijn→∞=ij=((i)) j.(1.9.2)б) Если матрица P неприводима, то все строки (i) матрицы Π совпадают между собой, так как существует единственное инвариантное распределение.

А также,XX(n)(n)lim P (Xn = j) = lim(1.9.3)i pij =i lim pij = j .n→∞n→∞iin→∞Для счетной цепи в уравнении (1.9.2) следует обосновать возможностьменять порядок перехода к пределу и суммирования. Однако формула(1.9.3) остается верной и в общем случае, при условии, что нам известно,что матрица Pn сходится к матрице Π, у которой строки равны между собойи представляют собой инвариантное распределение .место?Итак, когда же эта сходимость P n → Π имеет Простой контр0 1пример, когда такая сходимость невозможна: P = 1 0 . Здесь 1 0 , n четно,0 1P n = 0 1 , n нечетно.1 0(1.9.4)Рис. 1.27Более того, если матрица P неприводима, то(n)pij > 0 для всех достаточно больших n ∀ i, j ∈ I.(1.9.6)Теорема 1.9.2.

Предположим, что матрица P неприводима, апериодична и положительно возвратна. ТогдаPn → Π при n → ∞.Элементы в столбцах матрицы Π постоянны. Иными словами,столбцы матрицы Π состоят из повторений одного и того жевектора , где — (единственное) стационарное распределениедля P. Следовательно, неприводимая, апериодическая и положительно возвратная цепь Маркова забывает свое начальное распределение:lim P (Xn = j) = j ∀ и j ∈ I.(i)Д о к а з а т е л ь с т в о. Рассмотрим две цепи Маркова: (X n ), заданную( )парой ( (i) , P), и цепь (Xn ), заданную парой ( , P).

Тогда0 1 0 ... 0(n)pij = P i (Xn(i) = j),0 0 1 . . . 0 P=,. . . . . . . . . . . .1 0 0 ... 0которая соответствует рис. 1.25.Тогда P2 отвечает рис. 1.26 и так далее, m-я степень Pm = I соответствует рис. 1.27.Рисунок затем повторяется по модулю m. Опять стационарное распределение единственно: = (1/m . . . , 1/m).Мы знаем, что в этих примерах матрица P периодическая. Напомним,что матрица P — апериодическая тогда и только тогда, когда(n)Рис.

1.26n→∞В общем случае рассмотрим (m × m)-матрицуpii > 0 для всех достаточно больших n ∀ i ∈ I.Рис. 1.25(1.9.5)j= P (Xn( ) = j).Чтобы оценить разность между этими вероятностями, мы определим их«общую часть», склеив эти две цепи Маркова, т. е. рассматривая их совместно. Одна из возможностей — рассмотреть их как одну цепь Маркова,состоящую из двух независимых компонент. Это означает, что мы рассматриваем цепь Маркова (Yn) на I × I, состояниями являются (k, l) гдеk, l ∈ I, переходные вероятности имеют видpY(k,l) (u,v) = pku plv , k, l, u, v ∈ I,а начальное распределениеP (Y0 = (k, l)) = 1(k = i) l ,k, l ∈ I.(1.9.7)Глава 1.

Цепи Маркова с дискретным временемОднако, лучший способ — рассмотреть цепь (Wn), вероятности переходакоторой равны(pku plv ,если k 6= l,(1.9.8)k, l, u, v ∈ I,pW(k,l) (u,v) =pku 1(u = v), если k = l,а начальное распределение такое же, как и вышеP (W0 = (k, l)) = 1(k = i) l ,k, l ∈ I.(1.9.9)В самом деле, уравнение (1.9.8) определяет матрицу вероятностей перехода на I × I: все ее элементы pW(k,l) (u,v) > 0 и суммы элементов по строкамравны 1. Проверим это:PP pku plv , если k 6= lXuv= 1.pWP(k,l) (u,v) = pku ,если k = lu,v∈I§ 1.9. Сходимость к положению равновесия.

Предельные пропорции(i)и|pij(n) −u∈IОбразно говоря, две компоненты цепи (Wn) по отдельности ведут себякак (Xn(i) ) и (Xn); рассматриваемые совместно, они эволюционируют какнезависимые компоненты (т. е. как в (Yn)) до того (случайного) моментавремени T, когда они совпадаютT = inf [n > 1 : Xn(i) = Xn ] ,6 P W (T > n) = P Y (T > n).(1.9.12)P Y (T (l,l) < ∞) = 1,гдеT (l,l) = inf [n > 0 : Xn(i) = Xn = l] .Так как T 6 T (l,l) , отсюда следует требуемое утверждение.В случае конечной неприводимой апериодической цепи можно доказать,(n)что скорость сходимости pij к j — геометрическая: см.

теорему 1.9.3.В действительности, если конечная ц.м.д.в. неприводима и апериодична,то существуют такие m > 1 и ∈ (0, 1), чтоv∈Ij|Эта оценка называется неравенством спаривания (склейки).Таким образом, достаточно проверить, что P Y (T > n) → 0, т. е. P (T << ∞) = 1. Но (Yn) является неприводимой положительно возвратнойцепью Маркова.

(Неприводимость следует из того факта, что исходнаяматрица P является неприводимой и апериодичной (см. уравнение (1.9.6)),а положительная возвратность следует из того факта, что (Y n) имеет инвариантное распределение ( × ) (k,l) = k l .) Следовательно, в силу теоремы1.5.9 ∀ состояний l ∈ I,uДалее, частичное («маргинальное») суммирование приводит к исходнымвероятностям перехода PXXpWpW(k,l) (u,v) = pku ,(k,l) (u,v) = plv .91так как события {Xn = j, T 6 n} и {Xn = j, T 6 n} совпадают. Следовательно,(n)pij − j = P (Xn(i) = j, T > n) − P (Xn = j, T > n)(m)pij >90для любых состояний i, j.(1.9.13)Теорема 1.9.3. Если P — конечная, неприводимая и апериодическая матрица, то для любых состояний i, j выполняется неравенство (n)(1.9.14)pij − j 6 (1 − ) n/m − 1 ,после которого они движутся синхронно.

Следовательно,= P W (Xn(i) = j) − P W (Xn = j).(1.9.10)P W (Xn = j) = P W (Xn = j, T 6 n) + P W (Xn = j, T > n),(1.9.11)иP W (Xn(i) = j, T 6 n) = P W (Xn = j, T 6 n),u∈IP W (Xn(i) = j) = P (Xn(i) = j, T 6 n) + P (Xn(i) = j, T > n)замечаем, что первое слагаемое в каждой сумме одно и то же:где m и такие, как в неравенстве (1.9.13).Д о к а з а т е л ь с т в о. Повторяем ту же схему доказательства, что и втеореме 1.4.2 мы должны оценить P Y (T > n).

Но для конечного случаяможно записатьX (m) (m)X (m)pku plu >plu = ,PW(k,l) (T 6 m) >Записавu∈Iт. е.PW(k,l) (T > m) 6 (1 − ) ∀ k, l ∈ I.j(n)pij −92Глава 1. Цепи Маркова с дискретным временемТогда в силу строго марковского свойстваhni P W (T > n) 6 P W T >m 6 P W (T > m) [n/m] ,mоткуда и следует утверждение теоремы.Поучительным является следующий пример.Пример 1.9.4. Рассмотрим колоду карт, пронумерованных 1, 2, . . . , 52.Процесс тасования карт происходит следующим образом: мы снимаемверхнюю карту и помещаем ее случайным образом равномерно на одну из52 возможных позиций, т.

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

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