Марковские цепи с дискретным временем (МЦДВ)

ПредупреждениеЧерновик

Этот конспект ещё находится в процессе редактуры: в тексте могут встречаться опечатки, неточности и локально не проработанные места. Если что-то нашли — сообщите, пожалуйста, автору (контакты на странице курса).

Простое случайное блуждание и ветвящийся процесс Гальтона-Ватсона обладали следующим свойством: при условии сохранения значения на \(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}\).

Mn-extraДополнительно

Что если рассматривать будущее процесса не через \(1\) шаг, а через \(m\) шагов? Или рассматривать настоящее и прошлое выборочно, не во всех точках с \(0\) по \(n-1\)? Оказывается, во всех этих более общих случаях для марковского процесса будущее не будет зависеть от прошлого.

Лемма 1 Пусть \((X_n)\) – случайный процесс со значениями в дискретном пространстве \(\mathcal{X}\). Следующие условия эквивалентны:

1. \((X_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 \in \mathbb {N}\) и для всех состояний \(i_{0}, \ldots , i_{n}, i_{n+1} \in \mathcal{X}\), таких что выражения слева и справа имеют смысл.

2. Выполнено

\[ \mathbb {P}\left(X_{n+m} = i_{n+m} \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+m} = i_{n+m} \mid X_{n} = i_{n}\right) \]

для всех \(n, m \in \mathbb {N}\) и для всех состояний \(i_{0}, \ldots , i_{n}, i_{n+m} \in \mathcal{X}\), таких что выражения слева и справа имеют смысл.

3. Выполнено

\[ \mathbb {P}\left(X_{n_{k+1}} = i_{n_{k+1}} \quad \left| \quad \begin{array}{rl} X_{n_k} & = i_{n_k} \\ X_{n_{k-1}} & = i_{n_{k-1}} \\ \cdots & \cdots \\ X_{n_0} & = i_{n_0} \\ \end{array}\right.\right) \; = \; \mathbb {P}\left(X_{n_{k+1}} = i_{n_{k+1}} \mid X_{n_k} = i_{n_k}\right) \]

для всех целых неотрицательных \(n_0 < n_1 < \ldots < n_k < n_{k+1}\) и для всех состояний \(i_{n_0}, \ldots , i_{n_k}, i_{n_{k+1}} \in \mathcal{X}\), таких что выражения слева и справа имеют смысл.

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 \]

ExampleПример 1

Пусть однородная марковская цепь состоит из \(4\)-х состояний (\(1,2,3,4\)), пусть известно начальное распределение: \[ \Pi ^{(0)} = \left(0.1, 0.3, 0.4, 0.2\right) \] Пусть известна матрица переходов за \(1\) шаг: \[ \mathbf{P} = \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \\ 0.3 & 0.3 & 0.3 & 0.1 \\ 0 & 0 & 1 & 0 \\ 0.4 & 0.4 & 0 & 0.2 \end{pmatrix} \] Найдите распределение \(X_3\), т.е. распределение цепи после \(3\)-х шагов.

SolutionРешение

Необходимо найти строку \[ \Pi ^{(3)} = \left(\mathbb {P}\left(X_3 = 1\right), \mathbb {P}\left(X_3 = 2\right), \mathbb {P}\left(X_3 = 3\right), \mathbb {P}\left(X_3 = 4\right)\right) \] По формуле: \[ \begin{align} \Pi ^{(3)} & = \Pi ^{(0)} \cdot \mathbf{P}^3 = \left(0.1, 0.3, 0.4, 0.2\right) \cdot \begin{pmatrix} 0.34 & 0.34 & 0.27 & 0.05 \\ 0.244 & 0.244 & 0.474 & 0.038 \\ 0 & 0 & 1 & 0 \\ 0.352 & 0.352 & 0.24 & 0.056 \\ \end{pmatrix} = \\ & = \left(0.1776, 0.1776, 0.6172, 0.0276\right) \end{align} \]

Пока мы марковским свойством не пользовались. Оно требуется при попытке посчитать конечномерные распределения для МЦДВ. А именно,

\[ \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} \]

ExampleПример 2

В условиях предыдущего примера вычислите \[ \mathbb {P}\left(\begin{array}{rl} X_{4} & = 3 \\ X_{3} & = 2 \\ X_{2} & = 4 \\ X_{1} & = 2 \\ X_{0} & = 1 \\ \end{array}\right) \]

SolutionРешение

Имеем \[ \begin{align} \mathbb {P}\left(\begin{array}{rl} X_{4} & = 3 \\ X_{3} & = 2 \\ X_{2} & = 4 \\ X_{1} & = 2 \\ X_{0} & = 1 \\ \end{array}\right) & = \begin{array}{r} \mathbb {P}\left(X_4 = 3 \mid X_3 = 2\right) \cdot \\ \cdot \mathbb {P}\left(X_3 = 2 \mid X_2 = 4\right) \cdot \\ \cdot \mathbb {P}\left(X_2 = 4 \mid X_1 = 2\right) \cdot \\ \cdot \mathbb {P}\left(X_1 = 2 \mid X_0 = 1\right) \cdot \\ \cdot \mathbb {P}\left(X_{0} = 1\right) \\ \end{array} = \\ & = 0.3 \cdot 0.4 \cdot 0.1 \cdot 0.5 \cdot 0.1 = 0.06 \% \end{align} \]

Mn-extraДополнительно

Введем дополнительное обозначение для (матрицы) переходных вероятностей с \(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}\). Перечислим свойства переходных вероятностей.

Лемма 2 Пусть \(\mathbf{P}_{k \to l}\), \(0 \leq k \leq l\) – матрицы переходных вероятностей для некоторой МЦДВ. Тогда

1. Каждая из матриц является стохастической: все ее элементы неотрицательны и сумма элементов по каждой строке дает \(1\).

2. \(\mathbf{P}_{k \to k} = E\) для любого \(k \in \mathbb {Z}_+\). А именно, \(\left(\mathbf{P}_{k \to k}\right)_{i,j}= \delta_{i}^{j}\).

