марковская цепь

# тег · @ автор · ! учёный

Марковская цепь — стохастическая модель, описывающая последовательность состояний, в которой вероятность перехода в следующее состояние зависит исключительно от текущего состояния (марковское свойство). Формально: P(X_{n+1}=x | X_n=x_n,...,X_0=x_0) = P(X_{n+1}=x | X_n=x_n). Цепи бывают дискретными и непрерывными по времени, с конечным или счётным числом состояний. Основные инструменты: матрица переходных вероятностей, стационарное распределение, уравнения Чепмена–Колмогорова.

История

Российский математик Андрей Марков в начале XX века изучал последовательности зависимых случайных величин и ввёл понятие цепи, чтобы показать, что даже в случайных текстах можно найти статистические закономерности.

Как работает

Как в игре «Змейка» на телефоне, где змея движется по клеткам, выбирая направление случайно, но только из текущей позиции. Если известно, где она сейчас, неважно, как она туда приползла — это свойство отсутствия памяти.

💡 Первым практическим применением цепей Маркова был анализ чередования гласных и согласных в «Евгении Онегине» — Марков показал, что оно не случайно, и предсказал будущие буквы текста.

Марковская цепь — это последовательность событий, где каждое новое событие зависит только от предыдущего, но не от истории дальше. Например, если вы играете в настольную игру, ваш следующий ход зависит лишь от текущей клетки поля, а не от того, как вы на неё попали. Цепь задаётся состояниями (возможные клетки) и вероятностями перехода (шансы перепрыгнуть из одного состояния в другое).

История

Как работает

💡 Цепи Маркова лежат в основе алгоритма PageRank, который изначально принёс успех Google: страницы интернета моделируются как состояния, а переходы — гиперссылки; ранг страницы — стационарная вероятность посещения при случайном блуждании с возвратом.

Марковская цепь — случайный процесс с дискретным временем и конечным или счётным пространством состояний, обладающий марковским свойством: условное распределение будущих состояний зависит только от текущего состояния и не зависит от прошлой траектории. Определяется начальным распределением и матрицей переходных вероятностей P = (p_{ij}), где p_{ij} = P(X_{n+1}=j | X_n=i). Цепь называется однородной, если p_{ij} не зависят от n. Ключевые понятия: классификация состояний (возвратные, невозвратные, периодичность), эргодичность (существование предельного распределения), стационарное распределение π (πP = π). Для неприводимых апериодических конечных цепей существует единственное стационарное распределение, к которому сходятся распределения состояний. Цепи Маркова с непрерывным временем описываются матрицей интенсивностей Q. Применения: алгоритм Метрополиса–Гастингса в Монте-Карло, скрытые марковские модели в распознавании речи, теория массового обслуживания.

История

Андрей Андреевич Марков ввёл цепи в 1906 году, изучая закон больших чисел для зависимых величин. Его мотивировало желание опровергнуть утверждение Некрасова о том, что независимость необходима для статистических законов. Позднее, в 1930-х годах, Колмогоров разработал общую теорию марковских процессов. В середине XX века цепи Маркова стали центральным инструментом в исследованиях операций, физике (модель Изинга) и информатике (генерация текста, PageRank).

Как работает

Математически марковская цепь задаётся начальным вектором вероятностей π^{(0)} и стохастической матрицей P. Тогда распределение после n шагов: π^{(n)} = π^{(0)} P^n. Свойство отсутствия памяти означает, что для предсказания будущего достаточно знать только текущее состояние. Долгосрочное поведение определяется спектральным разложением матрицы P: если ∃ единственный левый собственный вектор с собственным значением 1 (стационарное распределение), то π^{(n)} → π при n→∞. Уравнения Чепмена–Колмогорова: P^{(n+m)} = P^{(n)} P^{(m)}, выражающие композицию переходов. Для непрерывного времени: dπ/dt = πQ, где Q — матрица интенсивностей переходов.

p_{ij}^{(n+m)} = \sum_{k} p_{ik}^{(n)} p_{kj}^{(m)}

p_{ij}^{(n)} — вероятность перехода из состояния i в состояние j за n шагов; суммирование по всем промежуточным состояниям k.

Открытые проблемы и интересные факты

Проблема ускорения сходимости для цепей с медленным смешиванием (например, в многомерных распределениях с острыми пиками).; Разработка эффективных алгоритмов оценки вероятностей редких событий в сложных системах.; Анализ скрытых марковских моделей с непрерывными скрытыми состояниями высокой размерности.

Пока нет статей

марковская цепь

История

Как работает

История

Как работает

История

Как работает

Открытые проблемы и интересные факты

Статьи по теме