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

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

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

Действительно, имеет место1оценка: P > P0 , где P0 = есть корень уравнения383(1 − P0)2 + 4P0 = ,которое соответствует ситуации, когда с вероятностью P 0 имеется четырекрасные вершины, а с дополнительной вероятностью 1 − P 0 в точностидве.Завершая данный параграф, мы хотели бы отметить, что в определении1.1.3 мы ввели класс так называемых однородных, или однородныхво времени, цепей Маркова. Мы будем опускать термин «однородный»,кроме нескольких случаев, когда мы рассматриваем «неоднородные» цепи(что имеет место для цепей Маркова с непрерывным временем, см.

§ 2.4).Отметим только, что в неоднородной цепи Маркова переходная вероятность из состояния i в j зависит от времени перехода. Следовательно,вместо одной переходной матрицы P мы будем рассматривать семействоматриц Pn , n = 0, 1, 2, . . ., которое описывает вероятности переходов изсостояния i, в котором цепь находится в момент времени n, в состояние jв момент времени n + 1.§ 1.2. Разбиение состояний на классы29§ 1.2.

Разбиение состояний на классыБорьба сообщающихся классов(Из серии «Кое-что из политики».)Разбиение на классы — это естественное разбиение пространства состояний I, порожденное матрицей перехода P. Если не оговорено заранее,мы имеем в виду, что пространство состояний и соответствующая матрицаконечны.Определение 1.2.1. Говорят, что состояния i и j принадлежат к одномусообщающемуся классу, если pij(n1) > 0 и pji(n2) > 0 для некоторых n1 , n2 >> 0 (Напомним, что если n = 0, то P 0 — единичная матрица I.) Этотфакт обозначается i ↔ j.

Если выполняется одно из этих условий, топишем i → j или j → i, а если мы хотим подчеркнуть, что одно из них невыполняется, то мы будем обозначать это как i 6→ j или j 6→ i.Чтобы проверить, что это разбиение корректно определено, заметим,(0)что а) каждое состояние сообщается с самим собой (i ↔ i, так как p ii = 1),б) соотношение i ↔ j симметрично, т. е.

выполняется или не выполняетсянезависимо от порядка внутри пары i, j (что очевидно из определения);P (n1) (n2)(n +n )(n ) (n )в) если i ↔ j и j ↔ k, то i ↔ k (так как pik 1 2 =pil plk > pij 1 pjk 2(n +n )pki 1 2 ).l∈Iи аналогичные оценки верны дляТогда в силу а) каждое состояниепопадает в некоторый класс, в силу б) каждый класс корректно определенкак (неупорядоченное) подмножество I, а в силу в) каждое состояниепопадает не более чем в один класс. Состояния из разных классов, конечно,не сообщаются.Полезно иметь в виду, что i → j тогда и только тогда, когда существуетпоследовательность таких состоянийi0 = i, i1 , .

. . , in−1 , in = j,что pil il+1 > 0 для любой пары (il , il+1), 0 6 l < n. Действительно, pij(n) =P=pii1 . . . pin−1 j и вся сумма положительна тогда и только тогда, когдаi1 ,...in−1по крайней мере одно слагаемое положительно.Определение 1.2.2. Класс сообщающихся состояний (класс эквивалентности, сообщающийся класс) C называют замкнутым, если длялюбых таких i ∈ C и j ∈ I, что i → j, состояние j принадлежит C. Иначеговоря, невозможно выйти из замкнутого класса. Если состояние (или всесостояния, что то же самое) выводит из класса, то такой класс называетсянезамкнутым.

Состояния, образующие незамкнутые классы эквивалентно-30Глава 1. Цепи Маркова с дискретным временемсти; часто называют несущественными, они и в самом деле несущественныс точки зрения асимптотического поведения цепи. Состояние i называетсяпоглощающим, если pii = 1. Это эквивалентно тому, что сообщающийся класс поглощающего состояния i состоит только из этого состоянияи является замкнутым.Цепь Маркова называется неприводимой, если все ее состояния образуют один класс сообщающихся состояний (который в этом случае долженбыть замкнутым). Изучение цепи, имеющей более одного класса сообщающихся состояний, по сути сводится к изучению ее «сужений» на различныеклассы.Новый факт, доказанный мною, ... состоитв том, что классовая борьба неизбежноведет к диктатуре пролетариата.К.

Маркс (1818–1883), немецкий философПример 1.2.3. Пусть частица переходит из состояния i = 1, . . . , N − 1в состояние i + 1 с вероятностью p, а в состояние i − 1 с вероятностью 1 − p,где 0 < p < 1. Из состояний 0 и N невозможны переходы ни в одно другоесостояние, т. е. достигнув однажды состояния 0 или N, частица останетсятам навсегда. Этот пример описывает матч двух игроков, когда в каждойигре проигравший выплачивает победителю одну единицу («очко») и матчпродолжается до тех пор, пока один из игроков не проиграет все свои очки.Другой интерпретацией является блуждание пьяного, который, выходя изпивной (паба), делает шаги либо в сторону дома (дом — это состояние 0),либо в сторону озера (озеро — это состояние N).

В первом случае значениеN — это общее число очков у обоих игроков перед началом поединка;вполне очевидно, что оно сохраняется неизменным в ходе игры. Во второмслучае N — это расстояние (число шагов) между домом и озером (паб находится где-то между домом и озером). Каждое состояние i = 0, 1, . . . , N —это число очков у первого игрока или расстояние от дома; p и 1 − p —вероятности выигрыша и проигрыша первого игрока в каждой игре иливероятности сделать шаг в сторону дома или озера соответственно. Результаты игр являются независимыми, так же как и направления движенияна каждом шаге.§ 1.2. Разбиение состояний на классы31Здесь матрица перехода является (N + 1) × (N + 1) -матрицей вида100 0 ...00 01 − p 0 p 0 .

