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

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

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

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}\) называется фазовым пространством или пространством состояний марковской цепи;

• Условные вероятности

  \[ \mathbb {P}\left(X_{t}=j \mid X_{s}=i\right) \]

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

• Из переходных вероятностей можно составить матрицы переходных вероятностей от временной точки \(s\) к временной точке \(t\):

  \[ \mathbf{P}_{s \to t} := \left( \mathbb {P}\left(X_{t}=j \mid X_{s}=i\right) \right)_{i, j \in \mathcal{X}}, \]

  где \(i\) – номер строки матрицы, \(j\) – номер столбца.

• \(\Pi^{(0)} = \left(\mathbb {P}\left(X_0 = j\right), j \in \mathcal{X}\right)\) – начальное распределение цепи.

• \(\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\) марковской цепи удовлетворяют следующим свойствам.

1. \(\mathbf{P}_{s \to t}\) – это стохастическая матрица (т.е. состоящая из неотрицательных элементов, причем сумма по любой строке равна \(1\)) для любых \(s,t\);

2. \(\mathbf{P}_{t \to t} = \mathbf{E}\) для любого времени \(0 \leq t\);

3. Выполнены уравнения Колмогорова-Чепмена: \(\forall s \leqslant u \leqslant t\)

   \[ \mathbf{P}_{s \to t} = \mathbf{P}_{s \to u} \cdot \mathbf{P}_{u \to 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\).

В дальнейшем, если не оговорено иного, мы будем рассматривать именно однородные МЦНВ.

1.2 Стандартная стохастическая полугруппа

Для однородной МЦНВ выполнено

\[ \mathbf{P}_{s \to t} = \mathbf{P}_{0 \to t-s} \]

т.е. все переходные вероятности определяются переходными вероятностями из нуля. Как и в дискретном случае, введем обозначение

\[ \mathbf{P}_{t} := \mathbf{P}_{0 \to t} \]

У однородной МЦДВ ее переходные вероятности полностью определялись одной стохастической матрицей \(\mathbf{P}\) переходов за один шаг. В непрерывном случае распределение однородной марковской цепи, в отличие от дискретного времени, определяется не одной матрицей, а целым континуумом стохастических матриц \(\mathbf{P}_t, t \geq 0\). При этом выполнено

1. \(\mathbf{P}_0 = \mathbf{E}\);

2. \(\mathbf{P}_{t + s} = \mathbf{P}_{t} \cdot \mathbf{P}_{s}\) (уравнения Колмогорова-Чепмена)

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

Для любой стохастической полугруппы (стохастических) матриц можно построить однородную МЦНВ.

Мы уже наложили на МЦНВ условие однородности. В дискретном случае мы на этом остановились: условие однородности оказалось вполне достаточным, чтобы получить достаточно богатую теорию, охарактеризовать предельное поведение и т.д. В непрерывном случае одной лишь однородности недостаточно, т.к. вылезают некоторые патологические примеры. Рассмотрим их.

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)\).

1. Докажите, что такой процесс существует;

2. Является ли этот процесс МЦНВ? Если да, является ли он однородной МЦНВ? Если да – найдите стохастическую полугруппу переходных вероятностей.

3. Можно ли построить модифицацию этого процесса с п.н. непрерывными справа траекториями?

SolutionРешение

Enum-item(1)

Применим теорему Колмогорова о согласованных конечномерных распределениях: зададим конечномерные распределения как произведения \(\operatorname {Ber}(1/2)\) по каждой временной точке – независимость делает проверку согласованности тривиальной.

Enum-item(2)

Это однородная МЦНВ. Матрицы переходов:

\[ \mathbf{P}_{t} = \begin{cases} \left(\begin{smallmatrix} 1 & 0\\ 0 & 1 \end{smallmatrix}\right), & t = 0 \\ \left(\begin{smallmatrix} 1/2 & 1/2\\ 1/2 & 1/2 \end{smallmatrix}\right), & t > 0 \end{cases} \]

Enum-item(3)

Нет. Пусть \((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} \xrightarrow [t \to 0+]{} \underbrace{\mathbf{P}_0}_{= \mathbf{E}} \]

Имеется в виду поэлементный предел: для любых \(i,j \in \mathcal{X}\) выполнено

\[ \begin{align} \underbrace{\left(\mathbf{P}_t\right)_{ij}}_{= \mathbb {P}_{i}\left(X_{t} = j\right)} & \xrightarrow [t \to 0+]{} \\ & \quad \underbrace{\left(\mathbf{P}_{0}\right)_{ij}}_{= \left(\mathbf{E}\right)_{ij} = \delta _{i}^{j}} \end{align} \]

