Цепь Маркова

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

Пример цепи с двумя состояниями

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

править

Определение

править

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

 .

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

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

Переходная матрица и однородные цепи

править

Матрица  , где

 

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

 

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

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

 .

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

 .

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

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

править

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

 ,

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

 ,

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

 .

Типы состояний

править

Примеры

править

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

править

Определение

править

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

 .

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

 .

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

править

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

 

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

 .

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

 

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

править

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

 .

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

Для обоих уравнений начальным условием выбирается  . Соответствующее решение  

Свойства матриц P и Q

править

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

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

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

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

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

править

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

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

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

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

Примеры

править
 
Рис. Примеры графов переходов для цепей Маркова: a) цепь не является слабо эргодической (не существует общего стока для состояний  ); b) слабо эргодическая цепь (граф переходов не является ориентированно связным) c) эргодическая цепь (граф переходов ориентированно связан).

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

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

править

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

 

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

 

где  

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

 

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

править

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

 .

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

 .

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

Примеры функций Моримото  

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

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

править

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

Примечания

править
  1. "Markov chain | Definition of Markov chain in US English by Oxford Dictionaries" (англ.). Oxford Dictionaries | English.. Lexico Dictionaries | English (14 декабря 2017). Дата обращения: 1 апреля 2020. Архивировано из оригинала 25 февраля 2021 года.
  2. Gagniuc, Paul A. Markov Chains: From Theory to Implementation and Experimentation (англ.). — USA, NJ: John Wiley & Sons, 2017. — P. 2—8. — ISBN 978-1-119-38755-8.
  3. Майстров, Л. Е. Развитие понятия вероятности. — Наука, 1980. — С. 188. — 269 с.

Литература

править
  • Кельберт М. Я., Сухов Ю. М. Вероятность и статистика в примерах и задачах. Т. ІІ: Марковские цепи как отправная точка теории случайных процессов и их приложения. — М.: МЦНМО, 2010. — 295 с. — ISBN 978-5-94057-252-7.
  • Марков А. А., Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 2-я серия. — Том 15. (1906) — С. 135—156.
  • Маркова цепь / А. В. Прохоров // Большая российская энциклопедия : [в 35 т.] / гл. ред. Ю. С. Осипов. — М. : Большая российская энциклопедия, 2004—2017.
  • 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.

Ссылки

править