Цепи Маркова (1121219), страница 30
Текст из файла (страница 30)
. . , yn−1 . Итак, последовательность (Yn , n = 0, 1, . . .)образует ц.м.д.в. с указанными выше вероятностями перехода.§ 1.16. Вопросы по теории цепей Маркова с дискретным временем181Задача 1.16.4. Лягушку посадили в подвал, пол которого разделен наN квадратов, занумерованных от 1 до N. Пусть Xn — это номер квадрата,в котором лягушка находится в момент n; последовательность (X n) n>0можно рассматривать как неприводимую цепь Маркова с вероятностямиперехода pij (1 6 i, j 6 N). Восприимчивая к движениям фотокамераделает мгновенный снимок подвала всякий раз после того, как лягушка перепрыгивает с одного квадрата на другой, и снимки производятсятолько в такие моменты. Пусть Yn обозначает номер квадрата, в котором находится лягушка на n-й фотографии.
Покажите, что (Yn) такжеявляется неприводимой ц.м.д.в., и найдите ее вероятности перехода. Пусть( 1 , . . . , N) — инвариантная вероятностная мера для цепи (X n). Найдитеинвариантную меру для цепи (Yn), а также среднее число фотографий,произведенных в единицу времени.Предположим теперь, что N = 9, квадраты расположены в виде таблицы 3 × 3147258369и в каждую единицу времени лягушка с равными вероятностями можетостаться на прежнем месте или перепрыгнуть на один из смежных квадратов (как в перпендикулярном направлении, так и по диагонали; так что,например, p2j = 1/6 для всех j 6 6).
Найдите инвариантную вероятностнуюмеру для цепи (Xn) и среднее число фотографий, произведенных в единицувремени.Решение. Заметим, что каждое значение pii меньше 1; в противномслучае цепь была бы приводимой. Предположим, что Y n = Xm , т. е. n-яфотография производится в момент m. Тогда для любого j 6= i условнаявероятность P (Yn+1 = j|Yn = i, Yn−1 = in−1 , .
. . , Y0 = i0) записывается ввидеP (Xm+1 = j|Xm = i) + P (Xm+1 = i, Xm+2 = j|Xm = i) + . . . == pij + pii pij + p2ii pij + . . . = pij (1 − pii) −1 := qijи qii := P (Yn+1 = i|Yn = i) = 0. Поскольку эти вероятности не зависят отn и от значений Yl при l < n, (Yn) является ц.м.д.в. с матрицей перехода0p12 / (1 − p11)p13 / (1 − p11) . . . p1N / (1 − p11) p21 / (1 − p22)0p23 / (1 − p22) . .
. p2N / (1 − p22) ................0pN1 / (1 − pNN) pN2 / (1 − pNN) pN3 / (1 − pNN) . . .182Глава 1. Цепи Маркова с дискретным временемБолее того, цепь (Yn) неприводима: при j 6= i можно перейти из состоянияi в j посредством той же последовательности прыжков, что и в цепи (X n) (аиз i в i можно перейти, совершив прыжок или серию прыжков из i, а затемобратно).Далее,P (в момент n + 1 сделана фотография |Xn = i) = 1 − pii .Следовательно, в инвариантном состоянии среднее число фотографийв единицу времени равноP (фотография произведена в единичном интервале времени) =NXX=i (1 − pii) = 1 −i pii .i=1iИнвариантная мера для Yn имеет вероятности− pii),NP1−k pkk=i (11 6 i 6 N.ik=1k=1k=1В заданном примере 1 = 3 = 7 = 9 и 2 = 4 = 6 =симметрии. Тогда уравнения инвариантности принимают вид2=2×5Учитывая равенство 414=1+2×141=4×41+414= ,492+162+161+4×6+3×115219225,191+9+5,5.= 1, находим6= ,4959= .49Среднее число фотографий в единицу времени равно1−9Xi=1j.k=11183Задача 1.16.5.
Улитка ползет по бесконечной ограде, которую можнорассматривать как решетку с вершинами в точках Z × {0, 1, 2}. Из вершины вида (n, 2) улитка перемещается влево или вправо (т. е. в (n − 1, 2)или в (n + 1, 2)) с равной вероятностью. Из вершины вида (n, 1) она перемещается вверх в вершину (n, 2) с вероятностью 1 /2 и в любую другую изтрех оставшихся вершин — с вероятностью 1/6.
Из вершины (n, 0) улиткаобязательно перемещается влево, если n четно, и вправо, если n нечетно.Классифицируйте состояния ц.м.д.в. соответствующей последовательностивершин, по которым осуществляется движение улитки. Если улитка выходит из вершины (0, 1), то какова вероятность того, что она когда-либопопадет в положительно возвратное состояние? Какова вероятность того,что она когда-нибудь попадет в вершину (0, 0)?Решение. Состояния (n, 2), n ∈ Z, образуют замкнутый сообщающийся класс и все имеют нулевую возвратность. Для каждого n парасостояний (2n − 1, 0) и (2n, 0) образует замкнутый сообщающийся класс,следовательно, все такие состояния — положительно возвратны.
Наконец,каждое состояние (n, 1) невозвратно: p (n,1) (n,2) > 0, но невозможен переходс уровня 2 на уровень 1.Предположим, что улитка выходит с уровня 1, и рассмотрим вероятность P (i,1) (когда-нибудь достичь уровень 0). Эта вероятность равнаi : i6=ji (1iXpij− pii)i pijj (1 − pjj)===NNN1 − piiPPPi=6j1−1−1−k pkkk pkkk pkkВ самом деле,XXi qij =§ 1.16.
Вопросы по теории цепей Маркова с дискретным временем140= .i pii = 1 − 949498в силу∞XP (i,1) (оставаться на уровне 1 на n шагах, затем перейти на уровень 0) =n=0=∞ nX1 1n=036=11 −111−= .634Улитка может когда-нибудь попасть в вершину (0, 0), если и толькоесли она когда-нибудь приползет туда из (0, 1) или из (−1, 1). Пустьhi = P (когда-нибудь попасть в (0,0) | текущее состояние (i, 1)).Тогда h−1 = h0 (в общем случае в силу симметрии h−i = hi−1) и111+ h0 + h1 ,66611hn = hn−1 + hn+1 ,66h0 =n > 1.n2Подставив√ hn = At во второе уравнение, находим t −√6t n+ 1 = 0, т.
е.t = 3 ± 2 2. Так как hn 6 1, получаем,√ что hn√= A(3 − 2 2) . Из первогоуравнения находим A = h0 = 1/2(1 + 2) = ( 2 − 1) /2.184Глава 1. Цепи Маркова с дискретным временемHold infinity in the palm of your hand...Попробуйте удержать бесконечность в своей ладони...У. Блейк (1757–1827), английский поэтЗадача 1.16.6. Две частицы A и B перемещаются случайно в моментывремени t = 1, 2, . . . на множестве M = {1, .
. . , m}, m > 3, отражаясьот границ, при этом их позиции XA (t) и XB (t) подчиняются некоторомупорядку (так что XA (t) 6 XB (t)) согласно следующей схеме.1. Если расстояние между ними больше единицы, то в следующиймомент они осуществляют движение независимо друг от друга согласноследующим правилам:а) если частица не находится на границе, т.
е. в точках 1 или m, то онасовершает скачок в одну из ближайших соседних точек с вероятностью1/2;б) если частица находится на границе, то она либо совершает скачокв одну из ближайших соседних точек в M, либо остается в той же точке,опять с вероятностью 1/2.2. Если частицы встречаются (попадают в одну и ту же точку) или жерасстояние между ними равно единице, то они меняют свое поведение.Если предполагаемые скачки могут привести к перестановке порядка частиц, т.
е. к неравенству XA > XB , то обе частицы сохраняют свое прежнееположение. (Вероятности предполагаемых скачков те же, что и ранее,и эти предполагаемые скачки независимы.) В противном случае частицысовершают эти предполагаемые скачки.Определите пространство состояний ц.м.д.в., которая образована парой(XA (t), XB (t)), и найдите ее инвариантное распределение. Обратима ли этацепь?Решение. Приведенное выше описание определяет конечную неприводимую цепь Маркова (с единственным сообщающимся классом) напространстве состоянийS = { (nA , nB) : 1 6 nA 6 nB 6 m},(m)с общим числом состояний m(m + 1) /2. В самом деле, p (nA ,nB),(n0 ,n0 ) > 0A Bдля всех (nA , nB), (n0A , n0B) ∈ S . Таким образом, цепь имеет единственноестационарное распределение.Кроме того, для всех (nA , nB), (n0A , n0B) ∈ S матрица перехода симметрична: p (nA ,nB),(n0A ,n0B) = p (n0A ,n0B),(nA ,nB) .
Действительно, каждая из этихвероятностей равна либо 0, либо 1/4, либо 1/2 (если (nA , nB) = (n0A , n0B) == (1, 1) или (nA , nB) = (n0A , n0B) = (m, m)). Следовательно, стационарноераспределение является равномерным на S , и цепь обратима.§ 1.16. Вопросы по теории цепей Маркова с дискретным временем185Задача 1.16.7. Рассмотрим стохастическую матрицу на множестве{1, . . . , 7}:01 /2 0 00 00 1 /20 00 10 1 /2 0 01/3 1 /3 0 01 / 3 0 0 1 /2P= 0 0 0 00 0 1 /20 1/3 1/30 00 1 00 .0 00 0 0 1 /20 1 /3 0Найдите все возвратные состояния соответствующей цепи Маркова с дискретным временем.Пусть pnij обозначает элемент матрицы P n с индексом ‘ij’. Определитепары (i, j), для которых существует предел lim pnij , и найдите эти предельn→∞ные значения.Решение.
См. пример 1.2.7. Более простой способ решения — воспользоваться следующей теоремой. Если матрица P неприводимая, аперио(n)дическая и имеет инвариантное распределение , то pij → j ∀ i, j.Действительно, замкнутыйкласс — это класс {1, 2, 6, 7}, а инвариантное распределение=1 3 1 3(n),, ,. Отсюда получаем предел lim pij5 10 5 10n→∞для i, j ∈ {1, 2, 6, 7}; а для i = 3 этот предел нужно разделить на 2.Задача 1.16.8. В модели, описанной в примере 1.3.2, предположим, чточастица начинает движение из угла A (см. рис. 1.12). Найдитеа) вероятность того, что частица вернется в A, так и не побывав в центральной вершине C;б) среднее время возвращения в A;в) математическое ожидание числа посещений вершины C до возвращения в A.Решение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
