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

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

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

В дальнейшем мы обстоятельно проанализируем некоторые из этих моделей в § 1.5–1.7.Рис. 1.9Рис. 1.8Вернемся к цепям Маркова с конечным числом состояний. В общемслучае если перенумеровать состояния, то матрица перехода P с конечнымчислом элементов приобретает некоторую структуру, см. рис. 1.8. Обычно в левом верхнем углу размещают квадратный блок O 0 , состоящий извероятностей возможных переходов между несущественными состояниями(т.

е. между и внутри незамкнутых сообщающихся классов). Этот блок может быть нулевым, если таковых переходов нет. Далее, квадратные блокиC1 , . . . , Cm размещены на главной диагонали. Эти блоки представляютзамкнутые сообщающиеся классы различных размеров; они образуют стохастические подматрицы. ПоследнееP означает, что для любых i = 1, .

. . , mи любых состояний j ∈ Ci суммаpjk элементов матрицы внутри классаk∈CiCi вдоль строки j равна 1. Цепи Маркова, соответствующие блокам C 1 ,. . . , Cm , могут изучаться по отдельности (что проще сделать ввиду ихменьшего размера). Блоки O1 , . . . , Om с правой стороны от O0 — этонеотрицательные прямоугольные матрицы; некоторые из них (но не все)могут быть нулевыми. (Конечно, суммы элементов каждой строки матрицыP всегда равны 1.) Если матрица не имеет несущественных состояний, тоблоки O0 , O1 , . . . , Om могут просто отсутствовать.Пространство между блоками O0 , O1 , . .

. , Om и C1 , . . . , Cm заполненонулями. (Внутри матриц также может быть много нулей, см. ниже.)Мы будем называть конечную ц.м.д.в. (Xn) (или, что то же самое, еепереходную матрицу P) неприводимой, если она состоит из единственногосообщающегося класса C (который автоматически является замкнутым).Иными словами, конечная переходная матрица неприводима, если каждаяпара состояний i, j ∈ I сообщается, а все множество состояний образуетодин замкнутый класс I = C. Графически в этом случае матрица P сводитсяк блоку C, см.

рис. 1.9 а). Отличительной особенностью здесь является то,что для любой пары состояний i, j ∈ I элементы pij(n) матрицы Pn (т. е.переходные вероятности из состояния i в состояние j за n шагов) строгобольше 0 для некоторого n > 1 (которое, как правило, зависит от i и j).Некоторые авторы рассматривают более сложную ситуацию и говорят, что ц.м.д.в.

неприводима, если она обладает единственным замкнутымсообщающимся классом и несколькими незамкнутыми классами. В этомслучае конечная цепь имеет единственное инвариантное, или стационарное, распределение, см. ниже. Соответствующая матрица приведена нарис. 1.9 б): имеется один квадратный блок C, который составляет стохастическую подматрицу, плюс квадратный блок O 0 в верхнем левом углу,и отдельный прямоугольный блок O1 , или просто O.

При итерации такойматрицы P, т. е. при возведении ее во все более высокую степень n, блокO0 будет стремиться к 0 при n → ∞. Поведение блока O более сложно:мы проанализируем его позднее. Что же касается блока C, то он простобудет возводиться в степень n (что удобно).Приведенные выше рассуждения наталкивают на мысль, что будетпроисходить при итерации конечной переходной матрицы P с несколькимизамкнутыми сообщающимися классами. Как и ранее, блок O 0 матрицыPn будет стремиться к 0 при n → ∞.

Как и ранее, блоки C 1 , . . . , Cm36Глава 1. Цепи Маркова с дискретным временемматрицы Pn будут просто возводиться в степень n. Последнее замечаниеиллюстрирует тот факт, что приводимую цепь, содержащую более чемодин класс, можно изучать, рассматривая отдельно каждый из классов.Для простоты предположим, что конечная матрица P неприводима.Нетрудно догадаться, что внутри блока C у нас может быть периодическая структура, содержащая v клеток меньшей (одинаковой) размерности,циклически перемещаемых матрицей P: клетка 1 «переходит» в клетку 2,и т.

д., клетка v переходит в клетку 1, см. рис. 1.10. Пространство внеклеток снова заполнено нулями.§ 1.2. Разбиение состояний на классы37может быть достаточно сложной. К счастью, большинство приложенийи интересных примеров не требуют большой степени общности, и намудастся сделать упрощающие предположения.Пример 1.2.7. Рассмотрим стохастическую 7 × 7 матрицу01 / 3 0P= 0 001 /31 /201 /2001 /21 /30 00 00 1 /20 00 10 00 00 0 1 /20 1/3 1/30 00 1 00  .0 00 0 0 1 /20 1 /3 0Найдите все сообщающиеся классы соответствующей ц.м.д.в.Рис. 1.10Эта картина соответствует разбиению пространства I (которое, понашему предположению, составляет отдельный (и замкнутый) сообщающийся класс) на такие периодические подклассы W1 , .

. . , Wv , что переходза один шаг возможен только из состояния j ∈ Wi в состояние k ∈ Wi+1 ,i = 1, . . . , v. (Здесь сумму i + 1 следует понимать как сумму по модулю v,так что Wv+1 = W1). Число v называется периодом класса C.В большинстве наших примеров период замкнутого сообщающегосякласса равен единице, т.