3. выполнены уравнения Колмогорова-Чепмена: для любых \(k<l<n, i, j \in \mathcal{X}\)

   \[ \mathbf{P}_{k \to n} = \mathbf{P}_{k \to l} \cdot \mathbf{P}_{l \to n} \]

   Под этим равенством мы понимаем следующее

   \[ \begin{align} \left(\mathbf{P}_{k \to n}\right)_{i,j} & = \sum _{i' \in \mathcal{X}} \left(\mathbf{P}_{k \to l}\right)_{i,i'} \\ & \quad \cdot \left(\mathbf{P}_{l \to n}\right)_{i',j} \end{align} \]

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

Теорема 1 Пусть \(\mathcal{X}\) – не более чем счетное множество, \(\Pi\) – распределение вероятностей на \(\mathcal{X}\), а матрицы \(\mathbf{P}_{k \to l}\), удовлетворяют свойствам из леммы Лемма 2. Тогда существует МЦДВ с фазовым пространством \(\mathcal{X}\), начальным распределением \(\Pi\) и переходными вероятностями \(\mathbf{P}_{k \to l}\).

Для однородной МЦДВ все упрощается.

Теорема 2 Пусть \(\mathcal{X}\) – не более чем счетное множество, \(\Pi\) – распределение вероятностей на \(\mathcal{X}\), а \(\mathbf{P}\) – некоторая стохастическая матрица размерности \(\left|\mathcal{X}\right| \times \left|\mathcal{X}\right|\) (она, возможно, бесконечна). Тогда существует однородная МЦДВ с фазовым пространством \(\mathcal{X}\), начальным распределением \(\Pi\) и переходными вероятностями за \(1\) шаг \(\mathbf{P}\).

Эти теоремы – прямое следствие теоремы Колмогорова о построении распределения процесса. Напомним, что теорема Колмогорова на пространстве траекторий \(\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) \]

Это согласуется с теми обозначениями, которые у нас были при изучении случайного блуждания.

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

Состояния и переходные вероятности между ними удобно изображать в виде ориентированного графа со взвешенными ребрами.

ExampleПример 3

Покажите, что различные виды случайного блуждания, приведенные ниже, являются однородными марковскими цепями. Нарисуйте состояния и переходные вероятности.

1. Обычное простейшее случайное блуждание;

2. С поглощающим барьером в \(1\);

3. С удерживающим барьером в \(1\);

4. С поглощающими барьерами в \(0\) и в \(5\).

SolutionРешение

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

\[ S_{n+1} = S_{n} + \xi _n \]

где \(\xi_n\) либо вообще не зависит от \(S_1, S_2, \ldots , S_n\) (в пункте а)), либо зависит, но только от \(S_{n}\).

Enum-item1.

Простейшее случайное блуждание: граф состояний и переходных вероятностей, и (бесконечная) матрица переходных вероятностей, \(q := 1-p\).

Граф состояний простейшего случайного блуждания: вправо с вероятностью p, влево — с вероятностью 1−p.

\[ \mathbf{P} = \begin{pmatrix} & \cdots & -3 & -2 & -1 & 0 & 1 & 2 & 3 & \cdots \\ \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & ⋰ \\ -3 & \cdots & 0 & p & 0 & 0 & 0 & 0 & 0 & \cdots \\ -2 & \cdots & q & 0 & p & 0 & 0 & 0 & 0 & \cdots \\ -1 & \cdots & 0 & q & 0 & p & 0 & 0 & 0 & \cdots \\ 0 & \cdots & 0 & 0 & q & 0 & p & 0 & 0 & \cdots \\ 1 & \cdots & 0 & 0 & 0 & q & 0 & p & 0 & \cdots \\ 2 & \cdots & 0 & 0 & 0 & 0 & q & 0 & p & \cdots \\ 3 & \cdots & 0 & 0 & 0 & 0 & 0 & q & 0 & \cdots \\ \vdots & ⋰ & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix} \]

Матрица (бесконечная) переходных вероятностей обычного блуждания, \(q := 1-p\).

Enum-item2.

Простейшее случайное блуждание с поглощающим барьером в \(1\). Игрок играет, пока капитал не достигнет \(1\).

Простейшее случайное блуждание с поглощающим барьером в состоянии 1: попав в 1, цепь остаётся там навсегда.

Enum-item3.

Простейшее случайное блуждание с удерживающим барьером в \(1\).

Простейшее случайное блуждание с удерживающим («липким») барьером в состоянии 1: из 1 цепь остаётся на месте с вероятностью p и спускается вниз с вероятностью 1−p.

Enum-item4.

Простейшее случайное блуждание с поглощающими барьерами в \(0\) и в \(5\). Игрок играет, пока капитал не обнулится или пока он не достигнет \(5\).

Простейшее случайное блуждание с поглощающими барьерами в 0 и в 5 (игрок играет, пока капитал не обнулится или пока не достигнет 5).

Матрица переходных вероятностей для этого блуждания (при p = 0.6, q = 1-p = 0.4 – конкретные значения взяты для иллюстрации).

ExampleПример 4

Покажите, что процесс Гальтона-Ватсона является однородной марковской цепью. Нарисуйте состояния и переходные вероятности для ветвящегося процесса Гальтона-Ватсона с законом размножения частиц

1. \(\operatorname {Bin}(1, 0.7) = \operatorname {Ber}(0.7)\);

2. \(\operatorname {Bin}(2, 0.7)\);

3. \(\operatorname {Pois}(\lambda )\). В каком случае число состояний конечно?

SolutionРешение

Enum-item(1)

\(\operatorname {Bin}(1, 0.7) = \operatorname {Ber}(0.7)\): состояний конечное количество.

Простая цепь с двумя состояниями: 1 — невозвратное, 0 — поглощающее.

Enum-item(2)

\(\operatorname {Bin}(2, 0.7)\): состояний счетное количество.

Граф переходных вероятностей ветвящегося процесса Гальтона–Ватсона с законом размножения Bin(2, 0.7): состояние 0 поглощающее (вырождение), из состояния n достижимы состояния 0,…,2n.

Enum-item(3)

\(\operatorname {Pois}(\lambda )\): состояний счетное количество.

Тот же граф переходных вероятностей для закона размножения Pois(λ): показана лишь часть вероятностей — из состояния n достижимо любое состояние ≥ 0.

ProblemЗадача 1

Пусть \(\left\{ X_{n}, n \in \mathbb {Z}_{+}\right\}\) – марковская цепь с фазовым пространством \(\mathcal{X}= \left\{ 1,2,3\right\}\), начальным состоянием \(X_{0}=1\) п.н. и матрицей переходных вероятностей

Граф переходных вероятностей цепи с тремя состояниями: указаны все 9 вероятностей перехода (включая три петли-самопереходы).

1. Запишите матрицу переходных вероятностей \(\mathbf{P}\).

2. Пусть начальное распределение такое:

\[ \mathbb {P}\left(X_0 = k\right) = \begin{cases} 0.5, & k = 1\\ 0.3 & k = 2 \\ 0.2 & k = 3 \end{cases} \]

