Цепь Маркова

Цепь Маркова — случайный процесс без памяти. Будущее зависит только от настоящего, а не от прошлого: как система попала в текущее состояние — неважно, важно лишь само состояние. Погода, очередь в магазине, фишка на игровом поле — всюду, где «сейчас» определяет вероятности «потом», работает марковская модель. Марковская цепь простыми словами: шагнули в новое состояние — и вся предыстория стёрлась.

Формально пусть $X_0,X_1,X_2,\dots$ — состояния системы в моменты 0, 1, 2, …, каждое из конечного набора $S_1,\dots ,S_m$ (для погоды: «ясно», «дождь»). Цепь называется марковской, если при известном настоящем прошлое не добавляет ничего к прогнозу. Это условная вероятность в её чистом виде:

Числа $p_{ij}$ — переходные вероятности — шанс за один шаг перескочить из $S_i$ в $S_j$. Их собирают в матрицу переходов $P$: по строкам «откуда», по столбцам «куда» (что такое матрица в целом — в статье матрица). Каждая строка — полноценное распределение, поэтому сумма её элементов равна единице.

Что будет через $n$ шагов? Запишем начальное распределение строкой вероятностей — по-математически это вектор ${\pi }^{(0)}$. Тогда ${\pi }^{(n)}={\pi }^{(0)}{P}^n$. Для матрицы выше при ясном старте шанс ясного дня через двое суток: $0.7\cdot 0.7+0.3\cdot 0.4=0.61$.

Главный вопрос про длинную перспективу: к чему всё идёт? Есть распределение, которое не меняется от шага к шагу, — стационарное. Оно удовлетворяет уравнению:

Если из любого состояния достижимо любое другое и цепь не скачет с фиксированным периодом (неразложимость и апериодичность), стационарное распределение существует, единственно, и ${\pi }^{(n)}\to \pi$ независимо от старта. Для погодной матрицы решение $\pi =(4/7,3/7)$: в долгосроке 57% ясных дней и 43% дождливых. Проверьте подстановкой: $\left(\frac{4}{7},\frac{3}{7}\right)\left(\begin{array}{cc}0.7& 0.3\\ 0.4& 0.6\end{array}\right)=\left(\frac{4}{7},\frac{3}{7}\right)$. Вычисление степеней $P^n$ и предельного вектора опирается на ту же технику, что рекуррентные соотношения: каждое следующее состояние получается из предыдущих по фиксированному правилу.

Где это живёт: ранжирование страниц в PageRank — стационарное распределение цепи блуждания по ссылкам; расчёт очередей и запасов на складах; модели отказов и износа техники; алгоритмы MCMC в статистике. По духу это конечные автоматы, в которых переходы случаются с вероятностями, а не жёстко; на графах с пропускными способностями те же идеи работают в задачах о потоках в сетях.

• Погода или спрос: два состояния, матрица $2\times 2$ — найти долю дней каждого типа из $\pi P=\pi$.
• Блуждание по вершинам графа: частица прыгает в случайного соседа — найти частоту посещения каждой вершины.
• Урны с перегородкой: перекладывание случайного шара задаёт матрицу переходов; вопрос — долгосрочное распределение.