Цепи Маркова (1121219), страница 12
Текст из файла (страница 12)
е. состояние k возвратно.3. Если матрица P неприводима, то для любых i, k ∈ I существуют(n)(m)такие m, n > 0, что pik > 0 и pki > 0. При условии, что матрица Pkявляется инвариантным и, следовательно, k Pm =возвратна, векторk nk= P = . Таким образом,X(m)kk (m)k (m)i =l pli > k pki = pki .а эта сумма стремится к kj при n → ∞.2) Пусть теперь матрица P неприводима и возвратна. Тогда k является− k тожеинвариантным вектором: k P = k . Значит, вектор e =инвариантен: e = e P, и в силу п. 1. он неотрицателен: e i > 0 ∀ i ∈ I,а при i = k вектор e k = k − kk = 1 − 1 = 0.(n)Далее, для заданного i ∈ I существует такое n > 1, что p ik > 0.
Тогда,посколькуX(n)(n)e l plk0 = ek => ei pik,kk.16n<∞P k (Tk = n) = P k (Tk < ∞) := fk 6 1 ==P k (X1 = j, Tk > 1) + P k (X2 = j, Tk > 2) + . . . + P k (Xn = j, Tk > n),26n<∞X73Теперь в силу неотрицательности последнее выражение ограничено снизувеличинойi : i6=k 16n<∞§ 1.7. Инвариантные распределения.
Положительная и нулевая возвратность. I72l pli1. . . pin−1 j .Определение 1.7.6. В случае а) говорят, что неприводимая цепь Маркова (или матрица P) положительно возвратна, а в случае б) — нульвозвратна.Если число состояний #I конечно, то случай б) невозможен. Следовательно, неприводимая конечная ц.м.д.в. всегда положительно возвратна74Глава 1. Цепи Маркова с дискретным временемположительны. Тогдаа) невозвратность: Pi (время возвращения Ti < ∞) < 1, т. e. Pi (Ti == ∞) > 0 ∀ i ∈ I. Или, что эквивалентно,kii=.Pi ((Xn) не посещала i после какого-то конечного момента времени) = 1kk, т. е.1=iiстационарному распределению, у которого всеможно восстановить, выполнив деление:k75и имеет (единственное) инвариантное распределение = ( i). Более того,стационарные вероятности i строго положительны.Теперь видно, что в общем. Pслучае, если матрица P положительновозвратна, то нормировка ji =j приводит к (единственному)§ 1.7.
Инвариантные распределения. Положительная и нулевая возвратность. I(1.7.12)k∞X{ i}(n)pii < ∞ ∀ i ∈ I, или, что эквивалентно, hj = Pj (попасть в i) < 1n=0для некоторых состояний j и i;б) возвратность: Pi (время возвращения Ti < ∞) = 1, т. e. Pi (Ti = ∞) == 0 ∀ i ∈ I. Или, что эквивалентно,Pi ((Xn) может попасть в i в бесконечно большие моменты времени) = 1Другими словами, нами получена следующая теорема.Теорема 1.7.7.
В неприводимой положительно возвратной цепидля любых состояний k 6= iсо стационарным распределениемвыполняется равенствои(1.7.13)и∞X{ i}(n)pii = ∞ ∀ i ∈ I, или, что эквивалентно, hj = Pj (попасть в i) = 1n=0для всех состояний j и i. В этом случае для любого i для вектора i = ( ij)из равенства (1.7.12) вытекает, что 0 < ij < ∞, и этот вектор задаетi.инвариантную меру для (Xt); все такие инвариантные меры имеют видki−1i= (bk) × вектор для любых состояний i, k.В частности, вектор3. Далее, для неприводимой возвратной ц.м.д.в. может выполнятьсяследующее:∀ i ∈ I;а) нулевая возвратность: mi = Ei (время возвращения Ti) = ∞ Pв этом случае не существует такой инвариантной меры = ( i), чтоj <,kоткуда следует, что mk = 1/ k .Мы завершим этот параграф подведением итогов по утверждениямотносительно возвратности и невозвратности, приведенным выше.1.
Для переходных вероятностей неприводимой ц.м.д.в. с более чем од(m)ним состоянием справедливы неравенства 0 < pij < 1 для всех состоянийi, j ∈ I, где m > 1 может зависеть от i и j (поглощение отсутствует).2. Неприводимая ц.м.д.в. (Xn) может быть невозвратной или возвратной:1и существует единственное стационарное распределение= Pi> 0; в этом случаеjk= m k , E i Ti =1k=j< ∞; следовательно, не существует стационарного распределения;б) положительная возвратность: mi < ∞ ∀ i ∈ I; в этом случаедляPлюбой инвариантной меры = ( i) справедливо неравенствоj < ∞j= ( i), гдеиijiiiXmk =Таким образом,i : i6=kД о к а з а т е л ь с т в о. Из уравнения (1.7.4) мы находим, чтоXXkkE k Tk = 1 + E k (Tk − 1) = 1 +i =i < ∞.Ei (время, проведенное в k до Ti) =k< ∞.(1.7.14)k1mk := E k Tk = среднее время возвращения в состояние k =Для случая i = k имеет место следующий результат.Теорема 1.7.8.
В неприводимой положительно возвратной цеписо стационарным распределением для любого состояния k выполняется равенство.kE k (число попаданий в i, прежде чем цепь вернется в k) =iдля любых состояний i, k.iКонечная неприводимая ц.м.д.в. всегда положительно возвратна.i=76Глава 1. Цепи Маркова с дискретным временем§ 1.8.
Положительная и нулевая возвратность. IIНе знать того, что было сделано в былые времена,означает навсегда остаться ребенком.Не извлекая никакой пользы из прошлого,человечество навсегда останется в младенчестве.§ 1.8. Положительная и нулевая возвратность. II77задают времена между (l − 1)-м и l-м моментами возвращения в состояниеi или продолжительность l-й экскурсии из состояния i, l = 1, 2, .
. .Очевидно, Ti(1) = Ti ; см. рис. 1.23.Марк Тулий Цицерон, (106–143 до н.э.), римский оратор и государственный деятельВ этом параграфе мы будем работать с начальным распределением= i , т. e. будем рассматривать цепи, стартующие из определенногосостояния, и использовать обозначения P i и E i . Предполагаем, что пространство состояний I счетно. Чтобы упростить формулы, будем опускатьиндекс I: утверждения типа «∀ i» означают ∀ i ∈ I. Мы также предполагаем, что переходная матрица P рассматриваемой ц.м.д.в.
(X n) неприводима.Начнем с повторения определений 1.5.1 и 1.7.6. Напомним, чтоTi = min[n > 1 : Xn = i]обозначает время возвращения в состояние i.Определение 1.8.1. Положим fi = P i (Ti < ∞) и mi = E i Ti . Состояние i называетсявозвратным (В),если fi = 1, илиPnpii(n)< ∞, илиP i (Xn = i для бесконечного числа n) = 1,положительновозвратным (ПВ),если mi = E i Ti < ∞,nP i (Xn = i для бесконечного числа n) = 0.(1.8.1)Эти свойства являются свойствами класса, и если переходная матрицаP неприводима, то все состояния ПВ, или НВ, или Н.Определение 1.8.2.
Для l = 0, 1, . . . определим последовательные(l)времена возвращения H (l) (= Hi ) в состояние i соотношениями H (0) == 0, H (1) = Ti(1) и(l−1)Hi = inf [n > HiРазностиTi(l)«Живите всегда в интересные времена возвращения».Из серии «Так говорил суперлектор».с нулевойвозвратностью (НВ), если mi = E i Ti = ∞, но fi = 1,P (n)pii < ∞, илиневозвратным (Н),если fi < 1, или(l)Рис.
1.23((l)(l−1)Hi − H i,=0,+ 1 : Xn = i] , l > 1.(l−1)если Hi< ∞,(l−1)= ∞,если Hi(1.8.2)(1.8.3)Анализ положительной и нулевой возвратности, проведенный выше,в сочетании со строго марковским свойством приводит к следующемурезультату.Теорема 1.8.3. Предположим, что цепь (Xn) возвратна, и пустьi — произвольное состояние. При заданном распределении P i случайные величины Ti(1) , Ti(2) , . . . н.о.р., принимают значения из Z+и конечны с вероятностью 1. Это означает, что при всех k > 1и t1 , . .
. tk ∈ Z+ выполняется равенствоXY(1)(k)P i (Ti = tl) иP i (Ti = t) = 1. (1.8.4)P i (Ti = t1 , . . . , Ti = tk) =16l6kt=1,2,...Далее, средние значения удовлетворяют условию1/ i , если цепь (Xn) положительно возвратна,mi := E i Ti = ∞,если цепь (Xn) имеет нулевую возвратностьили невозвратна.(1.8.5)(1.8.6)Мы не будем обсуждать доказательство теоремы 1.8.4; заинтересованный читатель может прочитать его в книгах [D] , [GS1] , [St1] .Пример 1.8.5. Случайные блуждания на Zd .a) Симметричное случайное блуждание «по ближайшим соседям».Мы уже знаем, что симметричное случайное блуждание «по ближайшимсоседям» на Zd (называемое также простым случайным блужданием)возвратно при d = 1 и d = 2 и невозвратно при d = 3.
Рассмотрим сначаласлучай d = 1. Уравнения инвариантности в этом случае принимают видi=11+ i+1 ,2 i− 12i ∈ Z,с точи, очевидно, имеют неотрицательное решение i ≡ 1 (единственноеPностью до положительного множителя). Поскольку сумма1 расходится,i∈Zто блуждание имеет нулевую возвратность.> 0 имеет компонентыСледовательно, любая инвариантная мера=const>0.Тогда∀i=6kikiСм. также пример 1.8.7 ниже. Кроме того,mk = E k (время возвращения в k) = ∞, k ∈ Z.При d = 2 уравнения инвариантности выглядят аналогично:1X( (i1 ±1,i2) + (i1 ,i2 ±1) ), i = (i1 , i2) ∈ Z2 ,(i1 ,i2) == E k (числа посещений состояния i, прежде чем цепь вернется в k) = 1.ki≡ 1.При d = 3 мера i ≡ 1 по-прежнему является инвариантной (чтов действительности верно вообще для всех d). Однако, поскольку блуждание невозвратно, векторы k являются субинвариантными, а не инваkриантными.
Следовательно, тождество i ≡ 1 уже не выполняется, хотяпо-прежнему mk ≡ ∞.б) Асимметричное случайное блуждание «по ближайшим соседям»на Z. Уравнения инвариантности в этом случае имеют вид= 1.2|k − i|l=12|k − i|i=pi−1+ (1 − p)i+1 ,i ∈ Z,где p 6= 1/2. Случайное блуждание невозвратно.
Общее неотрицательноерешение p ii =A+B1−pPзависит от двух параметров A, B > 0 и не удовлетворяет условиюi <i< ∞. Мы видим, что не все инвариантные мерыпропорциональны.В этом случае опять векторы k являются субинвариантными, а не инвариантными.
Кроме того, они ki уже не могут быть представлены в виде i / k ,где — некоторая инвариантная мера. Однако, как и прежде, m k ≡ ∞,посколькуPiP k (числа посещений состояния i, прежде чем цепь вернется в k, равно n) = 1 2 n−11=1−.и опять решением является i ≡ 1. Следовательно, блуждание имеетнулевую возвратность и, как и выше,стремится к математическому ожиданию mi (приведенному в соотношении (1.8.5)) при n → ∞.
Это означает, чтоn1 X (l)limTi = m in→∞ n(Это может показаться несколько удивительным, так как можно было быожидать, что должно выполняться неравенство 1 < kk+1 < kk+2 < . . .)Точнее,41 (1)(T + Ti(2) + . . . + Ti(n) )n i79Здесь = ( i) обозначает (единственное) стационарное распределение для положительно возвратной ц.м.д.в. (Xn).Приведенный пример независимых одинаково распределенных случай(1)(2)ных величин (н.о.р.с.в.) Ti , Ti , . . . довольно интригующий, так как их(совместное) распределение определяется переходной матрицей P и меняется довольно сложным способом при изменении P. Таким образом, чтобы(l)проанализировать последовательность (Ti ), нужно разработать общуютеорию н.о.р.с.в.
(в частности, это один из важных мотивов для разработкиэтой теории).В качестве примера одного из основных утверждений о н.о.р.с.в., который мы будем использовать в следующей главе, приведем «усиленный»(n)закон больших чисел (з.б.ч.) для последовательности (T i ).Теорема 1.8.4. С вероятностью 1 среднее§ 1.8. Положительная и нулевая возвратность. IIГлава 1. Цепи Маркова с дискретным временем781 − fk = P k (возвращение в k за конечное время не происходит) > 0.Глава 1.