Найдите вероятность \(\mathbb {P}\left(X_{4} = 2\right)\).

3. Посчитайте \(\mathbf{P}^{10}\). Как выглядят ее строки?

4. Положим

\[ Y_{n} = \begin{cases} 1, & X_n = 1 \\ 2, & X_n \in \left\{ 2,3\right\} \end{cases} \]

Докажите, что \(Y_{n}\) – тоже марковская цепь, и найдите ее матрицу переходов.

Для возведения матрицы в степень воспользуйтесь компьютером.

ExampleПример 5

Пусть \((X_n)\) – это марковская цепь, пусть \(f: \mathcal{X} \to \mathcal{Y}\) – некоторая функция на фазовом пространстве, пусть \(Y_n = f(X_n)\), \(n \geq 0\).

1. Покажите, что если \(f\) инъективна (не склеивает точки), то \(Y_n\) – также марковская цепь.

2. Приведите пример МЦДВ \(X_n\) и функции \(f\) (неинъективной, соотв.), что \(Y_n = f(X_n)\) марковской цепью не будет.

SolutionРешение

Enum-item(1)

Если \(f\) инъективна, то по значениям \(Y_n\) однозначно восстанавливаются значения \(X_n\). А именно, не ограничивая общности, можно положить \(\mathcal{Y} := \operatorname {Im}f\). Тогда \(f\) станет биективной и \(X_{n} = f^{-1}(Y_n)\). Имеем

\[ \begin{align} \mathbb {P}\left(Y_{n+1} = r_{n+1} \quad \left| \quad \begin{array}{rl} Y_{n} & = r_{n} \\ Y_{n-1} & = r_{n-1} \\ \cdots & \cdots \\ Y_{0} & = r_{0} \\ \end{array}\right.\right) & = \mathbb {P}\left(X_{n+1} = f^{-1}(r_{n+1}) \quad \left| \quad \begin{array}{rl} X_{n} & = f^{-1}(r_{n}) \\ X_{n-1} & = f^{-1}(r_{n-1}) \\ \cdots & \cdots \\ X_{0} & = f^{-1}(r_{0}) \\ \end{array}\right.\right) = \\ & =\mathbb {P}\left(X_{n+1} = f^{-1}(r_{n+1}) \mid X_{n} = f^{-1}(r_{n})\right) = \\ & = \mathbb {P}\left(Y_{n+1} = r_{n+1} \mid Y_{n} = r_{n}\right) \end{align} \]

Enum-item(2)

Рассмотрим МЦДВ со следующими переходными вероятностями:

ЭВОЛЮЦИЯ РАСПРЕДЕЛЕНИЯ π_t t = 0

НАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ π₀ Σ = 1.000

−1

0

1

2

скорость

показать стационарное распределение π*

π* =−1 · 16.7%0 · 33.3%1 · 33.3%2 · 16.7%

у цепи период 2, поэтому π_t не сходится к π*; к нему сходится среднее по Чезаро (пунктир на графике)

Интерактив: эволюция распределения МЦДВ на состояниях −1, 0, 1, 2. Задайте начальное распределение π₀ ползунками-столбиками или числом (значения нормируются автоматически при нажатии «Играть»/«Шаг»/«Сброс») или выберите пресет: размер и заливка вершин показывают текущее π_t = π₀Pᵗ, а график ниже — траектории π_t(s) по шагам. Флажок показывает стационарное распределение π: у цепи период 2, поэтому π_t колеблется и к π сходится лишь среднее по Чезаро (пунктирные линии).

Пусть \(f(x) = x^2\). Тогда событие \(Y_{2} = 0\) при условии \(Y_{1} = 1\), \(Y_{0} = 4\) восстанавливается однозначно:

\[ \begin{align} \left\{ Y_1 = 1, Y_0 = 4\right\} & = \left\{ X_{1} = 1, X_{0} = 2\right\} \\ \mathbb {P}\left(Y_{2} = 0 \mid Y_1 = 1, Y_0 = 4\right) & = \mathbb {P}\left(Y_2 = 0 \mid X_{1} = 1, X_{0} = 2\right) = \\ & = \mathbb {P}\left(X_{2} = 0 \mid X_{1} = 1, X_{0} = 2\right) = \frac{1}{2} \end{align} \]

С другой стороны, событие \(Y_{2} = 0\) при условии \(Y_{1} = 1\), \(Y_{0} = 0\) не восстанавливается однозначно:

\[ \left\{ Y_1 = 1, Y_0 = 0\right\} = \left\{ X_{1} = 1, X_{0} = 0\right\} \sqcup \left\{ X_{1} = -1 , X_{0} = 0\right\} \]

Вероятность:

\[ \begin{align} \mathbb {P}\left(Y_{2} = 0 \mid Y_1 = 1, Y_0 = 0\right) & = \begin{array}{l} \mathbb {P}\left(X_{2} = 0 \mid X_1 = 1\right) \cdot \\ \cdot \mathbb {P}\left(X_{1} = 1 \mid X_{0} = 0\right) \end{array} + \begin{array}{l} \mathbb {P}\left(X_{2} = 0 \mid X_1 = -1\right) \cdot \\ \cdot \mathbb {P}\left(X_{1} = -1 \mid X_{0} = 0\right) \end{array} = \\ & = \frac{1}{2} \cdot \frac{1}{2} + 1 \cdot \frac{1}{2} = \frac{3}{4} \end{align} \]

В итоге имеем

\[ \mathbb {P}\left(Y_{2} = 0 \mid Y_1 = 1, Y_0 = 4\right) \neq \mathbb {P}\left(Y_{2} = 0 \mid Y_1 = 1, Y_0 = 0\right), \]

нарушение марковского свойства.

ProblemЗадача 2

Пусть \(\left\{ \xi_{n}, n \in \mathbb {N}\right\}\) – независимые одинаково распределенные случайные величины со значениями в \(\mathbb {Z}\), с функцией вероятности \(p(x) := \mathbb {P}\left(\xi_i = x\right)\), положительной при всех \(x \in \mathbb {Z}\). Укажите, являются ли следующие случайные последовательности цепями Маркова:

1. \(\xi =\left(\xi_{n}, \; n \in \mathbb {N}\right)\);

2. \(S_{n}=\xi_{1}+\ldots +\xi_{n}, \; n \in \mathbb {Z}_{+}\), где \(S_{0}=0\);

3. \(S^{+}_{n} := S_{n} \cdot \; \mathbb {1}_{S_{n} \geq 0}, \; n \in \mathbb {Z}_{+}\);

