3. Основы теории случайных процессов. Карлин (1971) (3. Основы теории случайных процессов. Карлин (1971).djvu), страница 9

Состояния /= 1,2, ..., У вЂ” ! называются смешанными, а состояния О и М вЂ” чистыми. Состояние А! интересно тем, что ген, все элементарные единицы которого мутантны, может принести смерть своему обладателю, в то время как ген, находящийся в состоянии О, при делении не порождает мутантных генов. Позже мы вычис. лим в явном виде вероятности того, что ген из состояния с попадает в состояние О или А!. й З, МАТРИЦЫ ПЕРЕХОДНЫХ ВЕРОЯТНОСТЕЙ МАРКОВСКОЙ ЦЕПИ Марковская цепь полностью определяется своей матрицей одношаговых переходных вероятностей и заданием распределения вероятностей состояния процесса в момент времени О. Анализ марковской цепи связан главным образом с вычислением вероятностей возможных ее реализаций, важнейшей характеристикой которых является матрица вероятностей переходов за и шагов р'"'=~~Р(!!~~.

Рф обозначает вероятность того, что процесс перейдет из состояния 1 в состояние ! за и переходов, или, в принятых ранее обозначениях, (ЗЗ) Заметим, что мы имеем дело только с процессами, однородными во времени, т, е, с процессами, имеющими стационарные переходные вероятности; в противном случае правая часть в (3.1) зависела бы от т. 4 д Матрицы перехлйных ееяоятяоетей Марковское свойство процесса позволяет выразить (3.1) непосредственно через 1~Рц!1, как зто видно из следующей теоремы.

Т е о р е м а 3,1, Если Р = м' Рн ~! — матрица однотиаговьтх переходньтх вероятностей марковской цепи, то Ри =- 2.' Рирят я=а (3.2) для любой фиксированной пары неотрицательных целых чисел г и в, такой, чго т + з = гг; при этом по определению ~ 1, если т==/, Р"„= 1 О, если 1Ф1. В формуле (3.2) нетрудно узнать формулу умножения матриц (см.

приложение). Отсюда следует, что Роо = Р"; другими словами, вероятности Рй можно рассматривать как элементы матрицы Р" — и-й степени матрицы Р. Д о к а з а т е л ь с т в о. Рассуждения проведем для случая и = 2. Событие, состоящее в переходе из состояния т в состояние 1 за 2 шага, может произойти любым из следующих взаимно исключающих друг друга путей: на первом шаге — переход в некоторое промежуточное состояние й (к = О, 1, 2, ...), затем, на втором шаге, переход из состояния й в состояние 1. Так как процесс марковский, то вероятность второго перехода равна Ркь а первого — Рио Воспользовавшись формулой полной вероятности, приходим к (3,2). Рассуждения в общем случае точно такие же.

(3.3) Помимо определения совместных распределений вероятностей процесса для всех моментов времени, что, кстати, обычно является очень трудной задачей, часто интерес представляет выяснение асимптотического поведения вероятностей Р";~ при и — оо. Можно ожидать, что влияние начального состояния со времеяем умень.

шается, а, следовательно, Ртт стремится при и -+ оо к пределу, Если вероятность того, что процесс в начальный момент находится в состоянии 1, равна р,, то вероятность оказаться в состоянии Й в момента равна 52 Гм 2 Марковские цепи не зависящему от й Для того чтобы дать точный анализ асимптотического поведения марковской цепи, мы введем классификацию ее состояний. й 4. КЛАССИФИКАЦИЯ СОСТОЯНИИ МАРКОВСКОЙ ЦЕПИ Говорят, что состояние / достижимо из состояния с, если Рсс ) 0 для некоторого целого числа и ) О, т. е.

вероятность того, что процесс за конечное число шагов попадает в состояние /, отправляясь из состояния с', положительна. Состояния с и /, достижимые друг из друга, называют сообисасоисимссся; этот факт обозначают «/. Если два состояния с' и / не сообщаются, то либо Рсс=О для всех п)~ О, либо Рсс = 0 для всех п)~ О, либо оба условия выполняются одновременно. Свойство сообщаемости представляет собой отношение эквивалентности.

