Це́пь Ма́ркова — последовательность случайных событий с конечным или счётным числом исходов, где вероятность наступления каждого события зависит только от состояния, достигнутого в предыдущем событии. Характеризуется тем свойством, что, говоря нестрого, при текущем настоящем состоянии системы, её будущее состояние не зависит от прошлого. Названа в честь А. А. Маркова (старшего), который впервые ввёл это понятие в работе 1906 года.
В случае цепи Маркова -го порядка вероятность наступления каждого события зависит от состояния, достигнутого в предыдущих событиях.
Цепь Маркова с дискретным временем
Определение Последовательность дискретных случайных величин называется простой цепью Маркова (цепью Маркова первого порядка) (с дискретным временем), если . Таким образом, в простейшем случае условное распределение последующего состояния цепи Маркова зависит только от текущего состояния и не зависит от всех предыдущих состояний (в отличие от цепей Маркова высших порядков).
Последовательность дискретных случайных величин называется цепью Маркова -го порядка (с дискретным временем), если .
Таким образом, в условное распределение последующего состояния цепи Маркова -го порядка зависит от текущего состояния и от предыдущих состояний.
Область значений случайных величин называется простра́нством состоя́ний цепи, а номер — номером шага.
Переходная матрица и однородные цепи Матрица , где
называется ма́трицей перехо́дных вероя́тностей на -м шаге, а вектор , где
— нача́льным распределе́нием цепи Маркова.
Очевидно, матрица переходных вероятностей является стохастической справа, то есть .
Цепь Маркова называется одноро́дной, если матрица переходных вероятностей не зависит от номера шага, то есть . В противном случае цепь Маркова называется неоднородной. В дальнейшем будем предполагать, что имеем дело с однородными цепями Маркова.
Конечномерные распределения и матрица перехода за n шагов Из свойств условной вероятности и определения однородной цепи Маркова получаем: , откуда вытекает специальный случай уравнения Колмогорова — Чепмена: , то есть матрица переходных вероятностей за шагов однородной цепи Маркова есть -я степень матрицы переходных вероятностей за 1 шаг. Наконец, .
Типы состояний Возвратное состояние. Возвратная цепь Маркова. Достижимое состояние. Неразложимая цепь Маркова. Периодическое состояние. Периодическая цепь Маркова. Поглощающее состояние. Состояние называется поглощающим, если . Эргодическое состояние.
Примеры Ветвящийся процесс; Случайное блуждание;
Цепь Маркова с непрерывным временем
Определение Семейство дискретных случайных величин называется цепью Маркова (с непрерывным временем), если .
Цепь Маркова с непрерывным временем называется однородной, если .
Матрица переходных функций и уравнение Колмогорова — Чепмена Аналогично случаю дискретного времени, конечномерные распределения однородной цепи Маркова с непрерывным временем полностью определены начальным распределением
и ма́трицей перехо́дных фу́нкций (переходных вероятностей) . Матрица переходных вероятностей удовлетворяет уравнению Колмогорова — Чепмена: или
Матрица интенсивностей и дифференциальные уравнения Колмогорова По определению матрица интенсивностей , или, что эквивалентно, . Из уравнения Колмогорова — Чепмена следуют два уравнения: Прямое уравнение Колмогорова
Обратное уравнение Колмогорова
Для обоих уравнений начальным условием выбирается . Соответствующее решение
Свойства матриц P и Q Для любого матрица обладает следующими свойствами:
Матричные элементы неотрицательны: (неотрицательность вероятностей). Сумма элементов в каждой строке равна 1: (полная вероятность), то есть матрица является стохастической справа (или по строкам). Все собственные числа матрицы не превосходят 1 по абсолютной величине: . Если , то . Собственному числу матрицы соответствует как минимум один неотрицательный левый собственный вектор-строка (равновесие): . Для собственного числа матрицы все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.
Матрица обладает следующими свойствами:
Внедиагональные матричные элементы неотрицательны: . Диагональные матричные элементы неположительны: . Сумма элементов в каждой строке равна 0: Действительная часть всех собственных чисел матрицы неположительна: . Если , то Собственному числу матрицы соответствует как минимум один неотрицательный левый собственный вектор-строка (равновесие): Для собственного числа матрицы все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.
Граф переходов, связность и эргодические цепи Маркова Для цепи Маркова с непрерывным временем строится ориентированный граф переходов (кратко — граф переходов) по следующим правилам: Множество вершин графа совпадает со множеством состояний цепи. Вершины соединяются ориентированным ребром , если (то есть интенсивность потока из -го состояния в -е положительна).
Топологические свойства графа переходов связаны со спектральными свойствами матрицы . В частности, для конечных цепей Маркова верны следующие теоремы:
Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют слабо эргодическими): А. Для любых двух различных вершин графа переходов найдется такая вершина графа («общий сток»), что существуют ориентированные пути от вершины к вершине и от вершины к вершине . Замечание: возможен случай или ; в этом случае тривиальный (пустой) путь от к или от к также считается ориентированным путём. Б. Нулевое собственное число матрицы невырождено. В. При матрица стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением). Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют эргодическими): А. Граф переходов цепи ориентированно связен. Б. Нулевое собственное число матрицы невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение). В. Для некоторого матрица строго положительна (то есть для всех ). Г. Для всех матрица строго положительна. Д. При матрица стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
Примеры
Рассмотрим цепи Маркова с тремя состояниями и с непрерывным временем, соответствующие графам переходов, представленным на рис. В случае (a) отличны от нуля только следующие недиагональные элементы матрицы интенсивностей — , в случае (b) отличны от нуля только , а в случае (c) — . Остальные элементы определяются свойствами матрицы (сумма элементов в каждой строке равна 0). В результате для графов (a), (b), (c) матрицы интенсивностей имеют вид:
Основное кинетическое уравнение
Основное кинетическое уравнение описывает эволюцию распределения вероятностей в цепи Маркова с непрерывным временем. «Основное уравнение» здесь — не эпитет, а перевод термина . Для вектора-строки распределения вероятностей основное кинетическое уравнение имеет вид:
и совпадает, по существу, с прямым уравнением Колмогорова. В физической литературе чаще используют векторы-столбцы вероятностей и записывают основное кинетическое уравнение в виде, который явно использует закон сохранения полной вероятности:
где
Если для основного кинетического уравнения существует положительное равновесие , то его можно записать в форме
Функции Ляпунова для основного кинетического уравнения Для основного кинетического уравнения существует богатое семейство выпуклых функций Ляпунова — монотонно меняющихся со временем функций распределения вероятностей. Пусть — выпуклая функция одного переменного. Для любого положительного распределения вероятностей () определим функцию Моримото : . Производная по времени, если удовлетворяет основному кинетическому уравнению, есть . Последнее неравенство справедливо из-за выпуклости .
Примеры функций Моримото Hh(p) , ; эта функция — расстояние от текущего распределения вероятностей до равновесного в -норме. Сдвиг по времени является сжатием пространства вероятностных распределений в этой норме. (О свойствах сжатий см. статью Теорема Банаха о неподвижной точке.) , ; эта функция — (минус) энтропия Кульбака (см. Расстояние Кульбака — Лейблера). В физике она соответствует свободной энергии, деленной на (где — постоянная Больцмана, — абсолютная температура): если (распределение Больцмана), то . , ; эта функция — аналог свободной энергии для энтропии Бурга, широко используемой в обработке сигналов:
, ; это квадратичное приближение для (минус) энтропии Кульбака вблизи точки равновесия. С точностью до постоянного во времени слагаемого эта функция совпадает с (минус) энтропией Фишера, которую даёт следующий выбор, , ; это (минус) энтропия Фишера. , ; это один из аналогов свободной энергии для энтропии Тсаллиса.
служит основой для статистической физики неэкстенсивных величин. При она стремится к классической энтропии Больцмана — Гиббса — Шеннона, а соответствующая функция Моримото — к (минус) энтропии Кульбака.
Практическое применение
Одной из первых научных дисциплин, в которой цепи Маркова нашли практическое применение, стала лингвистика (в частности текстология). Сам Марков для иллюстрации своих результатов исследовал зависимость в чередовании гласных и согласных в первых главах «Евгения Онегина» и «Детских годов Багрова-внука».
Цепи Маркова используют для генерации текста, моделирования процессов смешивания сыпучих материалов, управленческом мониторинге, языковых моделях.
Примечания
Литература
Марков А. А. Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 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.
Ссылки
Категория:Марковские процессы