4. \(M_{n} := \max \left\{ S_{0}, \ldots , S_{n}\right\} , \; n \in \mathbb {Z}_{+}\). Для тех, которые окажутся цепями Маркова, укажите переходные вероятности за один шаг.

3 Конечное число состояний

В данном разделе фазовое пространство считается конечным.

3.1 Сообщающиеся состояния

В теории марковских цепей состояния \(i,j \in \mathcal{X}\) называют сообщающимися, если в графе переходов они сильно связны: можно с положительной вероятностью (за какое-то конечное количество шагов) дойти из \(i\) в \(j\) и из \(j\) в \(i\). Компоненты сильной связности называют сообщающимися классами.

Состояние называют невозвратным или транзитным, если можно выйти из этого состояния и с некоторой положительной вероятностью никогда в него не вернуться. В противном случае, т.е. когда при выходе из состояния с вероятностью \(1\) в него когда-нибудь возвращаешься, состояние называют возвратным.

Лемма 3  

• В одном и том же классе все состояния могут быть либо одновременно возвратными, либо невозвратными. Иначе говоря, каждый сообщающийся класс либо целиком возвратный, либо целиком невозвратный.

• Определить тип класса (возвратный/невозвратный) просто: если класс замкнут, т.е. из него нет переходов наружу, то он возвратный. В противном случае он невозвратный. ¹

ExampleПример 6

Переходные вероятности (за 1 шаг) некоторой марковской цепи заданы в виде графа.

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

1. Определите сообщающиеся классы состояний.

2. Для каждого класса определите, возвратный он или нет.

3. Занумеруйте классы так, чтобы сначала шли невозвратные, а затем возвратные. Причем невозвратные занумеруйте так, чтобы переходы были возможны только из меньшего в больший по номеру.

4. Занумеруйте вершины. Запишите матрицу переходов этой цепи.

SolutionРешение

Тот же граф с занумерованными состояниями и подсвеченными сообщающимися классами: I, II — невозвратные (транзитные), III, IV, V — возвратные.

Невозвратные классы (I, II) подкрашены жёлто-оранжевыми оттенками, возвратные (III, IV, V) — синими оттенками; цвет рамки каждой вершины повторяет это деление.

Полная матрица переходов P в канонической нумерации состояний примера выше. Цветом выделены только диагональные блоки, отвечающие сообщающимся классам: жёлтый и оранжевый — транзитные классы {1,2,3} и {4,5}, синий, бирюзовый и фиолетовый — возвратные (замкнутые) классы {6,7,8}, {9} и {10,11,12,13}. Наведите курсор на ячейку, чтобы увидеть вероятность перехода.

Почему подкрашены блоки \(2 \times 2\) в правой нижней подматрице (бирюзовой, отвечающей классу V), станет понятно чуть позже.

Нумерация состояний, полученная в примере выше, называется канонической. Это такая нумерация, при которой матрица переходов имеет блочный вид \[ \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} \]

Mn-extraДополнительно

Связь со старыми обозначениями из случайного блуждания: \(\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\)) называется отложенным процессом восстановления.

Какие предельные свойства у отложенного процесса восстановления? Оказывается, элементарная теорема восстановления во многих случаях остается верной.

Теорема 3 (Элементарная теорема восстановления для отложенного процесса) Пусть \(\xi_1, \xi_2, \xi_3, \ldots\) – независимые случайные величины со значениями в \([0, +\infty ]\), причем \(\xi_2, \xi_3, \ldots\) одинаково распределены и \(\mathbb {E}\left[\xi_2\right] > 0\). Тогда если \(\mathbb {P}\left(\xi_1 < \infty \right) = 1\), то построенный по ним отложенный процесс восстановления \(N_t = \max \left\{ n \; : \; \xi_1 + \ldots + \xi_n \leq t\right\}\) удовлетворяет элементарной теореме восстановления для обычного процесса восстановления, построенного по \(\xi_2, \xi_3, \ldots\): \[ \frac{\mathbb {E}\left[N_t\right]}{t} \xrightarrow [t \to +\infty ]{} \frac{1}{\mathbb {E}\left[\xi _2\right]} \]

Доказательство см. в (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} \]

Т.е. из любого состояния любое другое достигается за п.н. конечное время и все состояния возвратны. Такая цепь не является транзитной².

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

\[ \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\). Пришли к теореме.

Теорема 4 Пусть \((X_n)\) – неприводимая МЦДВ с конечным числом состояний с матрицей переходов \(\mathbf{P}\). Тогда матрицы \(\mathbf{P}^0, \mathbf{P}^{1}, \ldots\) имеют предел по Чезаро: \[ \frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^{k}\qquad \xrightarrow [n \to \infty ]{} \qquad \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} \] Т.е. предел не зависит от номера строки \(i\), а зависит только лишь от номера столбца \(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\) совпадают, значит найдется для данного собственного значения и левый собственный вектор. Причем его всегда можно нормировать, т.е. превратить его в распределение. Пришли к теореме.

Теорема 5 У МЦДВ с конечным числом состояний всегда есть стационарное распределение.

Как стационарное распределение связано с пределом по Чезаро? Заметим, что

\[ \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\). Сформулируем теорему.

Теорема 6 Пусть \((X_n)\) – неприводимая МЦДВ с конечным числом состояний с матрицей переходов \(\mathbf{P}\). Тогда ее стационарное распределение единственно и равно любой строке из предела по Чезаро матриц \(\mathbf{P}^0, \mathbf{P}^{1}, \ldots\).

3.5 Период состояния, эргодическая цепь

Мы детально разобрались с пределом по Чезаро матриц перехода \(\mathbf{P}^0, \mathbf{P}^1, \ldots\) для неприводимой МЦДВ с конечным числом состояний. Но что с обычным пределом? Он, оказывается, не всегда существует.

ExampleПример 7

Рассмотрим класс \(V\) из примера выше как отдельную цепь:

Граф переходов вспомогательной 4-состоятельной цепи с периодом 4: класс {1,3} и класс {2,4} чередуются на каждом шаге, поэтому у последовательности P⁰, P¹, … нет обычного (поэлементного) предела, хотя предел по Чезаро существует.

Покажите, что у последовательности \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) нет предела.

SolutionРешение

