Глава 2. Сильное марковское свойство
Далее мы всегда рассматриваем однородные по времени переходные вероятности \(p_{x,y}\) на конечном или счётном пространстве состояний \(S\) (хотя большинство идей обобщаются на довольно общее пространство состояний \(S\)). \(\mathbf{X}=(X_0,X_1,\ldots)\) обозначает цепь Маркова, а \(\mathbb{P}_\mu\) — вероятностную меру, когда \(\mathbf{X}\) начинается с распределения \(\mu\), \(X_0 \sim \mu\). \(\mathcal{B}(S)\) — это пространство ограниченных измеримых функций \(f\colon S\to \mathbb{R}\), а \(\mathcal{P}(S)\) — пространство вероятностных мер на \(S\).
Мы будем считать, что переходные вероятности \(p_{x,y}\) зафиксированы раз и навсегда. Тогда остаётся определённым пространство \(D(S)\) последовательностей \((x_i)\) из \(S\) таких, что \(p_{x_i,x_{i+1}}>0\) для всех \(i\ge 0\). Наконец, напомним, что \(P\) — это марковский оператор \(Pf(x):= \mathbb{E}_x[f(X_1)]\).
В этой главе мы стремимся формализовать некоторые интуитивные свойства цепи Маркова. Например, обусловливаясь на промежуточных моментах времени, мы имеем для \(f\in \mathcal{B}(S)\) \[ \mathbb{E}_x[f(X_t)]= (P^tf)(x) \] и для \(t\ge s\), независимо от \(\mu \in \mathcal{P}(S)\) \[ \mathbb{E}_\mu[f(X_t)\mid X_s=x]= (P^{t-s} f)(x) \] или, скажем, для \(f\in \mathcal{B}(S)\) \[ \mathbb{E}_\mu[f(X_t,X_{t+1})\mid X_s=x]= \mathbb{E}_{x}[f(X_{t-s},X_{t-s+1}) ] \]
В этой главе мы увидим, как правильно записать такого рода свойства и многие другие в общей структуре.
(Однородное) марковское свойство
Сначала введём оператор сдвига времени \(\theta_t\) для \(t\ge 0\) \[ \begin{aligned} & \theta_t \colon D(S) \to D(S) \\ & (\theta_t \mathbf{X})_{s}:=\mathbf{X}_{t+s} \end{aligned} \]
Утверждение 1 (Однородное марковское свойство) Пусть \(\mathbf{X}\) — однородная цепь Маркова. Тогда для \(s\ge 0\) и для всех ограниченных измеримых функций \(F\colon D(S)\to \mathbb{R}\) \[ \mathbb{E}_\mu[F(\theta_s \mathbf{X})\mid X_s=x]= \mathbb{E}_\mu[F(\theta_s \mathbf{X})\mid X_0=x_0, \ldots, X_{s-1}=x_{s-1}, X_s=x]= \mathbb{E}_x[F(\mathbf{X})] \] Другими словами, при условии \(X_t=x\), последовательность \((X_t,X_{t+1},\ldots)\) является цепью Маркова, начинающейся в \(x\), с теми же переходными вероятностями, что и \(\mathbf{X}\), и независимой от \((X_0,\ldots,X_{t-1})\).
Упражнение 1 Утверждение 1 может звучать абстрактно, но это довольно очевидное утверждение. Используйте предыдущий пример о случайном блуждающем, чтобы привести тривиальный пример этого утверждения. Возьмите переходные вероятности \(p_{x,y}\) однородными, и пусть \(f(x,y)\) — цена перелёта из города \(x\) в город \(y\). Пусть \(F(\mathbf{X})\) — стоимость, уплаченная за первые \(10\) перелётов. Что говорит это утверждение?
Доказательство (Утверждение 1). Без ограничения общности, чтобы сохранить явные обозначения, мы можем предположить, что \(F\) зависит от конечного числа координат \(F(\mathbf{X})= F(X_0,X_1,X_2,\ldots,X_t)\), поскольку измеримые функции на \(D(S)\) являются пределами таких функций. По линейности по \(F\) достаточно доказать равенство для индикаторных функций, а именно для \(F(X_0,X_1,X_2,\ldots,X_t)= \mathbf{1}_{z_0}(X_0) \mathbf{1}_{z_1}(X_1)\cdots \mathbf{1}_{z_t}(X_t)\) для некоторых \(z_0,\ldots,z_t\in S\). Тогда для такой \(F\) \[ \begin{aligned} \mathbb{E}_\mu[F(\theta_s \mathbf{X})\mid X_0=x_0, \ldots, X_{s-1}=x_{s-1}, X_s=x] & = \mathbb{P}_\mu(X_{s}=z_0,X_{s+1}=z_1,\ldots,X_{s+t}=z_t \mid X_0=x_0, \ldots, X_{s-1}=x_{s-1}, X_s=x ) \\ & = \mathbf{1}_{z_0}(x) \frac{ p_{x_0,x_1}\cdots p_{x_{s-1},x} p_{z_0,z_1}\cdots p_{z_{t-1},z_t}}{p_{x_0,x_1} \cdots p_{x_{s-1},x}}=\mathbf{1}_{z_0}(x) p_{z_0,z_1}\cdots p_{z_{t-1},z_t} =\mathbb{E}_x[F(\mathbf{X}) ] \end{aligned} \]
Моменты остановки
Определение 1 (Моменты остановки) Отображение \(\tau \colon \Omega \to \mathbb{N}\cup \{\infty\}\) называется моментом остановки, если для каждого \(t\ge 0\) событие \(\{\tau=t\}\) определяется по \((X_0,\ldots,X_t)\). То есть если \(\mathbf{1}_{\{\tau=t\}}\) является (измеримой) функцией от \((X_0,X_1,\ldots,X_t)\).
Примечание. Заметим, что, поскольку \(\{\tau =t\}= \{\tau\le t \} \setminus \{\tau \le t-1 \}\), эквивалентно сказать, что \(\tau\) является моментом остановки, если \(\{\tau \le t\}\) определяется по \((X_0,\ldots,X_t)\).
Например, для \(A\subset S\), момент достижения (более подробно обсуждаемый в следующей главе) множества \(A\) \[ \tau_A := \inf \{ t\ge 0 \st X_t \in A \} \] является моментом остановки: \(\{\tau_A=t\}=\{X_0 \not \in A,\ldots X_{t-1}\not \in A, X_t \in A\}\). Однако \(\tau_A-1\) (в общем случае) не является моментом остановки, так как событие \(\{\tau_A-1=t\}\) зависит от \(X_{t+1}\).
Упражнение 2 Пусть \(\tau_A^+:=\inf \{t \ge 1 \st X_t \in A\}\) — момент первого возвращения в \(A\). Проверьте, что \(\tau_A^+\) является моментом остановки.
Пусть \(\xi_A:=\sup \{ t\ge 0 \st X_t \in A\}\) — время последнего посещения \(A\). Проверьте, что \(\xi_A\), в общем случае, не является моментом остановки.
Упражнение 3 Пусть \(\tau_A^{(0)}=0\), и для \(k\ge 1\) \[ \tau_A^{(k)}:= \inf \{ t> \tau_A^{(k-1)} \st X_t\in A \} \] — \(k\)-й момент времени, когда процесс посещает \(A\). Является ли \(\tau_A^{(k)}\) моментом остановки?
Сильное марковское свойство
Теорема 1 (Сильное марковское свойство) Пусть \(\sigma\) — конечный момент остановки: \(\mathbb{P}(\sigma<\infty)=1\). Тогда выполняется более сильная версия марковского свойства: для всех ограниченных измеримых функций \(F\colon D(S)\to \mathbb{R}\). \[ \mathbb{E}_\mu[F(\theta_\sigma \mathbf{X})\mid (X_r)_{r\le \sigma}]= \mathbb{E}_{X_{\sigma}}[F(\mathbf{X})] \] В частности, \[ \mathbb{E}_\mu[F(\theta_\sigma \mathbf{X})\mid X_\sigma=x]= \mathbb{E}_x[F(\mathbf{X})] \] Другими словами, при условии \(X_\sigma=x\), \((X_{\sigma}, X_{\sigma+1},\ldots)\) является цепью Маркова, начинающейся в \(x\), независимой от \(X_0,\ldots,X_{\sigma-1}\) и с теми же переходными вероятностями, что и \(\mathbf{X}\).
Доказательство. Для всех \((x_0,x_1,\ldots) \in D(S)\) и \(x\in S\) \[ \begin{aligned} \mathbb{E}_\mu[F(\theta_\sigma \mathbf{X})\mid X_0=x_0, \ldots, X_{\sigma}=x] & = \frac{\sum_{t=0}^\infty \mathbb{E}_\mu[F(\theta_t \mathbf{X}) \ind{\sigma=t} \ind{X_0=x_0, \ldots, X_{t}=x}] }{\sum_{t=0}^\infty \mathbb{E}_\mu[\ind{\sigma=t} \ind{X_0=x_0, \ldots, X_{t}=x}]} \\ & = \frac{\sum_{t=0}^\infty \mathbb{E}_\mu[F(\theta_t \mathbf{X}) | \sigma=t, X_0=x_0, \ldots, X_{t}=x] \mathbb{P}_\mu({\sigma=t} ,X_0=x_0, \ldots, X_{t}=x)}{\sum_{t=0}^\infty \mathbb{P}_\mu({\sigma=t} ,X_0=x_0, \ldots, X_{t}=x)} \end{aligned} \] где мы понимаем \(\mathbb{E}[F|A]\mathbb{P}(A)=0\), когда \(\mathbb{P}(A)=0\). Поскольку \(\sigma\) — момент остановки, событие \(\{\sigma=t\}\) зависит только от \((X_0,\ldots,X_t)\). Таким образом, по марковскому свойству \[ \mathbb{E}_\mu[F(\theta_t \mathbf{X}) | \sigma=t, X_0=x_0, \ldots, X_{t}=x] = \mathbb{E}_x[F(\mathbf{X})] \] откуда мы легко заключаем, подставляя последнее равенство в формулу выше.
След цепи Маркова
Пусть \(A\subset S\). Предположим, что мы можем наблюдать цепь Маркова только внутри \(A\), а именно, мы определяем \[ Y_t:=X_{\tau_A^{(t+1)}} \tag{1}\] где \(\tau_A^{(t)}\) определено в Упражнение 3.
Цепь Маркова \(\mathbf{Y}\) называется следом \(\mathbf{X}\) на \(A\).
Утверждение 2 (След цепи Маркова) Если \(\mathbb{P}(\tau_A^{(t)}<\infty)=1\) для всех \(t\ge 1\), то процесс \(\mathbf{Y}=(Y_0,Y_1,\ldots)\), определённый в Уравнение 1, является цепью Маркова с переходными вероятностями \(q_{x,y}=\mathbb{P}_x(X_{\tau^+_A}=y)\), где \(\tau_A^+:=\inf \{t \ge 1 \st X_t \in A\}\) — момент остановки, определённый в Упражнение 2.
Доказательство. Для \(t \ge 0\), \(y, y_0, \ldots, y_t \in A\) \[ \mathbb{P}(Y_{t+1}=y \mid Y_0=y_0, \ldots, Y_t=y_t) = \mathbb{P}(X_{\tau^{(t+2)}_A}=y \mid X_{\tau^{(1)}_A}=y_0, \ldots, X_{\tau^{(t+1)}_A}=y_t) \] Однако:
- Поскольку \(\tau^{(s)}_A\) — моменты остановки, \(\mathbf{1}_{X_{\tau^{(1)_A}}=y_0, \ldots, X_{\tau^{(t+1)}_A}=y_t}\) является функцией от \((X_0, \ldots, X_{\tau^{(t+1)}_A})\).
- Мы имеем \(\mathbf{1}_{X_{\tau^{(t+2)}_A}=y}= \mathbf{1}_{(\theta_{\tau^{(t+1)}_A}\mathbf{X})_{\tau_A^+}=y}\).
Следовательно, мы можем применить сильное марковское свойство к функции \(F(\mathbf{X})=\mathbf{1}_{X_{\tau_A^+}=y}\), чтобы получить \[ \mathbb{P}(Y_{t+1}=y \mid Y_0=y_0, \ldots, Y_t=y_t)= \mathbb{E}[ \mathbf{1}_{(\theta_{\tau^{(t+1)}_A}\mathbf{X})_{\tau_A^+}=y} \mid X_{\tau^{(1)_A}}=y_0, \ldots, X_{\tau^{(t+1)}_A}=y_t] = \mathbb{E}_{y_t}[ \mathbf{1}_{X_{\tau_A^+}=y}] \] что и требовалось доказать.
Пример 1 Каждые 30 минут кот может либо есть, либо спать, либо играть на улице. Каждое действие влияет на вероятность следующего действия: \(p_{e,s}=0.7\), \(p_{e,p}=0.3\), \(p_{s,s}=0.9\), \(p_{s,e}=0.1\) и \(p_{p,e}=1\), так как кот устаёт после игры.
Мы записываем, что делает кот каждые 30 минут, но забываем об этом, если не видим кота (а именно, если он играет на улице). Таким образом, в наших записях будут только два состояния \(A=\{s,e\}\). Случайная последовательность наших записей, например, \((s,s,s,e,e,s,\ldots)\), по-прежнему является цепью Маркова с \(q_{e,e}=0.3\), \(q_{e,s}=0.7\), \(q_{s,s}=0.9\), \(q_{s,e}=0.1\).
Упражнение 4 Алгоритм, который не меняет своего состояния, — это просто пустая трата вычислительных ресурсов. Предположим, \(\mathbf{X}\) — это цепь Маркова, где \(p_{x,x}>0\) для некоторого \(x\), но \(p_{x,x}<1\) для всех \(x\).
- Определите \(\mathbf{Y}\), соответствующую идее, что \(\mathbf{Y}\) должна пропускать все моменты времени, когда \(\mathbf{X}\) не меняет своего положения.
- Докажите, что \(\mathbf{Y}\) является цепью Маркова.
Определим \(\tau_0=0\) и \(\tau_{t+1}:=\inf \{ s> \tau_{t} \st X_{s}\neq X_{\tau_t} \}\). \(\tau_t\) — момент остановки, и по сильному марковскому свойству \[ \mathbb{P}(Y_{t+1}=y| Y_0=x_0,\ldots,Y_{t-1}=x_{t-1}, Y_t=x)= \mathbb{P}(X_{\tau_{t+1}}=y| X_{\tau_0}=x_0,\ldots X_{\tau_t}=x)= \mathbb{P}(X_{\tau_{t+1}}=y| X_{\tau_t}=x)= \mathbb{P}_x(X_{\tau_{1}}=y)=:q_{x,y} \] и переходные вероятности \(\mathbf{Y}\) задаются как \(q_{x,y}:= p_{x,y}/(1-p_{x,x})\) для \(x\neq y\) и \(q_{x,x}=0\).