§ 4. КЛАССИФИКАЦИЯ СОСТОЯНИЙ МАРКОВСКОЙ ЦЕПИ

Говорят, что состояние достижимо из состояния если для некоторого целого числа т. е. вероятность того, что процесс за конечное число шагов попадает в состояние отправляясь из состояния положительна. Состояния достижимые друг из друга, называют сообщающимися; этот факт обозначают Если два состояния не сообщаются, то либо для всех либо для всех , либо оба условия выполняются одновременно. Свойство сообщаемости представляет собой отношение эквивалентности. Действительно:

(i) (рефлексивность), так как по определению имеем

(ii) если то (симметричность), согласно определению сообщающихся состояний;

(iii) если то (транзитивность).

Транзитивность доказывается следующим образом. Из следует, что существует пара неотрицательных целых чисел , таких, что Следовательно, в силу (3.2) и неотрицательности всех имеем

Аналогично показывается существование целого числа такого, что

Из этого следует, что все множество состояний можно разбить на классы эквивалентности. Состояния объединяются в один класс, если они сообщаются друг с другом. Возможно, что, отправляясь из состояния, принадлежащего одному классу, мы с положительной вероятностью попадаем в другой класс, но тогда, очевидно, возврат в исходный класс уже невозможен, так как иначе оба упомянутых класса входили бы в один класс эквивалентности. Мы будем говорить, что марковская цепь неприводима, если введенное нами соотношение эквивалентности порождает только один класс состояний. Другими словами, процесс неприводим, если все его состояния сообщаются друг с другом.

Для иллюстрации рассмотрим матрицу переходных вероятностей вида

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

В марковской цепи процесса случайного блуждания с матрицей переходных вероятностей

мы имеем три класса состояний: Очевидно, что из второго класса можно попасть и в первый и в третий классы, но возвратиться из них во второй класс невозможно.

Марковская цепь, описывающая процесс образования очереди в примере В из § 2, неприводима, если при всех Легко проверить, что при этом же условии неприводима и марковская цепь из примера Если то марковская цепь серий успехов (пример Д) также неприводима.

Периодичность марковской цепи

Определим период состояния далее обозначаемый как наибольший общий делитель (н.о.д.) всех целых чисел для которых (Если при всех то по определению

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

В конечной марковской цепи с состояниями и матрицей переходных вероятностей

каждое состояние имеет период

Приведем без доказательства три основных свойства периода состояния (см. задачи 5—7 в конце главы).

Теорема 4.1. Если то

Это утверждение определяет период как характеристику класса сообщающихся состояний.

Теорема 4.2. Если состояние имеет период то существует целое число зависящее от такое, что для всех целых чисел вероятность

Этим утверждается, что возвращение в состояние может происходить во все достаточно далекие моменты времени, кратные периоду

Следствие 4.1. Если то для всех достаточно больших положительных целых чисел

Марковская цепь, каждое состояние которой имеет период 1, называется непериодической. Большинство марковских цепей, рассматриваемых нами, относятся к классу непериодических. Результаты будут в основном доказываться именно для этого случая; для общего же случая мы обычно будем ограничиваться их формулировками. Трудолюбивый читатель сможет легко провести доказательство самостоятельно