Имеем \[ \mathbf{P} = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0.6 & 0.3 \\ 0 & 1 & 0 & 0 \\ 0.3 & 0.7 & 0 & 0 \end{pmatrix} \] Эта матрица блочная: \[ \mathbf{P} = \begin{pmatrix} \mathbf{0} & \mathbf{A} \\ \mathbf{B} & \mathbf{0} \end{pmatrix} \] Т.е. \[ \mathbf{P}^2 = \begin{pmatrix} \mathbf{A}\mathbf{B} & \mathbf{0} \\ \mathbf{0} & \mathbf{B}\mathbf{A} \end{pmatrix}, \quad \mathbf{P}^{3} = \begin{pmatrix} \mathbf{0} & \mathbf{A}\mathbf{B}\mathbf{A} \\ \mathbf{B}\mathbf{A}\mathbf{B} & \mathbf{0} \end{pmatrix}, \quad \mathbf{P}^4 = \begin{pmatrix} (\mathbf{A}\mathbf{B})^2 & \mathbf{0} \\ \mathbf{0} & (\mathbf{B}\mathbf{A})^2 \end{pmatrix}, \quad \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\).

Лемма 4 Период – это, как и возвратность, характеристика всего класса сообщающихся состояний. Т.е. если \(i,j\) – сообщающиеся состояния, то \(d(i) = d(j)\).

В частности, у неприводимой цепи период всех состояний совпадает. Т.е. можно говорить о периоде всей (неприводимой) цепи. У цепей выше период равен \(2\).

У неприводимой цепи периодичность возникает, как мы видели, если есть какой-то нетривиальный период (т.е. он больше \(1\)). Оказывается, если неприводимая цепь является апериодической, то \(\mathbf{P}^{n}\) сходятся. Неприводимая, апериодическая цепь называется эргодической цепью.

Сформулируем теорему.

Теорема 7 (Эргодическая теорема) Пусть \((X_n)\) – эргодическая МЦДВ с конечным числом состояний. Тогда

1. ее стационарное распределение \(\Pi\) существует, единственно и равно обратным временам возврата в состояния:

   \[ \Pi = \left(\frac{1}{\mathbb {E}_{1}\left[T_1\right]}, \quad \frac{1}{\mathbb {E}_{2}\left[T_2\right]}, \quad \cdots , \quad \frac{1}{\mathbb {E}_{|\mathcal{X}|}\left[T_{\left|\mathcal{X}\right|}\right]}\right) \]

2. Матрицы \(\mathbf{P}^{n}\) сходятся в обычном смысле и по Чезаро к матрице, состоящей по строкам из \(\Pi\):

   \[ \lim _{n \to \infty }\mathbf{P}^n \quad = \quad \lim _{n \to \infty }\frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^k \quad = \quad \begin{pmatrix} \Pi \\ \Pi \\ \vdots \\ \Pi \end{pmatrix} \]

Распределение \(\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 \]

Следствие 1 (Иногда также называют эргодической теоремой) Предельное распределение эргодической цепи всегда существует (т.е. \(X_n\) всегда сходится по распределению), и оно равно эргодическому распределению. В частности, предельное распределение не зависит от начального распределения цепи \(\Pi^{(0)}\), а только лишь от матрицы переходов \(\mathbf{P}\), и равно ее нормированному левому собственному вектору, соответствующему собственному значению \(1\).

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

ExampleПример 8

Рассмотрим МЦДВ \((X_n)\) из задачи Задача 1.

1. Найдите все стационарные распределения цепи.

2. Является ли эта цепь неприводимой? А эргодической? Если да – найдите эргодическое распределение.

3. Найдите предел последовательности \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) в обычном смысле и по Чезаро (если они существуют, конечно).

4. Найдите предел \(X_n\) по распределению, в зависимости от начального распределения \(\Pi^{0}\).

5. Найдите среднее время возврата \(\mathbb {E}_{i}\left[T_i\right]\) для каждого из состояний \(i \in \mathcal{X}\).

SolutionРешение

Enum-item(i)

Найдем все левые собственные векторы для матрицы \(\mathbf{P}\) (для собственного значения \(1\)):

\[ \Pi \cdot \begin{pmatrix} 3/7 & 3/7 & 1/7 \\ 1/11 & 2/11 & 8/11\\ 1/11 & 4/11 & 6/11 \end{pmatrix} = \Pi \]

Решаем СЛОУ

\[ \Pi \cdot \begin{pmatrix} -4/7 & 3/7 & 1/7 \\ 1/11 & -9/11 & 8/11\\ 1/11 & 4/11 & -5/11 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 \end{pmatrix} \]

… Решение:

\[ \Pi = \alpha \begin{pmatrix} 91 & 209 & 363 \end{pmatrix}, \quad \alpha \in \mathbb {R} \]

Нормируем, чтобы получить распределение:

\[ \Pi = \begin{pmatrix} \frac{91}{663} & \frac{209}{663} & \frac{363}{663} \end{pmatrix} \approx \begin{pmatrix} 13.73\% & 31.52\% & 54.75\% \end{pmatrix} \]

Enum-item(ii)

Все состояния сообщаются, значит она неприводима. Причем, например, из \(1\)-го состояния в себя можно добраться за \(1\) шаг. Значит, НОД шагов, за которые можно вернуться в \(1\), равен \(1\). Значит, \(1\) – это апериодическое состояние. Все состояния цепи образуют единый сообщающийся класс, значит цепь апериодическая. Получается, она эргодическая (поскольку неприводимая и апериодическая). Эргодическое распределение совпадает со стационарным, оно найдено в предыдущем пункте.

Enum-item(iii)

Согласно эргодической теореме,

\[ \lim _{n \to \infty } \mathbf{P}^{n} = \lim _{n \to \infty } \frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^k = \begin{pmatrix} \Pi \\ \Pi \\ \Pi \end{pmatrix} = \begin{pmatrix} \frac{91}{663} & \frac{209}{663} & \frac{363}{663} \\ \frac{91}{663} & \frac{209}{663} & \frac{363}{663}\\ \frac{91}{663} & \frac{209}{663} & \frac{363}{663} \end{pmatrix} \approx \begin{pmatrix} 13.73\% & 31.52\% & 54.75\% \\ 13.73\% & 31.52\% & 54.75\% \\ 13.73\% & 31.52\% & 54.75\% \end{pmatrix} \]

Enum-item(iv)

Согласно эргодической теореме,

\[ X_n \xrightarrow [n \to +\infty ]{d} \Pi \]

Предельное распределение не зависит от начального распределения.

Enum-item(v)

Согласно эргодической теореме,

