П. 4. Ассоциированный орграф

1. Ассоциированный орграф цепи Маркова — это такой орграф, где каждое состояние E_i представлено соответствующей ему вершиной v_i, а дуги из v_i в v_j проведены для тех и только тех вершин, для которых p_ij ¹ 0.

Ассоциированный орграф задачи о пьянице приведен ниже.

v ₁ v ₂ v ₃ v ₄ + v ₅ v ₆

Пример. Ниже приведена еще одна v ₁ v ₂

матрица перехода

цепи Маркова и ее

ассоциирован­ный v₆ v ₃

орграф.

v ₅ v ₆

Теперь ясно, что в цепи Маркова из состояния E_i в состояние E_j можно попасть в том и только в том случае, если в ассоциированном орграфе существует орцепь из v_i в v_j, и что наименьшее возможное время попадания равно длине кратчайшей из таких орцепей.

2. Классификация. Цепь Маркова, в которой из любого состояния можно попасть в любое другое, неприводима. Цепь Маркова неприводима тогда и только тогда, когда ее ассоциированный орграф сильно связен.

Упр. 10. Выше описаны две цепи Маркова. Они неприводимы? Почему?

Различают те состояния, в которые продолжают возвращаться независимо от продолжительности процесса, и другие. Более точно: если начальное состояние есть E_i и вероятность возвращения в E_i на некотором более позднем шаге равна 1, то E_i возвратно, или рекуррентно; в противном случае состояние E_i невозвратно. Состояние, из которого нельзя попасть ни в какое другое, называется поглощающим.

Пример. В задаче о пьянице состояния E ₁ и E ₆ возвратны, а все другие состояния невозвратны. Также эти состояния E ₁ и E ₆ поглощающие.

Упр. 11. Какие состояния во 2-й цепи невозвратны, а какие поглощающие?

Состояние периодическое с периодом t (t >1), если в него можно вернуться только по истечению времени, кратного t; если такого t нет, то состояние непериодическое. Каждое состояние E_i, для которого p_ii ¹ 0, непериодическое. Поэтому каждое поглощающее состояние непериодическое.

Пример. В задаче о пьянице все состояния непериодические.

Упр. 12. Какой период имеет каждое состояние во 2-й цепи Маркова?

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

Топология

Но все уже тропа становилась, и мрак

Постепенно окутал округу,

Так что сами они не заметили как

Их притерло вплотную друг к другу.

Льюис Кэрролл. Охота на Снарка.