Стохастическую полугруппу \((\mathbf{P}_t, t \geq 0)\) (и соотв. МЦНВ), обладающую непрерывностью в нуле, называют стандартной. В дальнейшем, если не оговорено иного, мы будем рассматривать только стандартные однородные МЦНВ.

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

Доказательство можно посмотреть в (Булинский и Ширяев 2005 г., гл. 4, § 16, теор. 9).

Матрицу \(\mathbf{Q}\) сокращенно можно записать как

\[ \begin{align} & \qquad \qquad \qquad \qquad \qquad \qquad \mathbf{Q} = \mathbf{P}'_0 \\ & \text{(подразумеваем поэлементное взятие правой производной)} \end{align} \]

Ее называют инфинитезимальной матрицей, генератором или матрицей интенсивности переходов для МЦНВ \((X_t, t \geq 0)\) или ее стохастической полугруппы \((\mathbf{P}_{t}, t \geq 0)\) (в конце концов, \(\mathbf{Q}\) не зависит от начального распределения цепи, а только от переходных вероятностей, т.е. от стохастической полугруппы). Из леммы известно, что на диагонали у \(\mathbf{Q}\) стоят неположительные числа, возможно даже \(-\infty\). Вне диагонали стоят неотрицательные (конечные) числа. Название генератор дано матрице \(\mathbf{Q}\), поскольку при помощи нее можно в большинстве случаев однозначно восстановить стохастическую полугруппу. Забегая вперед, формула такая:

\[ \mathbf{P}_t = e^{\mathbf{Q}t} := \sum _{k=0}^{\infty }\frac{1}{k!}t^k \mathbf{Q}^k \]

Примеры генераторов:

\[ \begin{pmatrix} -1 & 1 \\ 3 & -3 \end{pmatrix}, \qquad \begin{pmatrix} -5 & 4 & 1 \\ 2 & -10 & 8 \\ 3 & 3 & -6 \end{pmatrix}, \qquad \begin{pmatrix} -14& 7 & 5 & 2\\ 0 & 0 & 0 & 0 \\ 3 & 7 & -10 & 0 \\ 1 & 1 & 1 & -3 \end{pmatrix} \tag{1}\]

Рассмотрим, например, 3-й генератор. МЦНВ с этим генератором (вернее, одна из ее возможных модификаций с cadlag траекториями) ведет себя так:

• Если цепь оказалась в состоянии \(i\), то она сидит в этом состоянии случайное время, распределенное как \(\operatorname {Exp}(-\mathbf{Q}_{ii})\). Например, если она в состоянии \(1\), она будет ждать время \(\operatorname {Exp}(14)\).

• Когда время ожидания в состоянии \(i\) заканчивается, цепи нужно перескочить в новое состояние. Новое состояние \(j\) она выбирает случайно, независимо от предыдущего поведения, причем перескакивает в какое-то состояние с вероятностью, пропорциональной \(\mathbf{Q}_{ij}\). Например, если цепь была в состоянии \(i=1\), то она из него скакнет в состояние \(2\) c вероятностью \(\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\).

1. Покажите, что \(N_t\) – МЦНВ, найдите его стох. полугруппу;

2. Покажите, что стохастическая полугруппа стандартна;

3. Найдите генератор Пуассоновского процесса.

SolutionРешение

Enum-item(1)

Докажем марковость. Рассмотрим целые числа \(0 \leq a_1 \leq \dots \leq a_n \leq i \leq j\) (только такие имеет смысл рассматривать). Тогда из-за независимости приращений имеем

\[ \begin{align} \mathbb {P}\left(N_t = j \; \left| \; \begin{array}{rl} N_s & = i \\ N_{s_n} & = a_n \\ \cdots & \cdots \\ N_{s_1} & = a_1 \end{array}\right.\right) & = \mathbb {P}\left(N_t - N_s = j - i \; \left| \; \begin{array}{rl} N_s & = i \\ N_{s_n} & = a_n \\ \cdots & \cdots \\ N_{s_1} & = a_1 \end{array}\right.\right) = \\ & = \frac{(\lambda (t-s))^{j-i}}{(j-i)!}e^{-\lambda (t-s)} \\ \mathbb {P}\left(N_t = j \mid N_s = i\right) & = \mathbb {P}\left(N_t - N_s = j - i \mid N_s = i\right) = \frac{(\lambda (t-s))^{j-i}}{(j-i)!}e^{-\lambda (t-s)} \end{align} \]

Цепь однородная, т.к. переходные вероятности зависят только от разности \(t-s\).

Enum-item(2)

Матрица переходных вероятностей:

\[ \begin{align} \mathbf{P}_t & = \begin{pmatrix} e^{-\lambda t} & \lambda t e^{-\lambda t} & \frac{(\lambda t)^2}{2!}e^{-\lambda t} & \frac{(\lambda t)^3}{3!}e^{-\lambda t} & \frac{(\lambda t)^4}{4!}e^{-\lambda t} & \frac{(\lambda t)^5}{5!}e^{-\lambda t} & \dots \\ 0 & e^{-\lambda t} & \lambda t e^{-\lambda t} & \frac{(\lambda t)^2}{2!}e^{-\lambda t} & \frac{(\lambda t)^3}{3!}e^{-\lambda t} & \frac{(\lambda t)^4}{4!}e^{-\lambda t} & \dots \\ 0 & 0 & e^{-\lambda t} & \lambda t e^{-\lambda t} & \frac{(\lambda t)^2}{2!}e^{-\lambda t} & \frac{(\lambda t)^3}{3!}e^{-\lambda t} & \dots \\ 0 & 0 & 0 & e^{-\lambda t} & \lambda t e^{-\lambda t} & \frac{(\lambda t)^2}{2!}e^{-\lambda t} & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \ddots \\ \end{pmatrix}\\ & = e^{-\lambda t}\begin{pmatrix} 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \frac{(\lambda t)^4}{4!} & \frac{(\lambda t)^5}{5!} & \dots \\ 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \frac{(\lambda t)^4}{4!} & \dots \\ 0 & 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \dots \\ 0 & 0 & 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \ddots \\ \end{pmatrix} \end{align} \]

Проверим стандартность, т.е. поэлементную сходимость \(\mathbf{P}_t \to \mathbf{E}\) при \(t \to 0+\). Диагональные элементы: \(e^{-\lambda t} \to 1\). Внедиагональные (при \(j > i\)): \(\frac{(\lambda t)^{j - i}}{(j-i)!}e^{-\lambda t} \to 0\). Итого \(\left(\mathbf{P}_t\right)_{ij} \to \delta_i^j\), полугруппа стандартна.

Enum-item(3)

Инфинитезимальная матрица:

\[ \begin{align} \mathbf{P}_t' & = -\lambda e^{-\lambda t}\begin{pmatrix} 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \frac{(\lambda t)^4}{4!} & \frac{(\lambda t)^5}{5!} & \dots \\ 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \frac{(\lambda t)^4}{4!} & \dots \\ 0 & 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \frac{(\lambda t)^3}{3!} & \dots \\ 0 & 0 & 0 & 1 & \lambda t & \frac{(\lambda t)^2}{2!} & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \ddots \\ \end{pmatrix} + \\ & \qquad + e^{-\lambda t}\begin{pmatrix} 0 & \lambda & \lambda ^2 t & \frac{\lambda ^3 t^2}{2!} & \frac{\lambda ^4 t^3}{3!} & \frac{\lambda ^5 t^4}{4!} & \dots \\ 0 & 0 & \lambda & \lambda ^2 t & \frac{\lambda ^3 t^2}{2!} & \frac{\lambda ^4 t^3}{3!} & \dots \\ 0 & 0 & 0 & \lambda & \lambda ^2 t & \frac{\lambda ^3 t^2}{2!} & \dots \\ 0 & 0 & 0 & 0 & \lambda & \lambda ^2 t & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \ddots \\ \end{pmatrix} \\ \mathbf{Q} & = \mathbf{P}_t'\vert _{t=0} = \begin{pmatrix} -\lambda & \lambda & 0 & 0 & 0 & 0 & \dots \\ 0 & -\lambda & \lambda & 0 & 0 & 0 & \dots \\ 0 & 0 & -\lambda & \lambda & 0 & 0 & \dots \\ 0 & 0 & 0 & -\lambda & \lambda & 0 & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots & \ddots & \ddots \\ \end{pmatrix} \end{align} \]

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

1. все диагональные элементы из \([-\infty , 0]\);

2. все внедиагональные элементы из \([0,+\infty )\);

3. \(\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}\) имеем