\[ \begin{cases} \mathbb {E}_{1}\left[T_1\right] = \frac{663}{91} \approx 7.3 \\ \mathbb {E}_{2}\left[T_2\right] = \frac{663}{209} \approx 3.2 \\ \mathbb {E}_{3}\left[T_3\right] = \frac{663}{363} \approx 1.8 \\ \end{cases} \]

ProblemЗадача 3

Рассмотрим МЦДВ \((Y_n)\) из задачи Задача 1.

1. Найдите все стационарные распределения цепи.

2. Является ли эта цепь неприводимой? А эргодической? Если да – найдите эргодическое распределение.

3. Найдите предел последовательности \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) в обычном смысле и по Чезаро (если они существуют, конечно).

4. Найдите предел \(X_n\) по распределению, в зависимости от начального распределения \(\Pi^{0}\).

5. Найдите среднее время возврата \(\mathbb {E}_{i}\left[T_i\right]\) для каждого из состояний \(i \in \mathcal{X}\).

HintПодсказка

Матрица переходов \(Y_n\): \[ \mathbf{P} = \begin{pmatrix} 3/7 & 4/7\\ 1/11 & 10/11 \end{pmatrix} \]

ProblemЗадача 4

Рассмотрим МЦДВ \((X_n)\) из примера Пример 1. Напомним ее матрицу переходов: \[ \mathbf{P} = \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \\ 0.3 & 0.3 & 0.3 & 0.1 \\ 0 & 0 & 1 & 0 \\ 0.4 & 0.4 & 0 & 0.2 \end{pmatrix} \]

1. Найдите все стационарные распределения цепи.

2. Является ли эта цепь неприводимой? А эргодической? Если да – найдите эргодическое распределение.

3. Найдите предел последовательности \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) в обычном смысле и по Чезаро (если они существуют, конечно).

4. Найдите предел \(X_n\) по распределению, в зависимости от начального распределения \(\Pi^{(0)}\).

5. Найдите среднее время возврата \(\mathbb {E}_{i}\left[T_i\right]\) для каждого из состояний \(i \in \mathcal{X}\).

HintПодсказка

Можете перенумеровать состояния для наглядности.

Для неприводимой цепи (с конечным количеством состояний) есть полезный критерий эргодичности (т.е. апериодичности).

Лемма 5 (Критерий апериодичности Фробениуса) Пусть \((X_n)_{n \geq 0}\) – это неприводимая МЦДВ с конечным количеством состояний. Она является эргодической тогда и только тогда, когда найдется такое \(m \in \mathbb {Z}\), что за это количество шагов можно с положительной вероятностью дойти из любого состояния в любое другое: \[ \mathbb {P}\left(X_{m} = j \mid X_{0} = i\right) > 0, \qquad \forall i,j \in \mathcal{X} \] На языке матриц: \[ \mathbf{P}^{m} > \mathbf{0} \quad \text{(поэлементное сравнение)} \]

Доказательство см. в (Meyer 2001 г., строка 678).

ProblemЗадача 5

Компания, занимающаяся автострахованием, относит каждого из своих клиентов к одной из трех категорий. Чем больше номер категории \(i \in \{ 1,2,3\}\), тем выше цена страховки \(c_{i}\). Пусть \(X_{n} \in \{ 1,2,3\}\) – номер категории, к которой относится клиент в момент времени \(n, n=0,1,2, \ldots\), и \(Y_{n}\) – количество ДТП, в которые клиент попал в году \(n\). Величина \(X_{n}, n \geq 1\), определяется на основании \(X_{n-1}\) и \(Y_{n-1}\) с помощью таблицы:

	0 аварий	1 авария	\(\geq 2\) аварий
1 категория	1	2	3
2 категория	1	3	3
3 категория	2	3	3

Предположим, что вероятности попадания в 0,1 и \(\geq 2\) ДТП в год равны \(p_{0}, p_{1}, p_{2}>0\) вне зависимости от прошлого и номера года \(n\). Для простоты положим \(X_{0}=1\).

1. Пусть \(p_0 = \frac{1}{2}\), \(p_{1} = \frac{1}{3}\), \(p_2 = \frac{1}{6}\). Найдите математическое ожидание цены страховки в момент \(n\).

2. Существует ли предел \(X_{n}\) при \(n \rightarrow \infty\) в смысле сходимости по распределению?

3. Существует ли предел матожидания цены страховки? Если да – найдите его.

ProblemЗадача 6

Пусть \(\left(\xi_{n}, n \in \mathbb {Z}_{+}\right)\) – независимые одинаково распределенные случайные величины со значениями \(\left\{ 0,1,2,3\right\}\) и следующим распределением: \[ \begin{align} \mathbb {P}\left(\xi _{n}=0\right) & = \frac{1}{7}, & \quad \mathbb {P}\left(\xi _{n}=1\right) & = \frac{2}{7}, \\ \mathbb {P}\left(\xi _{n}=2\right) & = \frac{3}{7}, & \quad \mathbb {P}\left(\xi _{n}=3\right) & = \frac{1}{7} \end{align} \] Рассматриваются процессы \[ \begin{align} X_{0} = 0, X_{n} & = \xi _{1} + \ldots + \xi _{n} \; \pmod{4}, n \geq 1 \\ Y_{0} = 1, Y_{n} & = \xi _{1} \cdot \ldots \cdot \xi _{n} \; \pmod{4}, n \geq 1 \end{align} \] \(n \in \mathbb {N}\). Докажите, что \(\left(X_{n}, \; n \in \mathbb {N}\right)\) и \(\left(Y_{n}, \; n \in \mathbb {N} \right)\) являются однородными марковскими цепями, и найдите их предельные распределения, в зависимости от начального.

3.6 Предельные и стационарные распределения: общий случай

Рассмотрим теперь цепи, состоящие из нескольких сообщающихся классов.

ProblemЗадача 7

Рассмотрим большую МЦДВ \((X_n)\) из примера Пример 6.

1. Найдите все стационарные распределения цепи.

2. Является ли эта цепь неприводимой? А эргодической? Если да – найдите эргодическое распределение.

3. Найдите предел последовательности \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) в обычном смысле и по Чезаро (если они существуют, конечно).

4. Найдите предел \(X_n\) по распределению, в зависимости от начального распределения \(\Pi^{0}\).

5. Найдите среднее время возврата \(\mathbb {E}_{i}\left[T_i\right]\) для каждого из состояний \(i \in \mathcal{X}\).

Для поиска пределов \(\mathbf{P}^{0}, \mathbf{P}^{1}, \ldots\) можете пользоваться результатами, полученными выше.

ProblemЗадача 8