е. класс состоит из одной клетки. Такие классы(или, что то же самое, их переходные матрицы) называются апериодическими.Вообще говоря, если возвести переходную матрицу P, соответствующую замкнутому сообщающемуся классу C с периодом v, в степень v,то матрицу Pv можно разбить на квадратные стохастические подматрицы,расположенные на главной диагонали. Образно говоря, периодическиеподклассы W1 , . . . , Wv играют роль замкнутых сообщающихся классов дляматрицы Pv . (Нужно, правда, отметить, что формально такое утверждениеневерно: некоторые из подклассов Wi могут состоять из нескольких непересекающихся замкнутых сообщающихся классов матрицы P v .)Мы увидим, что полная структура конечной переходной матрицы PРис. 1.11Решение.

См. рис. 1.11. Сообщающимися классами являются{1, 2, 6, 7}, {3} и {4, 5}. Замкнутые классы — {1, 2, 6, 7} и {4, 5};состояние 3 является несущественным. Класс {4, 5} имеет периодическую(n)структуру. Следовательно, предел величины p ij не существует (онаосциллирует) при i = 3, 4, 5 и j = 4, 5. Для класса {1, 2, 6, 7} подматрицаперехода имеет вид01 /201 /21 / 3 0 1 / 3 1 / 3  0 1 /2 0 1 /2 1 /3 1 /3 1 /30и обладает симметрией 1 ↔ 6 и 2 ↔ 7. Таким образом, если объединитьсостояния 1 и 6 в (новое) состояние I, а состояния 2 и 7 объединитьв состояние II, то получим цепь с двумя состояниями и матрицей перехода01Π=.2 /3 1 /338Глава 1. Цепи Маркова с дискретным временем2−13Характеристическое уравнение для последней матрицы имеет вид−2= 0,3корни этого уравнения равны 0 = 1, 1 = −2/3.

Следовательно, элементыΠn имеют вид A + B(−2/3) n . Подобрав должным образом постоянные,получаем2 5 + 3/5(−2/3) n 3/5 − 3/5(−2/3) nΠn = /.nn2/5 − 2/5(−2/3)Таким образом,nΠ →3/5 + 2/5(−2/3)2 /5 3 /52 /5 3 /5.Тогда в силу симметрии для первоначального блока {1, 2, 6, 7} предельнойбудет матрица1/5 3/10 1/5 3/101/5 3/10 1/5 3/101/5 3/10 1/5 3/10 ,1/5 3/10 1/5 3/10(n)(n)(n)(n)(n)т. е.

pi1, pi6→ 1/5 и pi2, pi7→ 3/10, i = 1, 2, 6, 7. Вероятности p3j1стремятся кlim p (n) , j = 1, 2, 6, 7.2 n→∞ 2jСледует подчеркнуть, что такой способ вычисления пределов(n)limn→∞ pij не является оптимальным. В дальнейшем мы познакомимсяс намного более эффективными способами.§ 1.3. Времена и вероятности достижения§ 1.3. Времена и вероятности достижения39Вероятность достижения hAi — это вероятность того, что цепь, стартующаяиз состояния i, когда-нибудь попадет в A:hAi = P i (HA < ∞);если A — это замкнутый класс, то hAi называют вероятностью поглощения.Математическое ожидание величины H A обозначают kAi :XkAi = E i (HA) =n P i (HA = n) + ∞ · P i (HA = ∞).(1.3.3)0<n<∞Следовательно, если P i (HA = ∞) > 0, то kAi = ∞.

(По соглашению,∞ · 0 = 0.)Вычисление вероятностей достижения основывается на следующейтеореме.Теорема 1.3.1. При заданном множестве A ⊂ I величины hAiпредставляют собой минимальные неотрицательные решения следующей линейной системы:(hAi ≡ 1,i ∈ A,P(1.3.4)AApij hj , i 6∈ A,hi =j∈Iт. е. для любого решения gi > 0 системы (1.3.4) выполняется неравенство gi > hAi , i ∈ I.Д о к а з а т е л ь с т в о. Напомним, что hAi вычисляется при условии, чтоX0 = i. Если i ∈ A, то HA = 0, следовательно, hAi = 1.

Если i 6∈ A, тоHA > 1, и тогдаhAi =Xj∈IA hit, a very palpable hit. (Гамлет)P i (HA < ∞, X1 = j) =Xj∈IP i (X1 = j) P i (HA < ∞ | X1 = j) == (в силу марковского свойства)XjВ. Шекспир (1546–1616), английский драматург и поэтНапомним, что через P i обозначается распределение ц.м.д.в. (Xn), которая выходит из состояния i ∈ I. Аналогично будем обозначать черезE i математическое ожидание по мере P i . Пусть A ⊂ I — это некотороеподмножество множества состояний. Момент (первого) достиженияHA — это момент времени, когда цепь Маркова впервые попадает в A,т.

е.(1.3.1)HA = inf{n > 0 : Xn ∈ A}.(1.3.2)pij P j (HA < ∞) =Xpij hAj .jВозьмем любое неотрицательное решение gi . Если i ∈ A, то gi = hAi == 1. Если i 6∈ A, тоgi =Xjpij gj =Xj∈Apij +Xj6∈Apij gj =Xj∈Apij +Xj6∈ApijXpjk +k∈A= P i (X1 ∈ A) + P i (X1 6∈ A, X2 ∈ A) +Xk6∈AXpjk gk =j6∈A,k6∈Apij pjk gk .40Глава 1. Цепи Маркова с дискретным временемПовторяя подстановки, для любого n находим41Тогда искомая вероятность равна hA и в силу симметрии6 A, Xn ∈ A) +gi = P i (X1 ∈ A) + . . . + P i (X1 6∈ A, . . . , Xn−1 ∈XX...pij1 pj1 j2 . . . pjn−1 jn gjn .+j1 6∈A§ 1.3.

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

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