\[ \begin{align} \sum _{j=1}^{\left|\mathcal{X}\right|} \mathbf{Q}_{ij} & = \\ & \quad \sum _{j=1}^{\left|\mathcal{X}\right|} \lim _{t \to 0+} \frac{\left(\mathbf{P}_t\right)_{ij} - \left(\mathbf{P}_0\right)_{ij}}{t} = \\ & = \lim _{t \to 0+} \sum _{j=1}^{\left|\mathcal{X}\right|} \frac{\left(\mathbf{P}_t\right)_{ij} - \left(\mathbf{P}_0\right)_{ij}}{t} = \\ & = \lim _{t \to 0+} \frac{1 - 1}{t} = 0 \end{align} \]

Известно (см. лемму Лемма 2), что вне диагонали у матрицы \(\mathbf{Q}\) элементы неотрицательные и конечные. Значит на диагонали стоит тоже конечное число.

Лемма 3 (Консервативность генератора МЦНВ с конечным числом состояний) Если \(\mathcal{X}\) конечно, то

• все элементы \(\mathbf{Q}\) конечны;

• сумма любой строки равна \(0\). Иначе говоря, вне диагонали стоят неотрицательные числа, и

  \[ -\mathbf{Q}_{ii} = \sum _{\substack {j \in \mathcal{X}\\ j \neq i}}\mathbf{Q}_{ij} \in [0, +\infty ) \]

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}\) выполнено

