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


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

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

Содержание

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

Определение

Последовательность дискретных случайных величин \{X_n\}_{n \geqslant 0} называется цепью Маркова (с дискретным временем), если

\mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n, X_{n-1} = i_{n-1},\ldots,  X_0 = i_0) = \mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n).

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

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

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

Матрица P(n), где

P_{ij}{(n)} \equiv \mathbb{P}(X_{n+1} = j \mid X_n = i)

называется ма́трицей перехо́дных вероя́тностей на n-м шаге, а вектор \mathbf{p} = (p_1,p_2,\ldots)^{\top}, где

p_i \equiv \mathbb{P}(X_0 = i)

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

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

\sum\limits_{j=1}^{\infty} P_{ij}(n) = 1, \quad \forall n \in \mathbb{N}.

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

P_{ij}{(n)} = P_{ij},\quad \forall n \in \mathbb{N}.

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

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

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

\mathbb{P}(X_{n} = i_{n} , \ldots,  X_0 = i_0) = P_{i_{n-1},i_n} \cdots P_{i_0,i_1} p_{i_0},

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

\mathbb{P}(X_n = i_n \mid X_0 = i_0) = (P^n)_{i_0,i_n},

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

\mathbb{P}(X_n = i_n) = \left((P^T)^n \mathbf{p}\right)_{i_n}.

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

Примеры

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

Определение

Семейство дискретных случайных величин \{X_t\}_{t \geqslant 0} называется цепью Маркова (с непрерывным временем), если

\mathbb{P}(X_{t+h} = x_{t+h} \mid X_s = x_s,\; 0 < s \leqslant t ) = \mathbb{P}(X_{t+h} = x_{t+h} \mid X_t = x_t).

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

\mathbb{P}(X_{t+h} = x_{t+h} \mid X_t = x_t) = \mathbb{P}(X_{h} = x_{h} \mid X_0 = x_0).

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

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

\mathbf{p} = (p_1,p_2,\ldots)^{\top},\; p_i = \mathbb{P}(X_0 = i),\quad i=1,2,\ldots

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

\mathbf{P}(h)=(P_{ij}(h)) = \mathbb{P}(X_h = j \mid X_0 = i).

Матрица переходных вероятностей удовлетворяет уравнению Колмогорова — Чепмена: \mathbf{P}(t+s)=\mathbf{P}(t)\mathbf{P}(s) или

Pij(t + s) = Pik(t)Pkj(s)
k

.

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

По определению, матрица интенсивностей \mathbf{Q}=\lim_{h \to 0}\frac{\mathbf{P}(h)-\mathbf{I}}{h} или, что эквивалентно,

\mathbf{Q}=(q_{ij})=\left(\frac{dP_{ij}(h)}{dh}\right)_{h=0}.

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

Для обоих уравнений начальным условием выбирается \mathbf{P}(0)=\mathbf{I}. Соответствующее решение \mathbf{P}(t)=\exp(\mathbf{Q}t).

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

Для любого t > 0 матрица \mathbf{P}(t) обладает следующими свойствами.

  1. Матричные элементы \mathbf{P}(t) неотрицательны: P_{ij}(t) \geqslant 0 (неотрицательность вероятностей).
  2. Сумма элементов в каждой строке \mathbf{P}(t) равна 1:
Pij(t) = 1
j

(полная вероятность), то есть матрица \mathbf{P}(t) является стохастической справа (или по строкам).

  1. Все собственные числа λ матрицы \mathbf{P}(t) не превосходят 1 по абсолютной величине: |\lambda| \leqslant 1. Если | λ | = 1, то λ = 1.
  2. Собственному числу λ = 1 матрицы \mathbf{P}(t) соответствует, как минимум, один неотрицательный левый собственный вектор-строка (равновесие): (p_1^*,\, p_2^*, ...); p_i^* \geqslant 0; \sum_i p_i^*=1; \sum_i p_i^* P_{ij}(t) = p_j^*.
  3. Для собственного числа λ = 1 матрицы \mathbf{P}(t) все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

Матрица \mathbf{Q} обладает следующими свойствами.

  1. Внедиагональные матричные элементы \mathbf{Q} неотрицательны: q_{ij} \geqslant 0 \; i\neq j.
  2. Диагональные матричные элементы \mathbf{Q} неположительны: q_{ii} \leqslant 0.
  3. Сумма элементов в каждой строке \mathbf{Q} равна 0:
qij = 0
j

