Глава 3. Моменты и вероятности достижения

\[\newcommand{\st}{\, : \:} \newcommand{\ind}[1]{\mathbf{1}_{#1}} \newcommand{\dd}{\mathrm{d}}\]

Определения

Определение 1 (Момент первого достижения) Пусть $\mathbf{X}=(X_t)_{t\in \mathbb{N}}$ — однородная во времени цепь Маркова на пространстве состояний $S$. Для любого подмножества $A \subseteq S$, момент первого достижения (или момент первого прохода) множества $A$ — это случайная величина $\tau_A \colon \Omega \to \mathbb{N} \cup \{\infty\}$, определённая как \[ \tau_A := \inf \{ t \ge 0 \st X_t \in A \} \] где $\inf \emptyset = \infty$. Если $A = \{x\}$ для единственного состояния $x$, мы часто пишем $\tau_x$ вместо $\tau_{\{x\}}$.

Определение 2 (Вероятность достижения) Для $A \subset S$ и $x \in S$, вероятность достижения $A$ из $x$ определяется как \[ h_A(x) := \mathbb{P}_x(\tau_A < \infty) \] Это вероятность того, что цепь Маркова, стартуя из состояния $x$, когда-либо посетит какое-либо состояние из множества $A$.

Основные результаты

Теорема 1 Вероятность достижения $h_A(x) = \mathbb{P}_x(\tau_A < \infty)$ удовлетворяет следующей системе уравнений относительно неизвестной $h$ \[ \begin{cases} h(x)=1 & \text{если $ x\in A $} \\ ((I-P)h)(x)=0 & \text{если $x\in A^c$} \end{cases} \tag{1}\]

Более того, $h_A(x)$ является наименьшим неотрицательным решением этих уравнений. А именно, если $g\ge 0$ решает систему Уравнение 1, то $g\ge h_A$.

Наконец, $h_A$ — это единственное решение $g\ge 0$ системы Уравнение 1, такое что \[ \lim_{n\to \infty} \mathbb{E}_x[g(X_n) \ind{\tau_A > n}] = 0 \]

Доказательство. Мы будем действовать пошагово.

(Граничное условие) Если $x\in A$, то $\tau_A=0$ $\mathbb{P}_x$-п.н., и следовательно $h_A(x)=1$.
(Гармоничность) Так как $x\in A^c$, имеем $\{\tau_A<\infty\}=\{ \exists t\ge 0 \st X_t\in A\}= \{ \exists t\ge 1 \st X_t\in A\}$ с $\mathbb{P}_x$-вероятностью $1$. Таким образом, обуславливая по первому шагу цепи и используя Марковское свойство для функции $\ind{\{\tau_A<\infty\}}$ \[ \begin{aligned} h_A(x) &= \mathbb{P}_x(\tau_A < \infty) = \sum_{y \in S} \mathbb{P}_x(\tau_A < \infty \mid X_1 = y) \mathbb{P}_x(X_1 = y) \\ & = \sum_{y \in S} \mathbb{P}_y(\tau_A < \infty) p_{x,y} = \sum_{y \in S} p_{x,y} h_A(y) \end{aligned} \]
(Минимальность) Пусть $g \colon S \to [0, \infty)$ — любая неотрицательная функция, удовлетворяющая Уравнение 1. Докажем по индукции, что \[ g(x)=\mathbb{P}_x(\tau_A \le n) + \mathbb{E}_x[g(X_n) \ind{\tau_A > n}] \tag{2}\]
- Возьмём $n=1$. Если $x\in A$, то утверждение сводится к $1=1+0$. Если $x\not \in A$, то из Уравнение 1 \[ g(x) = \mathbb{E}_x[g(X_1)]= \mathbb{E}_x[\ind{A}(X_1)]+ \mathbb{E}_x[g(X_1)\ind{A^c}(X_1)] = \mathbb{E}_x[\ind{A^c}(X_0) \ind{A}(X_1)]+ \mathbb{E}_x[g(X_1) \ind{A^c}(X_0) \ind{A^c}(X_1)] \] что эквивалентно утверждению по определению $\tau_A$.
- Предположим, что утверждение верно для данного $n$. Поскольку $\{\tau_A > n\} \subset \{X_n \not \in A\}$, $g(X_n)= \mathbb{E}_{X_n}[g(X_1)]$, и рассуждая так же, как в случае $n=1$ \[ \begin{aligned} \mathbb{E}_x[g(X_n) \ind{\tau_A > n}] & = \mathbb{E}_x[\mathbb{E}_{X_n}[g(X_1)] \ind{\tau_A > n}] = \mathbb{E}_x[g(X_{n+1}) \ind{\tau_A > n}] \\ & = \mathbb{E}_x[\ind{X_{n+1}\in A} \ind{\tau_A > n}] + \mathbb{E}_x[g(X_{n+1}) \ind{X_{n+1}\not \in A} \ind{\tau_A > n}] = \mathbb{E}_x[\ind{\tau_A = n+1}] + \mathbb{E}_x[g(X_{n+1})\ind{\tau_A > n+1}] \end{aligned} \] Из индуктивного предположения и последнего равенства \[ g(x)= \mathbb{P}_x(\tau_A \le n) + \mathbb{E}_x[\ind{\tau_A = n+1}] + \mathbb{E}_x[g(X_{n+1})\ind{\tau_A > n+1}] = \mathbb{P}_x(\tau_A \le n+1 )+ \mathbb{E}_x[g(X_{n+1})\ind{\tau_A > n+1}] \] Уравнение 2, таким образом, установлено. По теореме о монотонной сходимости, $\lim_n \mathbb{P}_x(\tau_A \le n)= \mathbb{P}_x(\tau_A<\infty )=h_A(x)$. Следовательно \[ g(x)= h_A(x)+ \lim_n \mathbb{E}_x[g(X_n) \ind{\tau_A > n}] \ge h_A(x) \]
(Единственность) Из последнего уравнения мы видим, что предел в этом уравнении обращается в ноль тогда и только тогда, когда $g=h_A$.

Примеры

Пример 1

Линейная система, решением которой является вероятность достижения, не имеет единственного решения — Рисунок 1

На этом графе стрелки обозначают строго положительные вероятности перехода. Рассмотрим $h_{b}(x)$ — вероятность достижения $b$ при старте из $x$. На $\{a,b,c\}$ функция $h_{b}(x)$ однозначно определяется линейной системой Уравнение 1. С другой стороны, на $\{d,e,f,g\}$ (которое не связано с $b$), $h_{b}(x)=0$; однако $h(x)=c$ для $x\in \{d,e,f,g\}$ решает гармоническое уравнение Уравнение 1 для любой константы $c$. Мы действительно видим, что $h_b$ является наименьшим неотрицательным решением системы Уравнение 1.

Упражнение 1 Пусть $A,B \subset S$, причём $A \cap B=\emptyset$. Найдите уравнение, аналогичное Уравнение 1, которому удовлетворяет \[ h_{A,B}(x):= \mathbb{P}_x(\tau_A < \tau_B, \tau_{A\cup B}<\infty) \] используя два разных метода

Обуславливание по первому шагу, как в доказательстве Теорема 1.
Рассмотрение модифицированной цепи Маркова с вероятностями перехода \[ q_{x,y}:= \begin{cases} p_{x,y} & \text{если $x\not \in B $} \\ \ind{x}(y) & \text{если $x\in B$} \end{cases} \]

Упражнение 2 Мы хотим дать аналитическую характеризацию вероятностей перехода $q_{x,y}$ следа возвратной цепи Маркова. Мы доказали, что след $\mathbf{X}$ на $A$ имеет вероятности перехода, для $x,y\in A$ \[ q_{x,y}=\mathbb{P}_x(X_{\tau^+_A}=y) \] Определим оператор $P^{(A^c)}$ с элементами \[ p^{(A^c)}_{x,y}= \begin{cases} p_{x,y} & \text{если $y\in A^c$} \\ 0 & \text{если $y\in A$} \end{cases} \] Докажите, что для каждого фиксированного $y\in A$, $q_{x,y}$ является наименьшим решением задачи относительно неизвестной $h \ge 0$ \[ ((I-P^{(A^c)}) h)(x) = p_{x,y}, \qquad x\in S \tag{3}\] то есть $q_{x,y} - \sum_{z \in A^c} p_{x,z} q_{z,y} = p_{x,y}$ для всех $x\in S$.

Решение

Зафиксируем $y \in A$, и обозначим $h(x) \equiv q_{x,y}= \mathbb{P}_x(X_{\tau_A^+} = y)$ для $x\in S$. Обуславливая по первому шагу: \[ h(x) = \sum_{z \in S} p_{x,z} \mathbb{P}_x(X_{\tau_A^+}=y | X_1=z) = \sum_{z\in A} p_{x,z} \ind{y=z}+\sum_{z\in A^c} p_{x,z} h(z)= p_{x,y}+\sum_{z\in A^c} p_{x,z} h(z) \] Чтобы доказать минимальность, пусть теперь $g \ge 0$ — любое неотрицательное решение системы Уравнение 3 для фиксированного $y\in A$ (который мы опустим в обозначениях). Определим $h^{(n)}(x):= \mathbb{P}_x(X_{\tau_A^+} = y, \tau_A^+\le n)$. Тогда $h^{(n)}(x) \le q_{x,y}$, и в силу непрерывности вероятностей на монотонных последовательностях, $h^{(n)}(x) \uparrow h(x)$. Следовательно, достаточно проверить, что $g\ge h^{(n)}$ для всех $n\ge 0$. Теперь перейдём к индукции.

Тривиально $g\ge h^{(0)}\equiv 0$.
$h^{(n)}$ удовлетворяет (рассуждая так же, как для $q_{\cdot,y}$ выше) \[ h^{(n+1)}(x)=p_{x,y}+\sum_{z\in A^c} p_{x,z} h^{(n)}(z) \] Следовательно, по индуктивному предположению \[ g(x)= p_{x,y}+(P^{(A^c)}g)(x) \ge p_{x,y}+(P^{(A^c)}h^{(n)})(x) = h^{(n+1)}(x) \]

Упражнение 3 (Разорение игрока) Человек идёт в казино с начальным капиталом $x$ долларов. В каждой игре он выигрывает доллар с вероятностью $p$ и проигрывает доллар с вероятностью $1-p$. Его стратегия — не уходить, пока капитал не составит $N$ долларов, или пока он не разорится. Найдите вероятность того, что человек разорится в этой игре.

Упражнение 4 (Рождение и гибель) Мы наблюдаем за популяцией бактерий и отмечаем каждый раз, когда одна из них размножается (общая численность популяции увеличивается на $1$) или погибает (общая численность популяции уменьшается на $1$). Вероятность увеличения/уменьшения популяции зависит от размера популяции. Скажем, если популяция в данный момент составляет $n\ge 1$, вероятность того, что размножение произойдёт раньше гибели, равна $r_n$ (а гибель произойдёт раньше размножения с вероятностью $1-r_n$). Найдите вероятность того, что бактерии вымрут, как функцию от последовательности $(r_n)_{n\ge 1}$.

Упражнение 5 Вы идёте по пустыне без воды, но с $2000$ долларов. Вы находите волшебную лампу, и как только вы её берёте, появляется злой волшебный итальянский торговец, продающий бутилированную воду. Вы думаете, что спасены, но есть подвох. Одна бутылка стоит $10000$ долларов.

Итальянец предлагает вам следующую игру: вы можете поставить любую сумму денег $b$ на бросок шестигранной кости. Если выпадет 5 или 6 (то есть с вероятностью $p=1/3$), вы выигрываете $b$. В противном случае ваши деньги уменьшаются на $b$. Вы можете играть столько раундов, сколько захотите, пока у вас не кончатся деньги или вы не решите остановиться. Ваша цель — максимизировать вероятность покупки бутылки воды по предложенной дешёвой цене. Вычислите такую оптимальную вероятность.

Абстракция

Вероятности достижения

В контексте общих цепей Маркова мы можем определить марковский момент времени (stopping time) $\tau \colon \Omega \to \Theta$ как отображение, такое что $\{\tau \le t\}$ является $\mathcal{F}_t$-измеримым для всех $t\in \Theta$. Затем можно определить $\sigma$-алгебру событий, измеримых до момента $\tau$: \[ \mathcal{F}_{\tau}:= \left\{ A \in \mathcal{F} \st A \cap \{\tau \le t\} \in \mathcal{F}_t \text{ для всех } t \in \Theta \right\} \]

Если взять $\Theta=\mathbb{N}\cup \{\infty\}$ или $\Theta=[0,\infty]$, говорят, что выполняется строгое Марковское свойство, если \[ \mathbb{E}_\mu[F(\theta_\tau \mathbf{X})\mid X_\tau=x, \tau<\infty]= \mathbb{E}_x[F(\mathbf{X})] \] для всех ограниченных измеримых отображений $F\colon D(E)\to \mathbb{R}$ и для всех марковских моментов, таких что $\mathbb{P}_\mu(\tau<\infty)>0$. Заметьте, что в этой общей структуре требуются некоторые дополнительные предположения, чтобы гарантировать выполнение этого свойства; оно не является простым следствием Марковского свойства. Отсюда и название строгое Марковское свойство. В этом смысле мы доказали, что цепь Маркова с дискретным временем ($\Theta=\mathbb{N}$) на счётном пространстве состояний (или даже на польских пространствах с небольшими адаптациями) обладает строгим Марковским свойством.