\[ \frac{d}{dt} \left(\mathbf{P}_t\right)_{ij} = \left(\mathbf{Q} \cdot \mathbf{P}_t\right)_{ij} = \left(\mathbf{P}_t \cdot \mathbf{Q}\right)_{ij} \]

для любого \(t \geq 0\).

Прямые и обратные уравнения – это система из дифференциальных уравнений. Они так называются, исходя из положения генератора. В прямых уравнениях генератор стоит <<сзади>> (справа): \(\mathbf{P}_t \cdot \mathbf{Q}\). В обратных, соотв., <<спереди>> (слева): \(\mathbf{Q} \cdot \mathbf{P}_t\).

Уравнения Колмогорова позволяют вывести уравнения и для распределения цепи \(\Pi^{(t)}\) в произвольный момент времени \(t \geq 0\) (напомним, что мы понимаем \(\Pi^{(t)}\) как вектор-строку).

Лемма 4 Выполнено \[ \left(\Pi ^{(t)}\right)' = \Pi ^{(t)} \cdot \mathbf{Q} \]

ProblemЗадача 3

1. Докажите обе системы дифференциальных уравнений Колмогорова.

2. Докажите формулу \(\left(\Pi^{(t)}\right)' = \Pi^{(t)} \cdot \mathbf{Q}\).

Теорема 4 (Восстановление \(\mathbf{P}_t\) по генератору \(\mathbf{Q}\)) Пусть \(\mathbf{Q}\) – это (консервативная) \(Q\)-матрица. Семейство матриц \[ \mathbf{P}_t := e^{\mathbf{Q}t} = \sum _{k=0}^{\infty }\frac{1}{k!}\mathbf{Q}^k t^k, \qquad t \geq 0 \] удовлетворяет следующим условиям:

• \((\mathbf{P}_t, t \geq 0)\) – это стох. полугруппа;

• \((\mathbf{P}_t, t \geq 0)\) – это единственное решение прямых и обратных уравнений Колмогорова с начальным условием \(\mathbf{P}_0 = \mathbf{E}\);

• \(\frac{d^n}{dt^n}\mathbf{P}_t = \mathbf{P}_t \cdot \mathbf{Q}^n = \mathbf{Q}^n \cdot \mathbf{P}_t\).

ExampleПример 3

Рассмотрим общую \(Q\)-матрицу размерности \(2 \times 2\): \[ \mathbf{Q} = \left(\begin{array}{cc} -\alpha & \alpha \\ \beta & -\beta \end{array}\right), \quad \alpha , \beta \geqslant 0 . \] Граф интенсивностей:

Граф интенсивностей двухсостоятельной цепи с непрерывным временем: переход \(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}\) являются корнями уравнения

\[ \operatorname {det}\left(\begin{array}{cc} -\lambda -\alpha & \alpha \\ \beta & -\lambda -\beta \end{array}\right)=(\lambda +\alpha )(\lambda +\beta )-\alpha \beta =\lambda (\alpha +\beta +\lambda )=0, \]

т.е.

\[ \lambda _1=0, \quad \lambda _2=-(\alpha +\beta ) . \]

С.зн. разные, значит матрицу можно привести к диагональному виду, а именно \(\mathbf{Q} =\mathbf{U} \mathbf{D} \mathbf{U}^{-1}\), где

\[ \mathbf{D} = \begin{pmatrix} 0 & 0 \\ 0 & -\alpha - \beta \end{pmatrix} \]

Таким образом,

\[ \begin{align} \mathbf{P}_t & = \sum _{k=0}^{\infty } \frac{t^k}{k!} \mathbf{Q}^k = \\ & = \sum _{k=0}^{\infty } \frac{t^k}{k!} \mathbf{U} \mathbf{D}^k \mathbf{U}^{-1} = \\ & = \mathbf{U} \sum _{k=0}^{\infty } \frac{t^k}{k!} \mathbf{D}^k \mathbf{U}^{-1} = \mathbf{U} e^{t \mathbf{D}}\mathbf{U}^{-1} = \\ & =\mathbf{U}\left(\begin{array}{cc} 1 & 0 \\ 0 & e^{-t(\alpha +\beta )} \end{array}\right) \mathbf{U}^{-1} . \end{align} \]

Значит все элементы матрицы \(\mathbf{P}_t\) имеют вид

\[ \left(\mathbf{P}_t\right)_{ij} = A_{ij}+B_{ij} e^{-t(\alpha +\beta )}, \]

причем

\[ \left(\mathbf{P}_0\right)_{ij}=A_{ij}+B_{ij}=\delta _{i j} \]

и

\[ \left.\left(\mathbf{P}_t\right)_{ij}'\right|_{t=0}=-(\alpha +\beta ) B_{ij} = \mathbf{Q}_{ij}. \]

Например, для верхнего левого элемента

\[ A_{11}+B_{11}=1, \quad -(\alpha +\beta ) B_{11}=-\alpha \]

значит

\[ A_{11}=\frac{\beta }{\alpha +\beta }, \quad B_{11}=\frac{\alpha }{\alpha +\beta } . \]

Поэтому матрица \(\mathbf{P}_t\) равна

\[ \mathbf{P}_{t}=\left(\begin{array}{cc} \frac{\beta }{\alpha +\beta }+\frac{\alpha }{\alpha +\beta } e^{-(\alpha +\beta ) t} & \frac{\alpha }{\alpha +\beta }-\frac{\alpha }{\alpha +\beta } e^{-(\alpha +\beta ) t} \\ \frac{\beta }{\alpha +\beta }-\frac{\beta }{\alpha +\beta } e^{-(\alpha +\beta ) t} & \frac{\alpha }{\alpha +\beta }+\frac{\beta }{\alpha +\beta } e^{-(\alpha +\beta ) t} \end{array}\right) ; \]

при \(t \rightarrow \infty\) имеет место поэлементная сходимость к матрице

\[ \left(\begin{array}{cc} \frac{\beta }{\alpha +\beta } & \frac{\alpha }{\alpha +\beta } \\ \frac{\beta }{\alpha +\beta } & \frac{\alpha }{\alpha +\beta } \end{array}\right) . \]

ProblemЗадача 4

Рассмотрим \(Q\)-матрицу размерности \(3 \times 3\) вида \[ \mathbf{Q} = \left(\begin{array}{ccc} -1 & 1 / 2 & 1 / 2 \\ 3 & -6 & 3 \\ 0 & 4 & -4 \end{array}\right) \] Граф интенсивностей (обратите внимание: ребра \(3 \to 1\) нет, т.к. \(\mathbf{Q}_{31} = 0\)):

Граф интенсивностей МЦНВ с генератором \(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\) независимы.

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

Лемма 6 (О сумме независимых экспонент) Пусть \(\xi_1, \xi_2, \ldots\) – независимые, \(\xi_n \sim \operatorname {Exp}(\lambda_n)\). Тогда

• если \(\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}\) из матожиданий.

Пусть \(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]\). По независимости и монотонной (мажорируемой) сходимости

  \[ \begin{align} \mathbb {E}\left[e^{-S}\right] & = \prod _{n=1}^{\infty } \mathbb {E}\left[e^{-\xi _n}\right] = \\ & = \prod _{n=1}^{\infty } \frac{\lambda _n}{1 + \lambda _n} = \prod _{n=1}^{\infty } \left(1 + \frac{1}{\lambda _n}\right)^{-1} \end{align} \]

  Расходимость \(\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\) п.н.

