Марковские цепи и стационарные распределения в оптимизации стохастических систем

Математически Марковская цепь с дискретным временем и конечным пространством состояний полностью определяется матрицей переходных вероятностей $P$, где элемент $p_{ij}$ обозначает вероятность перехода из состояния $i$ в состояние $j$ за один шаг. Динамика изменения распределения вероятностей системы описывается матричным умножением: вектор вероятностей на шаге $n+1$ равен вектору вероятностей на шаге $n$, умноженному на матрицу $P$. Центральной концепцией здесь является стационарное распределение $\pi$ — такой вектор вероятностей, который не меняется с течением времени, удовлетворяя уравнению $\pi P = \pi$. Поиск стационарного распределения сводится к вычислению левого собственного вектора матрицы переходов, соответствующего собственному значению, равному единице.

Для того чтобы стационарное распределение существовало и было единственным (независимо от начального состояния системы), Марковская цепь должна быть эргодической: неразложимой (из любого состояния можно попасть в любое другое за конечное число шагов) и апериодической. Теорема Перрона-Фробениуса для неотрицательных матриц предоставляет строгие математические гарантии сходимости системы к равновесию. В задачах оптимизации сетей массового обслуживания (например, при проектировании узлов связи или колл-центров) именно элементы вектора стационарного распределения определяют среднюю долю времени, которую система проводит в состоянии перегрузки, что является главным критерием для минимизации потерь.

Глубоким приложением теории Марковских цепей в вычислительной оптимизации являются методы Монте-Карло для марковских цепей (Markov Chain Monte Carlo, MCMC). Алгоритмы Метрополиса-Гастингса и сэмплирование по Гиббсу позволяют генерировать выборки из сложнейших многомерных распределений (например, в байесовском машинном обучении), для которых невозможно вычислить аналитический интеграл. Идея MCMC состоит в искусственном конструировании такой эргодической Марковской цепи, для которой целевое (трудновычислимое) распределение является стационарным. Моделируя блуждание по этой цепи в течение достаточно долгого времени (период burn-in), алгоритм начинает выдавать состояния, строго соответствующие искомому распределению.

Теория Марковских цепей также является базой для метаэвристических алгоритмов глобальной оптимизации, таких как имитация отжига (Simulated Annealing). В этих алгоритмах процесс поиска оптимума формализуется как нестационарная Марковская цепь, матрица переходов которой медленно изменяется со временем (снижение температуры). Строгий математический анализ сходимости алгоритма отжига доказывает, что при логарифмически медленном охлаждении система гарантированно достигает стационарного распределения, сосредоточенного исключительно в точках глобального минимума целевой функции. Владение аппаратом Марковских процессов выводит инженера-оптимизатора на уровень, где стохастический хаос подчиняется строгим законам матричной алгебры.

Список литературы:
1. Кемени Дж., Снелл Дж. Конечные цепи Маркова. — М.: Наука, 1970.
2. Ширяев А.Н. Вероятность. — М.: МЦНМО, 2004.
3. Robert C.P., Casella G. Monte Carlo Statistical Methods. — Springer, 2004.