- Цепи Маркова
-
Це́пь Ма́ркова — последовательность случайных событий с конечным или счётным бесконечным числом исходов, характеризующаяся тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего).
Содержание
Цепь Маркова с дискретным временем
Определение
Последовательность дискретных случайных величин называется цепью Маркова (с дискретным временем), если
- .
Таким образом, в простейшем случае условное распределение последующего состояния цепи Маркова зависит только от текущего состояния и не зависит от всех предыдущих состояний (в отличии от цепей Маркова высших порядков).
Область значений случайных величин называется простра́нством состоя́ний цепи, а номер — номером шага.
Переходная матрица и однородные цепи
Матрица P(n), где
называется ма́трицей перехо́дных вероя́тностей на n-м шаге, а вектор , где
— нача́льным распределе́нием цепи Маркова.
Очевидно, матрица переходных вероятностей является стохастической, то есть
- .
Цепь Маркова называется одноро́дной, если матрица переходных вероятностей не зависит от номера шага, то есть
- .
В противном случае цепь Маркова называется неоднородной. В дальнейшем будем предполагать, что имеем дело с однородными цепями Маркова.
Конечномерные распределения и матрица перехода за n шагов
Из свойств условной вероятности и определения однородной цепи Маркова получаем:
- ,
откуда вытекает специальный случай уравнения Колмогорова — Чепмена:
- ,
то есть матрица переходных вероятностей за n шагов однородной цепи Маркова есть n-я степень матрицы переходных вероятностей за 1 шаг. Наконец,
- .
Классификация состояний цепи Маркова
- Возвратное состояние;
- Возвратная цепь Маркова;
- Достижимое состояние;
- Неразложимая цепь Маркова;
- Периодическое состояние;
- Периодическая цепь Маркова;
- Поглощающее состояние;
- Эргодическое состояние.
Примеры
Цепь Маркова с непрерывным временем
Определение
Семейство дискретных случайных величин называется цепью Маркова (с непрерывным временем), если
- .
Цепь Маркова с непрерывным временем называется однородной, если
- .
Матрица переходных функций и уравнение Колмогорова — Чепмена
Аналогично случаю дискретного времени конечномерные распределения однородной цепи Маркова с непрерывным временем полностью определены начальным распределением
и ма́трицей перехо́дных фу́нкций (переходных вероятностей)
- .
Матрица переходных вероятностей удовлетворяет уравнению Колмогорова — Чепмена: или
Pij(t + s) = ∑ Pik(t)Pkj(s) k .
Матрица интенсивностей и дифференциальные уравнения Колмогорова
По определению, матрица интенсивностей или, что эквивалентно,
- .
Из уравнения Колмогорова — Чепмена следуют два уравнения:
Для обоих уравнений начальным условием выбирается . Соответствующее решение
Свойства матриц P и Q
Для любого t > 0 матрица обладает следующими свойствами.
- Матричные элементы неотрицательны: (неотрицательность вероятностей).
- Сумма элементов в каждой строке равна 1:
∑ Pij(t) = 1 j (полная вероятность), то есть матрица является стохастической справа (или по строкам).
- Все собственные числа λ матрицы не превосходят 1 по абсолютной величине: . Если | λ | = 1, то λ = 1.
- Собственному числу λ = 1 матрицы соответствует, как минимум, один неотрицательный левый собственный вектор-строка (равновесие): .
- Для собственного числа λ = 1 матрицы все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.
Матрица обладает следующими свойствами.
- Внедиагональные матричные элементы неотрицательны: .
- Диагональные матричные элементы неположительны: .
- Сумма элементов в каждой строке равна 0:
∑ qij = 0 j .
- Действительная часть всех собственных чисел μ матрицы неположительна: . Если Re(μ) = 0, то μ = 0.
- Собственному числу μ = 0 матрицы соответствует, как минимум, один неотрицательный левый собственный вектор-строка (равновесие): .
- Для собственного числа μ = 0 матрицы все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.
Граф переходов, связность и эргодические цепи Маркова
Для цепи Маркова с непрерывным временем строится ориентированный граф переходов (кратко — граф переходов) по следующим правилам:
- Множество вершин графа совпадает со множеством состояний цепи.
- Вершины соединяются ориентированным ребром , если qij > 0 (то есть интенсивность потока из iго состояния в jе положительна.
Топологические свойства графа переходов связаны со спектральными свойствами матрицы . В частности, для конечных цепей Маркова верны следующие теоремы:
- Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют слабо эргодическими):
- А. Для любых двух различных вершин графа переходов найдется такая вершина k графа («общий сток»), что существуют ориентированные пути от вершины i к вершине k и от вершины j к вершине k. Замечание: возможен случай k = i или k = j; в этом случае тривиальный (пустой) путь от i к i или от j к j также считается ориентированным путем.
- Б. Нулевое собственное число матрицы невырождено.
- В. При матрица стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
- Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют эргодическими):
- А. Граф переходов цепи ориентированно связен.
- Б. Нулевое собственное число матрицы невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение).
- В. Для некоторого t > 0 матрица строго положительна (то есть Pij(t) > 0 для всех i,j).
- Г. Для всех t > 0 матрица строго положительна.
- Д. При матрица стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
Примеры
Расмотрим цепи Маркова с тремя состояниями и с непрерывным временем, соответствующие графам переходов, представленным на рис. В случае (a) отличны от нуля только следующие недиагональные элементы матрицы интенсивностей — , в случае (b) отличны от нуля только , а в случае (c) — . Остальные элементы определяются свойствами матрицы (сумма элементов в каждой строке равна 0). В результате для графов (a), (b), (c) матрицы интенсивностей имеют вид:
Основное кинетическое уравнение
Основное кинетическое уравнение описывает эволюцию распределения вероятностей в цепи Маркова с непрерывным временем. «Основное уравнение» здесь — не эпитет, а перевод термина англ. Master equation. Для вектора-строки распределения вероятностей π основное кинетическое уравнение имеет вид:
и совпадает, по существу, с прямым уравнением Колмогорова. В физической литературе чаще используют векторы-столбцы вероятностей и записывают основное кинетическое уравнение в виде, который явно использует закон сохранения полной вероятности:
где Tij = qji.
Если для основного кинетического уравнения существует положительное равновесие , то его можно записать в форме
Функции Ляпунова для основного кинетического уравнения
Для основного кинетического уравнения существует богатое семейство выпуклых функций Ляпунова — монотонно меняющихся со временем функций распределения вероятностей. Пусть - выпуклая функция одного переменного. Для любого положительного распределения вероятностей (pi > 0) определим функцию Моримото Hh(p):
- .
Производная Hh(p) по времени, если p(t) удовлетворяет основному кинетическому уравнению, есть
- .
Последнее неравенство справедливо из-за выпуклости h(x).
Примеры функций Моримото Hh(p)
- h(x) = | x − 1 | , ;
- эта функция — расстояние от текущего распределения вероятностей до равновесного в l1-норме. Сдвиг по времени является сжатием пространства вероятностных распределений в этой норме. (О свойствах сжатий см. статью Теорема Банаха о неподвижной точке.)
- h(x) = xlnx, ;
- эта функция — (минус) энтропия Кульбака (см. Расстояние Кульбака — Лейблера). В физике она соответствует свободной энергии, деленной на kT (где k - постоянная Больцмана, T - абсолютная температура):
- если (распределение Больцмана), то
- .
- h(x) = − lnx, ;
- эта функция — аналог свободной энергии для энтропии Бурга, широко испльзуемой в обработке сигналов:
SBurg = ∑ lnpi i - , ;
- это квадратичное приближение для (минус) энтропии Кульбака вблизи точки равновесия. С точностью до постоянного во времени слагаемого эта функция совпадает с (минус) энтропией Фишера, которую даёт следующий выбор,
- , ;
- это (минус) энтропия Фишера.
- , ;
- это один из аналогов свободной энергии для энтропии Тсаллиса. Энтропия Тсаллиса (Tsallis entropy)
- служит основой для статистической физики неэкстенсивных величин. При она стремится к классической энтропии Больцмана — Гиббса — Шеннона, а соответствующая функция Моримото — к (минус) энтропии Кульбака.
Литература
- Марков А. А., Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 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 Pavel, Monotonically equivalent entropies and solution of additivity equation, Physica A 328 (2003), 380—390. arXiv e-print
Классификация состояний и цепей Маркова Состояние: апериодическое | возвратное | достижимое | невозвратное | несущественное | нулевое | периодическое | положительное | сообщающееся | существенное Цепь: апериодическая | возвратная | невозвратная | неразложимая | нулевая | периодическая | положительная | разложимая | эргодическая
Wikimedia Foundation. 2010.