.

  1. Действительная часть всех собственных чисел μ матрицы \mathbf{Q} неположительна: Re(\mu) \leqslant 0. Если Re(μ) = 0, то μ = 0.
  2. Собственному числу μ = 0 матрицы \mathbf{Q} соответствует, как минимум, один неотрицательный левый собственный вектор-строка (равновесие): (p_1^*,\, p_2^*, ...); p_i^* \geqslant 0; \sum_i p_i^*=1; \sum_i p_i^* q_{ij}= 0.
  3. Для собственного числа μ = 0 матрицы \mathbf{Q} все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

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

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

  • Множество вершин графа совпадает со множеством состояний цепи.
  • Вершины i,j \, (i\neq j) соединяются ориентированным ребром i \to j , если qij > 0 (то есть интенсивность потока из iго состояния в jе положительна.

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

  • Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют слабо эргодическими):
А. Для любых двух различных вершин графа переходов i,j \, (i\neq j) найдется такая вершина k графа («общий сток»), что существуют ориентированные пути от вершины i к вершине k и от вершины j к вершине k. Замечание: возможен случай k = i или k = j; в этом случае тривиальный (пустой) путь от i к i или от j к j также считается ориентированным путем.
Б. Нулевое собственное число матрицы \mathbf{Q} невырождено.
В. При t \to \infty матрица \mathbf{P}(t) стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).
  • Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют эргодическими):
А. Граф переходов цепи ориентированно связен.
Б. Нулевое собственное число матрицы \mathbf{Q} невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение).
В. Для некоторого t > 0 матрица \mathbf{P}(t) строго положительна (то есть Pij(t) > 0 для всех i,j).
Г. Для всех t > 0 матрица \mathbf{P}(t) строго положительна.
Д. При t \to \infty матрица \mathbf{P}(t) стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

Примеры

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

Расмотрим цепи Маркова с тремя состояниями и с непрерывным временем, соответствующие графам переходов, представленным на рис. В случае (a) отличны от нуля только следующие недиагональные элементы матрицы интенсивностей — q_{12}, \, q_{13}, в случае (b) отличны от нуля только q_{12}, \, q_{31}  \, q_{32}, а в случае (c) — q_{12}, \, q_{31}  \, q_{23}. Остальные элементы определяются свойствами матрицы \mathbf{Q} (сумма элементов в каждой строке равна 0). В результате для графов (a), (b), (c) матрицы интенсивностей имеют вид: \mathbf{Q}_a=\begin{pmatrix} -(q_{12}+q_{13})& q_{12} & q_{13}\\  0&  0 &  0 \\  0&  0 &  0 \end{pmatrix}, \mathbf{Q}_b=\begin{pmatrix} -q_{12}& q_{12} & 0 \\  0&  0 &  0 \\  q_{31}&  q_{32} &  -(q_{31}+q_{32}) \end{pmatrix},   \mathbf{Q}_c=\begin{pmatrix} -q_{12}& q_{12} & 0 \\  0&  -q_{23} &  q_{23} \\  q_{31}&  0&  -q_{31} \end{pmatrix},

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

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

\frac{d \pi}{d t} = \pi \mathbf{Q}

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

\frac{d p_i}{d t} = \sum_{j, \, j \neq i} (T_{ij}p_j - T_{ji}p_i),

где Tij = qji.

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

\frac{d p_i}{d t} = \sum_{j, \, j \neq i} T_{ij}p_j^*\left(\frac{p_j}{p_j^*} - \frac{p_i}{p_i^*}\right).

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

Для основного кинетического уравнения существует богатое семейство выпуклых функций Ляпунова — монотонно меняющихся со временем функций распределения вероятностей. Пусть h(x) \, (x>0) - выпуклая функция одного переменного. Для любого положительного распределения вероятностей (pi > 0) определим функцию Моримото Hh(p):

H_h(p)=\sum_i p_i^* h\left(\frac{p_i}{p_i^*}\right).

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

