WikiSort.ru - Не сортированное

Определение

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

${\displaystyle \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})}$ .

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

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

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

Матрица ${\displaystyle P{(n)}}$ , где

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

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

${\displaystyle p_{i}\equiv \mathbb {P} (X_{0}=i)}$

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

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

${\displaystyle \sum \limits _{j}P_{ij}(n)=1,\quad \forall n\in \mathbb {N} }$ .

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

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

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

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

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

${\displaystyle \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}}}$ ,

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

${\displaystyle \mathbb {P} (X_{n}=i_{n}\mid X_{0}=i_{0})=(P^{n})_{i_{0},i_{n}}}$ ,

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

${\displaystyle \mathbb {P} (X_{n}=i_{n})=\left((P^{T})^{n}\mathbf {p} \right)_{i_{n}}}$ .

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

• Возвратное состояние.
• Возвратная цепь Маркова.
• Достижимое состояние.
• Неразложимая цепь Маркова.
• Периодическое состояние.
• Периодическая цепь Маркова.
• Поглощающее состояние. Состояние ${\displaystyle i}$ называется поглощающим если ${\displaystyle P_{i,i}=1}$ .
• Эргодическое состояние.

Примеры

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

Определение

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

${\displaystyle \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})}$ .

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

${\displaystyle \mathbb {P} (X_{t+h}=x_{t+h}\mid X_{t}=x_{t})=\mathbb {P} (X_{h}=x_{h}\mid X_{0}=x_{0})}$ .

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

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

${\displaystyle \mathbf {p} =(p_{1},p_{2},\ldots )^{\top },\;p_{i}=\mathbb {P} (X_{0}=i),\quad i=1,2,\ldots }$

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

${\displaystyle \mathbf {P} (h)=(P_{ij}(h))=\mathbb {P} (X_{h}=j\mid X_{0}=i)}$ .

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

${\displaystyle P_{ij}(t+s)=\sum _{k}P_{ik}(t)P_{kj}(s).}$

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

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

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

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

• Прямое уравнение Колмогорова

  ${\displaystyle {\frac {d\mathbf {P} (t)}{dt}}=\mathbf {P} (t)\mathbf {Q} ,}$

• Обратное уравнение Колмогорова

  ${\displaystyle {\frac {d\mathbf {P} (t)}{dt}}=\mathbf {Q} \mathbf {P} (t).}$

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

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

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

1. Матричные элементы ${\displaystyle \mathbf {P} (t)}$ неотрицательны: ${\displaystyle P_{ij}(t)\geqslant 0}$ (неотрицательность вероятностей).
2. Сумма элементов в каждой строке ${\displaystyle \mathbf {P} (t)}$ равна 1: ${\displaystyle \sum _{j}P_{ij}(t)=1}$ (полная вероятность), то есть матрица ${\displaystyle \mathbf {P} (t)}$ является стохастической справа (или по строкам).
3. Все собственные числа ${\displaystyle \lambda }$ матрицы ${\displaystyle \mathbf {P} (t)}$ не превосходят 1 по абсолютной величине: ${\displaystyle |\lambda |\leqslant 1}$ . Если ${\displaystyle |\lambda |=1}$ , то ${\displaystyle \lambda =1}$ .
4. Собственному числу ${\displaystyle \lambda =1}$ матрицы ${\displaystyle \mathbf {P} (t)}$ соответствует, как минимум, один неотрицательный левый собственный вектор-строка (равновесие): ${\displaystyle (p_{1}^{*},\,p_{2}^{*},...);}$ ${\displaystyle p_{i}^{*}\geqslant 0;}$ ${\displaystyle \sum _{i}p_{i}^{*}=1;}$ ${\displaystyle \sum _{i}p_{i}^{*}P_{ij}(t)=p_{j}^{*}}$ .
5. Для собственного числа ${\displaystyle \lambda =1}$ матрицы ${\displaystyle \mathbf {P} (t)}$ все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

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