Докажите, что для любой МЦДВ (даже бесконечной, забегая вперед) последовательность \(\mathbf{P}^{0}, \mathbf{P}^1, \ldots\) сходится по Чезаро. Какой вероятностный смысл у предела \[ \lim _{n \to \infty } \left(\frac{1}{n} \sum _{k=0}^{n-1} \mathbf{P}^k\right)_{ij} \] для произвольных состояний \(i,j \in \mathcal{X}\)? А именно, нужно записать формулу этого предела через вероятности и матожидания. В частности, какой вероятностный смысл у чисел в правом верхнем углу у предела по Чезаро для большой марковской цепи (с 13 состояниями) из примера выше?

Как вы думаете, при каком эквивалентном условии на цепь у последовательности \(\mathbf{P}^{0}, \mathbf{P}^1, \ldots\) есть обычный предел? При каком условии цепь сходится по вероятности?

HintПодсказка

Примените элементарную теорему восстановления для отложенных процессов восстановления (теор. Теорема 3).

4 Счетное число состояний

Определения из МЦДВ с конечным числом состояний переносятся на МЦДВ со счетным числом состояний: сообщающиеся состояния, классы состояний, неприводимые цепи, возвратные/невозвратные состояния, период состояния, и т.д. При этом так же, как и в конечном случае, возвратность и период – это свойства, сохраняющиеся в рамках одного сообщающегося класса.

ExampleПример 9

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

SolutionРешение

Enum-item(1)

Обычное простейшее блуждание с вероятностью шага \(+1\) равной \(p \in [0,1]\):

Обычное простейшее блуждание с вероятностью шага +1, равной p ∈ [0,1] (и шага −1 с вероятностью 1−p).

Если \(p = 1\), то никто ни с кем не сообщается, каждое состояние образует отдельный класс, при этом все состояния невозвратны. То же самое, когда \(p = 0\).

Если \(p \in (0,1)\), то все состояния сообщаются, цепь неприводима (состоит из одного класса), период равен \(2\). При этом если \(p = \frac{1}{2}\), то (доказывали ранее в случайных блужданиях) \(\mathbb {P}_{0}\left(T_0 < \infty \right) = 1\), т.е. цепь возвратная. Заметим, правда, что \(\mathbb {E}_{0}\left[T_0\right]\) все равно \(+\infty\), как у невозвратного состояния.

Если \(p \in (0,1)\), \(p \neq \frac{1}{2}\), то цепь невозвратная.

Enum-item(2)

Поглощающий барьер в \(1\):

Простейшее случайное блуждание с поглощающим барьером в состоянии 1: из состояния 0 переход в 1 происходит с вероятностью p, после чего цепь остаётся в 1 навсегда.

Случай \(p = 1\) или \(0\) не очень интересен.

Пусть \(p \in (0,1)\). Тогда цепь распадается на \(2\) класса: \(\left\{ 1\right\}\) и \(\left\{ 0, -1,-2,\ldots \right\}\). Первый класс, разумеется, возвратный, он состоит из одного (поглощающего) состояния. Второй класс невозвратный, поскольку состояние \(0\) невозвратно: с вероятностью \(p\) можно уйти в \(1\) и оттуда не вернуться.

Период класса \(\left\{ 1\right\}\): \(1\). Период класса \(\left\{ 0,-1,\ldots \right\}\): \(2\).

Enum-item(3)

Удерживающий барьер в \(1\):

Простейшее случайное блуждание с удерживающим («липким») барьером в состоянии 1: из состояния 1 цепь остаётся на месте с вероятностью p и спускается вниз с вероятностью 1−p.

Эта цепь очень похожа на предыдущую. Опять-таки, \(p=0,1\) не будем рассматривать, можете самостоятельно это сделать. Если \(p \in (0,1)\), то цепь состоит из одного класса, т.е. она неприводима. Определим возвратность.

\[ \begin{align} \mathbb {P}_{1}\left(T_1 < \infty \right) & = \underbrace{\mathbb {P}_{1}\left(T_1 < \infty \mid S_{1} = 1\right)}_{=1} \cdot \mathbb {P}\left(S_{1} = 1\right) \\ & \quad + \underbrace{\mathbb {P}_{1}\left(T_1 < \infty \mid S_{1} = 0\right)}_{=\mathbb {P}_{0}\left(T_1 < \infty \right), \text{ марк. св-во}} \cdot \; \mathbb {P}\left(S_{1} = 0\right) = \\ & = p + \mathbb {P}_{0}\left(T_{1} < \infty \right) \cdot (1-p)\\ \mathbb {E}_{1}\left[T_1\right] & = \underbrace{\mathbb {E}_{1}\left[T_1 \mid S_{1} = 1\right]}_{=1} \cdot \mathbb {P}\left(S_{1} = 1\right) \\ & \quad + \underbrace{\mathbb {E}_{1}\left[T_1 \mid S_{1} = 0\right]}_{=1 + \mathbb {E}_{0}\left[T_1\right], \text{ марк. св-во}} \cdot \; \mathbb {P}\left(S_{1} = 0\right) = \\ & = p + \left(1 + \mathbb {E}_{0}\left[T_{1}\right]\right) \cdot (1-p) = 1 + (1-p)\mathbb {E}_{0}\left[T_1\right] \end{align} \]

Распределение случайной величины \(T_1\) (по мере \(\mathbb {P}_0\)) такое же, как и у обычного случайного блуждания. Мы его вычисляли:

• если \(p > \frac{1}{2}\), то \(\mathbb {P}_{0}\left(T_1 < \infty \right) = 1\) и \(\mathbb {E}_{0}\left[T_1\right] < \infty\). Значит \(\mathbb {P}_{1}\left(T_1 < \infty \right) = 1\) и \(\mathbb {E}_{1}\left[T_1\right] < \infty\), цепь возвратна (даже положительно-возвратна, см. определение ниже);

• если \(p = \frac{1}{2}\), то \(\mathbb {P}_{0}\left(T_1 < \infty \right) = 1\), но \(\mathbb {E}_{0}\left[T_1\right] = \infty\). Значит, \(\mathbb {P}_{1}\left(T_1 < \infty \right) = 1\), но \(\mathbb {E}_{1}\left[T_1\right] = \infty\). Цепь возвратна, хотя матожидание времени возврата бесконечно;

• если \(p < \frac{1}{2}\), то \(\mathbb {P}_{0}\left(T_1 < \infty \right) < 1\) и \(\mathbb {E}_{0}\left[T_1\right] = \infty\). Значит, \(\mathbb {P}_{1}\left(T_1 < \infty \right) < 1\) и \(\mathbb {E}_{1}\left[T_1\right] = \infty\). Цепь невозвратна.