Подробнее об этих свойствах: (Norris 1997 г., разд. 2.3).

Еще один красивый факт из той же серии – про пуассоновский процесс (который, как мы видели, целиком построен из экспоненциальных интервалов).

Лемма 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\), ни от экспоненциальности как таковой – скачки <<равномерно разбросаны>> по отрезку.

Доказательство см. в (Norris 1997 г., Theorem 2.4.6).

2.4 Конструкция <<прыжок–ожидание>>: построение cadlag версии МЦНВ

Вернемся к неформальному описанию поведения цепи, данному после примеров генераторов (см. Уравнение 1), и сформулируем его аккуратно. Интуиция: марковское свойство влечёт, что

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

2. следующее посещаемое состояние (будущее) не зависит от предыдущих посещённых состояний (прошлое) \(\; \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})\), следующее состояние выбирается с вероятностями

  \[ \mathbb {P}_{i}\left(X_{H} = j\right) = \frac{\mathbf{Q}_{ij}}{-\mathbf{Q}_{ii}}, \qquad j \neq i, \]

  причем \(H\) и \(X_{H}\) независимы.

Доказательство см. в (Norris 1997 г., Theorem 2.8.2).

Верно и обратное: по консервативной \(Q\)-матрице цепь можно построить по следующему алгоритму (он же – рецепт симуляции МЦНВ на компьютере):