Действительно: (!) с «с (рефлексивность), так как по определению имеем а (), с=/ О с~/ (й) если с' /, то / с' (симметричность), согласно определению сообщающихся состояний; (ш) если с « / и / /с, то с «й (транзитивность). Транзитивность доказывается следующим образом. Из с « / и / ц-«й следует, что существует пара неотрицательных целых чисел п и и, таких, что Ри>0 и Ръ>0. Следовательно, в силу (3.2) и с неотрицательности всех Р„имеем Р";~и~ = ~ Р";„Р и ) РссРсс, > О. г 0 Аналогично показывается существование целого числа т, такого, что Рйс> О. Из этого следует, что все множество состояний можно разбить на классы эквивалентности. Состояния объединяются в один класс, если они сообщаются друг с другом. Возможно, что, отправляясь из состояния, принадлежащего одному классу, мы с положительной вероятностью попадаем в другой класс, но тогда, очевидно, возврат в исходный класс уже невозможен, так как иначе оба упомянутых класса входили бы в один класс эквивалентности.

Мы будем говорить, что марковская цепь неириводима, если введенное нами соотношение эквивалентности порождает только один класс состояний. Другими словами, процесс неприводим, если все его состояния сообщаются друг с другом. зз э .Я Коасспс)пскаспсп соссокпий марковской цели Для иллюстрации рассмотрим матрицу переходных вероятностей вида — †.о о о —,о о о Р, О о О О::О 1 О ! ! о о: ::— о 2 2 О О!О 1 О Состояния марковской цепи, имеющей такую матрицу переходных вероятностей, распадаются на два класса сообщающихся состояний: (1, 2) и (3, 4, 5).

В зависимости от начального состояния процесс развертывается либо только в первом классе состояний и его переходы описываются подматрицей Рь либо только во втором классе и его переходы описываются подматрицей Рь В марковской цепи процесса случайного блуждаяия с матрицей переходных вероятностей состояния 1 О О О ... О О О д о р О...о о о о д о р...о о о 0 1 2 д о р 0 0 1 а — 1 Периодичность марковской цепи Определим период состояния й далее обозначаемый е)(1), как наибольший общий делитель (н.о.д.) всех целых чисел п)~1, для котоРых Р,", >О.

(Если Р"т = 0 пРи всех п)~1, то по опРеделению мы имеем три класса состояний: (О), (1, 2, ..., а — Ц и (а). Очевидно, что из второго класса можно попасть и в первый и в третий классы, но возвратиться из них во второй класс невозможно. Марковская цепь, описывающая процесс образования очереди в примере В из З 2, неприводима, если ак > 0 при всех й.

Легко проверить, что при этом же условии неприводима и марковская цепь из примера Г, Если с)е > О, р; > 0 (1= О, 1, ...), то марковская цепь серий успехов (пример Д) также неприводима. Гл д Марковские цепи с((1) = 0.) Если в матрице переходных вероятностей (2.2) случайного блуждания все т; = О, то период каждого из состояний цепи равен двум.

Если же хотя бы для одного состояния 1ь величина ги больше нуля, то все состояния цепи имеют период 1, так как независимо от начального состояния 1' система может попасть в состояние 1о и оставаться в нем в течение произвольного времени прежде, чем вернуться в состояние 11 В конечной марковской цепи с п состояниями н матрицей переходных вероятностей и м 0100...0 0 0 1 0...0 0 0 ....

! 1 0 0... 0 каждое состояние имеет период и. Приведем без доказательства три основных свойства периода состояния (см. задачи 5 — 7 в конце главы). Теорема 4.1. Если ! !, то Н(1) = е((!'). Это утверждение определяет период как характеристику класса сообщающихся состояний. Теорем а 4.2.

Если состояние 1 имеет период д(1), то существует целое число й', зависящее от 1, такое, что для всех целых чисел п)~У вероятность Рйш>0. Этим утверждается, что возвращение в состояние 1 может происходить во все достаточно далекие моменты времени, кратные периоду с((1). Следствие 4.!.

Если Рсс)0, то Рй~кли~)0 для всех достаточно больших положительных целых чисел п. Марковская цепь, каждое состояние которой имеет период 1, называется непериодическои. Большинство марковских цепей, рассматриваемых нами, относятся к классу непериодических. Результаты будут в основном доказываться именно для этого случая; для общего же случая мы обычно будем ограничиваться их формулировками. Трудолюбивый читатель сможет легко провести доказательство самостоятельно зз З 5. Воввратвосте З. ВОЗВРЛТНОСТЬ Рассмотрим произвольное, но фиксированное состояние й Положим для каждого целого числа п)~1 !Н=Р(Х„=(, Х,Ф1, о=1, 2, ...

и — 1)Х =1). Другими словами, (с", есть вероятность того, что, отправляясь из состояния й система впервые возвратится в это состояние через и переходов. Ясно, что )„=РН, а )и можно вычислить рекуррентно в соответствии с формулой (5.1) в-о где, согласно определению, !он = О для всех Е, Соотношение (5.1) выводится следующим образом.