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

Цепь Маркова с дискретным временем

Определение

Последовательность дискретных случайных величин называется простой цепью Маркова (с дискретным временем), если

.

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

Область значений случайных величин называется простра́нством состоя́ний цепи, а номер — номером шага.

Переходная матрица и однородные цепи[править ]

Матрица , где

называется ма́трицей перехо́дных вероя́тностей на -м шаге, а вектор , где

— нача́льным распределе́нием цепи Маркова.

Очевидно, матрица переходных вероятностей является стохастической, то есть

.

Цепь Маркова называется одноро́дной, если матрица переходных вероятностей не зависит от номера шага, то есть

.

В противном случае цепь Маркова называется неоднородной. В дальнейшем будем предполагать, что имеем дело с однородными цепями Маркова.

Конечномерные распределения и матрица перехода за n шагов

Из свойств условной вероятности и определения однородной цепи Маркова получаем:

,

откуда вытекает специальный случай уравнения Колмогорова — Чепмена:

,

то есть матрица переходных вероятностей за шагов однородной цепи Маркова есть -я степень матрицы переходных вероятностей за 1 шаг. Наконец,

.

Классификация состояний цепи Маркова

• Возвратное состояние;
• Возвратная цепь Маркова;
• Достижимое состояние;
• Неразложимая цепь Маркова;
• Периодическое состояние;
• Периодическая цепь Маркова;
• Поглощающее состояние;
• Эргодическое состояние.

Примеры

• Ветвящийся процесс;
• Случайное блуждание;
• В сериале 4исла (Numb3rs) на примере цепи Маркова пытаются раскрыть побег двух заключенных. Первый сезон, 13 эпизод

Цепь Маркова с непрерывным временем

Определение

Семейство дискретных случайных величин называется цепью Маркова (с непрерывным временем), если

.

Цепь Маркова с непрерывным временем называется однородной, если

.

Матрица переходных функций и уравнение Колмогорова — Чепмена

Аналогично случаю дискретного времени, конечномерные распределения однородной цепи Маркова с непрерывным временем полностью определены начальным распределением

и ма́трицей перехо́дных фу́нкций (переходных вероятностей)

.

Матрица переходных вероятностей удовлетворяет уравнению Колмогорова — Чепмена: или

Матрица интенсивностей и дифференциальные уравнения Колмогорова

По определению, матрица интенсивностей или, что эквивалентно,

.

Из уравнения Колмогорова — Чепмена следуют два уравнения:

• Прямое уравнение Колмогорова

  

• Обратное уравнение Колмогорова

  

Для обоих уравнений начальным условием выбирается . Об этом говорит сайт https://intellect.icu . Соответствующее решение

Свойства матриц P и Q[править ]

Для любого матрица обладает следующими свойствами:

1. Матричные элементы неотрицательны: (неотрицательность вероятностей).
2. Сумма элементов в каждой строке равна 1: (полная вероятность), то есть матрица является стохастической справа (или по строкам).
3. Все собственные числа матрицы не превосходят 1 по абсолютной величине: . Если , то .
4. Собственному числу матрицы соответствует, как минимум, один неотрицательный левый собственный вектор-строка (равновесие): .
5. Для собственного числа матрицы все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

Матрица обладает следующими свойствами:

1. Внедиагональные матричные элементы неотрицательны: .
2. Диагональные матричные элементы неположительны: .
3. Сумма элементов в каждой строке равна 0:
4. Действительная часть всех собственных чисел матрицы неположительна: . Если , то
5. Собственному числу матрицы соответствует, как минимум, один неотрицательный левый собственный вектор-строка (равновесие):
6. Для собственного числа матрицы все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

Граф переходов, связность и эргодические цепи Маркова

Для цепи Маркова с непрерывным временем строится ориентированный граф переходов (кратко — граф переходов) по следующим правилам:

• Множество вершин графа совпадает со множеством состояний цепи.
• Вершины соединяются ориентированным ребром , если (то есть интенсивность потока из -го состояния в -е положительна.

Топологические свойства графа переходов связаны со спектральными свойствами матрицы . В частности, для конечных цепей Маркова верны следующие теоремы:

• Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют слабо эргодическими):

А. Для любых двух различных вершин графа переходов найдется такая вершина графа («общий сток»), что существуют ориентированные пути от вершины к вершине и от вершины к вершине . Замечание: возможен случай или ; в этом случае тривиальный (пустой) путь от к или от к также считается ориентированным путем.

Б. Нулевое собственное число матрицы невырождено.

В. При матрица стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

• Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют эргодическими):

А. Граф переходов цепи ориентированно связен.

Б. Нулевое собственное число матрицы невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение).

В. Для некоторого матрица строго положительна (то есть для всех ).

Г. Для всех матрица строго положительна.

Д. При матрица стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

Примеры

Рассмотрим цепи Маркова с тремя состояниями и с непрерывным временем, соответствующие графам переходов, представленным на рис. В случае (a) отличны от нуля только следующие недиагональные элементы матрицы интенсивностей — , в случае (b) отличны от нуля только , а в случае (c) — . Остальные элементы определяются свойствами матрицы (сумма элементов в каждой строке равна 0). В результате для графов (a), (b), (c) матрицы интенсивностей имеют вид:

Основное кинетическое уравнение

Основное кинетическое уравнение описывает эволюцию распределения вероятностей в цепи Маркова с непрерывным временем. «Основное уравнение» здесь — не эпитет, а перевод термина англ. Master equation. Для вектора-строки распределения вероятностей основное кинетическое уравнение имеет вид:

и совпадает, по существу, с прямым уравнением Колмогорова. В физической литературе чаще используют векторы-столбцы вероятностей и записывают основное кинетическое уравнение в виде, который явно использует закон сохранения полной вероятности:

где

Если для основного кинетического уравнения существует положительное равновесие , то его можно записать в форме

Функции Ляпунова для основного кинетического уравнения

Для основного кинетического уравнения существует богатое семейство выпуклых функций Ляпунова — монотонно меняющихся со временем функций распределения вероятностей. Пусть — выпуклая функция одного переменного. Для любого положительного распределения вероятностей () определимфункцию Моримото :

.

Производная по времени, если удовлетворяет основному кинетическому уравнению, есть

.

Последнее неравенство справедливо из-за выпуклости .

Примеры функций Моримото [править ]

• , ;

эта функция — расстояние от текущего распределения вероятностей до равновесного в -норме. Сдвиг по времени является сжатием пространства вероятностных распределений в этой норме. (О свойствах сжатий см. статью Теорема Банаха о неподвижной точке.)

• , ;

эта функция — (минус) энтропия Кульбака (см. Расстояние Кульбака — Лейблера). В физике она соответствует свободной энергии, деленной на (где —постоянная Больцмана, — абсолютная температура):

если (распределение Больцмана), то

.

• , ;

эта функция — аналог свободной энергии для энтропии Бурга, широко используемой в обработке сигналов:

• , ;

это квадратичное приближение для (минус) энтропии Кульбака вблизи точки равновесия. С точностью до постоянного во времени слагаемого эта функция совпадает с (минус) энтропией Фишера, которую дает следующий выбор,

• , ;

это (минус) энтропия Фишера.

• , ;

это один из аналогов свободной энергии для энтропии Тсаллиса. Энтропия Тсаллиса (Tsallis entropy)

служит основой для статистической физики неэкстенсивных величин. При она стремится к классической энтропии Больцмана — Гиббса — Шеннона, а соответствующая функция Моримото — к (минус) энтропии Кульбака.

Практическое применение

Одной из первых научных дисциплин, в которой цепи Маркова нашли практическое применение, стала лингвистика (в частности текстология). Сам Марков для иллюстрации своих результатов исследовал зависимость в чередовании гласных и согласных в первых главах «Евгения Онегина» и «Детских годов Багрова-внука» ].