1. построить встроенную МЦДВ \((\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\));

2. взять независимые (и независимые от \(\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\);

3. положить \(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\), и т.д.

Альтернативный взгляд на тот же механизм – <<гонка часов>>. Находясь в состоянии \(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\), что

\[ \left(\mathbf{P}_{t_1}\right)_{i,j} > 0, \qquad \left(\mathbf{P}_{t_2}\right)_{j,i} > 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\) называют возвратным, если

\[ \mathbb {P}_{i}\left(T_{i} < \infty \right) = 1 \]

В противном случае состояние называют транзитным или невозвратным¹.

Отличие от дискретного времени: в случае непрерывного времени нет понятия периода состояния.

Пусть \(J_{0} := 0\),

\[ J_{n} := \min \left\{ t > J_{n - 1} \; : \; X_{t-} \neq X_{t}\right\} \]

– это время \(n\)-го прыжка (от англ. jump) цепи. Пусть

\[ \tilde{X}_{n} := X_{J_{n}} \]

Лемма 8 Процесс \((\tilde{X}_{n}, n \geq 0)\)

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

• имеет то же начальное распределение, что и у \(X_{t}\),

• имеет матрицу переходных вероятностей \[ \tilde{\mathbf{P}} = \begin{pmatrix} 0 & \frac{\mathbf{Q}_{12}}{-\mathbf{Q}_{11}} & \frac{\mathbf{Q}_{13}}{-\mathbf{Q}_{11}} & \cdots & \frac{\mathbf{Q}_{1n}}{-\mathbf{Q}_{11}} \\ \frac{\mathbf{Q}_{21}}{-\mathbf{Q}_{22}} & 0 & \frac{\mathbf{Q}_{23}}{-\mathbf{Q}_{22}} & \cdots & \frac{\mathbf{Q}_{2n}}{-\mathbf{Q}_{22}} \\ \frac{\mathbf{Q}_{31}}{-\mathbf{Q}_{33}} & \frac{\mathbf{Q}_{32}}{-\mathbf{Q}_{33}} & 0 & \cdots & \frac{\mathbf{Q}_{3n}}{-\mathbf{Q}_{33}} \\ \vdots & \vdots & \cdots & \ddots & \vdots \\ \frac{\mathbf{Q}_{\left|\mathcal{X}\right|,1}}{-\mathbf{Q}_{\left|\mathcal{X}\right|,\left|\mathcal{X}\right|}} & \frac{\mathbf{Q}_{\left|\mathcal{X}\right|,2}}{-\mathbf{Q}_{\left|\mathcal{X}\right|,\left|\mathcal{X}\right|}} & \cdots & \frac{\mathbf{Q}_{\left|\mathcal{X}\right|,\left|\mathcal{X}\right|-1}}{-\mathbf{Q}_{\left|\mathcal{X}\right|,\left|\mathcal{X}\right|}} & 0 \end{pmatrix}, \] если для всех состояний \(\mathbf{Q}_{ii} \neq 0\). Если для какого-то состояния \(i\) все таки \(\mathbf{Q}_{ii} = 0\), то \(i\) – это поглощающее состояние как для самой \(X_t\), так и для \(\tilde{X}_{n}\), т.е. \(i\)-я строка матрицы \(\tilde{\mathbf{P}}\) – это \(i\)-й базисный вектор:

  \[ \left(\tilde{\mathbf{P}}\right)_{ij} = \delta _{ij} \]

МЦДВ \(\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)\), если