. . 0 0 0  0 1 − p 0 p . . . 0 0 0P=. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  , 000 0 ...0p 000000 0 ... 1 − p 0 p0 0 ...00 1см. рис. 1.5. Сообщающимися классами являются классы {0}, {1, . . .. . . , N − 1} и {N}, классы {0} и {N} замкнуты (т.

е. состояния 0 и N являются поглощающими). Таким образом, состояния 1, . . . , N − 1 являютсянесущественными, и игра обязательно закончится в одном из граничныхсостояний.Рис. 1.5Пример 1.2.4. Рассмотрим (6 × 6)-матрицу перехода на множествесостояний {1, 2, 3, 4, 5, 6} следующего вида:∗ 00 00 0P=0 ∗0∗∗0∗ 0 00 ∗ 0000000∗00∗0000∗,0∗0где символ ∗ обозначает ненулевой элемент, см. рис. 1.6. Сообщающимисяклассами являются классы C1 = {1, 5}, C2 = {2, 3, 6} и C3 = {4}, изкоторых лишь класс C2 замкнут.

Стрелки между классами показываютдинамику цепи. Если мы стартуем из класса C2 , то остаемся в C2 навсегда.Если мы стартуем из C3 (т. е. из состояния 4), то попадаем либо в C2(и тогда остаемся в C2 навсегда), либо в C1 . Интуиция подсказывает,что, проведя некоторое время в C1 , мы должны покинуть этот класс,т. е. перейти в C2 . В действительности так и происходит, как мы вскореувидим.Приведем простой, но полезный факт.Теорема 1.2.5. Цепь Маркова с конечным пространством состояний всегда имеет хотя бы один замкнутый сообщающийся класс.32Глава 1.

Цепи Маркова с дискретным временем§ 1.2. Разбиение состояний на классыматрицы перехода таковы:...................иРис. 1.6Чтобы доказать это, рассмотрим любой класс, скажем C 1 . Если этоткласс незамкнут, возьмем следующий класс, достижимый из C 1 . Еслии этот класс незамкнут, будем продолжать этот процесс. В конце концовмы достигнем замкнутого класса.Замечание 1.2.6. Случай счетной цепи Маркова со счетным пространством состояний I более сложен. Здесь может не существовать ниодного замкнутого класса. Вдобавок в бесконечном замкнутом классемогут также быть «несущественные» состояния, в том смысле, что цепьможет побывать в каждом из таких состояний только конечное число раз,а затем уйти в «бесконечность» (хотя все еще может оставаться в этом жезамкнутом классе).Рис.

1.7Самыми простыми являются примеры, когда пространство состоянийI представляет собой множество неотрицательных целых чисел Z + == {0, 1, 2, . . .}. Три примера показаны на рис. 1.7; соответствующие0 1 0 0 ... 0 ...0 0 1 0 . . . 0 . . . a) ,0 0 0 1 . . . 0 .

. .33010 0 ... 0 ...1 − p 0 p 0 . . . 0 . . . б) 01 − p 0 p . . . 0 . . ...........................010 0 ... 0 ...0p1 0 . . . 0 . . . 1 − p 1в) .01 − p 2 0 p2 . . . 0 . . . ..............................Эти примеры описывают так называемые процессы рождения и гибели, когда состояние i представляет собой размер популяции, а припереходе к следующему состоянию может умереть одна особь или можетпоявиться одна особь. В случае а) допускаются только переходы в сторонуувеличения популяции и цепь является детерминированной. Здесь каждое состояние i образует незамкнутый класс и является несущественным.В модели б) «смерть» особи происходит с одной и той же вероятностью1 − p, а рождение — с вероятностью p, независимо от размера популяцииi в данный момент времени (если только, конечно, i не равно 0).

Примером такого процесса может служить очередь «заданий», обслуживаемыхнекоторой системой (например, клиенты, ожидающие своей очереди в парикмахерской, в которой имеется лишь одно кресло для обслуживания,либо компьютерные программы, последовательно выполняемые процессором). Тогда i — это число заданий в очереди. Если до того момента, когдапарикмахер закончит обслуживание текущего клиента, приходит новыйклиент, то имеем скачок i → i + 1; в противном случае имеем скачокi → i − 1; из состояния 0 возможен лишь скачок в состояние 1 (хотяв действительности парикмахер может ожидать некоторое время, покапоявится первый клиент).

Возможны два случая: p > 1 /2 и 0 < p < 1/2.Интуитивно ясно, что если p > 1/2, то задания поступают по крайней мерес такой же частотой, с какой происходит их обслуживание, и очередь можетпревратиться в бесконечную (что, конечно, доставит удовольствие нашемупарикмахеру). В этом случае, как мы далее увидим, каждое состояние iбудет посещаться цепью лишь конечное число раз и X n (размер очередив момент времени n) будет бесконечно расти с ростом n.

Если 0 < p << 1/2, то задания будут поступать не так часто и система сможет достичь«равновесия» с некоторым стационарным распределением длины очереди.Часто используется модификация примера б), когда состояние 0 полагают поглощающим с вероятностью p00 = 1.В более общем случае в) правила динамики популяции таковы, что длякаждой особи существует шанс погибнуть (но только для одного в каждый34Глава 1. Цепи Маркова с дискретным временем§ 1.2. Разбиение состояний на классы35момент времени); например pn = / ( + n ), 1 − pn = n / ( + n ), где> 0 и > 0 — «интенсивности» «миграции» и смерти; общая картинастановится более сложной.

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

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