Этот конспект ещё находится в процессе редактуры: в тексте могут встречаться опечатки, неточности и локально не проработанные места. Если что-то нашли — сообщите, пожалуйста, автору (контакты на странице курса).
1 Общая информация
1.1 Марковское свойство
Пусть \(\mathcal{X}\) – не более чем счетное множество.
Определение 1 Случайный процесс \(\left(X_{t}, t \geqslant 0\right)\) со значениями в не более чем счетном пространстве \(\mathcal{X}\) называется марковской цепью с непрерывным временем (сокр. МЦНВ), если он удовлетворяет марковскому свойству: \[
\mathbb {P}\left(X_{t_{n+1}} = s_{n+1} \quad \left| \quad \begin{array}{rl} X_{t_n} & = s_{n} \\ X_{t_{n-1}} & = s_{n-1} \\ \cdots & \cdots \\ X_{t_0} & = s_{0} \\ \end{array}\right.\right) \; = \; \mathbb {P}\left(X_{t_{n+1}} = s_{n+1} \mid X_{t_n} = s_{n}\right)
\] для любых \(n \in \mathbb {N}\), \(0 \leq t_0 < t_1 < \ldots < t_{n} < t_{n+1}\), \(s_0, s_1, \ldots , s_{n+1} \in \mathcal{X}\).
Терминология повторяет дискретный случай.
Множество \(\mathcal{X}\) называется фазовым пространством или пространством состояний марковской цепи;
\(\Pi^{(t)} = \left(\mathbb {P}\left(X_{t}=j\right), j \in \mathcal{X}\right)\) – распределение цепи в момент времени \(t \geqslant 0\).
Как и в дискретном случае, конечномерные распределения однозначно определяются переходными вероятностями и начальным распределением. Свойства переходных вероятностей остаются теми же.
Лемма 1 Переходные вероятности \(\mathbf{P}_{s \to t}\), \(0 \leq s \leq t\) марковской цепи удовлетворяют следующим свойствам.
\(\mathbf{P}_{s \to t}\) – это стохастическая матрица (т.е. состоящая из неотрицательных элементов, причем сумма по любой строке равна \(1\)) для любых \(s,t\);
\(\mathbf{P}_{t \to t} = \mathbf{E}\) для любого времени \(0 \leq t\);
Выполнены уравнения Колмогорова-Чепмена: \(\forall s \leqslant u \leqslant t\)
Как и в дискретном случае, перечисленные свойства не только необходимы, но и достаточны для существования марковской цепи.
Теорема 1 Пусть \(\mathcal{X} \subset \mathbb {R}\) – не более чем счетное множество, \(\Pi^{(0)}\) – распределение вероятностей на \(\mathcal{X}\), \(\mathbf{P}_{s \to t},\; 0 \leqslant s \leqslant\)\(t\) – матрицы, обладающие свойствами из леммы Лемма 1. Тогда существует такая МЦНВ \(\left(X_{t}, t \geqslant 0\right)\) с фазовым пространством \(\mathcal{X}\), что \(\Pi^{(0)}\) является её начальным распределением, а \(\mathbf{P}_{s\to t}\) являются её переходными вероятностями.
МЦНВ называют однородной, если выполнено
\[
\mathbf{P}_{s \to t} = \mathbf{P}_{s + u \to t + u}
\]
для любых \(0 \leq s \leq t\), \(0 \leq u\).
В дальнейшем, если не оговорено иного, мы будем рассматривать именно однородные МЦНВ.
т.е. все переходные вероятности определяются переходными вероятностями из нуля. Как и в дискретном случае, введем обозначение
\[
\mathbf{P}_{t} := \mathbf{P}_{0 \to t}
\]
У однородной МЦДВ ее переходные вероятности полностью определялись одной стохастической матрицей \(\mathbf{P}\) переходов за один шаг. В непрерывном случае распределение однородной марковской цепи, в отличие от дискретного времени, определяется не одной матрицей, а целым континуумом стохастических матриц \(\mathbf{P}_t, t \geq 0\). При этом выполнено
Набор стохастических матриц, удовлетворяющих этим свойствам, называется стохастической полугруппой.
Для любой стохастической полугруппы (стохастических) матриц можно построить однородную МЦНВ.
Мы уже наложили на МЦНВ условие однородности. В дискретном случае мы на этом остановились: условие однородности оказалось вполне достаточным, чтобы получить достаточно богатую теорию, охарактеризовать предельное поведение и т.д. В непрерывном случае одной лишь однородности недостаточно, т.к. вылезают некоторые патологические примеры. Рассмотрим их.
ExampleПример 1
Пусть \((X_t, t \geq 0)\) – такой случайный процесс, что для любого конечного набора временных точек \(0 \leq t_0 < \ldots < t_{n}\) случайные величины \(X_{t_0}, \ldots , X_{t_n}\) независимы (в совокупности) и \(X_{t} \sim \operatorname {Ber}(1/2)\).
Докажите, что такой процесс существует;
Является ли этот процесс МЦНВ? Если да, является ли он однородной МЦНВ? Если да – найдите стохастическую полугруппу переходных вероятностей.
Можно ли построить модификацию этого процесса с п.н. непрерывными справа траекториями?
SolutionРешение
Enum-item(1)
Применим теорему Колмогорова о согласованных конечномерных распределениях: зададим конечномерные распределения как произведения \(\operatorname {Ber}(1/2)\) по каждой временной точке – независимость делает проверку согласованности тривиальной.
Нет. Пусть \((Y_t)\) – модификация с п.н. непрерывными справа траекториями. Модификация имеет те же конечномерные распределения, поэтому \(\mathbb {P}\left(Y_{t + h} = Y_t\right) = \frac{1}{2}\) для любого \(h > 0\). Но по правой непрерывности \(Y_{t + h} \to Y_t\) п.н. при \(h \to 0+\), а процесс принимает лишь значения \(0\) и \(1\) – значит, \(\mathbb {P}\left(Y_{t+h} = Y_t\right) \to 1\). Противоречие.
Рассмотренная в примере цепь за сколь угодно малое время может совершить сколь угодно много прыжков (из состояния \(0\) в \(1\) и обратно). Чтобы это исключить, наложим на стохастическую полугруппу свойство непрерывности в нуле:
Стохастическую полугруппу \((\mathbf{P}_t, t \geq 0)\) (и соотв. МЦНВ), обладающую непрерывностью в нуле, называют стандартной. В дальнейшем, если не оговорено иного, мы будем рассматривать только стандартные однородные МЦНВ.
Mn-extraДополнительно
На самом деле из непрерывности в нуле вытекает непрерывность справа в любой точке \(s \geq 0\): \[
\mathbf{P}_{s + t} = \mathbf{P}_{s} \cdot \mathbf{P}_{t} \xrightarrow [t \to 0+]{} \mathbf{P}_{s} \cdot \mathbf{E}
\] В случае конечных матриц переход к пределу возможен, поскольку можно менять местами конечную сумму и предел: \[
\begin{align} \lim _{t \to 0+}\left(\mathbf{P}_{s + t}\right)_{i,j} & = \lim _{t \to 0+}\left(\mathbf{P}_{s} \cdot \mathbf{P}_{t}\right)_{i,j} = \\ & = \lim _{t \to 0+}\left(\sum _{l = 1}^{\left|\mathcal{X}\right|} \left(\mathbf{P}_{s}\right)_{i,l} \cdot \left(\mathbf{P}_{t}\right)_{l,j}\right) = \\ & = \sum _{l = 1}^{\left|\mathcal{X}\right|} \left(\left(\mathbf{P}_{s}\right)_{i,l} \cdot \lim _{t \to 0+} \left(\mathbf{P}_{t}\right)_{l,j} \right) = \\ & =\sum _{l = 1}^{\left|\mathcal{X}\right|} \left(\left(\mathbf{P}_{s}\right)_{i,l} \cdot \delta _{l}^j\right) = \left(\mathbf{P}_{s}\right)_{i,j} \end{align}
\] В случае с бесконечными матрицами непрерывность не настолько очевидна: предел и бесконечную сумму не всегда можно переставлять местами. Здесь спасает теорема Лебега о мажорируемой сходимости (в ее варианте для рядов): \(l\)-е слагаемое по модулю не превосходит \(\left(\mathbf{P}_{s}\right)_{i,l}\), а \(\sum_{l}\left(\mathbf{P}_{s}\right)_{i,l} = 1 < \infty\) – мажоранта суммируема. Для произвольных состояний \(i,j \in \mathcal{X}\) имеем \[
\begin{align} \lim _{t \to 0+}\left(\mathbf{P}_{s + t}\right)_{i,j} & = \lim _{t \to 0+}\left(\mathbf{P}_{s} \cdot \mathbf{P}_{t}\right)_{i,j} = \\ & = \lim _{t \to 0+}\left(\sum _{l \in \mathcal{X}} \left(\mathbf{P}_{s}\right)_{i,l} \cdot \left(\mathbf{P}_{t}\right)_{l,j}\right) = \\ & = \sum _{l \in \mathcal{X}} \left(\left(\mathbf{P}_{s}\right)_{i,l} \cdot \lim _{t \to 0+} \left(\mathbf{P}_{t}\right)_{l,j} \right) = \\ & =\sum _{l \in \mathcal{X}} \left(\left(\mathbf{P}_{s}\right)_{i,l} \cdot \delta _{l}^j\right) = \left(\mathbf{P}_{s}\right)_{i,j} \end{align}
\] Непрерывность слева (а с ней и полноценная, даже равномерная, непрерывность на \(\mathbb {R}_+\)) тоже верна – см. задачу ниже.
ProblemЗадача 1
Докажите, что переходные вероятности \(p_{i j}(t) := \left(\mathbf{P}_t\right)_{ij}\) стандартной стохастической полугруппы равномерно непрерывны на \(\mathbb {R}_{+}\) (по \(t\), при фиксированных \(i,j\)).
1.3 Генератор (\(Q\)-матрица) МЦНВ
Следующий результат, доказанный Колмогоровым, совершенно неочевиден: оказывается, если стохастическая полугруппа (поэлементно) непрерывна в нуле, то она дифференцируема в нуле.
Лемма 2 Пусть \((\mathbf{P}_t, t \geqslant 0)\) – стандартная стохастическая полугруппа. Тогда существует правая производная в нуле для каждого элемента: \[
\begin{align} \frac{d^+}{dt}\left(\mathbf{P}_{t}\right)_{ij}\bigg\rvert _{t=0} & = \\ & \quad \lim _{t \to 0+} \frac{\left(\mathbf{P}_t\right)_{ij} - \overbrace{\left(\mathbf{P}_0\right)_{ij}}^{=\delta _i^j}}{t} =: \mathbf{Q}_{ij} \end{align}
\] причем \(\forall i \neq j\) имеем \(0 \leq \mathbf{Q}_{ij} < +\infty\), и \(\mathbf{Q}_{ii} \in [-\infty , 0]\).
Ее называют инфинитезимальной матрицей, генератором или матрицей интенсивности переходов для МЦНВ \((X_t, t \geq 0)\) или ее стохастической полугруппы \((\mathbf{P}_{t}, t \geq 0)\) (в конце концов, \(\mathbf{Q}\) не зависит от начального распределения цепи, а только от переходных вероятностей, т.е. от стохастической полугруппы). Из леммы известно, что на диагонали у \(\mathbf{Q}\) стоят неположительные числа, возможно даже \(-\infty\). Вне диагонали стоят неотрицательные (конечные) числа. Название генератор дано матрице \(\mathbf{Q}\), поскольку при помощи нее можно в большинстве случаев однозначно восстановить стохастическую полугруппу. Забегая вперед, формула такая:
Рассмотрим, например, 3-й генератор. МЦНВ с этим генератором (вернее, одна из ее возможных модификаций с cadlag траекториями) ведет себя так:
Если цепь оказалась в состоянии \(i\), то она сидит в этом состоянии случайное время, распределенное как \(\operatorname {Exp}(-\mathbf{Q}_{ii})\). Например, если она в состоянии \(1\), она будет ждать время \(\operatorname {Exp}(14)\).
Когда время ожидания в состоянии \(i\) заканчивается, цепи нужно перескочить в новое состояние. Новое состояние \(j\) она выбирает случайно, независимо от предыдущего поведения, причем перескакивает в какое-то состояние с вероятностью, пропорциональной \(\mathbf{Q}_{ij}\). Например, если цепь была в состоянии \(i=1\), то она из него скакнет в состояние \(2\) с вероятностью \(\frac{7}{14}\), в состояние \(3\) с вероятностью \(\frac{5}{14}\), в состояние \(4\) с вероятностью \(\frac{2}{14}\).
Отдельный случай – состояние с нулевой диагональю: у 3-го генератора \(\mathbf{Q}_{22} = 0\), т.е. время ожидания в состоянии \(2\) распределено как \(\operatorname {Exp}(0)\), что естественно интерпретировать как \(+\infty\): попав в состояние \(2\), цепь остается в нем навсегда (поглощающее состояние).
ExampleПример 2
Пусть \(N_t\) – стационарный Пуассоновский процесс интенсивности \(\lambda\).
Покажите, что \(N_t\) – МЦНВ, найдите его стох. полугруппу;
Покажите, что стохастическая полугруппа стандартна;
Найдите генератор Пуассоновского процесса.
SolutionРешение
Enum-item(1)
Докажем марковость. Рассмотрим целые числа \(0 \leq a_1 \leq \dots \leq a_n \leq i \leq j\) (только такие имеет смысл рассматривать). Тогда из-за независимости приращений имеем
Согласуется с интуицией из описания выше: в каждом состоянии \(n\) процесс ждет время \(\operatorname {Exp}(\lambda )\) (интервал между скачками пуассоновского процесса!), после чего прыгает в \(n+1\) с вероятностью \(\frac{\lambda }{\lambda } = 1\). Граф интенсивностей:
Граф интенсивностей пуассоновского процесса: переход \(n\to n+1\) с постоянной интенсивностью \(\lambda\). У графа интенсивностей нет петель — диагональ генератора \(Q\) восстанавливается из условия сохранения (сумма строки равна нулю).
Пуассоновский процесс – это одновременно процесс восстановления и марковская цепь. Естественный вопрос: любой ли процесс восстановления марковский?
ProblemЗадача 2
Всякий ли процесс восстановления является марковской цепью?
\(Q\)-матрицей мы будем называть любую квадратную матрицу \(\mathbf{Q}\) размерности \(\left|\mathcal{X}\right| \times \left|\mathcal{X}\right|\), такую что
все диагональные элементы из \([-\infty , 0]\);
все внедиагональные элементы из \([0,+\infty )\);
\(\sum_{j \neq i}\mathbf{Q}_{ij} \leq -\mathbf{Q}_{ii}\) для любого \(i \in \mathcal{X}\).
Если все элементы \(Q\)-матрицы (а именно, элементы на диагонали) конечны и в последнем пункте выполнено равенство, т.е.
\[
\sum _{j \neq i}\mathbf{Q}_{ij} = -\mathbf{Q}_{ii} \quad \text{ для любого } i \in \mathcal{X}
\]
то такую \(Q\)-матрицу называют консервативной.
Генератор любой МЦНВ – это \(Q\)-матрица, и в случае конечного количества состояний он всегда будет консервативным. В бесконечном случае он может оказаться неконсервативным (и на диагонали может даже стоять \(-\infty\) – такие состояния называют мгновенными); в нашем курсе мы такие цепи рассматривать не будем, подробности можно найти в (Булинский и Ширяев 2005 г., гл. 4, § 16) и (Liggett 2010 г., разд. 2.4).
Как и в дискретном случае, цепь удобно изображать в виде ориентированного графа: вершины – состояния, ребра – ненулевые внедиагональные интенсивности \(\mathbf{Q}_{ij} > 0\). Такой граф называют графом интенсивностей. Заметим два отличия от графа переходных вероятностей МЦДВ:
в графе интенсивностей нет петель: диагональ консервативной \(Q\)-матрицы восстанавливается по внедиагональным элементам (\(\mathbf{Q}_{ii} = -\sum_{j \neq i}\mathbf{Q}_{ij}\)), поэтому ее не рисуют;
веса ребер – это не вероятности, а интенсивности: они неотрицательны, но могут быть больше \(1\), и сумма весов исходящих ребер может быть любой.
Например, вот граф интенсивностей для 2-го генератора из Уравнение 1:
Граф интенсивностей для генератора \(Q=\begin{pmatrix}-5&4&1\\2&-10&8\\3&3&-6\end{pmatrix}\): все шесть внедиагональных интенсивностей положительны, цепь неприводима.
1.4 Распределение цепи VS стохастическая полугруппа VS генератор
Нас будет интересовать связь распределения процесса, стохастической полугруппы и генератора для стандартной однородной МЦНВ. Можно ли однозначно восстановить один объект, имея другой? По распределению однородной цепи однозначно определяется стохастическая полугруппа (это просто переходные вероятности из нулевого времени), а по стохастической полугруппе однозначно (учитывая стандартность) определяется генератор (см. лемму Лемма 2). Можно ли пойти в обратную сторону?
Мы уже формулировали теорему (см. Теорема 1) о построении цепи по начальному распределению и переходным вероятностям в общем случае. Сформулируем для однородного случая.
Теорема 2 (Существование однородной МЦНВ) Пусть \(\mathcal{X}\) – конечное или счетное множество, пусть \((\mathbf{P}_t, t \geq 0)\) – это стохастическая полугруппа размерности \(\left|\mathcal{X}\right| \times \left|\mathcal{X}\right|\), пусть \(\Pi\) – некоторое распределение на \(\mathcal{X}\). Тогда существует единственная (с точки зрения распределения процесса) однородная МЦНВ \((X_{t}, t \geq 0)\) с начальным распределением \(\Pi\) и с переходными вероятностями, равными \(\mathbf{P}_t\).
Распределение цепи и стохастическая полугруппа (вместе с начальным распределением) друг по другу восстанавливаются однозначно. Но что с генератором (в случае стандартной цепи)? Оказывается, в конечном случае генератор обязан быть консервативным и (стандартная) стохастическая полугруппа по нему восстанавливается однозначно по формуле
\[
\mathbf{P}_t = e^{\mathbf{Q}t}, \quad t \geq 0
\]
В бесконечном случае все не так просто, по генератору не всегда однозначно восстанавливается стохастическая полугруппа (и процесс, соотв.). Иначе говоря, для одного и того же генератора можно предложить несколько цепей с заданным генератором, но с разными распределениями, с разными переходными вероятностями. Причина – явление взрыва; подробности см. в разделе про счетное число состояний ниже.
2 МЦНВ с конечным числом состояний
В данном разделе мы везде считаем \(\mathcal{X}\) конечным множеством. Как и в случае дискретного времени, в случае непрерывного времени теория становится сильно проще, если пространство состояний конечно.
2.1 Консервативность генератора
Мы знаем, что сумма любой строки у \(\mathbf{P}_t\) равна \(1\). Следовательно, поскольку в случае конечных сумм предел и сумму можно свободно переставлять местами, сумма производных в нуле по строке (т.е. сумма строки \(\mathbf{Q}\)) равна \(0\): для произвольного \(i \in \mathcal{X}\) имеем
Известно (см. лемму Лемма 2), что вне диагонали у матрицы \(\mathbf{Q}\) элементы неотрицательные и конечные. Значит на диагонали стоит тоже конечное число.
Лемма 3 (Консервативность генератора МЦНВ с конечным числом состояний) Если \(\mathcal{X}\) конечно, то
все элементы \(\mathbf{Q}\) конечны;
сумма любой строки равна \(0\). Иначе говоря, вне диагонали стоят неотрицательные числа, и
2.2 Прямые и обратные уравнения Колмогорова: восстановление стохастической полугруппы по генератору
Матрица \(\mathbf{Q}\) определяет целиком всю стох. полугруппу. По ней можно восстановить переходные вероятности с помощью дифференциальных уравнений Колмогорова.
Теорема 3 (Уравнения Колмогорова) Пусть \((X_t, t \geq 0)\) – это МЦНВ с конечным кол-ом состояний, пусть \(\mathbf{P}_{t}, t \geq 0\) – ее стох. полугруппа, пусть \(\mathbf{Q} = \mathbf{P}'_t \mid_{t= 0}\) – ее генератор. Тогда выполнены
обратные уравнения Колмогорова: \(\mathbf{P}'_t = \mathbf{Q} \cdot \mathbf{P}_t\) для всех \(t \geq 0\);
прямые уравнения Колмогорова: \(\mathbf{P}'_t = \mathbf{P}_t \cdot \mathbf{Q}\) для всех \(t \geq 0\);
В теореме имеется в виду поэлементное взятие производной. Иначе говоря, для любых \(i,j \in \mathcal{X}\) выполнено
Прямые и обратные уравнения – это система из дифференциальных уравнений. Они так называются, исходя из положения генератора. В прямых уравнениях генератор стоит <<сзади>> (справа): \(\mathbf{P}_t \cdot \mathbf{Q}\). В обратных, соотв., <<спереди>> (слева): \(\mathbf{Q} \cdot \mathbf{P}_t\).
Уравнения Колмогорова позволяют вывести уравнения и для распределения цепи \(\Pi^{(t)}\) в произвольный момент времени \(t \geq 0\) (напомним, что мы понимаем \(\Pi^{(t)}\) как вектор-строку).
Граф интенсивностей двухсостоятельной цепи с непрерывным временем: переход \(1\to 2\) с интенсивностью \(\alpha\), \(2\to 1\) — с интенсивностью \(\beta\).
Восстановите \(\mathbf{P}_t\). Попробуйте найти поэлементный предел \(\mathbf{P}_t\) при \(t \to \infty\).
SolutionРешение
Если \(\alpha =\beta =0\), т.е. \(\mathbf{Q} = \mathbf{0}\), то решение такое: \(\mathbf{P}_t = e^{\mathbf{0}t} = \mathbf{E}\) для любого \(t \geq 0\). Далее считаем, что они не равны одновременно нулю. Эквивалентно: \(\alpha + \beta > 0\).
Собственные значения \(\lambda_{1,2}\) матрицы \(\mathbf{Q}\) являются корнями уравнения
Граф интенсивностей МЦНВ с генератором \(Q=\begin{pmatrix}-1&1/2&1/2\\3&-6&3\\0&4&-4\end{pmatrix}\): ребра \(1\leftrightarrow2\), \(1\to3\), \(2\leftrightarrow3\); перехода \(3\to1\) нет, так как \(Q_{31}=0\).
Найдите формулу для \(\left(\mathbf{P}_{t}\right)_{11}\). Чему равен предел \(\left(\mathbf{P}_{t}\right)_{11}\) при \(t \to +\infty\)?
2.3 Отступление: свойства экспоненциального распределения
Напомним (см. главу про процессы восстановления): экспоненциальное распределение – единственное абсолютно непрерывное распределение на \([0, +\infty )\) с отсутствием памяти: для \(\xi \sim \operatorname {Exp}(\lambda )\) и \(s, t > 0\)
\[
\mathbb {P}\left(\xi > t + s \mid \xi > s\right) = \mathbb {P}\left(\xi > t\right)
\]
Именно поэтому экспоненциальное распределение неизбежно возникает в марковских цепях с непрерывным временем: время, которое цепь просидит в текущем состоянии, не должно зависеть от того, сколько она в нем уже просидела (иначе нарушилось бы марковское свойство). Сформулируем еще два свойства, которые понадобятся ниже.
Лемма 5 (Гонка экспонент) Пусть \(I\) – не более чем счётное множество, и пусть \(\eta_k\), \(k \in I\), – независимые случайные величины, \(\eta_k \sim \operatorname {Exp}(q_k)\), причем \(0 < q := \sum_{k \in I} q_k < \infty\). Положим \(\eta := \inf_{k \in I} \eta_k\). Тогда инфимум п.н. достигается в единственном случайном индексе \(K\), причем \[
\eta \sim \operatorname {Exp}(q), \qquad \mathbb {P}\left(K = k\right) = \frac{q_k}{q},
\] и случайные величины \(\eta\) и \(K\) независимы.
Mn-proofДоказательство
Вероятность совпадения двух независимых абсолютно непрерывных величин равна нулю, а пар \((j,k)\) не более чем счетное число – значит, п.н. все \(\eta_k\) различны и минимум (если достигается) достигается в единственном индексе. Посчитаем для \(k \in I\), \(t \geq 0\), пользуясь независимостью (формула полной вероятности по значению \(\eta_k\)): \[
\begin{align} \mathbb {P}\left(K = k, \; \eta \geq t\right) & = \mathbb {P}\left(\eta _k \geq t, \; \eta _j > \eta _k \; \forall j \neq k\right) = \\ & = \int _t^{+\infty } q_k e^{-q_k s} \prod _{j \neq k} \underbrace{\mathbb {P}\left(\eta _j > s\right)}_{=e^{-q_j s}} \, ds = \\ & = \int _t^{+\infty } q_k e^{-q s} \, ds = \frac{q_k}{q} \, e^{-q t} \end{align}
\] При \(t = 0\) получаем \(\mathbb {P}\left(K = k\right) = \frac{q_k}{q}\); суммирование по \(k\) дает \(1\), т.е. минимум п.н. достигается. Правая часть распадается в произведение \(\mathbb {P}\left(K=k\right) \cdot e^{-qt}\), откуда независимость \(\eta\) и \(K\) и \(\eta \sim \operatorname {Exp}(q)\).
если \(\sum_{n=1}^{\infty } \frac{1}{\lambda_n} < \infty\), то \(\mathbb {P}\left(\sum_{n=1}^{\infty } \xi_{n} < \infty \right) = 1\);
если \(\sum_{n=1}^{\infty } \frac{1}{\lambda_n} = \infty\), то \(\mathbb {P}\left(\sum_{n=1}^{\infty } \xi_{n} = \infty \right) = 1\).
Иначе говоря, сумма \(\sum_n \xi_n\) либо п.н. конечна, либо п.н. бесконечна, и это определяется сходимостью ряда \(\sum_n \frac{1}{\lambda_n}\) из матожиданий.
Mn-proofДоказательство
Пусть \(S := \sum_{n=1}^{\infty }\xi_n\) (предел монотонной последовательности, возможно \(+\infty\)).
Если \(\sum_n \frac{1}{\lambda_n} < \infty\): по теореме о монотонной сходимости \(\mathbb {E}\left[S\right] = \sum_n \mathbb {E}\left[\xi_n\right] = \sum_n \frac{1}{\lambda_n} < \infty\), а величина с конечным матожиданием п.н. конечна.
Если \(\sum_n \frac{1}{\lambda_n} = \infty\): посчитаем \(\mathbb {E}\left[e^{-S}\right]\). По независимости и монотонной (мажорируемой) сходимости
Расходимость \(\sum_n \frac{1}{\lambda_n}\) равносильна расходимости \(\sum_n \ln \left(1 + \frac{1}{\lambda_n}\right)\) (если \(\frac{1}{\lambda_n} \to 0\), то \(\ln (1+x) \sim x\); если не стремится к нулю – оба ряда расходятся тривиально). Значит, произведение равно \(0\), т.е. \(\mathbb {E}\left[e^{-S}\right] = 0\). Но \(e^{-S} \geq 0\), поэтому \(e^{-S} = 0\) п.н., т.е. \(S = \infty\) п.н.
Еще один красивый факт из той же серии – про пуассоновский процесс (который, как мы видели, целиком построен из экспоненциальных интервалов).
Лемма 7 Пусть \(\left(N_t\right)_{t \geq 0}\) – пуассоновский процесс, \(J_1, \ldots , J_n\) – моменты его скачков. Тогда при условии события \(\left\{ N_t=n\right\}\) вектор \((J_1, \ldots , J_n)\) имеет совместную плотность распределения \[
f\left(t_1, \ldots , t_n\right)=n!\, t^{-n} \, \; \mathbb {1}_{0 \leq t_1 \leq \ldots \leq t_n \leq t}
\] Иначе говоря, при условии \(\left\{ N_t=n\right\}\) моменты скачков распределены как упорядоченная выборка объёма \(n\) из равномерного распределения на \([0, t]\). Условное распределение не зависит ни от интенсивности \(\lambda\), ни от экспоненциальности как таковой – скачки <<равномерно разбросаны>> по отрезку.
2.4 Конструкция <<прыжок–ожидание>>: построение cadlag версии МЦНВ
Вернемся к неформальному описанию поведения цепи, данному после примеров генераторов (см. Уравнение 1), и сформулируем его аккуратно. Интуиция: марковское свойство влечёт, что
время до следующего скачка (будущее) не зависит от времени, прошедшего с момента последнего скачка (прошлое) \(\; \Rightarrow \;\) времена ожидания не имеют памяти \(\; \Rightarrow \;\) они экспоненциальны;
следующее посещаемое состояние (будущее) не зависит от предыдущих посещённых состояний (прошлое) \(\; \Rightarrow \;\) последовательность посещаемых состояний образует марковскую цепь с дискретным временем.
Теорема 5 (Время ожидания и распределение скачка) Пусть \((X_t, t \geq 0)\) – стандартная МЦНВ с конечным числом состояний, с генератором \(\mathbf{Q}\) и cadlag траекториями. Пусть \(H := \inf \left\{ s > 0 \; : \; X_{s} \neq X_0\right\}\) – время первого скачка (англ. holding time). Тогда при условии \(X_0 = i\):
если \(\mathbf{Q}_{ii} = 0\), то \(H = +\infty\) п.н., т.е. \(i\) – поглощающее состояние;
если \(\mathbf{Q}_{ii} < 0\), то \(H \sim \operatorname {Exp}(-\mathbf{Q}_{ii})\), следующее состояние выбирается с вероятностями
Верно и обратное: по консервативной \(Q\)-матрице цепь можно построить по следующему алгоритму (он же – рецепт симуляции МЦНВ на компьютере):
построить встроенную МЦДВ \((\tilde{X}_n, n \geq 0)\) (формальное определение – в следующем пункте) с матрицей переходов \(\tilde{\mathbf{P}}\), где \(\tilde{\mathbf{P}}_{ij} = \frac{\mathbf{Q}_{ij}}{-\mathbf{Q}_{ii}}\) при \(i \neq j\) и \(\tilde{\mathbf{P}}_{ii} = 0\) (поглощающие состояния обрабатываются отдельно: \(\tilde{\mathbf{P}}_{ii} = 1\));
взять независимые (и независимые от \(\tilde{X}\)) величины \(E_1, E_2, \ldots \sim \operatorname {Exp}(1)\) и положить времена ожидания \(W_n := \frac{E_n}{-\mathbf{Q}_{\tilde{X}_{n-1}, \tilde{X}_{n-1}}}\), моменты скачков \(J_n := W_1 + \ldots + W_n\);
положить \(X_t := \tilde{X}_{n}\) при \(t \in [J_{n}, J_{n+1})\).
Полученный процесс – стандартная МЦНВ с генератором \(\mathbf{Q}\) и cadlag траекториями (Norris 1997 г., разд. 2.6).
Одна возможная реализация такой траектории (для некоторой \(3\)-состоятельной цепи) выглядит так: Одна реализация выборочной траектории МЦНВ, построенной по конструкции «прыжок–ожидание»: цепь ждёт в состоянии \(i\) случайное время \(W_n \sim \operatorname{Exp}(-\mathbf{Q}_{ii})\), затем прыгает в состояние \(j \neq i\) с вероятностью \(\tilde{\mathbf{P}}_{ij} = \mathbf{Q}_{ij} / (-\mathbf{Q}_{ii})\) (встроенная цепь). Нажмите кнопку «Новая реализация», чтобы перегенерировать времена ожидания и скачки — точка побежит по новой траектории в реальном времени. Слайдеры задают интенсивности \(\mathbf{Q}_{ij}\) (\(i \neq j\)) генератора; диагональ \(\mathbf{Q}_{ii} = -\sum_{j \neq i} \mathbf{Q}_{ij}\) пересчитывается автоматически.
Цепь стартовала в состоянии \(1\), просидела в нем случайное время \(W_1\), прыгнула в состояние \(3\), просидела время \(W_2\), и т.д.
Mn-extraДополнительно
Альтернативный взгляд на тот же механизм – <<гонка часов>>. Находясь в состоянии \(i\), запустим независимые экспоненциальные часы \(\eta_j \sim \operatorname {Exp}(\mathbf{Q}_{ij})\) для всех \(j \neq i\) (часы с нулевой интенсивностью никогда не звонят), и прыгнем в то состояние, чьи часы зазвонили первыми. По лемме Лемма 5 о гонке экспонент:
время до скачка \(H = \min_{j \neq i} \eta_j \sim \operatorname {Exp}\left(\sum_{j \neq i}\mathbf{Q}_{ij}\right) = \operatorname {Exp}(-\mathbf{Q}_{ii})\) (консервативность!);
прыжок происходит в состояние \(j\) с вероятностью \(\frac{\mathbf{Q}_{ij}}{-\mathbf{Q}_{ii}}\), независимо от времени скачка.
Получили в точности теорему Теорема 5. Эта интерпретация объясняет, почему \(\mathbf{Q}_{ij}\) называют интенсивностью перехода\(i \to j\): это <<скорость звонка>> часов, отвечающих за данный переход.
С этого момента для любой МЦНВ мы рассматриваем именно версию с cadlag траекториями.
2.5 Сообщающиеся состояния, возвратность, встроенная цепь с дискретным временем
Как и в случае цепей с дискретным временем, состояния \(i,j\) называют сообщающимися, если найдутся такие \(t_1, t_2 \geq 0\), что
Пусть \(T_{i} := \inf \left\{ t > 0 \; : \; X_{t-} \neq X_{t} = i\right\}\), где \(X_{t-} := \lim_{s \to t - 0} X_{s}\) – левый предел процесса в точке \(t\) (у нас все траектории cadlag, значит предел всегда существует в любой точке). \(T_{i}\) – это непрерывный аналог времени (первого) возвращения в состояние \(i\). Состояние \(i\) называют возвратным, если
МЦДВ \(\tilde{X}_n, n \geq 0\) называют встроенной цепью для МЦНВ \(X_t, t \geq 0\) (англ. embedded Markov chain).
Лемма 9 (Связь МЦНВ с встроенной цепью) У МЦНВ \((X_{t}, t \geq 0)\) и у ее встроенной МЦДВ \((\tilde{X}_{n}, n \geq 0)\) одинаковые сообщающиеся состояния, одинаковые возвратные и транзитные состояния.
2.6 Стационарное распределение
Распределение (строка) \(\Pi\) на \(\mathcal{X}\) называется стационарным для МЦНВ \((X_{t}, t \geq 0)\) с переходными вероятностями \((\mathbf{P}_t, t \geq 0)\), если
Лемма 10 Пусть \(\Pi\) – некоторое распределение на \(\mathcal{X}\). Тогда \[
\Pi \text{ -- стационарное распределение} \quad \iff \quad \Pi \cdot \mathbf{Q} = \mathbf{0}
\] Иначе говоря, распределение является стационарным тогда и только тогда, когда распределение – это левый собственный вектор (строка) матрицы \(\mathbf{Q}\) с собственным значением \(0\).
Следовательно, \(\Pi \cdot \mathbf{P}_t\) (поэлементно) не зависит от времени. В таком случае \(\Pi \cdot \mathbf{P}_t =\Pi \cdot \mathbf{P}_0\). Но \(\mathbf{P}_0 = \mathbf{E}\). В итоге получаем
\[
\Pi \cdot \mathbf{P}_t =\Pi
\]
2.7 Неприводимая (эргодическая) цепь: предельные свойства
Пусть \((X_t, t \geq 0)\) – неприводимая цепь. Неприводимую положительно-возвратную МЦНВ называют эргодической. Отличие от дискретного случая: ушло требование апериодичности.
В случае с конечным числом состояний любое возвратное состояние будет положительно-возвратным, и, соотв., любая неприводимая цепь будет эргодической.
Теорема 6 (Эргодическая теорема) У неприводимой МЦНВ с конечным числом состояний (т.е. эргодической МЦНВ) только одно стационарное распределение \(\Pi = \Pi^{\operatorname {erg}}\), называемое эргодическим. Свойства:
\(\Pi^{\operatorname {erg}}\) – это левый собственный вектор матрицы \(\mathbf{Q}\) для собственного значения \(0\);
Тот же результат, что и для дискретных цепей Маркова, с двумя отличиями:
Апериодичность не определена в непрерывном времени/не требуется для эргодической теоремы;
\(\frac{1}{\mathbb {E}_{i}\left[T_i\right]}\) заменяется на \(\frac{1}{-\mathbf{Q}_{ii}} \cdot \frac{1}{\mathbb {E}_{i}\left[T_i\right]}\). В дискретном времени одно посещение \(i\) – это одна единица времени в \(i\); в непрерывном времени одно посещение в \(i\) равно \(1/-\mathbf{Q}_{ii}\) единиц времени в \(i\) (в среднем).
ProblemЗадача 5
Переходные вероятности марковской цепи \(\left(X_{t}, t \geqslant 0\right)\) с фазовым пространством \(\mathcal{X} = \left\{ 1,2,3\right\}\) имеют вид: \[
\begin{align} p_{11}(h)& =1-\lambda h+o(h), & p_{12}(h)& =\lambda h+o(h), & p_{13}(h)& =o(h) \\ p_{21}(h)& =o(h), & p_{22}(h)& = 1 - \mu h + o(h), & p_{23}(h)& = \mu h + o(h) \\ p_{31}(h)& = \nu h + o(h), & p_{32}(h)& = o(h), & p_{33}(h)& =1 - \nu h + o(h), \end{align}
\] при \(h \to 0+\), где \(\lambda , \mu , \nu > 0\). Докажите, что такая цепь удовлетворяет условию эргодической теоремы. Найдите ее инфинитезимальную матрицу и стационарное распределение.
ProblemЗадача 6
Система <<массового обслуживания>> состоит из прибора и ремонтного устройства. Прибор работает случайное время, имеющее экспоненциальное распределение с параметром \(\alpha\). Ремонт прибора занимает случайное время, имеющее экспоненциальное распределение с параметром \(\beta\). Обозначим \[
\begin{align} \Pi _1^{(t)} & = \mathbb {P}\left(\text{прибор работает в момент времени }t\right) \\ \Pi _2^{(t)} & = \mathbb {P}\left(\text{прибор ремонтируется в момент времени }t\right) \end{align}
\] Найдите \(\Pi_1^{(t)}, \Pi_2^{(t)}\), при условии \(\Pi_1^{(0)} = \Pi_2^{(0)} = 1/2\), предполагая, что процесс образует марковскую цепь. Чему равен предел этого распределения при \(t \to +\infty\)? Зависит ли он от начального распределения?
Цепь «прибор–ремонт»: вероятность \(\Pi_1^{(t)}\) того, что прибор работает в момент \(t\), при \(\Pi_1^{(t)} = \frac{\beta}{\alpha+\beta} + \left(\Pi_1^{(0)} - \frac{\beta}{\alpha+\beta}\right) e^{-(\alpha+\beta)t}\). Двигайте слайдеры \(\alpha\), \(\beta\) и \(\Pi_1^{(0)}\) (последний задаёт четвёртую, выделенную кривую) — все кривые экспоненциально стягиваются к одному и тому же стационарному уровню \(\frac{\beta}{\alpha+\beta}\): цепь «забывает» начальное распределение.
ProblemЗадача 7
Рассмотрим МЦНВ \((X_t, t\geq 0)\) из задачи Задача 4, с матрицей интенсивности переходов \[
\mathbf{Q} = \begin{pmatrix} -1 & 1 / 2 & 1 / 2 \\ 3 & -6 & 3 \\ 0 & 4 & -4 \end{pmatrix}
\]
Найдите все стационарные распределения цепи.
Найдите стационарные распределения для встроенной цепи \(\tilde{X}_n\). Является ли она эргодической? Если да – найдите эргодическое распределение.
Является ли цепь \(X_t\) неприводимой? А эргодической? Если да – найдите эргодическое распределение.
Найдите предел \(\mathbf{P}_t\) при \(t \to +\infty\).
Найдите предел \(X_t\) по распределению, в зависимости от начального распределения \(\Pi^{(0)}\).
Найдите среднее время возврата \(\mathbb {E}_{i}\left[T_i\right]\) для каждого из состояний \(i \in \mathcal{X}\).
Эргодичность «в лицах» для цепи \((X_t)\) из задачи с матрицей \(\mathbf{Q} = \begin{pmatrix} -1 & 1/2 & 1/2 \\ 3 & -6 & 3 \\ 0 & 4 & -4 \end{pmatrix}\): одна смоделированная траектория «бежит» по времени (метод «прыжок–ожидание»), а доли времени \(\frac{1}{t}\int_0^{t} \;\mathbb{1}_{X_s = i}\, ds\), проведённого в каждом из трёх состояний, обновляются на глазах и сходятся к стационарному распределению \(\Pi = \left(\frac{24}{41}, \frac{8}{41}, \frac{9}{41}\right)\) (пунктирные уровни). Кнопка «Новая траектория» перегенерирует реализацию.
2.8 Предельные свойства в общем случае
Что если конечная цепь приводима, т.е. состоит из нескольких сообщающихся классов? Картина полностью аналогична дискретному случаю (см. главу про МЦДВ): состояния делятся на транзитные и возвратные классы (тип класса определяется замкнутостью, как и раньше, – через встроенную цепь); стартуя из транзитного класса, цепь за п.н. конечное время попадает в один из возвратных классов и остается в нем навсегда; внутри каждого возвратного класса работает эргодическая теорема.
Единственное – приятное – отличие от дискретного случая: у конечной МЦНВ поэлементный предел \(\lim_{t \to \infty } \mathbf{P}_t\) существует всегда (а не только предел по Чезаро). Периодических эффектов, из-за которых у МЦДВ мог не существовать предел \(\mathbf{P}^n\), в непрерывном времени нет: время ожидания в состоянии непрерывно и <<размывает>> любую периодичность.
3 МЦНВ со счетным числом состояний
Определения переносятся со случая конечного числа состояний: сообщающиеся состояния и классы, неприводимость, возвратность, стационарные распределения, встроенная цепь и т.д. При этом, как и в дискретном случае, часть <<хороших>> свойств конечных цепей перестает быть автоматической: возвратное состояние может быть нуль-возвратным (\(\mathbb {E}_{i}\left[T_i\right] = +\infty\)), у неприводимой цепи может не быть стационарного распределения, и т.д. Но появляются и два принципиально новых эффекта, не имеющих дискретного аналога: взрыв и связанная с ним неоднозначность восстановления цепи по генератору. Начнем с них.
3.1 Взрыв
Вспомним конструкцию <<прыжок–ожидание>> (п. Глава 2.4): цепь сидит в состояниях случайные времена \(W_1, W_2, \ldots\) и прыгает в моменты \(J_n = W_1 + \ldots + W_n\). В конечном случае \(J_n \to +\infty\) п.н. (времена ожидания – экспоненты с конечным набором интенсивностей). В счетном случае интенсивности \(-\mathbf{Q}_{ii}\) могут неограниченно расти вдоль траектории, времена ожидания – убывать так быстро, что их сумма сходится:
Событие \(\left\{ \zeta < \infty \right\}\) называют взрывом (англ. explosion), а \(\zeta\) – моментом взрыва: за конечное время цепь успевает совершить бесконечно много прыжков. Если \(\mathbb {P}_{i}\left(\zeta = +\infty \right) = 1\) для любого начального состояния \(i\), цепь называют невзрывающейся.
ExampleПример 5
Рассмотрим чистый процесс рождения (англ. pure birth process): \(\mathcal{X} = \mathbb {N}\), из состояния \(n\) возможен единственный переход \(n \to n+1\) с интенсивностью \[
\mathbf{Q}_{n,n+1} = -\mathbf{Q}_{nn} = \mu \cdot n^{\alpha },
\] где \(\mu , \alpha > 0\). Граф интенсивностей:
Граф интенсивностей чистого процесса рождения с \(\lambda_n = \mu\cdot n^\alpha\) (при \(\alpha=1\) — процесс Юла; общий процесс рождения может «взорваться» за конечное время).
Пусть \(X_0 = 1\). При каких \(\alpha\) цепь взрывается?
SolutionРешение
Встроенная цепь детерминирована: \(1 \to 2 \to 3 \to \ldots\). По конструкции <<прыжок–ожидание>> времена ожидания \(W_n\) независимы, \(W_n \sim \operatorname {Exp}(\mu n^{\alpha })\), и \[
\zeta = \sum _{n=1}^{\infty } W_n
\] По лемме Лемма 6 о сумме независимых экспонент все определяется сходимостью ряда \[
\sum _{n=1}^{\infty } \frac{1}{\mu n^{\alpha }}
\]
Если \(\alpha > 1\), ряд сходится, значит \(\mathbb {P}_{1}\left(\zeta < \infty \right) = 1\): цепь п.н. взрывается – за конечное время <<пробегает>> все натуральные числа и уходит на бесконечность.
Если \(\alpha \leq 1\), ряд расходится, значит \(\mathbb {P}_{1}\left(\zeta = \infty \right) = 1\): взрыва нет.
Пограничный случай \(\alpha = 1\) – это процесс Юла: популяция из \(n\) частиц, каждая из которых независимо делится с интенсивностью \(\mu\); по лемме о гонке экспонент (лемма Лемма 5) суммарная интенсивность деления равна \(\mu n\). Популяция растет экспоненциально быстро, но не взрывается.
Взрыв чистого процесса рождения: \(\mathbf{Q}_{n,n+1} = \mu n^{\alpha}\), \(\mu = 1\), \(X_0 = 1\). Двигайте слайдер \(\alpha\) — при переходе через \(1\) ряд \(\sum_n n^{-\alpha}\) начинает сходиться, и у смоделированной (красная кривая) траектории появляется конечный момент взрыва \(\zeta\) (пунктирная вертикальная асимптота). Синяя пунктирная кривая — процесс Юла (\(\alpha = 1\)) для сравнения: он растёт экспоненциально быстро, но никогда не взрывается. Кнопка перегенерирует обе траектории заново.
Что происходит с цепью после взрыва? Формула \(X_t = \tilde{X}_n\) при \(t \in [J_n, J_{n+1})\) определяет процесс только до момента \(\zeta\). Стандартный выход – рассмотреть минимальную цепь: доопределить \(X_t := \partial\) для \(t \geq \zeta\), где \(\partial \notin \mathcal{X}\) – специальное <<кладбищенское>> состояние. Но тогда \(\sum_{j \in \mathcal{X}}\left(\mathbf{P}_t\right)_{ij} = \mathbb {P}_{i}\left(\zeta > t\right)\) может быть меньше \(1\) – матрицы становятся субстохастическими. Альтернативно, можно после взрыва <<перезапускать>> цепь в каком-нибудь состоянии \(\mathcal{X}\) – причем в каком именно, генератор \(\mathbf{Q}\) не диктует! Разные правила перезапуска дают разные стохастические полугруппы (и разные цепи) с одним и тем же генератором. Это и есть обещанная выше неоднозначность восстановления цепи по генератору в бесконечном случае. Подробности: (Norris 1997 г., разд. 2.7), (Liggett 2010 г., разд. 2.4) (в том числе знаменитый пример Блэквелла).
Полезно иметь простые достаточные условия отсутствия взрыва.
Теорема 7 Пусть \((X_t, t \geq 0)\) – (минимальная) МЦНВ с консервативным генератором \(\mathbf{Q}\). Цепь не взрывается, если выполнено хотя бы одно из условий:
\(\mathcal{X}\) конечно;
интенсивности выхода ограничены: \(\sup_{i \in \mathcal{X}}\left(-\mathbf{Q}_{ii}\right) < \infty\);
цепь стартует из состояния \(i\), возвратного для встроенной цепи \(\tilde{X}_n\).
3.2 Стационарное распределение и предельные свойства
Для неприводимых невзрывающихся цепей картина предельного поведения полностью аналогична дискретному случаю – и даже проще, поскольку не нужна апериодичность.
Теорема 8 Пусть \((X_t, t \geq 0)\) – неприводимая невзрывающаяся МЦНВ с консервативным генератором \(\mathbf{Q}\), причем \(-\mathbf{Q}_{ii} > 0\) для всех \(i\). Тогда возможны ровно два случая.
Положительно-возвратный случай: \(\mathbb {E}_{i}\left[T_i\right] < \infty\) для какого-то (эквивалентно: для любого) состояния \(i\). Тогда у цепи существует единственное стационарное распределение \(\Pi\), причем
Осторожно: хотя возвратность/транзитность у МЦНВ и ее встроенной цепи совпадают, положительная возвратность – нет! Цепь \(X_t\) может быть положительно-возвратной при нуль-возвратной встроенной цепи, и наоборот: сравните стационарные распределения \(\Pi_i \propto \tilde{\Pi }_i / (-\mathbf{Q}_{ii})\) – <<перевзвешивание>> временами пребывания может превратить суммируемое распределение в несуммируемую меру и наоборот.
3.3 Процессы рождения и гибели
Процессом рождения и гибели (англ. birth-death process) называют МЦНВ на \(\mathcal{X} = \mathbb {Z}_+\), у которой возможны переходы только в соседние состояния:
где \(\lambda_n \geq 0\) – интенсивности рождения, \(\mu_n \geq 0\) – интенсивности гибели (\(\mu_0 := 0\)). Граф интенсивностей:
Граф интенсивностей общего процесса рождения и гибели: переход \(n\to n+1\) с интенсивностью \(\lambda_n\), \(n\to n-1\) — с интенсивностью \(\mu_n\).
Интерпретация по конструкции <<прыжок–ожидание>>: в состоянии \(n\) цепь ждет время \(\operatorname {Exp}(\lambda_n + \mu_n)\) и прыгает вверх с вероятностью \(\frac{\lambda_n}{\lambda_n + \mu_n}\), вниз – с вероятностью \(\frac{\mu_n}{\lambda_n + \mu_n}\). Много уже знакомых нам процессов – частные случаи: пуассоновский процесс (\(\lambda_n \equiv \lambda\), \(\mu_n \equiv 0\)), чистый процесс рождения (\(\mu_n \equiv 0\)), процесс Юла (\(\lambda_n = n\mu\), \(\mu_n \equiv 0\)).
Для процессов рождения и гибели стационарное распределение ищется явно. Ключевое наблюдение: для них стационарность равносильна более сильному на вид условию детального баланса.
Лемма 11 (Детальный баланс) Пусть \((X_t, t \geq 0)\) – процесс рождения и гибели, \(\Pi\) – распределение на \(\mathbb {Z}_+\). Тогда \[
\Pi \cdot \mathbf{Q} = \mathbf{0} \qquad \iff \qquad \Pi _n \lambda _n = \Pi _{n+1}\mu _{n+1} \quad \forall n \geq 0
\] Условие справа (детальный баланс) означает: в стационарном режиме <<поток вероятности>> через каждое ребро \(n \leftrightarrow n+1\) уравновешен.
Следствие 1 Пусть все \(\lambda_n > 0\) (\(n \geq 0\)) и \(\mu_n > 0\) (\(n \geq 1\)). Из детального баланса \(\Pi_{n+1} = \Pi_n \frac{\lambda_n}{\mu_{n+1}}\) индукцией получаем \[
\Pi _n = \Pi _0 \cdot \prod _{k=1}^{n} \frac{\lambda _{k-1}}{\mu _{k}}, \qquad n \geq 1
\] Значит, нормируемое решение уравнения \(\Pi \cdot \mathbf{Q} = \mathbf{0}\) существует тогда и только тогда, когда \[
Z := 1 + \sum _{n=1}^{\infty }\prod _{k=1}^{n} \frac{\lambda _{k-1}}{\mu _{k}} < \infty ,
\] и в этом случае оно единственно: \(\Pi_0 = \frac{1}{Z}\). Если цепь при этом не взрывается (например, выполнено какое-то из условий теоремы Теорема 7), то это решение – стационарное распределение цепи в полном смысле (\(\Pi \cdot \mathbf{P}_t = \Pi\) для всех \(t\)). Осторожно: для взрывающейся цепи эквивалентность \(\Pi \mathbf{Q} = \mathbf{0} \iff \Pi \mathbf{P}_t = \Pi\) может нарушаться – она была доказана нами только в конечном случае.
ExampleПример 6
Очередь M/M/1: клиенты приходят в моменты скачков пуассоновского процесса интенсивности \(\lambda\); единственный сервер обслуживает клиентов по одному, время обслуживания \(\sim \operatorname {Exp}(\mu )\), все времена независимы. \(X_t\) – число клиентов в системе (обслуживаемый + очередь). Граф интенсивностей:
Граф интенсивностей очереди M/M/1: приход клиента — «рождение» с интенсивностью \(\lambda\), обслуживание — «гибель» с интенсивностью \(\mu\).
Найдите стационарное распределение при \(\rho := \frac{\lambda }{\mu } < 1\). Что происходит при \(\rho \geq 1\)?
SolutionРешение
Это процесс рождения и гибели с постоянными интенсивностями \(\lambda_n \equiv \lambda\), \(\mu_n \equiv \mu\) (отсутствие памяти экспоненциального распределения гарантирует марковость). Цепь не взрывается: интенсивности выхода ограничены числом \(\lambda + \mu\) (условие (ii) теоремы Теорема 7). По следствию Следствие 1:
– геометрическое распределение. В частности, в стационарном режиме сервер простаивает долю времени \(\Pi_0 = 1 - \rho\), а среднее число клиентов в системе равно \(\sum_n n \Pi_n = \frac{\rho }{1 - \rho }\) – оно взрывается при \(\rho \to 1-\): система, загруженная почти на \(100\%\), работает плохо.
При \(\rho \geq 1\) ряд \(Z\) расходится, стационарного распределения нет: очередь <<уплывает на бесконечность>> (при \(\rho > 1\) цепь транзитна, при \(\rho = 1\) – нуль-возвратна, ср. с простейшим случайным блужданием). По теореме Теорема 8 в этом случае \(\mathbb {P}\left(X_t = n\right) \to 0\) для любого фиксированного \(n\).
Очередь M/M/1 при \(\mu = 1\) (число клиентов в системе \(X_t\)): двигайте слайдер загрузки \(\rho = \lambda/\mu\), чтобы увидеть «фазовый переход» в \(\rho = 1\) — при \(\rho < 1\) (эргодический режим) очередь снова и снова возвращается к нулю, а при \(\rho \geq 1\) (транзитный режим) уплывает на бесконечность. Справа — при \(\rho < 1\) эмпирическая доля времени в каждом состоянии (по долгой отдельной симуляции) против теоретического геометрического распределения \(\Pi_n = (1-\rho)\rho^n\). Кнопка перегенерирует траекторию заново.
При ρ ≥ 1 стационарного распределения нет — сравнение с геометрическим распределением не определено.
ProblemЗадача 8
Очередь M/M/\(\infty\): клиенты приходят по пуассоновскому процессу интенсивности \(\lambda\), но теперь серверов бесконечно много: каждый клиент немедленно начинает обслуживаться своим сервером, время обслуживания \(\sim \operatorname {Exp}(\mu )\), все времена независимы. \(X_t\) – число клиентов в системе. Покажите, что \(X_t\) – процесс рождения и гибели, найдите его интенсивности и стационарное распределение.
использованная литература
Liggett, T. M. 2010 г. Continuous Time Markov Processes: An Introduction. Continuous Time Markov Processes. American Mathematical Society.
Norris, J. R. 1997 г. Markov Chains. Cambridge University Press.
Булинский, А. В., и А. Н. Ширяев. 2005 г. Теория случайных процессов. Физматлит.
Сноски
Как и в случае цепей с дискретным временем, все возвратные состояния цепи с непрерывным временем и с конечным числом состояний являются положительно-возвратными.↩︎