\[ \Pi \cdot \mathbf{P}_{t} = \Pi , \qquad \forall \; t \geq 0 \]

Лемма 10 Пусть \(\Pi\) – некоторое распределение на \(\mathcal{X}\). Тогда \[ \Pi \text{ -- стационарное распределение} \quad \iff \quad \Pi \cdot \mathbf{Q} = \mathbf{0} \] Иначе говоря, распределение является стационарным тогда и только тогда, когда распределение – это левый собственный вектор (строка) матрицы \(\mathbf{Q}\) с собственным значением \(0\).

ExampleПример 4

Докажите предыдущую лемму.

SolutionРешение

• \(\stackrel{?}{\; \Rightarrow \; }\). Воспользуемся прямыми уравнениями Колмогорова:

  \[ \Pi \cdot \mathbf{Q} = \Pi \cdot \mathbf{P}'_t = \left(\Pi \cdot \mathbf{P}_t\right)' = \Pi ' = \mathbf{0} \]

  (везде имеется в виду поэлементное взятие производной)

• \(\stackrel{?}{\Leftarrow }\). Воспользуемся обратными уравнениями Колмогорова:

  \[ \left(\Pi \cdot \mathbf{P}_t\right)' = \Pi \cdot \mathbf{P}'_t = \underbrace{\Pi \cdot \mathbf{Q}}_{=\mathbf{0}} \cdot \mathbf{P}_t = \mathbf{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\);

• \(\Pi^{\operatorname {erg}}_{i} = \frac{1}{-\mathbf{Q}_{ii}} \cdot \frac{1}{\mathbb {E}_{i}\left[T_i\right]} > 0\);

• \[ \mathbf{P}_{t} \quad \xrightarrow [t \to +\infty ]{} \quad \begin{pmatrix} \Pi ^{\operatorname {erg}} \\ \Pi ^{\operatorname {erg}} \\ \vdots \\ \Pi ^{\operatorname {erg}} \end{pmatrix} = \begin{pmatrix} \frac{1}{-\mathbf{Q}_{11}}\frac{1}{\mathbb {E}_{1}\left[T_1\right]} & \frac{1}{-\mathbf{Q}_{22}}\frac{1}{\mathbb {E}_{2}\left[T_2\right]} & \cdots & \frac{1}{-\mathbf{Q}_{nn}}\frac{1}{\mathbb {E}_{n}\left[T_n\right]} \\ \frac{1}{-\mathbf{Q}_{11}}\frac{1}{\mathbb {E}_{1}\left[T_1\right]} & \frac{1}{-\mathbf{Q}_{22}}\frac{1}{\mathbb {E}_{2}\left[T_2\right]} & \cdots & \frac{1}{-\mathbf{Q}_{nn}}\frac{1}{\mathbb {E}_{n}\left[T_n\right]} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{1}{-\mathbf{Q}_{11}}\frac{1}{\mathbb {E}_{1}\left[T_1\right]} & \frac{1}{-\mathbf{Q}_{22}}\frac{1}{\mathbb {E}_{2}\left[T_2\right]} & \cdots & \frac{1}{-\mathbf{Q}_{nn}}\frac{1}{\mathbb {E}_{n}\left[T_n\right]} \end{pmatrix} \]

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

1. Апериодичность не определена в непрерывном времени/не требуется для эргодической теоремы;

2. \(\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}\): цепь «забывает» начальное распределение.

\(\alpha\) = 1.0 \(\beta\) = 2.0 \(\Pi_1^{(0)}\) = 0.75

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

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

2. Найдите стационарные распределения для встроенной цепи \(\tilde{X}_n\). Является ли она эргодической? Если да – найдите эргодическое распределение.

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

4. Найдите предел \(\mathbf{P}_t\) при \(t \to +\infty\).

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

6. Найдите среднее время возврата \(\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}\) могут неограниченно расти вдоль траектории, времена ожидания – убывать так быстро, что их сумма сходится:

\[ \zeta := \sup _n J_n = \sum _{n=1}^{\infty } W_n < \infty \]

Событие \(\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\)) для сравнения: он растёт экспоненциально быстро, но никогда не взрывается. Кнопка перегенерирует обе траектории заново.

\(\alpha\) = 2.00