В данном примере можно видеть отличия МЦДВ с сч. числом состояний от конечного случая:

• В цепи может не быть ни одного замкнутого класса (простейшее блуждание с \(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\).

Лемма 6 Эти характеристики (положительная/нулевая возвратность) также сохраняются в рамках одного сообщающегося класса.

Приведем полезную таблицу, верную как в конечном, так и в бесконечном случае. Доказательства см. в (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 \]

Теорема 8  

• Неприводимая МЦДВ имеет стационарное распределение \(\Pi\) \(\iff\) она положительно-возвратна. В этом случае стационарное распределение единственно и равно обратным временам возврата:

  \[ \Pi _{i} = \frac{1}{\mathbb {E}_{i}\left[T_i\right]}, \qquad \forall i \in \mathcal{X} \]

• Если неприводимая цепь возвратна (нуль-возвратна или положительно-возвратна), то найдется мера \(\Psi\) на \(\mathcal{X}\), единственная с точностью до домножения на константу, и состоящая полностью из положительных вероятностей (\(\Psi_i > 0\) для любого \(i \in \mathcal{X}\)). При этом цепь

  • положительно-возвратна, если \(\sum_{i \in \mathcal{X}}\Psi_{i} < +\infty\);

  • нуль-возвратна, если \(\sum_{i \in \mathcal{X}}\Psi_{i} = +\infty\);

• Для неприводимой и апериодической МЦДВ выполнено

  \[ \left(\mathbf{P}^{n}\right)_{ij} \xrightarrow [n \to \infty ]{} \frac{1}{\mathbb {E}_{j}\left[T_j\right]}, \qquad \forall i,j \in \mathcal{X} \]

  Т.е. какое бы ни было начальное распределение \(\Pi^{(0)}\), будет выполнено

  \[ \left(\Pi ^{(0)} \cdot \mathbf{P}^{n}\right)_j = \mathbb {P}_{\Pi ^{(0)}}\left(X_{n} = j\right) \xrightarrow [n \to \infty ]{} \frac{1}{\mathbb {E}_{j}\left[T_j\right]} \]

Доказательство см. в (Grimmett и Stirzaker 2020 г., п. 6.4).

ProblemЗадача 9

Пусть \(\frac{1}{2} < p \leq 1\), \(q = 1 - p\). Рассмотрим цепь

Бесконечная цепь, «сгущающаяся» к нулю: из состояния 0 — переход в ±1 с вероятностью q и самопереход с вероятностью 1−2q; из любого другого состояния — переход к нулю с вероятностью p и от нуля с вероятностью q (здесь 1/2 < p ⩽ 1, q = 1−p).

1. Найдите \(\mathbb {E}_{i}\left[T_i\right]\) для каждого из состояний \(i \in \mathcal{X}\) и все стационарные распределения цепи.

2. Является ли эта цепь неприводимой? Эргодической? Положительно-возвратной?

3. Найдите (поэлементный) предел последовательности \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) в обычном смысле и по Чезаро (если они существуют, конечно).

4. Найдите предел \(X_n\) по распределению, в зависимости от начального распределения \(\Pi^{0}\).

HintПодсказка

Из теории случайного блуждания нам известно, что в данном случае \(\mathbb {E}_{-1}\left[T_0\right] = \frac{1}{p-q}\).

ProblemЗадача 10

В этой задаче все цепи предполагаются неприводимыми. Может ли быть

1. у невозвратной (транзитной) цепи стационарное распределение?

2. у невозвратной (транзитной) цепи стационарная мера?

3. у нуль-возвратной цепи стационарное распределение?

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\) может быть бесконечным с положительной вероятностью.

Теорема 9 Для любой МЦДВ предел по Чезаро существует и равен \[ \lim _{n \to \infty } \left(\frac{1}{n} \sum _{k=0}^{n-1} \mathbf{P}^k\right)_{ij} = \frac{\mathbb {P}_{i}\left(\tau _j < \infty \right)}{\mathbb {E}_{j}\left[T_j\right]}, \qquad \forall i, j \in \mathcal{X} \] (с соглашением \(\frac{1}{+\infty } = 0\)). В частности, столбцы, отвечающие невозвратным и нуль-возвратным состояниям \(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 (эквивалентность форм марковского свойства)

Mn-proofДоказательство

(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}\))

Mn-proofДоказательство

(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 (существование МЦДВ)

Mn-proofДоказательство

Строим по теореме Колмогорова о согласованных распределениях (теорема Колмогорова о согласованных распределениях) распределение \(\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 (элементарная теорема восстановления для отложенного процесса)

Mn-proofДоказательство

Пусть \(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 (предел по Чезаро для неприводимой конечной цепи)

Mn-proofДоказательство

Как уже отмечено в основном тексте: для неприводимой конечной цепи \(\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 (существование стационарного распределения)

Mn-proofДоказательство

Рассмотрим симплекс \(\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 (единственность = строка предела по Чезаро)

Mn-proofДоказательство

Пусть \(\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 (возвратность — характеристика класса; замкнутый конечный класс возвратен)

Mn-proofДоказательство

Критерий возвратности: \(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\).

Следствие 2 (к лемме Лемма 3, доказывает утверждение из примера про неприводимую конечную цепь, см. текст перед теоремой Теорема 4) Для неприводимой конечной МЦДВ \(\mathbb {P}_{i}\left(\tau_j<\infty \right)=1\) для любых \(i,j\in \mathcal{X}\).

Mn-proofДоказательство

Весь \(\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 (период — характеристика класса)

Mn-proofДоказательство

Пусть \(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

Mn-proofДоказательство

Пункт (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 (критерий апериодичности Фробениуса)

Mn-proofДоказательство

Пусть \(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 (положительная/нулевая возвратность — характеристика класса)

Mn-proofДоказательство

Пусть \(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 (общая теорема для счётного числа состояний)

Mn-proofДоказательство

Часть 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.

Сноски

1. Это верно лишь когда в цепи конечное число состояний. Если в цепи бесконечное число состояний, то в ней может найтись замкнутый класс состояний, явл. невозвратным. См. подробности ниже.

2. Опять же, это верно, только если количество состояний конечно. Как бы парадоксально это ни казалось, цепь с бесконечным количеством состояний может состоять из одного класса, являющегося транзитным. Пример – простейшее случайное блуждание с \(p\neq \frac{1}{2}\). Подробнее см. ниже.