Граф состояний простейшего случайного блуждания: вправо с вероятностью p, влево — с вероятностью 1−p.
Марковские цепи с дискретным временем (МЦДВ)
ПредупреждениеЧерновик
Этот конспект ещё находится в процессе редактуры: в тексте могут встречаться опечатки, неточности и локально не проработанные места. Если что-то нашли — сообщите, пожалуйста, автору (контакты на странице курса).
Простое случайное блуждание и ветвящийся процесс Гальтона-Ватсона обладали следующим свойством: при условии сохранения значения на \(n\)-м шаге, их будущие значения не зависели от предыдущих значений. Это свойство оказалось очень полезным при их анализе, и именно к общей теории процессов с этим свойством мы сейчас и обратимся.
1 Марковское свойство
Пусть \((X_n \; : \; n \in \mathbb {Z}_+) = (X_0, X_1, \ldots )\) – случайный процесс со значениями в некотором пространстве \(\mathcal{X}\), где \(\mathcal{X}\) – конечное или счетное множество, называемое пространством состояний или фазовым пространством. Процесс \((X_n)\) (с дискретным временем) называется марковской цепью (с дискретным временем), сокращенно МЦДВ, если он обладает марковским свойством: при фиксированном настоящем в произвольной точке во времени \(n\) будущее процесса (через произвольное количество шагов \(m\)) не зависит от прошлого (фиксированного в точках \(n_{0} < n_{1} < \ldots < n_{k} < n\)). Формально:
\[ \mathbb {P}\left(X_{n+1} = i_{n+1} \quad \left| \quad \begin{array}{rl} X_{n} & = i_{n} \\ X_{n-1} & = i_{n-1} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) \; = \; \mathbb {P}\left(X_{n+1} = i_{n+1} \mid X_{n} = i_{n}\right) \]
для всех \(n\) и для всех состояний \(i_{0}, \ldots , i_{n+1} \in \mathcal{X}\), таких что выражения слева и справа имеют смысл (события в условии имеют ненулевую вероятность).
Иначе говоря, при фиксированном настоящем состоянии \(X_{n} = i_{n}\) будущее процесса через 1 шаг \(X_{n+1} = i_{n+1}\) не зависит от прошлого \(X_{n-1} = i_{n-1}, \ldots , X_{0} = i_{0}\).
Что если рассматривать будущее процесса не через \(1\) шаг, а через \(m\) шагов? Или рассматривать настоящее и прошлое выборочно, не во всех точках с \(0\) по \(n-1\)? Оказывается, во всех этих более общих случаях для марковского процесса будущее не будет зависеть от прошлого.
2 Распределение цепи, переходные вероятности
\(\mathcal{X}\) конечно или счетно. Если \(\mathcal{X}\) конечно, то его можно отождествить с \(\left\{ 1, 2, \ldots , \left|\mathcal{X}\right|\right\}\). Если \(\mathcal{X}\) счетно, то его можно отождествить с \(\mathbb {N}\).
Легко доказать, что распределение МЦДВ полностью задается
начальным распределением, т.е. распределением \(X_0\). Обычно его обозначают строкой \(\Pi^{(0)}\):
\[ \Pi ^{(0)} = \left(\mathbb {P}\left(X_0 = i\right)\right)_{i \in \mathcal{X}} = \left(\mathbb {P}\left(X_0 = 1\right), \mathbb {P}\left(X_0 = 2\right), \ldots \right) \]
переходными вероятностями за \(1\) шаг, т.е. вероятностями \(\mathbb {P}\left(X_{n+1} = i \mid X_{n} = j\right)\). Их можно объединить в (возможно, бесконечные) матрицы \(\mathbf{P}_{0}\), \(\mathbf{P}_{1}\), \(\mathbf{P}_{2}\), \(\ldots\):
\[ \mathbf{P}_n = \bigg(\mathbb {P}\left(X_{n+1} = j \mid X_{n} = i\right)\bigg)_{i,j \in \mathcal{X}} \]
А именно, распределение цепи в момент \(k\), обозначаемое \(\Pi^{(k)} = \left(\mathbb {P}\left(X_k = i\right)\right)_{i \in \mathcal{X}}\), можно найти так:
\[ \mathbb {P}\left(X_k = i\right) = \sum _{j\in \mathcal{X}} \mathbb {P}\left(X_{k-1} = j\right) \cdot \mathbb {P}\left(X_{k}= i \mid X_{k-1} = j\right) \]
т.е.
\[ \Pi ^{(k)} = \Pi ^{(k-1)} \cdot \mathbf{P}_{k-1} \]
Продолжая процесс далее, получаем формулу
\[ \Pi ^{(k)} = \Pi ^{(0)} \cdot \mathbf{P}_0 \cdot \mathbf{P}_1 \cdot \cdots \cdot \mathbf{P}_{k-1} \]
Марковская цепь с дискретным временем называется однородной, если все матрицы переходов совпадают: \(\mathbf{P} := \mathbf{P}_{0} = \mathbf{P}_{1} = \ldots\). Для однородной марковской цепи распределение находить становится проще:
\[ \Pi ^{(k)} = \Pi ^{(0)} \cdot \mathbf{P}^k \]
Пока мы марковским свойством не пользовались. Оно требуется при попытке посчитать конечномерные распределения для МЦДВ. А именно,
\[ \begin{align} \mathbb {P}\left(\left. \begin{array}{rl} X_{n} & = i_{n} \\ X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) & = \underbrace{\mathbb {P}\left(X_{n} = i_{n} \quad \left| \quad \begin{array}{rl} X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right)}_{\substack {=\mathbb {P}\left(X_{n}= i_n \mid X_{n-1} = i_{n-1}\right) = \left(\mathbf{P}_{n-1}\right)_{i_{n-1},i_n},\\ \text{марковское свойство}}} \quad \cdot \quad \mathbb {P}\left(\left. \quad \begin{array}{rl} X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) = \\ & = \left(\mathbf{P}_{n-1}\right)_{i_{n-1},i_n} \quad \cdot \quad \mathbb {P}\left(\left. \quad \begin{array}{rl} X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) \end{align} \]
Далее, аналогично
\[ \mathbb {P}\left(\left. \begin{array}{rl} X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) = \left(\mathbf{P}_{n-2}\right)_{i_{n-2},i_{n-1}} \quad \cdot \quad \mathbb {P}\left(\left. \quad \begin{array}{rl} X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) \]
В конце получим \(\mathbb {P}\left(X_0 = i_0\right) = \Pi^{(0)}_{i_0}\). В итоге получаем формулу
\[ \mathbb {P}\left(\left. \begin{array}{rl} X_{n} & = i_{n} \\ X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) = \begin{array}{cc}& \left(\mathbf{P}_{n-1}\right)_{i_{n-1},i_n} \times \\ \times & \left(\mathbf{P}_{n-2}\right)_{i_{n-2},i_{n-1}} \times \\ & \vdots \\ \times & \left(\mathbf{P}_{0}\right)_{i_{0},i_{1}} \times \\ \times & \Pi ^{(0)}_{i_0} \\ \end{array} \]
Для однородной МЦДВ формула упрощается:
\[ \mathbb {P}\left(\left. \begin{array}{rl} X_{n} & = i_{n} \\ X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) = (\mathbf{P})_{i_{n-1}, i_{n}} \cdot \ldots \cdot (\mathbf{P})_{i_{0}, i_{1}} \cdot \Pi ^{(0)}_{i_0} \]
Введем дополнительное обозначение для (матрицы) переходных вероятностей с \(k\)-го шага на \(l\)-й шаг:
\[ \mathbf{P}_{k \to l} := \left(\mathbb {P}\left(X_l = j \mid X_{k} = i\right)\right)_{i,j \in \mathcal{X}} \]
В старых обозначениях: \(\mathbf{P}_{k} = \mathbf{P}_{k \to k+1}\). Перечислим свойства переходных вероятностей.
Данные свойства являются не только необходимыми, но и достаточными для того, чтобы при заданных функциях с такими свойствами существовала марковская цепь с равными этим функциям переходными вероятностями. Об этом говорит теорема о существовании марковских цепей.
Для однородной МЦДВ все упрощается.
Эти теоремы – прямое следствие теоремы Колмогорова о построении распределения процесса. Напомним, что теорема Колмогорова на пространстве траекторий \(\mathcal{X}^{T}\) (в нашем случае \(T = \mathbb {Z}_+\)) строит распределение \(\mathbb {P}\) с заданными конечномерными распределениями, и далее сам процесс может быть задан через проекции: \(X_n := \pi_n\), \(\pi_n(f) := f(n)\), \(f \in \mathcal{X}^{\mathbb {Z}_+}\). Это называется стандартной моделью.
В теории марковских цепей зачастую требуется при фиксированной матрице \(\mathbf{P}\) переходов за \(1\) шаг смотреть на цепь при разных начальных распределениях \(\Pi^{(0)}\). В стандартной модели это можно так реализовать: для данной (одной) матрицы \(\mathbf{P}\) на пространстве \(\mathcal{X}^{\mathbb {Z}_+}\) (с цилиндрической сигма-алгеброй соотв.) построить сразу семейство распределений \(\mathbb {P}_{\Pi }\), в зависимости от начального распределения \(\Pi = \Pi^{(0)}\). И далее исследовать процесс, составленный из проекций, при разных \(\Pi\). Т.е. выражение
\[ \mathbb {P}_{\Pi }\left(X_3 = 4\right) \]
означает вероятность марковской цепи с начальным распределением \(\Pi\) и с матрицей переходов \(\mathbf{P}\) быть равной \(3\). В частности, если начальное распределение сосредоточено только в одном состоянии \(i\) (т.е. \(\Pi_j = \delta_i^j\), \(\Pi = (\ldots , 0,0,1,0,0,\ldots )\)), то мы будем использовать обозначение
\[ \mathbb {P}_{i}\left(X_3 = 4\right) \]
Это согласуется с теми обозначениями, которые у нас были при изучении случайного блуждания.
В дальнейшем, если не оговорено иного, мы будем рассматривать только однородные цепи.
Состояния и переходные вероятности между ними удобно изображать в виде ориентированного графа со взвешенными ребрами.
3 Конечное число состояний
В данном разделе фазовое пространство считается конечным.
3.1 Сообщающиеся состояния
В теории марковских цепей состояния \(i,j \in \mathcal{X}\) называют сообщающимися, если в графе переходов они сильно связны: можно с положительной вероятностью (за какое-то конечное количество шагов) дойти из \(i\) в \(j\) и из \(j\) в \(i\). Компоненты сильной связности называют сообщающимися классами.
Состояние называют невозвратным или транзитным, если можно выйти из этого состояния и с некоторой положительной вероятностью никогда в него не вернуться. В противном случае, т.е. когда при выходе из состояния с вероятностью \(1\) в него когда-нибудь возвращаешься, состояние называют возвратным.
Нумерация состояний, полученная в примере выше, называется канонической. Это такая нумерация, при которой матрица переходов имеет блочный вид \[ \mathbf{P} = \left( \begin{array}{c|c} \mathbf{T}_{11} & \mathbf{T}_{12} \\ \hline \mathbf{0} & \mathbf{T}_{22} \end{array} \right) \]
Блочный вид матрицы переходов при канонической нумерации состояний: \(\mathbf{T}_{11}\) — переходы внутри транзитных классов и между ними, \(\mathbf{T}_{12}\) — переходы из транзитных классов в возвратные, \(\mathbf{T}_{22}\) — переходы внутри возвратных классов, \(\mathbf{0}\) — блок, отвечающий за (невозможные) переходы из возвратных классов в транзитные. Размеры блоков зависят от конкретной цепи, поэтому матрица приведена схематически.
\(\mathbf{T}_{11}\) отвечает за переходы внутри транзитных классов и между транзитными классами. Пусть \(r\) – это число транзитных классов. Тогда \(\mathbf{T}_{11}\) – это квадратная матрица, имеющая блочную структуру
\[ \mathbf{T}_{11} = \begin{pmatrix} \mathbf{P}_{11} & \mathbf{P}_{12} & \cdots & \mathbf{P}_{1r} \\ \mathbf{0} & \mathbf{P}_{22} & \cdots & \mathbf{P}_{2r} \\ \vdots & \ddots & \ddots & \vdots \\ \mathbf{0} & \cdots & \mathbf{0} & \mathbf{P}_{rr} \\ \end{pmatrix} \]
Матрица верхнетреугольная (если по блокам смотреть). При канонической нумерации переходы возможны только из меньшего по номеру транзитного класса в больший.
\(\mathbf{T}_{12}\) отвечает за переходы из транзитных классов в возвратные. Пусть \(m\) – это общее число классов. Тогда \(\mathbf{T}_{12}\) имеет вид
\[ \mathbf{T}_{12} = \begin{pmatrix} \mathbf{P}_{1,r+1} & \cdots & \mathbf{P}_{1m} \\ \vdots & \cdots & \vdots \\ \mathbf{P}_{r,r+1} & \cdots & \mathbf{P}_{rm} \\ \end{pmatrix} \]
\(\mathbf{T}_{22}\) отвечает за переходы внутри возвратных классов (переходы между возвратными классами невозможны по определению). Она имеет блочный вид
\[ \mathbf{T}_{22} = \begin{pmatrix} \mathbf{P}_{r+1,r+1} & \mathbf{0} & \mathbf{0} & \cdots & \mathbf{0} \\ \mathbf{0} & \mathbf{P}_{r+1,r+1} & \mathbf{0} & \cdots & \mathbf{0} \\ \vdots & \cdots & \cdots & \cdots & \vdots \\ \mathbf{0} & \mathbf{0} & \cdots & \mathbf{P}_{m-1,m-1} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & \cdots & \mathbf{0} & \mathbf{P}_{mm} \\ \end{pmatrix} \]
Любую МЦДВ с конечным числом состояний можно привести к такому виду.
3.2 Предельное поведение
Нас будет интересовать поведение цепи с ростом \(n\). Как мы уже выяснили, распределение на \(n\)-м шаге задается \(\Pi^{(n)} = \Pi^{(0)} \cdot \mathbf{P}^n\). Рассмотрим поведение матриц \(\mathbf{P}^n\) с ростом \(n\), а также последовательность средних арифметических
\[ \frac{1}{n}\left(\mathbf{P}^0 + \mathbf{P}^1 + \ldots + \mathbf{P}^{n-1}\right) \]
(\(\mathbf{P}^0 = E\)).
Будем говорить, что последовательность матриц \(\mathbf{P}^0, \mathbf{P}^1, \mathbf{P}^2, \ldots\) сходится, если каждый из ее элементов сходится. Будем говорить, что та же последовательность суммируема (суммируема по Чезаро, сходится по Чезаро), если у последовательности средних арифметических \(\frac{1}{n}\left(\mathbf{P}^0 + \mathbf{P}^1 + \ldots + \mathbf{P}^{n-1}\right)\) есть поэлементный предел.
Напомним, что если числовая последовательность сходится (в обычном смысле), то она сходится и по Чезаро, причем пределы совпадают. Однако сходимость по Чезаро – это более общее понятие. Например, последовательность \(1,0,1,0,1,0, \ldots\) не сходится, однако последовательность средних арифметических
\[ \frac{1}{1}, \frac{1}{2}, \frac{2}{3}, \frac{2}{4}, \frac{3}{5}, \frac{3}{6}, \ldots , \frac{n}{2n}, \frac{n+1}{2n+1}, \ldots \]
сходится к \(\frac{1}{2}\). Т.е. последовательность суммируема по Чезаро. Поэтому удобнее сначала изучить предел по Чезаро, а затем обычный предел.
Рассмотрим тепловые карты последовательности \(\mathbf{P}^n\) и \(\frac{1}{n}(\mathbf{P}^0 + \ldots + \mathbf{P}^{n-1})\) для примера выше.
Анимация эволюции Pⁿ при n = 0,1,2,…,40 (та же матрица, что и в примере выше). Используйте ползунок или кнопку Play, чтобы проследить, как значения элементов матрицы меняются с ростом n.
Предел lim Pⁿ (с точностью до 2 знаков там, где он существует). Диагональные блоки транзитных классов {1,2,3}, {4,5} стремятся к нулю (цепь покидает транзитные состояния п.н.). Блок возвратного класса {6,7,8} и поглощающее состояние {9} сходятся к своим стационарным значениям. Но для периодического (период 2) класса {10,11,12,13}, а также для всех переходов из транзитных состояний в этот класс, предел Pⁿ не существует — матрица лишь колеблется между двумя предельными точками с ростом n (см. также анимацию выше и предел по Чезаро ниже, который существует всегда).
Анимация эволюции средних по Чезаро Cₙ = (1/n)(P⁰+P¹+…+Pⁿ⁻¹) для той же матрицы переходов P. В отличие от Pⁿ (см. анимацию выше), эта последовательность сходится поэлементно при n → ∞ для всех блоков матрицы, включая периодический возвратный класс {10,11,12,13}.
Предел по Чезаро lim(1/n)·(P⁰+P¹+…+Pⁿ⁻¹) для матрицы переходов P из примера выше. В отличие от обычного предела Pⁿ, предел по Чезаро существует для всех блоков — в том числе для периодического возвратного класса {10,11,12,13}. Значения вычислены точно: для каждого возвратного класса строка предела совпадает с его стационарным распределением, а для транзитных состояний — это вероятность поглощения в класс, умноженная на стационарное распределение внутри него.
Как видно из анимаций тепловых карт, часть элементов последовательности \((\mathbf{P}^n, \; n \in \mathbb {Z}_+)\) сходится, а часть не сходится. При этом \((\mathbf{P}^n, \; n \in \mathbb {Z}_+)\) суммируема по Чезаро. На самом деле это \(\mathbf{P}^n\) всегда будут суммируемы по Чезаро. См. ниже.
Какой вероятностный смысл предела по Чезаро? Разберемся с \(\frac{1}{n}\sum_{k=0}^{n-1}\mathbf{P}^{k}\). Элемент \(i,j\) этой матрицы равен
\[ \begin{align} \left(\frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^{k}\right)_{ij} & = \frac{1}{n}\bigg(\mathbb {P}_{i}\left(X_{0} = j\right) + \mathbb {P}_{i}\left(X_{1} = j\right) + \ldots + \mathbb {P}_{i}\left(X_{n-1} = j\right)\bigg) = \\ & = \frac{1}{n} \bigg( \mathbb {E}_{i}\left[\; \mathbb {1}_{X_{0} = j}\right] + \mathbb {E}_{i}\left[\; \mathbb {1}_{X_{1} = j}\right] + \ldots + \mathbb {E}_{i}\left[\; \mathbb {1}_{X_{n-1} = j}\right] \bigg) = \\ & = \mathbb {E}_{i}\left[\frac{\; \mathbb {1}_{X_0 = j} + \; \mathbb {1}_{X_1 = j} + \ldots + \; \mathbb {1}_{X_{n-1} = j}}{n}\right] = \\ & = \mathbb {E}_{i}\left[\frac{1}{n} \sum _{k=0}^{n-1} \; \mathbb {1}_{X_k = j}\right] \end{align} \]
Введем обозначение:
\[ V^{(n)}_{j} := \left|\left\{ 0 \leq k \leq n \; : \; X_{k} = j\right\} \right| = \sum _{k=0}^{n} \; \mathbb {1}_{X_k = j} \]
Сумма индикаторов \(V^{(n-1)}_j = \sum_{k=0}^{n-1} \; \mathbb {1}_{X_k = j}\) – это количество посещений (visits, поэтому буква \(V\)) состояния \(j\) в моменты времени \(0, 1, \ldots , n-1\). Разделив на \(n\), т.е. на общее время, получим частоту посещений состояния \(j\). Значит, элемент \(i,j\) матрицы \(\frac{1}{n}\sum_{k=0}^{n-1}\mathbf{P}^{k}\) – это матожидание частоты посещения состояния \(j\) за \(n\) шагов, если цепь вышла из состояния \(i\).
Заметим, что (при фиксированном \(j\)) процесс \(V^{(n)}_{j}, n \geq 0\) – это почти что процесс восстановления. А именно, пусть \(\tau^{(k)}_j\) – момент \(k\)-го посещения состояния \(j\). Их можно определить индуктивно:
\[ \begin{align} \tau _{j}^{(1)} & := \min \left\{ n \geq 0 \; : \; X_n = j\right\} \\ \tau _{j}^{(k)} & := \min \left\{ n > \tau _{j}^{(k-1)} \; : \; X_n = j\right\} , \; k \geq 2 \end{align} \]
Связь со старыми обозначениями из случайного блуждания: \(\tau_j = \tau^{(1)}_j\) – момент 1-го посещения \(j\), \[ T_j = \min \left\{ n \geq 1 \; : \; X_n = j\right\} = \begin{cases} \tau ^{(1)}_j, & X_0 \neq j \\ \tau ^{(2)}_j, & X_0 = j \end{cases} \] – момент 1-го посещения \(j\) после 1-го шага. Попутно заметим, что по определению состояние \(j\) называют возвратным, если \[ \mathbb {P}_{j}\left(\tau ^{(2)}_j < \infty \right) = 1 \quad \text{или, что то же самое, } \quad \mathbb {P}_{j}\left(T_j < \infty \right) = 1 \]
В таком случае \(V^{(n)}_j\) – это счетчик посещений, построенный по
\[ \begin{align} \xi ^{(1)}_j & := \tau _{j}^{(1)}, \\ & \quad \xi ^{(2)}_j := \tau _{j}^{(2)} - \tau _{j}^{(1)}, \\ & \quad \xi ^{(3)}_j := \tau _{j}^{(3)} - \tau _{j}^{(2)}, \ldots \end{align} \]
Мы уже хорошо изучили подобные процессы, процессы восстановления в частности. Попробуем применить наши знания!
Напомним, что в определении процесса восстановления мы требовали, чтобы \(\xi_1, \xi_2, \ldots\) были неотрицательные НОРСВ с невырожденным распределением. Нам нужно понять, как распределены \(\xi^{(1)}_j, \xi^{(2)}_j, \xi^{(3)}_j, \ldots\). Будут ли они НОРСВ?
Далее будут немного неформальные рассуждения, поскольку формально это расписывать долго и утомительно, а у нас все таки конспект семинаров, а не лекций. Марковское свойство: процесс, попадая в состояние \(j\), забывает свое предыдущее поведение. Значит, при любом начальном распределении \(\Pi\) (т.е. при любом \(\mathbb {P}_{\Pi }\)) эти случайные величины независимы. Причем, за счет опять же марковского свойства, \(\xi^{(2)}_j, \xi^{(3)}_j, \ldots\) будут одинаково распределены (и это распределение также не зависит от \(\Pi\), поскольку оно характеризуется тем, что процесс попал на каком-то фиксированном шаге в состояние \(j\), а значит уже не важно, как до этого он шел). Распределение \(\xi^{(1)}_j = \tau^{(1)}_j\) при этом может отличаться от остальных. Например, если процесс п.н. стартует в \(j\), т.е. \(\Pi_i = \delta_i^j\), то \(\xi^{(1)}_j \equiv 0\),
\[ \mathbb {P}_{j}\left(\tau ^{(1)}_j = 0\right) = 1, \]
а у \(\xi^{(2)}_j, \xi^{(3)}_j, \ldots\) все таки будет какое-то нетривиальное распределение.
Итого, \(\xi^{(1)}_j, \xi^{(2)}_j, \xi^{(3)}_j, \ldots\) – независимые случайные величины, причем все, кроме первого времени, одинаково распределенные. Напомним, \(\tau^{(m)}_j = \xi^{(1)}_j + \ldots + \xi^{(m)}_j\). Процесс
\[ V^{(n-1)}_j = \max \left\{ m \geq 1 \; : \; \tau ^{(m)}_j \leq n-1\right\} = \sum _{k=0}^{n-1} \; \mathbb {1}_{X_k = j} , \qquad n \geq 1 \]
(максимум по пустому множеству считаем равным \(0\)) называется отложенным процессом восстановления.
Какие предельные свойства у отложенного процесса восстановления? Оказывается, элементарная теорема восстановления во многих случаях остается верной.
Доказательство см. в (Grimmett и Stirzaker 2020 г., Theorem 10.4.15).
Рассмотрим сначала некоторые частные случаи.
3.3 Неприводимые цепи
Цепь Маркова называется неприводимой, если все ее состояния образуют один класс сообщающихся состояний (который в этом случае должен быть замкнутым). Изучение цепи, имеющей более одного класса сообщающихся состояний, по сути сводится к изучению ее «сужений» на различные классы.
Можно доказать, что если цепь неприводима и в ней конечное число состояний, то
\[ \mathbb {P}_{i}\left(\tau _j < \infty \right) = \mathbb {P}_{j}\left(T_j < \infty \right) = 1, \qquad \forall i,j \in \mathcal{X} \]
Т.е. из любого состояния любое другое достигается за п.н. конечное время и все состояния возвратны. Такая цепь не является транзитной2.
Возвращаясь к отложенному процессу восстановления, в данном случае имеем
\[ \mathbb {P}_{i}\left(\xi ^{(1)}_j < \infty \right) = 1 \]
(вспомним, что \(\xi^{(1)}_j = \tau^{(1)}_j = \tau_j\)). Т.е. при старте в состоянии \(i\) п.н. за конечное время процесс достигает состояния \(j\). Счетчик за п.н. конечное время преодолевает первый барьер \(\xi^{(1)}_j\). В таком случае дальше включаются в дело \(\xi^{(2)}_j, \xi^{(3)}_j, \ldots\), которые НОРСВ, а значит предельные свойства у процесса такие же, как и у обычного процесса восстановления, построенного по \(\xi^{(2)}_j, \xi^{(3)}_j, \ldots\). В частности, выполнена элементарная теорема восстановления:
\[ \begin{align} \left(\frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^{k}\right)_{ij} & = \frac{1}{n} \cdot \mathbb {E}_{i}\left[ V^{(n-1)}_j\right] \quad \xrightarrow [n \to \infty ]{} \\ & \quad \frac{1}{\mathbb {E}_{i}\left[\xi ^{(2)}_j\right]} \end{align} \]
Заметим, что \(\xi^{(2)}_j = \tau^{(2)}_j - \tau^{(1)}_j\) – это время между первым и вторым посещением \(j\). Поскольку процесс уже посетил \(j\), то по марковскому свойству его распределение, в частности, распределение \(\xi^{(2)}_j\) не зависит от начального распределения. Иначе говоря,
\[ \mathbb {E}_{i'}\left[\xi ^{(2)}_j\right] = \mathbb {E}_{i''}\left[\xi ^{(2)}_j\right] = \mathbb {E}_{j}\left[\xi ^{(2)}_j\right] \]
для всех \(i', i'' \in \mathcal{X}\). А если цепь стартовала из \(j\), то \(\tau^{(1)}_j \equiv 0\) и
\[ \xi ^{(2)}_j = \tau ^{(2)}_j - \tau ^{(1)}_j = \tau ^{(2)}_j = T_j \]
– время возврата в состояние \(j\). Пришли к теореме.
3.4 Стационарное распределение
Для однородной МЦДВ (начальное) распределение \(\Pi\) называется стационарным, если оно не меняется со временем, т.е.
\[ \Pi = \Pi \cdot \mathbf{P} \]
В сущности это собственный левый вектор (т.е. строка) для матрицы \(\mathbf{P}\). Или \(\Pi^T\) – собственный правый вектор (столбец) для матрицы \(\mathbf{P}^T\). Заметим, что сумма всех столбцов самой матрицы \(\mathbf{P}\) равна столбцу из единиц. Т.е. \((1,1,\ldots ,1)^T\) – это собственный правый вектор для матрицы \(\mathbf{P}\) с собственным значением \(1\). Собственные значения у \(\mathbf{P}\) и у \(\mathbf{P}^T\) совпадают, значит найдется для данного собственного значения и левый собственный вектор. Причем его всегда можно нормировать, т.е. превратить его в распределение. Пришли к теореме.
Как стационарное распределение связано с пределом по Чезаро? Заметим, что
\[ \begin{align} \Pi \cdot \left(\frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^{k}\right) & = \frac{1}{n}\sum _{k=0}^{n-1}\Pi \cdot \mathbf{P}^{k} \\ & = \frac{1}{n}\sum _{k=0}^{n-1}\Pi = \Pi \end{align} \]
Предположим, что у нас неприводимая цепь, как в предыдущем параграфе. Перейдем к пределу по \(n\). Получим
\[ \Pi \cdot \begin{pmatrix} \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \\ \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \\ \vdots & \vdots & \vdots & \vdots \\ \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \end{pmatrix} = \Pi \]
Раскроем то, что слева стоит:
\[ \begin{pmatrix} \sum _{i=1}^{\left|\mathcal{X}\right|} \Pi _i \cdot \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1}, & \sum _{i=1}^{\left|\mathcal{X}\right|} \Pi _i \cdot \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1}, & \cdots , & \sum _{i=1}^{\left|\mathcal{X}\right|} \Pi _i \cdot \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \end{pmatrix} \]
Но ведь \(\sum_{i=1}^{\left|\mathcal{X}\right|} \Pi_i = 1\). В итоге получаем
\[ \begin{pmatrix} \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \end{pmatrix} = \Pi \]
Иначе говоря, предел по Чезаро состоит построчно как раз из стационарных распределений! Отсюда, кстати, можно сделать вывод, что в случае неприводимой цепи стационарное распределение может быть только одно, поскольку предел единственен. Иначе говоря, геом. кратность собственного значения \(1\) для матрицы \(\mathbf{P}\) равна \(1\). Сформулируем теорему.
3.5 Период состояния, эргодическая цепь
Мы детально разобрались с пределом по Чезаро матриц перехода \(\mathbf{P}^0, \mathbf{P}^1, \ldots\) для неприводимой МЦДВ с конечным числом состояний. Но что с обычным пределом? Он, оказывается, не всегда существует.
В чем проблема с цепью выше? Она имеет периодическое поведение: стартуя из любого состояния, вернутся в него можно только лишь через четное количество шагов. Еще более простой пример подобной цепи таков:
Простейшая периодическая цепь из 2 состояний: детерминированные переходы 1→2→1→…, период равен 2.
Ее матрица переходов:
\[ \mathbf{P} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \]
В данном случае
\[ \mathbf{P}^{2k} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \qquad \mathbf{P}^{2k + 1} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \]
У нее нет поэлементного предела. Хотя при этом есть предел по Чезаро:
\[ \frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^k \quad \xrightarrow [n \to \infty ]{} \quad \begin{pmatrix} 1/2 & 1/2 \\ 1/2 & 1/2 \end{pmatrix} \]
Периодом состояния \(j\) (обозначение: \(d(j)\)) называется НОД всех номеров шагов, за которые можно с положительной вероятностью вернуться в \(j\), выйдя из \(j\). Иначе говоря,
\[ d(j) := \operatorname {НОД} \left\{ k \geq 1 \; : \; \mathbb {P}_{j}\left(T_j = k\right) > 0\right\} \]
Состояние называют апериодическим, если \(d(j) = 1\).
В частности, у неприводимой цепи период всех состояний совпадает. Т.е. можно говорить о периоде всей (неприводимой) цепи. У цепей выше период равен \(2\).
У неприводимой цепи периодичность возникает, как мы видели, если есть какой-то нетривиальный период (т.е. он больше \(1\)). Оказывается, если неприводимая цепь является апериодической, то \(\mathbf{P}^{n}\) сходятся. Неприводимая, апериодическая цепь называется эргодической цепью.
Сформулируем теорему.
Распределение \(\Pi\) из эргодической теоремы само называется эргодическим. Заметим, что если \(\Pi^{(0)}\) – это какое-то другое начальное распределение, то
\[ \Pi ^{(0)} \cdot \mathbf{P}^{n} \quad \xrightarrow [n \to \infty ]{} \Pi ^{(0)} \cdot \begin{pmatrix} \Pi \\ \Pi \\ \vdots \\ \Pi \end{pmatrix} = \Pi \]
Эргодическая цепь с течением времени как-бы забывает, откуда она вышла, стабилизируясь на стационарном распределении.
Для неприводимой цепи (с конечным количеством состояний) есть полезный критерий эргодичности (т.е. апериодичности).
Доказательство см. в (Meyer 2001 г., строка 678).
3.6 Предельные и стационарные распределения: общий случай
Рассмотрим теперь цепи, состоящие из нескольких сообщающихся классов.
4 Счетное число состояний
Определения из МЦДВ с конечным числом состояний переносятся на МЦДВ со счетным числом состояний: сообщающиеся состояния, классы состояний, неприводимые цепи, возвратные/невозвратные состояния, период состояния, и т.д. При этом также, как и в конечном случае, возвратность и период – это свойства, сохраняющиеся в рамках одного сообщающегося класса.
В данном примере можно видеть отличия МЦДВ с сч. числом состояний от конечного случая:
В цепи может не быть ни одного замкнутого класса (простейшее блуждание с \(p = 1\)).
Бесконечный класс (и сама цепь, соотв.) может быть невозвратным и замкнутым одновременно (простейшее блуждание с \(p \in (0,1)\), \(p \neq \frac{1}{2}\)).
Это означает, что определять возвратность класса состояний теперь сложнее: если он незамкнут, то, как и прежде, он невозвратный; если же класс замкнут, то он может быть как возвратным, так и невозвратным (в конечном случае он был бы обязательно возвратным).
При этом даже если класс невозвратный и незамкнутый, то цепь не обязательно выйдет из этого класса с вероятностью \(1\), из него стартовав (блуждание с поглощающим барьером в \(1\)). Напомним, что в конечном случае цепь, стартуя из невозратного (и незамкнутого, соотв.) класса с вероятностью \(1\) его покидала (в какой-то конечный момент).
Даже если состояние возвратное, то матожидание времени возврата может быть бесконечным, при том что оно само п.н. конечное по определению возвратности (простейшее блуждание с \(p = \frac{1}{2}\), блуждание с удерживающим барьером в \(1\) и \(p = \frac{1}{2}\)). В конечном случае для возвратного состояния матожидание времени возврата всегда было конечным.
В связи с последним пунктом вводят новое определение: возвратное состояние \(i\) (т.е. такое, что \(\mathbb {P}_{i}\left(T_{i} < +\infty \right) = 1\)) называется
положительно-возвратным, если \(\mathbb {E}_{i}\left[T_{i}\right] < +\infty\);
нуль-возвратным, если \(\mathbb {E}_{i}\left[T_{i}\right] = +\infty\).
Приведем полезную таблицу, верную как в конечном, так и в бесконечном случае. Доказательства см. в (Grimmett и Stirzaker 2020 г., гл. 6).
| Состояние \(j\) невозвратное | Состояние \(j\) возвратное | ||
| Положительно-возвратное | Нуль-возвратное | ||
| Эквивалентное условие через время возвращения \(T_j\) | \(\displaystyle \mathbb{P}_j\!\left(T_j = +\infty\right) > 0\) | \(\displaystyle \mathbb{P}_j\!\left(T_j = +\infty\right) = 0\) | |
| \(\displaystyle \mathbb{E}_j\!\left[T_j\right] < +\infty\) | \(\displaystyle \mathbb{E}_j\!\left[T_j\right] = +\infty\) | ||
| Эквивалентное условие через матрицу переходов \(\mathbf{P}\). \(V_j = \left|\{n \geq 0 : X_n = j\}\right|\) — общее количество посещений (visits) цепью состояния \(j\) | \(\displaystyle \underbrace{\sum_{n=0}^{+\infty} \left(\mathbf{P}^n\right)_{jj}}_{=\, \mathbb{E}_j[V_j]} < +\infty\) | \(\displaystyle \sum_{n=0}^{+\infty} \left(\mathbf{P}^n\right)_{jj} = +\infty\) | |
| \(\displaystyle \left(\mathbf{P}^n\right)_{jj} \not\to 0\) | \(\displaystyle \left(\mathbf{P}^n\right)_{jj} \xrightarrow[n \to \infty]{} 0\) | ||
| Эквивалентное условие через число возвращений | \(\displaystyle \mathbb{P}_j\!\left(X_n = j \text{ б.ч.}\right) = 0\) | \(\displaystyle \mathbb{P}_j\!\left(X_n = j \text{ б.ч.}\right) = 1\) | |
| Эквивалентное условие через сообщающиеся классы (для конечного числа состояний) | \(j\) в незамкнутом классе (т.е. несущественно) | \(j\) в замкнутом классе | |
| Если цепь с конечным числом состояний | Обязательно найдётся хотя бы одно состояние | Не существует | |
| Некоторые свойства. Обозначение: \(f_{ij} = \mathbb{P}_i\!\left(T_j < \infty\right)\) — вероятность дойти из \(i\) в \(j\) за конечное время | \(\displaystyle \underbrace{\sum_{n=0}^{+\infty} \left(\mathbf{P}^n\right)_{ij}}_{\mathbb{E}_i[V_j]} < +\infty\) для всех \(i\) | \(\displaystyle \sum_{n=0}^{+\infty} \left(\mathbf{P}^n\right)_{ij} = +\infty\) для всех \(i\), таких что \(f_{ij} > 0\) | |
Таблица 1: Сводка эквивалентных условий возвратности/невозвратности и положительной/нулевой возвратности состояния (j) марковской цепи с дискретным временем.
4.1 Неприводимые цепи
Для МЦДВ с матрицей переходов \(\mathbf{P}\) стационарной мерой \(\Psi\) называется мера на \(\mathcal{X}\) (т.е. строка из неотрицательных чисел, индексированная \(\mathcal{X}\)), что
\[ \Psi \cdot \mathbf{P} = \Psi \]
Доказательство см. в (Grimmett и Stirzaker 2020 г., п. 6.4).
4.2 Предельные свойства в общем случае
Соберем воедино картину предельного поведения для произвольной (возможно, счетной, из нескольких классов) МЦДВ. Ключ – все то же представление \(\left(\frac{1}{n}\sum_{k=0}^{n-1}\mathbf{P}^k\right)_{ij} = \frac{1}{n}\mathbb {E}_{i}\left[V^{(n-1)}_j\right]\) через средние частоты посещений и элементарная теорема восстановления для отложенных процессов (теорема Теорема 3), примененная аккуратно: теперь первый интервал \(\xi^{(1)}_j = \tau_j\) может быть бесконечным с положительной вероятностью.
Идея: на событии \(\left\{ \tau_j = \infty \right\}\) посещений \(j\) нет вовсе и частота равна \(0\); на событии \(\left\{ \tau_j < \infty \right\}\) работает рассуждение для отложенного процесса восстановления, дающее частоту \(\frac{1}{\mathbb {E}_{j}\left[T_j\right]}\). Формула объединяет оба случая. Она же расшифровывает правый верхний угол предела по Чезаро для большой цепи из примера Пример 6: это вероятность из транзитного состояния \(i\) когда-нибудь попасть в (возвратное) состояние \(j\), умноженная на долю времени \(\pi_j\), которую цепь проводит в \(j\) внутри своего класса.
Обычный (не чезаровский) предел \(\mathbf{P}^n\) существует тогда и только тогда, когда каждый положительно-возвратный класс апериодичен: внутри периодического класса диагональные элементы \(\left(\mathbf{P}^n\right)_{jj}\) колеблются (обращаются в нуль при \(n\), не кратных периоду), как мы видели в примерах выше. Подробности см. в (Grimmett и Stirzaker 2020 г., гл. 6).
5 Доказательства
5.1 Доказательство леммы Лемма 1 (эквивалентность форм марковского свойства)
(i)⟹(ii), индукция по \(m\). База \(m=1\) — это (i). Пусть (ii) верно для \(m-1\) при любом \(n\). По формуле полной вероятности:
\[ \begin{align} \mathbb {P}\left(X_{n+m}=i_{n+m}\mid X_n=i_n,\ldots ,X_0=i_0\right) & = \sum _{i_{n+1}} \\ & \quad \mathbb {P}\left(X_{n+m}=i_{n+m}\mid X_{n+1}=i_{n+1},X_n=i_n,\ldots ,X_0=i_0\right)\cdot \\ & \quad \cdot \mathbb {P}\left(X_{n+1}=i_{n+1}\mid X_n=i_n,\ldots ,X_0=i_0\right) \end{align} \]
Второй множитель по (i) равен \(\mathbb {P}\left(X_{n+1}=i_{n+1}\mid X_n=i_n\right)\). Первый — это (ii) уровня \(m-1\) с «настоящим» в \(n+1\), равен \(\mathbb {P}\left(X_{n+m}=i_{n+m}\mid X_{n+1}=i_{n+1}\right)\). Итого сумма \(=\sum_{i_{n+1}}\mathbb {P}\left(X_{n+m}=i_{n+m}\mid X_{n+1}=i_{n+1}\right)\mathbb {P}\left(X_{n+1}=i_{n+1}\mid X_n=i_n\right)\). Та же выкладка (полная вероятность + (i) + ИП), применённая напрямую к \(\mathbb {P}\left(X_{n+m}=i_{n+m}\mid X_n=i_n\right)\), даёт ту же самую сумму. Значит выражения равны — это (ii) для \(m\).
(ii)⟹(i): частный случай \(m=1\).
(ii)⟹(iii): достаточно научиться убирать самую раннюю точку разрежения \(n_0\) из условия (дальше — по одной точке индукцией). По формуле полной вероятности, вставляя между \(n_0\) и \(n_1\) полную (не разреженную) траекторию \(\mathbf c=(c_{n_0+1},\ldots ,c_{n_1-1})\):
\[ \mathbb {P}\left(X_{n_{k+1}}=i_{k+1}, X_{n_1}=i_1,X_{n_0}=i_0,\ldots \right) = \sum _{\mathbf c}\mathbb {P}\left(X_{n_{k+1}}=i_{k+1}, X_{n_1}=i_1, X_{n_1-1}=c_{n_1-1},\ldots ,X_{n_0+1}=c_{n_0+1}, X_{n_0}=i_0,\ldots \right) \]
Для каждого слагаемого условие уже содержит полную историю вплоть до \(n_1\) — применяем (ii): хвост зависит только от \(X_{n_1}=i_1\), множитель выносится из суммы по \(\mathbf c\), а оставшаяся сумма по \(\mathbf c\) — это в точности \(\mathbb {P}\left(X_{n_1}=i_1,X_{n_0}=i_0,\ldots \right)\). После деления зависимость от \(i_0\) (и более ранних точек) сокращается.
(iii)⟹(ii): частный случай \(n_r=r\).
5.2 Доказательство леммы Лемма 2 (свойства \(\mathbf{P}_{k\to l}\))
(1) Стохастичность. \(\left(\mathbf{P}_{k\to l}\right)_{ij}=\mathbb {P}\left(X_l=j\mid X_k=i\right)\ge 0\) очевидно; \(\sum_j\mathbb {P}\left(X_l=j\mid X_k=i\right)=\mathbb {P}\left(X_l\in \mathcal{X}\mid X_k=i\right)=1\).
(2) \(\left(\mathbf{P}_{k\to k}\right)_{ij}=\mathbb {P}\left(X_k=j\mid X_k=i\right)\): при \(i=j\) вероятность \(1\), при \(i\ne j\) события несовместны, вероятность \(0\). Т.е. \(=\delta_i^j\).
(3) Колмогоров-Чепмен. Для \(k<l<n\), по полной вероятности и марковскому свойству (форма (iii) леммы Лемма 1):
\[ \begin{align} \left(\mathbf{P}_{k\to n}\right)_{ij}=\mathbb {P}\left(X_n=j\mid X_k=i\right) & = \sum _{i'}\mathbb {P}\left(X_n=j,X_l=i'\mid X_k=i\right) \\ & = \sum _{i'}\mathbb {P}\left(X_n=j\mid X_l=i',X_k=i\right)\cdot \mathbb {P}\left(X_l=i'\mid X_k=i\right) \\ & \overset {\text{Марк. св-во}}{=} \sum _{i'}\mathbb {P}\left(X_n=j\mid X_l=i'\right)\cdot \mathbb {P}\left(X_l=i'\mid X_k=i\right) \\ & = \sum _{i'}\left(\mathbf{P}_{k\to l}\right)_{ii'}\left(\mathbf{P}_{l\to n}\right)_{i'j} \end{align} \]
5.3 Доказательство теорем Теорема 1 и Теорема 2 (существование МЦДВ)
Строим по теореме Колмогорова о согласованных распределениях (теорема Колмогорова о согласованных распределениях) распределение \(\mathbb {P}\) на \(\mathcal{X}^{\mathbb {Z}_+}\) (с цилиндрической \(\sigma\)-алгеброй), задав конечномерные распределения формулой из леммы Лемма 2: \[ \mathbf{P}_{i_0,\ldots ,i_n}\left(\right) := \Pi _{i_0}\cdot \left(\mathbf{P}_{0\to 1}\right)_{i_0i_1}\cdots \left(\mathbf{P}_{n-1\to n}\right)_{i_{n-1}i_n} \] Проверка согласованности. По стохастичности \(\mathbf{P}_{n-1\to n}\) (лемма Лемма 2, свойство 1): \[ \sum _{i_n}\mathbf{P}_{i_0,\ldots ,i_n}\left(\right) = \Pi _{i_0}\cdots \left(\mathbf{P}_{n-2\to n-1}\right)_{i_{n-2}i_{n-1}}\cdot \underbrace{\sum _{i_n}\left(\mathbf{P}_{n-1\to n}\right)_{i_{n-1}i_n}}_{=1} = \mathbf{P}_{i_0,\ldots ,i_{n-1}}\left(\right) \] — условие согласованности выполнено. Теорема Колмогорова даёт \(\mathbb {P}\) на \(\mathcal{X}^{\mathbb {Z}_+}\) с этими конечномерными распределениями; полагаем \(X_n:=\pi_n\) (проекция). У получившегося процесса ровно нужные начальное распределение (\(\mathbf{P}_{i_0}\left(\right)=\Pi_{i_0}\) при \(n=0\)) и переходные вероятности (восстанавливаются из совместных через лемму Лемма 2). Однородный случай (теорема Теорема 2) — частный случай при \(\mathbf{P}_{k\to k+1}\equiv \mathbf{P}\).
5.4 Доказательство теоремы Теорема 3 (элементарная теорема восстановления для отложенного процесса)
Пусть \(N'_t\) — обычный (не отложенный) процесс восстановления по \(\xi_2,\xi_3,\ldots\), \(m(t):=\mathbb {E}\left[N'_t\right]\) — его функция восстановления; по обычной элементарной теореме восстановления \(m(t)/t\to 1/\mathbb {E}\left[\xi_2\right]\).
Связь \(N_t\) и \(N'_t\). Если \(\xi_1\le t\): после первого скачка в момент \(\xi_1\) дальнейшие скачки — это ровно процесс \(N'\), сдвинутый на \(\xi_1\), т.е. \(N_t=1+N'_{t-\xi_1}\). Если \(\xi_1>t\): \(N_t=0\). Итого \(N_t=\; \mathbb {1}_{\xi_1\le t}\left(1+N'_{t-\xi_1}\right)\), и, пользуясь независимостью \(\xi_1\) от \((\xi_2,\xi_3,\ldots )\):
\[ \mathbb {E}\left[N_t\right] = \mathbb {E}\left[\; \mathbb {1}_{\xi _1\le t}\left(1+m(t-\xi _1)\right)\right] \]
Предельный переход. Т.к. \(\mathbb {P}\left(\xi_1<\infty \right)=1\), для п.н. \(\omega\) при \(t\to \infty\) имеем \(\xi_1(\omega )\le t\) и
\[ \frac{\; \mathbb {1}_{\xi _1\le t}\left(1+m(t-\xi _1)\right)}{t} = \frac{1+m(t-\xi _1)}{t-\xi _1}\cdot \frac{t-\xi _1}{t} \xrightarrow [t\to \infty ]{} \frac{1}{\mathbb {E}\left[\xi _2\right]}\cdot 1 \]
Стандартная линейная мажорация функции восстановления \(m(s)\le c(1+s)\) даёт равномерную интегрируемость и позволяет перейти к пределу под знаком \(\mathbb {E}\left[\right]\) (теорема о мажорируемой сходимости), откуда \(\mathbb {E}\left[N_t\right]/t\to 1/\mathbb {E}\left[\xi_2\right]\).
5.5 Доказательство теоремы Теорема 4 (предел по Чезаро для неприводимой конечной цепи)
Как уже отмечено в основном тексте: для неприводимой конечной цепи \(\mathbb {P}_{i}\left(\xi^{(1)}_j<\infty \right)=1\) (по лемме Лемма 3), а \(\xi^{(2)}_j,\xi^{(3)}_j,\ldots\) — НОРСВ с \(\mathbb {E}_{j}\left[\xi^{(2)}_j\right]=\mathbb {E}_{j}\left[T_j\right]\). Применяя теорему Теорема 3 к \(\xi_1:=\xi^{(1)}_j\), \(\xi_2,\xi_3,\ldots :=\xi^{(2)}_j,\xi^{(3)}_j,\ldots\): \[ \frac{\mathbb {E}_{i}\left[V^{(n-1)}_j\right]}{n}\xrightarrow [n\to \infty ]{}\frac{1}{\mathbb {E}_{j}\left[T_j\right]} \] Осталось заметить (уже показано в основном тексте), что \(\left(\frac1n\sum_{k=0}^{n-1}\mathbf{P}^k\right)_{ij}=\frac1n\mathbb {E}_{i}\left[V^{(n-1)}_j\right]\) — это в точности левая часть.
5.6 Доказательство теоремы Теорема 5 (существование стационарного распределения)
Рассмотрим симплекс \(\Delta =\left\{ \Pi \in \mathbb {R}^{\left|\mathcal{X}\right|}: \Pi_i\ge 0,\sum_i\Pi_i=1\right\}\) — компактное выпуклое множество. Отображение \(f(\Pi ):=\Pi \cdot \mathbf{P}\) непрерывно (линейно) и переводит \(\Delta\) в себя: для \(\Pi \in \Delta\), \((\Pi \mathbf{P})_j=\sum_i\Pi_i\mathbf{P}_{ij}\ge 0\) и \(\sum_j(\Pi \mathbf{P})_j=\sum_i\Pi_i\underbrace{\sum_j\mathbf{P}_{ij}}_{=1}=1\). По теореме Брауэра о неподвижной точке существует \(\Pi^*\in \Delta\) с \(\Pi^*\mathbf{P}=\Pi^*\).
5.7 Доказательство теоремы Теорема 6 (единственность = строка предела по Чезаро)
Пусть \(\Pi\) — любое стационарное распределение, \(\Pi^{\text{Чез}}\) — матрица из теоремы Теорема 4 (все строки совпадают). Тогда \(\Pi \cdot \frac1n\sum_{k=0}^{n-1}\mathbf{P}^k = \frac1n\sum_{k=0}^{n-1}\Pi \mathbf{P}^k=\frac1n\sum_{k=0}^{n-1}\Pi =\Pi\). Переходя к пределу \(n\to \infty\): \(\Pi \cdot \Pi^{\text{Чез}}=\Pi\). Раскрывая покоординатно и используя \(\sum_i\Pi_i=1\) и совпадение строк \(\Pi^{\text{Чез}}\), левая часть равна этой общей строке. Значит \(\Pi =\) (строка \(\Pi^{\text{Чез}}\)) — единственно возможное значение.
5.8 Доказательство леммы Лемма 3 (возвратность — характеристика класса; замкнутый конечный класс возвратен)
Критерий возвратности: \(i\) возвратно \(\iff \sum_{n=1}^\infty p_{ii}^{(n)}=\infty\). Пусть \(f_i:=\mathbb {P}_{i}\left(T_i<\infty \right)\), \(V_i:=\sum_{n=0}^\infty \; \mathbb {1}_{X_n=i}\). По строго марковскому свойству и тому, что \(\xi_j^{(k)}\), \(k\ge 2\) — НОРСВ, \(\mathbb {P}_{i}\left(V_i\ge k+1\right)=f_i^k\). Значит \(\mathbb {E}_{i}\left[V_i\right]=\sum_{k\ge 0}f_i^k\), что равно \(\frac{1}{1-f_i}<\infty\) при \(f_i<1\) и \(+\infty\) при \(f_i=1\). С другой стороны, \(\mathbb {E}_{i}\left[V_i\right]=\sum_n\mathbb {P}_{i}\left(X_n=i\right)=\sum_n p_{ii}^{(n)}\). Значит \(\sum_n p_{ii}^{(n)}=\infty \iff f_i=1 \iff i\) возвратно.
Возвратность — характеристика класса. Пусть \(i\leftrightarrow j\): \(\exists n,m\) с \(\alpha := p_{ij}^{(n)}>0\), \(\beta := p_{ji}^{(m)}>0\). Для любого \(r\ge 0\) (путь \(j\to i\to (\text{стоять }r)\to i\to j\)): \(p_{jj}^{(m+r+n)}\ge \beta \cdot p_{ii}^{(r)}\cdot \alpha\). Суммируя по \(r\ge 0\): \(\sum_k p_{jj}^{(k)}\ge \alpha \beta \sum_r p_{ii}^{(r)}\). Значит \(\sum p_{ii}=\infty \Rightarrow \sum p_{jj}=\infty\); симметрично — обратно.
Замкнутый конечный класс \(C\) возвратен. Зафиксируем \(i\in C\). Т.к. \(C\) замкнут, \(\sum_{k\in C}V_k=\sum_n\; \mathbb {1}_{X_n\in C}=+\infty\) тождественно. Если бы каждое \(V_k\) (\(k\in C\)) было п.н. конечно, то конечная сумма п.н.-конечных величин была бы п.н. конечна — противоречие. Значит найдётся \(k_0\in C\) с \(\mathbb {P}_{i}\left(V_{k_0}=\infty \right)>0\), т.е. \(k_0\) возвратно. По характеристике класса, \(i\) тоже возвратно.
Незамкнутый класс \(C\) невозвратен. \(\exists i\in C, j\notin C\) с \(p_{ij}>0\). Если бы был возврат из \(j\) в \(i\), то \(i,j\) сообщались бы, т.е. \(j\in C\) — противоречие. Значит \(1-f_i\ge \mathbb {P}_{i}\left(X_1=j\right)=p_{ij}>0\), т.е. \(f_i<1\).
Весь \(\mathcal{X}\) — один класс, тривиально замкнутый. По лемме Лемма 3 все состояния возвратны: \(\mathbb {P}_{j}\left(T_j<\infty \right)=1\). Пусть \(u_i:=\mathbb {P}_{i}\left(\tau_j<\infty \right)\); по формуле полной вероятности (первый шаг) \(u_j=1\), \(u_i=\sum_k\mathbf{P}_{ik}u_k\) при \(i\ne j\). Пусть \(i^*=\arg \min_i u_i\). Если \(u_{i^*}<1\), то, т.к. \(u_{i^*}\) — взвешенное среднее величин \(u_k\ge u_{i^*}\), равенство возможно только если \(u_k=u_{i^*}\) для всех \(k\) с \(\mathbf{P}_{i^*k}>0\). По неприводимости из \(i^*\) можно дойти до \(j\) по цепочке положительных переходов — вдоль неё \(u\equiv u_{i^*}\), в частности \(u_j=u_{i^*}<1\) — противоречие. Значит \(u_{i^*}=1\), т.е. \(u_i\equiv 1\).
5.9 Доказательство леммы Лемма 4 (период — характеристика класса)
Пусть \(i\leftrightarrow j\), \(\alpha =p_{ij}^{(n)}>0\), \(\beta =p_{ji}^{(m)}>0\). Для любого \(r\ge 1\) с \(p_{jj}^{(r)}>0\) (путь \(i\to j\to j\to i\)): \(p_{ii}^{(n+r+m)}\ge \alpha \cdot p_{jj}^{(r)}\cdot \beta >0 \Rightarrow d(i)\mid (n+r+m)\). Также \(p_{ii}^{(n+m)}\ge \alpha \beta >0\Rightarrow d(i)\mid (n+m)\). Вычитая: \(d(i)\mid r\) для каждого \(r\) из множества, задающего \(d(j)\) — значит \(d(i)\mid d(j)\). Симметрично \(d(j)\mid d(i)\). Значит \(d(i)=d(j)\).
5.10 Доказательство теоремы Теорема 7 (эргодическая теорема) и следствия Следствие 1
Пункт (i) — частный случай теорем Теорема 5 и Теорема 6 (не требуют апериодичности).
Пункт (ii), метод склейки (coupling). Пусть \((Y_n)\) — независимая копия цепи с \(Y_0\sim \Pi\) (тогда \(Y_n\sim \Pi \; \forall n\)). \(Z_n=(X_n,Y_n)\) — МЦДВ на \(\mathcal{X}\times \mathcal{X}\) с переходами \(\mathbf{P}_{xx'}\mathbf{P}_{yy'}\).
Неприводимость \(Z\). По лемме Лемма 5 для эргодической \(\mathbf{P}\) \(\exists m\): \(\mathbf{P}^m>0\) всюду. Тогда \(\mathbf{P}^m_{xx'}\mathbf{P}^m_{yy'}>0\) для любых \((x,y),(x',y')\) — \(Z\) неприводима (и конечна).
По лемме Лемма 3, конечная неприводимая (замкнутая) \(Z\) возвратна: диагональ \(\Delta =\left\{ (a,a)\right\}\) достигается п.н. Пусть \(\tau =\min \left\{ n:X_n=Y_n\right\} <\infty\) п.н.
Определим \(\tilde Y_n:= Y_n\) при \(n<\tau\), \(\tilde Y_n:= X_n\) при \(n\ge \tau\). По строго марковскому свойству замена хвоста не меняет распределение: \(\tilde Y_n\sim \Pi \; \forall n\). Т.к. \(\left\{ X_n=j\right\}\) и \(\left\{ \tilde Y_n=j\right\}\) различаются только на \(\left\{ \tau >n\right\}\):
\[ \left|\mathbb {P}_{i}\left(X_n=j\right)-\Pi _j\right|=\left|\mathbb {P}\left(X_n=j\right)-\mathbb {P}\left(\tilde Y_n=j\right)\right|\le \mathbb {P}\left(\tau >n\right)\xrightarrow [n\to \infty ]{}0 \]
т.е. \(\mathbf{P}^n_{ij}\to \Pi_j\) для всех \(i,j\).
Следствие Следствие 1. \(\Pi^{(0)}\mathbf{P}^n=\sum_i\Pi^{(0)}_i\left(\mathbf{P}^n\right)_{i\cdot }\to \sum_i\Pi^{(0)}_i\Pi =\Pi \cdot \underbrace{\sum_i\Pi^{(0)}_i}_{=1}=\Pi\).
5.11 Доказательство леммы Лемма 5 (критерий апериодичности Фробениуса)
Пусть \(R_i:=\left\{ n\ge 1: p_{ii}^{(n)}>0\right\}\). \(R_i\) замкнуто относительно сложения (\(a,b\in R_i\Rightarrow p_{ii}^{(a+b)}\ge p_{ii}^{(a)}p_{ii}^{(b)}>0\)), и \(d(i)=\gcd (R_i)\).
Апериодичность \(\iff\) \(\exists m_0: p_{ii}^{(m)}>0\; \forall m\ge m_0\). Числовой факт (проблема Фробениуса о монетах): числовое множество, замкнутое относительно сложения, с \(\gcd =1\), содержит все достаточно большие натуральные числа; обратно, если \(\gcd (R_i)=d>1\), то \(R_i\subset d\mathbb {N}\) никогда не содержит все большие числа.
\(\mathbf{P}^m>0\) всюду \(\Rightarrow\) апериодичность. Пусть \(\mathbf{P}^m>0\). Тогда \(d(i)\mid m\; \forall i\). Допустим \(d:= d(i)>1\) для некоторого (а по лемме Лемма 4 — для всех, цепь неприводима) \(i\). Классы \(C_r:=\left\{ k: \exists n\equiv r\! \! \pmod d,\, p_{i_0 k}^{(n)}>0\right\}\), \(r=0,\ldots ,d-1\) (для фиксированного \(i_0\)), разбивают \(\mathcal{X}\), и за один шаг цепь переходит из \(C_r\) в \(C_{r+1\bmod d}\) (проверяется через уравнения Колмогорова-Чепмена и определение \(d\) как НОД). Тогда из \(C_0\) за ровно \(m\) шагов можно попасть только в \(C_{m\bmod d}\) — противоречие с \(\mathbf{P}^m>0\) всюду при \(d>1\).
Апериодичность \(\Rightarrow\) \(\exists m: \mathbf{P}^m>0\) всюду. По неприводимости для каждой пары \((i,j)\) \(\exists n_{ij}\) с \(p_{ij}^{(n_{ij})}>0\); т.к. \(\mathcal{X}\) конечно, \(N:=\max_{ij}n_{ij}<\infty\). По апериодичности \(\exists m_0(i)\): \(p_{ii}^{(r)}>0\; \forall r\ge m_0(i)\); \(M=\max_i m_0(i)\). При \(m\ge M+N\): \(p_{ij}^{(m)}\ge p_{ii}^{(m-n_{ij})}\cdot p_{ij}^{(n_{ij})}>0\).
5.12 Доказательство леммы Лемма 6 (положительная/нулевая возвратность — характеристика класса)
Пусть \(i\leftrightarrow j\), оба возвратны (по лемме Лемма 3 это уже одно на класс). Пусть \(\gamma_i:=\mathbb {E}_{j}\left[\sum_{n=0}^{T_j-1}\; \mathbb {1}_{X_n=i}\right]\) — среднее число визитов в \(i\) за одну экскурсию из \(j\) в \(j\). По усиленному закону больших чисел, применённому к отложенному процессу восстановления по циклам \(j\to j\) (визиты в \(i\) внутри каждого цикла — i.i.d. слагаемые): \[ \frac{1}{N}\sum _{n=0}^{N-1}\; \mathbb {1}_{X_n=i} \xrightarrow [N\to \infty ]{\text{п.н.}} \frac{\gamma _i}{\mathbb {E}_{j}\left[T_j\right]} \] С другой стороны, та же частота, вычисленная относительно самого состояния \(i\) (циклы \(i\to i\)), даёт предел \(1/\mathbb {E}_{i}\left[T_i\right]\). Приравнивая: \[ \frac{1}{\mathbb {E}_{i}\left[T_i\right]} = \frac{\gamma _i}{\mathbb {E}_{j}\left[T_j\right]} \quad \Longrightarrow \quad \mathbb {E}_{i}\left[T_i\right] = \frac{\mathbb {E}_{j}\left[T_j\right]}{\gamma _i} \] Т.к. \(i,j\) сообщаются, \(0<\gamma_i<\infty\). Значит \(\mathbb {E}_{i}\left[T_i\right]<\infty \iff \mathbb {E}_{j}\left[T_j\right]<\infty\).
5.13 Доказательство теоремы Теорема 8 (общая теорема для счётного числа состояний)
Часть 1: положительно-возвратна \(\Rightarrow\) \(\exists\) стац. распределение \(\Pi_i=1/\mathbb {E}_{i}\left[T_i\right]\). Зафиксируем \(j\in \mathcal{X}\), \(\gamma_i:=\mathbb {E}_{j}\left[\sum_{n=0}^{T_j-1}\; \mathbb {1}_{X_n=i}\right]\) (среднее число визитов в \(i\) за экскурсию \(j\to j\)).
\(\gamma \mathbf{P}=\gamma\). Каждый визит в состояние \(k\) внутри экскурсии порождает ровно один следующий шаг; переходя от \(k\) к \(i\) с вероятностью \(\mathbf{P}_{ki}\) и суммируя по всем визитам в \(k\) и по \(k\), получаем среднее число “приходов” в \(i\): \(\sum_k\gamma_k\mathbf{P}_{ki}\). Это же — среднее число визитов в \(i\) внутри экскурсии (каждый визит в \(i\), кроме, возможно, старта, — это приход с предыдущего шага). Баланс входов/выходов по замкнутой экскурсии: \(\gamma_i=\sum_k\gamma_k\mathbf{P}_{ki}\).
Сумма. \(\sum_i\gamma_i=\mathbb {E}_{j}\left[T_j\right]\) (каждый из \(T_j\) шагов экскурсии учтён ровно один раз).
При \(\mathbb {E}_{j}\left[T_j\right]<\infty\) нормируем: \(\Pi_i:=\gamma_i/\mathbb {E}_{j}\left[T_j\right]\) — стационарное распределение, \(\Pi_j=1/\mathbb {E}_{j}\left[T_j\right]\). По лемме Лемма 6, \(j\) произвольно, значит \(\Pi_i=1/\mathbb {E}_{i}\left[T_i\right]\) для каждого \(i\).
Обратно. Пусть \(\Pi\) стационарно. По неприводимости \(\Pi_i>0\; \forall i\) (если \(\Pi_k>0\) и \(p_{ki}^{(n)}>0\), то \(\Pi_i\ge \Pi_k p_{ki}^{(n)}>0\)). Усиленный ЗБЧ для отложенного процесса восстановления при старте из \(\Pi\) даёт частоту визитов в \(i\), равную одновременно \(1/\mathbb {E}_{i}\left[T_i\right]\) (по построению) и \(\Pi_i\) (по эргодической теореме Биркгофа-Хинчина для стационарной цепи). Значит \(\mathbb {E}_{i}\left[T_i\right]=1/\Pi_i<\infty\).
Часть 2: стационарная мера при возвратности, единственность с точностью до масштаба. Существование — то же построение \(\gamma\) (нужна лишь возвратность \(j\); \(\sum \gamma_i=\mathbb {E}_{j}\left[T_j\right]\) может быть и \(+\infty\)). Строгая положительность \(\gamma_i>0\) — по неприводимости \(i\) достижимо из \(j\) с положительной вероятностью за конечное число шагов, значит посещается за экскурсию с положительной вероятностью. Единственность с точностью до масштаба: если \(\Psi\) — другая стационарная мера, то \(\Psi =\Psi_j\cdot \gamma\) (конструкция через выражение \(\Psi_i\) суммой по путям, приходящим в \(i\); не привожу полностью — самая техническая часть, см. (Grimmett и Stirzaker 2020 г., гл. 6)).
Классификация через \(\sum \Psi_i\). При положительной возвратности \(\gamma_i=\mathbb {E}_{j}\left[T_j\right]\cdot \Pi_i\) (часть 1 + единственность с точностью до масштаба), \(\sum \gamma_i=\mathbb {E}_{j}\left[T_j\right]<\infty\). При нулевой возвратности \(\mathbb {E}_{j}\left[T_j\right]=+\infty =\sum_i\gamma_i\).
Часть 3: \(\mathbf{P}^n_{ij}\to 1/\mathbb {E}_{j}\left[T_j\right]\). То же рассуждение методом склейки, что в доказательстве теоремы Теорема 7, работает и для счётного \(\mathcal{X}\); единственное отличие — возвратность произведения \(Z=(X,Y)\) на \(\mathcal{X}\times \mathcal{X}\) здесь не следует автоматически из леммы Лемма 3 (которая требует конечности), а нуждается в отдельном аргументе о возвратности произведения двух независимых копий одной и той же возвратной апериодической цепи. За деталями — в (Grimmett и Stirzaker 2020 г., п. 6.4).
использованная литература
Grimmett, Geoffrey, и David Stirzaker. 2020 г. Probability and Random Processes. 4-я изд. OUP Oxford.
Meyer, Carl D. 2001 г. Matrix Analysis and Applied Linear Algebra. SIAM.
Сноски
Это верно лишь когда в цепи конечное число состояний. Если в цепи бесконечное число состояний, то в ней может найтись замкнутый класс состояний, явл. невозвратным. См. подробности ниже.↩︎
Опять же, это верно, только если количество состояний конечно. Как бы парадоксально это ни казалось, цепь с бесконечным количеством состояний может состоять из одного класса, являющегося транзитным. Пример – простейшее случайное блуждание с \(p\neq \frac{1}{2}\). Подробнее см. ниже.↩︎