Цепь Маркова

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

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

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

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

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

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

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

Конечномерные распределения и матрица перехода за n шагов 
Из свойств условной вероятности и определения однородной цепи Маркова получаем:
 ,
откуда вытекает специальный случай уравнения Колмогорова — Чепмена:
 ,
то есть матрица переходных вероятностей за  шагов однородной цепи Маркова есть -я степень матрицы переходных вероятностей за 1 шаг. Наконец,
 .

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

Примеры 
 Ветвящийся процесс;
 Случайное блуждание;

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

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

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

Матрица переходных функций и уравнение Колмогорова — Чепмена 
Аналогично случаю дискретного времени, конечномерные распределения однородной цепи Маркова с непрерывным временем полностью определены начальным распределением
 
и ма́трицей перехо́дных фу́нкций (переходных вероятностей)
 .
Матрица переходных вероятностей удовлетворяет уравнению Колмогорова — Чепмена:  или

Матрица интенсивностей и дифференциальные уравнения Колмогорова 
По определению матрица интенсивностей , или, что эквивалентно,
 .
Из уравнения Колмогорова — Чепмена следуют два уравнения:
 Прямое уравнение Колмогорова
 
 Обратное уравнение Колмогорова
 
Для обоих уравнений начальным условием выбирается . Соответствующее решение

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

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

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

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

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

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

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

Примеры 

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

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

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

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

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

Примеры функций Моримото  
 , ;
 эта функция — расстояние от текущего распределения вероятностей до равновесного в -норме. Сдвиг по времени является сжатием пространства вероятностных распределений в этой норме. (О свойствах сжатий см. статью Теорема Банаха о неподвижной точке.)
 , ;
 эта функция — (минус) энтропия Кульбака (см. Расстояние Кульбака — Лейблера). В физике она соответствует свободной энергии, деленной на  (где  — постоянная Больцмана,  — абсолютная температура):
 если  (распределение Больцмана), то
 .
 , ;
 эта функция — аналог свободной энергии для энтропии Бурга, широко используемой в обработке сигналов:
 
 , ;
 это квадратичное приближение для (минус) энтропии Кульбака вблизи точки равновесия. С точностью до постоянного во времени слагаемого эта функция совпадает с (минус) энтропией Фишера, которую даёт следующий выбор,
 , ;
 это (минус) энтропия Фишера.
 , ;
 это один из аналогов свободной энергии для .
 
 служит основой для статистической физики неэкстенсивных величин. При  она стремится к классической энтропии Больцмана — Гиббса — Шеннона, а соответствующая функция Моримото — к (минус) энтропии Кульбака.

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

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

Примечания

Литература 
 
 Марков А. А., Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 2-я серия. — Том 15. (1906) — С. 135—156.
 
 Kemeny J. G., Snell J. L., Finite Markov chains. — The University Series in Undergraduate Mathematics. — Princeton: Van Nostrand, 1960
 Перевод: Кемени Дж. Дж., Снелл Дж. Л. Конечные цепи Маркова. — М.: Наука. 1970. — 272 с.
 Чжун Кай-лай Однородные цепи Маркова. Перев. с англ. — М.: Мир, 1964. — 425 с.
 Нуммелин Э., Общие неприводимые цепи Маркова и неотрицательные операторы. — М.: Мир, 1989. — 207 с.
 Morimoto T., Markov processes and the H-theorem. — J. Phys. Soc. Jap. 12 (1963), 328—331.
 Яглом А. М., Яглом И. М., Вероятность и информация. — М., Наука, 1973. — 512 с.
 Kullback S., Information theory and statistics. — Wiley, New York, 1959.
 Burg J.P., The Relationship Between Maximum Entropy Spectra and Maximum Likelihood Spectra, Geophysics 37(2) (1972), 375—376.
 Tsallis C., Possible generalization of Boltzmann-Gibbs statistics. J. Stat. Phys. 52 (1988), 479—487.
 Рудой Ю. Г., Обобщенная информационная энтропия и неканоническое распределение в равновесной статистической механике, ТМФ, 135:1 (2003), 3-54.
 Gorban, Alexander N.; Gorban, Pavel A.; Judge, George. Entropy: The Markov Ordering Approach. Entropy 12, no. 5 (2010), 1145—1193.

Ссылки 
 

Марковские процессы