\frac{d H_h(p(t))}{dt }=\sum_{i,j \, i \neq j} T_{ij}p_j^* \left[h\left(\frac{p_i}{p_i^*}\right)- h\left(\frac{p_j}{p_j^*}\right) + h'\left(\frac{p_i}{p_i^*}\right)\left(\frac{p_j}{p_j^*}-\frac{p_i}{p_i^*}\right)\right] \leqslant 0 .

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

Примеры функций Моримото Hh(p)

  • h(x) = | x − 1 | , H_h(p)=\sum_i |p_i-p_i^*|;
эта функция — расстояние от текущего распределения вероятностей до равновесного в l1-норме. Сдвиг по времени является сжатием пространства вероятностных распределений в этой норме. (О свойствах сжатий см. статью Теорема Банаха о неподвижной точке.)
  • h(x) = xlnx, H_h(p)=\sum_i p_i \ln\left(\frac{p_i}{p_i^*}\right);
эта функция — (минус) энтропия Кульбака (см. Расстояние Кульбака — Лейблера). В физике она соответствует свободной энергии, деленной на kT (где k - постоянная Больцмана, T - абсолютная температура):
если p_i^*=\exp(\mu_0-U_i/kT) (распределение Больцмана), то
H_h(p)=\sum_i p_i \ln p_i + \sum_i p_i U_i/kT -\mu_0 = (\langle U \rangle - TS)/kT.
  • h(x) = − lnx, H_h(p)=-\sum_i p_i^* \ln\left(\frac{p_i}{p_i^*}\right);
эта функция — аналог свободной энергии для энтропии Бурга, широко испльзуемой в обработке сигналов:
SBurg = lnpi
i
  • h(x)= \frac{(x-1)^2}{2}, H_h(p)=\sum_i \frac{(p_i-p_i^*)^2}{2p_i^*};
это квадратичное приближение для (минус) энтропии Кульбака вблизи точки равновесия. С точностью до постоянного во времени слагаемого эта функция совпадает с (минус) энтропией Фишера, которую даёт следующий выбор,
  • h(x)= \frac{x^2}{2}, H_h(p)=\sum_i \frac{p_i^2}{2p_i^*};
это (минус) энтропия Фишера.
  • h(x)= \frac{x^q - 1}{q-1}, \, q>0, \, q\neq 1, H_h(p)=\frac{1}{q-1}\left[\sum_i p_i^* \left(\frac{p_i}{p_i^*}\right)^q - 1\right];
это один из аналогов свободной энергии для энтропии Тсаллиса. Энтропия Тсаллиса (Tsallis entropy)
S_{q {\rm Tsallis}}(p) = {1 \over q - 1} \left( 1 - \sum_i p^q_i \right).
служит основой для статистической физики неэкстенсивных величин. При q \to 1 она стремится к классической энтропии Больцмана — Гиббса — Шеннона, а соответствующая функция Моримото — к (минус) энтропии Кульбака.

Литература

  • Марков А. А., Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 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.

Смотреть что такое "Марковские цепи" в других словарях:

  • Цепь Маркова — Пример цепи с двумя состояниями Цепь Маркова  последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем свойством, что, го …   Википедия

  • Список атеистов — Список известных людей, считающихся или публично называвших себя атеистами. Содержание 1 Древний мир 2 Средние века 3 Эпоха Возрождения …   Википедия

  • МОДЕЛИРОВАНИЕ МАТЕМАТИЧЕСКОЕ В СОЦИОЛОГИИ — словосочетание, обозначающее использование математич. языка и аппарата для описания и последующего анализа основных свойств соц. явлений и процессов. М.м. дает возможность заменить непосредственный анализ реальных явлений анализом свойств и… …   Российская социологическая энциклопедия

  • Дорвей — (от англ. doorway  входная дверь, портал) или входная страница  вид поискового спама, веб страница, специально оптимизированная под один или несколько поисковых запросов с единственной целью её попадания на высокие места в… …   Википедия

  • Логистическое отображение — У этого термина существуют и другие значения, см. Отображение (значения). Логистическое отображение (также квадратичное отображение или отображение Фейгенбаума)  это полиномиальное отображение, которое описывает, как меняется численность… …   Википедия

  • Маслов, Виктор Павлович — В Википедии есть статьи о других людях с такой фамилией, см. Маслов. Виктор Павлович Маслов Дата рождения: 15 июня 1930(1930 06 15) (82 года) Место рождения: Москва, СССР Страна …   Википедия

  • Теорема о конце света — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Теорема о конце света (Doomsday argument, сокращённо далее DA, нет устоявшегося перевода на русский язык, обычно используют английское …   Википедия

  • Виктор Павлович Маслов — Дата рождения: 15 июня 1930 Место рождения: Москва Гражданство: Россия Научная сфера: Математическая физика Место работы …   Википедия

  • Маслов Виктор Павлович — Виктор Павлович Маслов Дата рождения: 15 июня 1930 Место рождения: Москва Гражданство: Россия Научная сфера: Математическая физика Место работы …   Википедия

  • MilkyWay@Home — Тип Распределённые вычисления Операционная система Кроссплатформенное ПО Первый выпуск 7 июля 2007 г Аппаратная платформа x86 Последняя версия 0.19 …   Википедия

Книги

Другие книги по запросу «Марковские цепи» >>