1. Внедиагональные матричные элементы ${\displaystyle \mathbf {Q} }$ неотрицательны: ${\displaystyle q_{ij}\geqslant 0\;i\neq j}$ .
2. Диагональные матричные элементы ${\displaystyle \mathbf {Q} }$ неположительны: ${\displaystyle q_{ii}\leqslant 0}$ .
3. Сумма элементов в каждой строке ${\displaystyle \mathbf {Q} }$ равна 0: ${\displaystyle \sum _{j}q_{ij}=0.}$
4. Действительная часть всех собственных чисел ${\displaystyle \mu }$ матрицы ${\displaystyle \mathbf {Q} }$ неположительна: ${\displaystyle Re(\mu )\leqslant 0}$ . Если ${\displaystyle Re(\mu )=0}$ , то ${\displaystyle \mu =0.}$
5. Собственному числу ${\displaystyle \mu =0}$ матрицы ${\displaystyle \mathbf {Q} }$ соответствует, как минимум, один неотрицательный левый собственный вектор-строка (равновесие): ${\displaystyle (p_{1}^{*},\,p_{2}^{*},...);}$ ${\displaystyle p_{i}^{*}\geqslant 0;}$ ${\displaystyle \sum _{i}p_{i}^{*}=1;}$ ${\displaystyle \sum _{i}p_{i}^{*}q_{ij}=0.}$
6. Для собственного числа ${\displaystyle \mu =0}$ матрицы ${\displaystyle \mathbf {Q} }$ все корневые векторы являются собственными, то есть соответствующие жордановы клетки тривиальны.

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

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

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

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

• Следующие три свойства А, Б, В конечной цепи Маркова эквивалентны (обладающие ими цепи иногда называют слабо эргодическими):

А. Для любых двух различных вершин графа переходов ${\displaystyle i,j\,(i\neq j)}$ найдется такая вершина ${\displaystyle k}$ графа («общий сток»), что существуют ориентированные пути от вершины ${\displaystyle i}$ к вершине ${\displaystyle k}$ и от вершины ${\displaystyle j}$ к вершине ${\displaystyle k}$ . Замечание: возможен случай ${\displaystyle k=i}$ или ${\displaystyle k=j}$ ; в этом случае тривиальный (пустой) путь от ${\displaystyle i}$ к ${\displaystyle i}$ или от ${\displaystyle j}$ к ${\displaystyle j}$ также считается ориентированным путём.

Б. Нулевое собственное число матрицы ${\displaystyle \mathbf {Q} }$ невырождено.

В. При ${\displaystyle t\to \infty }$ матрица ${\displaystyle \mathbf {P} (t)}$ стремится к матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

• Следующие пять свойств А, Б, В, Г, Д конечной цепи Маркова эквивалентны (обладающие ими цепи называют эргодическими):

А. Граф переходов цепи ориентированно связен.

Б. Нулевое собственное число матрицы ${\displaystyle \mathbf {Q} }$ невырождено и ему соответствует строго положительный левый собственный вектор (равновесное распределение).

В. Для некоторого ${\displaystyle t>0}$ матрица ${\displaystyle \mathbf {P} (t)}$ строго положительна (то есть ${\displaystyle P_{ij}(t)>0}$ для всех ${\displaystyle i,j}$ ).

Г. Для всех ${\displaystyle t>0}$ матрица ${\displaystyle \mathbf {P} (t)}$ строго положительна.

Д. При ${\displaystyle t\to \infty }$ матрица ${\displaystyle \mathbf {P} (t)}$ стремится к строго положительной матрице, у которой все строки совпадают (и совпадают, очевидно, с равновесным распределением).

Примеры

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

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

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

${\displaystyle H_{h}(p)=\sum _{i}p_{i}^{*}h\left({\frac {p_{i}}{p_{i}^{*}}}\right)}$ .

Производная ${\displaystyle H_{h}(p)}$ по времени, если ${\displaystyle p(t)}$ удовлетворяет основному кинетическому уравнению, есть

${\displaystyle {\frac {dH_{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}$ .

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