Цепь Маркова — это математическая модель случайного процесса, который по шагам переходит между состояниями, и вероятность следующего состояния зависит только от текущего, а не от всей предыстории. Это свойство называют беспамятностью, или свойством Маркова.
Содержание
В этой статье рассматриваем конечную однородную цепь Маркова с дискретным временем: система ходит по конечному набору состояний, а вероятности переходов не меняются от шага к шагу. В общем случае дискретная цепь может иметь конечное или счетное пространство состояний, но конечный случай удобнее записать матрицей и прогнать в коде.
Ниже разберем, что такое состояния и матрица переходов, как задать цепь в коде и прогнать симуляцию, что такое стационарное распределение и когда оно единственно. Все примеры на Python запущены, вывод в тексте — реальный.
Что такое цепь Маркова
В основе модели лежит одно допущение. Если известно, в каком состоянии система находится сейчас, то для прогноза будущего прошлое уже не добавляет информации. Формально: вероятность перейти в следующее состояние зависит только от текущего.
Это и есть свойство Маркова. Оно резко упрощает описание: вместо всей истории достаточно хранить одно текущее состояние и правила перехода из него.
Стоит развести два близких термина. Марковский процесс — общее семейство процессов со свойством Маркова, время и пространство состояний могут быть непрерывными. Цепь Маркова — частный случай с дискретным набором состояний; в этой статье время тоже дискретное (шаги), а вероятности переходов не меняются со временем (такую цепь называют однородной).
Простой пример — смена погоды по дням, огрубленная до трех состояний: ясно, облачно, дождь. Завтрашняя погода в этой модели зависит только от сегодняшней, а не от всей недели. Это упрощение: реальная погода зависит от многих факторов, но для демонстрации механики цепи его достаточно.
Состояния и матрица переходов
Состояния — это возможные положения системы (у нас их три). Правила перехода задают матрицей переходов P: в ней элемент в строке i и столбце j — это вероятность за один шаг перейти из состояния i в состояние j.
Ключевое ограничение: каждая строка матрицы — это распределение вероятностей, поэтому сумма по строке равна 1 (из любого состояния мы куда-то обязательно перейдем, возможно, в то же самое). На столбцы такого условия нет.
Зададим матрицу для погоды:
| Из \ В | ясно | облачно | дождь |
|---|---|---|---|
| ясно | 0.7 | 0.2 | 0.1 |
| облачно | 0.3 | 0.4 | 0.3 |
| дождь | 0.2 | 0.5 | 0.3 |
Читается по строкам: если сегодня ясно, то завтра с вероятностью 0.7 снова ясно, 0.2 — облачно, 0.1 — дождь. Если сегодня дождь, то шанс, что завтра прояснится, всего 0.2.
Симуляция цепи Маркова
Самый наглядный способ увидеть, как работает цепь — прогнать ее много шагов и посчитать, какую долю времени система провела в каждом состоянии. Ниже полная программа: она проверяет корректность матрицы, а затем делает 100 000 шагов из состояния «ясно».
import random
# Состояния погоды: 0 = ясно, 1 = облачно, 2 = дождь
states = ["ясно", "облачно", "дождь"]
# Матрица переходов P: P[i][j] = вероятность перейти из i в j за один шаг
P = [
[0.7, 0.2, 0.1], # из "ясно"
[0.3, 0.4, 0.3], # из "облачно"
[0.2, 0.5, 0.3], # из "дождь"
]
# Проверка корректности: каждая строка - распределение, сумма = 1
for i, row in enumerate(P):
assert abs(sum(row) - 1.0) < 1e-9, f"строка {i} не дает в сумме 1"
print("матрица корректна: все строки в сумме дают 1")
def next_state(current, rng):
r = rng.random()
acc = 0.0
for j, p in enumerate(P[current]):
acc += p
if r < acc:
return j
return len(P) - 1 # страховка от ошибок округления
rng = random.Random(42)
current = 0 # старт из "ясно"
counts = [0, 0, 0]
N = 100000
for _ in range(N):
current = next_state(current, rng)
counts[current] += 1
print("доля времени в каждом состоянии за", N, "шагов:")
for name, c in zip(states, counts):
print(f" {name}: {c / N:.3f}")Вывод программы (сид фиксирован, число воспроизводится):
матрица корректна: все строки в сумме дают 1
доля времени в каждом состоянии за 100000 шагов:
ясно: 0.464
облачно: 0.328
дождь: 0.208
Функция next_state работает как рулетка: берет случайное число от 0 до 1 и по накопленным вероятностям строки решает, куда шагнуть. Доли времени 0.464, 0.328 и 0.208 — это оценка того, как часто система бывает в каждом состоянии на длинной дистанции.
Стационарное распределение
Долгосрочные доли из симуляции — не случайность. У «хороших» цепей есть стационарное распределение: такой вектор вероятностей pi, что если применить к нему матрицу переходов, он не изменится. Записывают это как pi = pi P.
Смысл прямой: если система уже распределена по состояниям в пропорции pi, то через шаг пропорция останется той же. Найти pi можно степенной итерацией — взять любое стартовое распределение и прогонять его через матрицу, пока оно не перестанет меняться.
# Стационарное распределение: вектор pi, для которого pi @ P = pi
P = [
[0.7, 0.2, 0.1],
[0.3, 0.4, 0.3],
[0.2, 0.5, 0.3],
]
def vec_mat(v, M):
n = len(M)
return [sum(v[i] * M[i][j] for i in range(n)) for j in range(len(M[0]))]
# Метод степенной итерации: гоняем любое стартовое распределение через P,
# пока оно не перестанет меняться
pi = [1.0, 0.0, 0.0] # старт "ясно" с вероятностью 1
for step in range(1, 61):
new = vec_mat(pi, P)
diff = max(abs(new[k] - pi[k]) for k in range(len(pi)))
pi = new
if diff < 1e-12:
print(f"сошлось за {step} шагов")
break
else:
# цикл прошел все 60 шагов без break: критерий сходимости не достигнут
raise RuntimeError(
"степенная итерация не сошлась за 60 шагов - "
"нельзя печатать pi как стационарное распределение"
)
# Проверка стационарности: pi @ P обязано совпасть с pi, иначе это не стационарный вектор
check = vec_mat(pi, P)
is_stationary = all(abs(check[k] - pi[k]) < 1e-9 for k in range(len(pi)))
assert is_stationary, "pi @ P != pi: полученный вектор не стационарен"
print("стационарное распределение:")
for name, p in zip(["ясно", "облачно", "дождь"], pi):
print(f" {name}: {p:.3f}")
print("pi @ P == pi:", is_stationary)Вывод программы:
сошлось за 34 шагов
стационарное распределение:
ясно: 0.466
облачно: 0.328
дождь: 0.207
pi @ P == pi: True
В коде две страховки. Ветка else у цикла срабатывает, если за 60 шагов критерий diff < 1e-12 так и не выполнился: без нее программа напечатала бы последнее приближение как готовый ответ, и на медленно сходящейся или периодической матрице читатель принял бы несошедшееся число за стационарное распределение. Отдельная проверка pi @ P == pi подтверждает, что найденный вектор действительно стационарен, а не просто последнее значение итерации.
Сравним с симуляцией: там доли были 0.464, 0.328, 0.208, здесь — 0.466, 0.328, 0.207. Числа практически совпали, и это не совпадение: у эргодической цепи (о ней ниже) доля времени в состоянии на длинной дистанции стремится к его стационарной вероятности. Разница в третьем знаке — это шум конечной выборки в симуляции.
Важна еще одна деталь: старт был из «ясно» с вероятностью 1, но итерация все равно сошлась к тому же pi. У подходящих цепей стационарное распределение не зависит от начального состояния. Независимость предельного распределения от старта — следствие несводимости и апериодичности в рассматриваемой конечной цепи, а не самого свойства Маркова: марковское свойство — это условная независимость будущего от прошлого при известном настоящем, и цепь может им обладать, оставаясь периодической или распадаясь на несколько замкнутых классов.
Когда стационарное распределение единственно и когда цепь к нему сходится
У любой конечной цепи стационарное распределение существует — вопрос в том, единственно ли оно и сходится ли к нему цепь по шагам. За это отвечают три свойства. Ниже — ориентир, а не строгие формулировки из учебника.
| Свойство | Что значит простыми словами | Что дает |
|---|---|---|
| Несводимость | из любого состояния можно в итоге попасть в любое другое | единственность pi и сходимость временных долей (доли времени в состояниях) |
| Апериодичность | возвраты в состояние не привязаны к жесткому периоду (2, 3, …) | сходимость распределения по шагам, без циклических колебаний |
| Эргодичность | несводимость и апериодичность вместе (для конечной цепи) | распределение состояния на шаге n сходится к pi независимо от старта |
Наша погодная цепь несводима (из любого состояния достижимо любое) и апериодична, поэтому она эргодична — отсюда и совпадение симуляции со стационарным распределением.
Контрпример на границе: если сделать цепь строго периодической (например, состояния меняются по кругу 1 — 2 — 3 — 1 без задержек), то система будет вечно колебаться и к единому распределению не сойдется, хотя формально стационарный вектор у нее посчитать можно. Периодичность — типичная причина, по которой степенная итерация не сходится.
PageRank как цепь Маркова
Классическое применение — алгоритм PageRank, с которого начинался ранжирующий движок Google. Состояния — это веб-страницы, а переходы — клики воображаемого пользователя, который случайно идет по ссылкам: со страницы он с равной вероятностью выбирает одну из исходящих ссылок.
Это ровно цепь Маркова: следующая страница зависит только от текущей. Стационарное распределение такой цепи и есть вектор PageRank — чем выше стационарная вероятность страницы, тем чаще на нее заходят и тем она «важнее».
В PageRank добавляют демпфирование: с небольшой вероятностью пользователь прыгает на случайную страницу, а не идет по ссылке. Это чинит тупики (страницы без исходящих ссылок) и делает модифицированную цепь несводимой и апериодичной, поэтому вектор PageRank единственен, а степенная итерация к нему сходится. Стационарное распределение у конечной цепи есть и без демпфирования — оно обеспечивает именно единственность вектора и устойчивую сходимость итерации, а не само существование.
Выводы
- Цепь Маркова — это модель переходов между дискретными состояниями, где следующее состояние зависит только от текущего (свойство Маркова, беспамятность).
- Правила задают матрицей переходов: элемент — вероятность перехода из строки-состояния в столбец-состояние, сумма каждой строки равна 1.
- Стационарное распределение pi не меняется под действием матрицы (pi = pi P); его находят степенной итерацией или из симуляции по долям времени.
- У эргодической цепи (несводимость плюс апериодичность) распределение единственно, не зависит от старта, и симуляция сходится к нему; периодичность эту сходимость ломает.
- PageRank — цепь Маркова на графе ссылок, а вектор важности страниц — ее стационарное распределение.
Где применяется и что учить дальше
Цепи Маркова лежат в основе многих прикладных методов: ранжирование (PageRank), моделирование очередей и надежности, распознавание речи через скрытые марковские модели, а марковские процессы принятия решений — фундамент обучения с подкреплением. Матрица переходов и стационарное распределение — базовый инструмент, который встречается в ML и анализе данных постоянно.
Освойте тему на практике
Если хочется освоить вероятностные модели и машинное обучение системно, с практикой на реальных данных, посмотрите курс Machine Learning. Basic. Оценить уровень и формат до старта помогают бесплатные открытые уроки Otus — живые занятия с преподавателями.
FAQ
Чем цепь Маркова отличается от обычной последовательности случайных величин? В общей случайной последовательности следующее значение может зависеть от всей истории. В цепи Маркова оно зависит только от текущего состояния — это и есть ограничение, которое делает модель простой и вычислимой.
Всегда ли у цепи есть единственное стационарное распределение? Нет. Единственность гарантирует несводимость, а сходимость симуляции к нему — еще и апериодичность. Периодические или распадающиеся на изолированные части цепи этих гарантий не дают.
Обязательно ли число состояний конечно? Нет, бывают цепи со счетным бесконечным числом состояний (например, длина очереди). В этой статье примеры конечные, потому что их удобно записать матрицей и прогнать в коде.
