🔀 Дискретка

Матрица перехода цепи Маркова

Q: Как связаны матрица перехода и умножение матриц из линейной алгебры?

Напрямую: элемент $p^{(n)}_{ij}$ матрицы $P^n$ — вероятность за $n$ шагов из $i$ в $j$, а умножение — это закон полной вероятности по промежуточным состояниям. Динамика распределения — итерации линейного оператора, поэтому сходимость цепи Маркова — это спектральная история про собственное значение 1 и второе по модулю значение.

англ. Markov transition matrix

Матрица $P = (p_{ij})$ одношаговых вероятностей переходов цепи Маркова: строки (или столбцы — вторая конвенция) суммируются в единицу. Умножение на $P$ двигает распределение на шаг, степени $P^n$ — на $n$ шагов.

Матрица перехода цепи Маркова — таблица одношаговых вероятностей: $p_{ij}$ — вероятность за один шаг попасть из состояния $i$ в состояние $j$ . Каждая строка — полная группа событий, поэтому сумма по строке равна 1 — свойство стохастичности. Распределение по состояниям удобно держать строкой $π$ , и тогда шаг цепи — умножение: $π_{n + 1} = π_{n} P$ . Оговорим вторую конвенцию сразу: в части учебников вероятности пишут $p_{ij}$ «из $j$ в $i$ », распределения берут столбцами, и тогда столбцы суммируются в 1, а шаг выглядит как $p_{n + 1} = P p_{n}$ . Обе легальны, формулы — зеркальные; ошибка начинается, когда в одном решении смешивают обе. Далее работаем в строчной конвенции.

Интуиция: матрица перехода — правила настольной игры, где вместо кубика — вероятности. Хочешь знать позицию через два хода — просуммируй все способы попасть через промежуточное состояние: это в точности умножение матриц, $P^{2}$ , а через $n$ ходов — $P^{n}$ . Знаменитое следствие — эргодическая теорема: у регулярной цепи $P^{n}$ сходится к матрице с одинаковыми строками, и куда бы система ни стартовала, распределение съезжает к одному и тому же стационарному $π$ , которое решает уравнение $π P = π$ . Стационарное распределение — собственный вектор матрицы (левый, с собственным значением 1), так что теория матриц работает на вероятности напрямую.

j \sum p_{ij} = 1, π_{n + 1} = π_{n} P, π P = π, i \sum π_{i} = 1

стохастичность по строкам, шаг цепи и уравнение стационарного распределения; при столбцовой конвенции всё то же с транспонированием:

\sum_{i} p_{ij} = 1

p_{n + 1} = P p_{n}

Микропример — погода из двух состояний: солнечно и дождь, $P = (0.8 0.3 0.2 0.7)$ : после солнечного дня дождь с шансом $0.2$ , после дождливого — солнце с шансом $0.3$ . Строки дают $0.8 + 0.2 = 1$ и $0.3 + 0.7 = 1$ . Стартуем из солнца: $π_{0} = (1, 0)$ , тогда $π_{1} = (0.8, 0.2)$ , а $P^{2} = (0.7 0.45 0.3 0.55)$ , то есть $π_{2} = (0.7, 0.3)$ . Стационар: из $π P = π$ выходит $0.3 π_{2} = 0.2 π_{1}$ , то есть $π = (0.6, 0.4)$ — проверка: $0.6 \cdot 0.8 + 0.4 \cdot 0.3 = 0.6$ . Характеристический многочлен: $λ^{2} - 1.5 λ + 0.5 = (λ - 1) (λ - 0.5)$ , и отклонение от стационара гасится как $0. 5^{n}$ : $π_{1} - π = (0.2, - 0.2) = (0.4, - 0.4) \cdot 0.5$ , $π_{2} - π = (0.1, - 0.1) = (0.4, - 0.4) \cdot 0.25$ .

Базовая теория и примеры — в термине цепь Маркова; условный характер переходов — условная вероятность. Стационар ищется как собственный вектор, а степени $P^{n}$ достаются через диагонализацию — линейная алгебра здесь главный инструмент. Состояния и переходы как модель автоматов — урок конечные автоматы; сводка формул — в шпаргалке по вероятностям.

Частые вопросы

Почему у регулярной цепи существует и единственно стационарное распределение?

Единица — всегда собственное значение стохастической матрицы (по строкам и по столбцам суммы дают 1, спектральный радиус равен 1), а неразложимость и апериодичность регулярной цепи гарантируют, что все остальные значения по модулю строго меньше: компоненты при них гаснут как $λ_{2}^{n}$ , остаётся вклад собственного значения 1. Он и даёт уникальное $π$ с $π P = π$ .

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

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