Что происходит с цепью после взрыва? Формула \(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}\). Цепь не взрывается, если выполнено хотя бы одно из условий:

1. \(\mathcal{X}\) конечно;

2. интенсивности выхода ограничены: \(\sup_{i \in \mathcal{X}}\left(-\mathbf{Q}_{ii}\right) < \infty\);

3. цепь стартует из состояния \(i\), возвратного для встроенной цепи \(\tilde{X}_n\).

Доказательство см. в (Norris 1997 г., Theorem 2.7.1).

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\), причем

  \[ \begin{align} \Pi _j & = \frac{1}{-\mathbf{Q}_{jj}} \cdot \frac{1}{\mathbb {E}_{j}\left[T_j\right]} > 0, \qquad \\ & \quad \left(\mathbf{P}_t\right)_{ij} \xrightarrow [t \to +\infty ]{} \Pi _j \quad \forall i, j \in \mathcal{X} \end{align} \]

  Кроме того, доля времени, проведенного в состоянии \(j\), п.н. сходится к \(\Pi_j\):

  \[ \frac{1}{t}\int _0^{t} \; \mathbb {1}_{X_s = j} \, ds \quad \xrightarrow [t \to +\infty ]{\text{п.н.}} \quad \Pi _j \]

• Нуль-возвратный или транзитный случай: стационарного распределения не существует, и

  \[ \left(\mathbf{P}_t\right)_{ij} \xrightarrow [t \to +\infty ]{} 0 \qquad \forall i, j \in \mathcal{X} \]

Доказательство см. в (Norris 1997 г., разд. 3.8).

Осторожно: хотя возвратность/транзитность у МЦНВ и ее встроенной цепи совпадают, положительная возвратность – нет! Цепь \(X_t\) может быть положительно-возвратной при нуль-возвратной встроенной цепи, и наоборот: сравните стационарные распределения \(\Pi_i \propto \tilde{\Pi }_i / (-\mathbf{Q}_{ii})\) – <<перевзвешивание>> временами пребывания может превратить суммируемое распределение в несуммируемую меру и наоборот.

3.3 Процессы рождения и гибели

Процессом рождения и гибели (англ. birth-death process) называют МЦНВ на \(\mathcal{X} = \mathbb {Z}_+\), у которой возможны переходы только в соседние состояния:

\[ \mathbf{Q}_{n, n+1} = \lambda _n \; (n \geq 0), \qquad \mathbf{Q}_{n, n-1} = \mu _n \; (n \geq 1), \qquad \mathbf{Q}_{nn} = -(\lambda _n + \mu _n), \]

где \(\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\) уравновешен.

Введем <<поток через ребро>> \(F_n := \Pi_n \lambda_n - \Pi_{n+1}\mu_{n+1}\), \(n \geq 0\). Распишем \(j\)-ю компоненту уравнения \(\Pi \mathbf{Q} = \mathbf{0}\) (в столбце \(j\) у \(\mathbf{Q}\) ненулевые элементы стоят в строках \(j-1\), \(j\), \(j+1\)): \[ \begin{align} j = 0& : \quad -\lambda _0 \Pi _0 + \mu _1 \Pi _1 = 0 \quad \iff \quad F_0 = 0 \\ j \geq 1& : \quad \lambda _{j-1}\Pi _{j-1} - (\lambda _j + \mu _j)\Pi _j + \mu _{j+1}\Pi _{j+1} = 0 \quad \iff \quad F_{j-1} = F_{j} \end{align} \] Итого стационарность равносильна цепочке \(0 = F_0 = F_1 = F_2 = \ldots\), т.е. детальному балансу.

Следствие 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 _n = \Pi _0 \cdot \prod _{k=1}^{n}\frac{\lambda }{\mu } = \Pi _0 \, \rho ^n, \qquad Z = \sum _{n=0}^{\infty }\rho ^n \]

При \(\rho < 1\) ряд сходится: \(Z = \frac{1}{1-\rho }\), и

\[ \Pi _n = (1 - \rho )\, \rho ^n, \qquad n \geq 0 \]

– геометрическое распределение. В частности, в стационарном режиме сервер простаивает долю времени \(\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 стационарного распределения нет — сравнение с геометрическим распределением не определено.

\(\rho\) = 0.80

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 г. Теория случайных процессов. Физматлит.

Сноски

1. Как и в случае цепей с дискретным временем, все возвратные состояния цепи с непрерывным временем и с конечным числом состояний являются положительно-возвратными.