Марковские цепи

Докажите Теорему 8.1 для случая конечного $S$, построив соответствующую вероятностную меру на пространстве последовательностей $S^{\infty }$: замените слагаемое в правой части (2.21) на $\alpha_{u_{1}} p_{u_{1} u_{2}} \cdots p_{u_{n-1} u_{n}}$ и распространите рассуждения, предшествующие Теореме 2.3. Если $X_{n}(\cdot )=z_{n}(\cdot )$, то $X_{1}, X_{2}, \ldots$ — соответствующая цепь Маркова (здесь время сдвинуто на 1).

Пусть $Y_{0}, Y_{1}, \ldots$ независимы и одинаково распределены, причём $P\left[Y_{n}=1\right]=p$, $P\left[Y_{n}=0\right]=q=1-p, p \neq q$. Положим $X_{n}=Y_{n}+Y_{n+1}(\bmod 2)$. Покажите, что $X_{0}, X_{1}, \ldots$ не является цепью Маркова, хотя $P\left[X_{n+1}=j \mid X_{n-1}=i\right]=P\left[X_{n+1}=j\right]$. Выполняется ли это последнее соотношение для всех цепей Маркова? Почему?

Покажите на примере, что функция $f\left(X_{0}\right), f\left(X_{1}\right), \ldots$ от цепи Маркова не обязана быть цепью Маркова.

Покажите, что

и докажите, что если $j$ невозвратно, то $\sum_{n} p_{i j}^{(n)}<\infty$ для каждого $i$ (сравните с Теоремой 8.3(i)). Если $j$ невозвратно, то

${ }^{\dagger }$ Единственное существенное изменение в рассуждении состоит в том, что вместо Теоремы 54 в доказательстве Леммы 5 нужно использовать лемму Фату (Теорема 16.3). ${ }^{\ddagger }$ См. Задачи 836 и 8.37

Специализируйте на случай $i=j$: помимо того, что это влечёт невозвратность $i$ (Теорема 8.2(i)), конечное значение $\sum_{n=1}^{\infty } p_{i i}^{(n)}$ позволяет точно определить $f_{i i}$.

Назовём $\left(x_{i}\right)$ субрешением (8.24), если $x_{i} \leq \sum_{j} q_{i j} x_{j}$ и $0 \leq x_{i} \leq 1, i \in U$. Обобщив Лемму 1, покажите, что субрешение $\left\{ x_{i}\right\}$ удовлетворяет $x_{i} \leq \sigma_{i}$: решение $\left\{ \sigma_{i}\right\}$ уравнения (8.24) мажорирует все субрешения, а также все решения. Покажите, что если $x_{i}=\sum_{j} q_{i j} x$, и $-1 \leq x_{i} \leq 1$, то $\left\{ \left|x_{i}\right|\right\}$ является субрешением (8.24).

Решив (8.27), покажите, что неограниченное случайное блуждание на прямой (Пример 8.3) возвратно тогда и только тогда, когда $p=\frac{1}{2}$

Предположим, что $S=\left\{ 0,1,2, \ldots \right\} , p_{00}=1$, и $f_{i 0}>0$ для всех $i$.

$8.5 \uparrow$ Покажите для неприводимой цепи, что (8.27) имеет нетривиальное решение тогда и только тогда, когда существует нетривиальная ограниченная последовательность $\left\{ x_{i}\right\}$ (не обязательно неотрицательная), удовлетворяющая $x_{i}=\sum_{j \neq i_{0}} p_{i j} x_{j}, i \neq i_{0}$. (См. замечание после доказательства Теоремы 8.5.)

↑ Покажите, что неприводимая цепь невозвратна тогда и только тогда, когда (при произвольном $i_{0}$) система $y_{i}=\sum_{j} p_{i j} y_{j}, i \neq i_{0}$ (суммирование по всем $j$) имеет ограниченное непостоянное решение $\left(y_{i}, i \in S\right)$.

Покажите, что $P_{i}$-вероятности когда-либо покинуть $U$ для $i \in U$ являются минимальным решением системы

Ограничение $z_{i} \leq 1$ можно отбросить: минимальное решение автоматически ему удовлетворяет, поскольку $z_{i} \equiv 1$ является решением.

Покажите, что в Лемме 2 возможно $\sup_{i j} n_{0}(i, j)=\infty$.

Предположим, что $(\pi_{i})$ — решение (8.30), где предполагается, что $\sum_{i}\left|\pi_{i}\right|<\infty$, так что левая часть определена корректно. Покажите, что в неприводимом случае $\pi_{i}$ либо все положительны, либо все отрицательны, либо все равны 0. Таким образом, в неприводимом случае стационарные вероятности существуют тогда и только тогда, когда (8.30) имеет нетривиальное решение $\left\{ \pi_{i}\right\} \left(\sum_{i} \pi_{i}\right.$ абсолютно сходится).

Покажите на примере, что сцепленная цепь в доказательстве Теоремы 8.6 не обязана быть неприводимой, если исходная цепь не является непериодической.

Предположим, что $S$ состоит из всех целых чисел и

Покажите, что цепь неприводима и непериодична. При каких $p$ цепь возвратна? При каких $p$ существуют стационарные вероятности?

Покажите, что период $j$ равен наибольшему общему делителю множества

$\uparrow$ Возвратные события. Пусть $f_{1}, f_{2}, \ldots$ — неотрицательные числа, для которых $f=\sum_{n=1}^{\infty } f_{n} \leq$ 1. Определим $u_{1}, u_{2}, \ldots$ рекурсивно: $u_{1}=f_{1}$ и

Мыслитель, владеющий $r$ зонтами, ходит туда-сюда между домом и офисом, беря с собой зонт (если таковой имеется под рукой) в дождь (вероятность $p$), но не в ясную погоду (вероятность $q$). Пусть состоянием будет число зонтов под рукой, независимо от того, находится ли мыслитель дома или на работе. Составьте матрицу переходных вероятностей и найдите стационарные вероятности. Найдите стационарную вероятность того, что он промокнет, и покажите, что пять зонтов защитят его на уровне $5\%$ при любом климате (любом $p$).

Множество $C$ в $S$ называется замкнутым, если $\Sigma_{j \in C} p_{i j}=1$ для $i \in C$: попав в $C$, система уже не может его покинуть. Покажите, что цепь неприводима тогда и только тогда, когда $S$ не имеет собственного замкнутого подмножества.

$\uparrow$ Пусть $T$ — множество невозвратных состояний, и назовём возвратные состояния $i$ и $j$ (если таковые есть) эквивалентными, если $f_{i j}>0$. Покажите, что это отношение эквивалентности на $S-T$, разбивающее его на классы эквивалентности $C_{1}, C_{2}, \ldots$, так что $S=T \cup C_{1} \cup C_{2} \cup \cdots$ Покажите, что каждое $C_{m}$ замкнуто и что $f_{i j}=1$ для $i$ и $j$ из одного и того же $C_{m}$.

8.118.21 ↑ Пусть $T$ — множество невозвратных состояний, и пусть $C$ — произвольное замкнутое множество возвратных состояний. Покажите, что $P_{i}$-вероятности в конечном счёте оказаться поглощёнными в $C$ для $i \in T$ являются минимальным решением системы

Предположим, что неприводимая цепь имеет период $t>1$. Покажите, что $S$ разбивается на множества $S_{0}, \ldots , S_{t-1}$, такие что $p_{i j}>0$ только если $i \in S_{\nu }$ и $j \in S_{\nu +1}$ для некоторого $\nu$ ($\nu +1$ берётся по модулю $t$). Таким образом, система проходит через $S_{\nu }$ в циклическом порядке.

$\uparrow$ Предположим, что неприводимая цепь периода $t>1$ имеет стационарное распределение $(\pi_{j})$. Покажите, что если $i \in S_{\nu }$ и $j \in S_{\nu +\alpha }(\nu +\alpha$ берётся по модулю $t)$, то $\lim_{n} p_{i j}^{(n t+\alpha )}=\pi_{j}$. Покажите, что $\lim_{n} n^{-1} \sum_{m=1}^{n} p_{i j}^{(m)}=\pi_{j} / t$ для всех $i$ и $j$.

Собственные значения. Рассмотрим неприводимую непериодическую цепь с пространством состояний $\left\{ 1, \ldots , s\right\}$. Пусть $r_{0}=\left(\pi_{1}, \ldots , \pi_{s}\right)$ — (Пример 8.14) вектор-строка стационарных вероятностей, и пусть $c_{0}$ — вектор-столбец из единиц; тогда $r_{0}$ и $c_{0}$ — левый и правый собственные векторы $P$, отвечающие собственному значению $\lambda =1$.

↑ Предположим, что $P$ диагонализуема, то есть предположим, что существует невырожденная $C$, такая что $C^{-1} P C=\Lambda$, где $\Lambda$ — диагональная матрица. Пусть $\lambda_{1}, \ldots , \lambda_{s}$ — диагональные элементы $\Lambda$, пусть $c_{1}, \ldots , c_{s}$ — последовательные столбцы $C$, пусть $R=C^{-1}$, и пусть $r_{1}, \ldots , r_{s}$ — последовательные строки $R$.

Предположим, что $\left\{ X_{n}\right\}$ — цепь Маркова с пространством состояний $S$, и положим $Y_{n}=\left(X_{n}, X_{n+1}\right)$. Пусть $T$ — множество пар $(i, j)$, таких что $p_{i j}>0$, и покажите, что $\left\{ Y_{n}\right\}$ — цепь Маркова с пространством состояний $T$. Выпишите переходные вероятности. Покажите, что если $\left\{ X_{n}\right\}$ неприводима и непериодична, то и $\left\{ Y_{n}\right\}$ такова же. Покажите, что если $\pi_{i}$ — стационарные вероятности для $\left(X_{n}\right)$, то $\pi_{i} p_{i j}$ — стационарные вероятности для $\left\{ Y_{n}\right\}$.

$6.108 .29 \uparrow$ Предположим, что цепь конечна, неприводима и непериодична и что начальные вероятности являются стационарными. Зафиксируем состояние $i$, пусть $A_{n}=\left[X_{i}=\right. i]$, и пусть $N_{n}$ — число прохождений через $i$ за первые $n$ шагов. Вычислите $\alpha_{n}$ и $\beta_{n}$, определённые в (5.41). Покажите, что $\beta_{n}-\alpha_{n}^{2}=O(1 / n)$, так что $n^{-1} N_{n} \rightarrow \pi_{i}$ с вероятностью 1. Покажите для функции $f$ на пространстве состояний, что $n^{-1} \sum_{k=1}^{n} f\left(X_{k}\right) \rightarrow \sum_{i} \pi_{i} f(i)$ с вероятностью 1. Покажите, что $n^{-1} \sum_{k=1}^{n} g\left(X_{k}, X_{k+1}\right) \rightarrow \sum_{i j} \pi_{i} p_{i j} g(i, j)$ для функций $g$ на $S \times S$.

$6.148 .30 \uparrow$ Если $X_{0}(\omega )=i_{0}, \ldots , X_{n}(\omega )=i_{n}$ для состояний $i_{0}, \ldots , i_{n}$, положим $p_{n}(\omega )= \pi_{i_{0}} p_{i_{0} i_{1}} \cdots p_{i_{n-1} i_{n}}$, так что $p_{n}(\omega )$ — вероятность наблюдаемого исхода. Покажите, что $-n^{-1} \log p_{n}(\omega ) \rightarrow h=-\sum_{i j} \pi_{i} p_{i j} \log p_{i j}$ с вероятностью 1, если цепь конечна, неприводима и непериодична. Распространите на этот случай понятия источника, энтропии и асимптотической равнораспределённости.

Последовательность $\left\{ X_{n}\right\}$ называется цепью Маркова второго порядка, если $P\left[X_{n+1}=j \mid X_{0}=\right. \left.i_{0}, \ldots , X_{n}=i_{n}\right]=P\left[X_{n+1}=j \mid X_{n-1}=i_{n-1}, X_{n}=i_{n}\right]=p_{i_{n-1} i_{n}}$. Покажите, что по сути здесь нет ничего нового, поскольку последовательность пар $(X_{n}, X_{n+1})$ является обычной цепью Маркова (первого порядка). Сравните с Задачей 8.29. Обобщите эту идею на цепи порядка $r$.

Рассмотрим цепь на $S=\left\{ 0,1, \ldots , r\right\}$, где 0 и $r$ — поглощающие состояния и $p_{i, i+1}=p_{i}>0, p_{i, i-1}=q_{i}=1-p_{i}>0$ при $0<i<r$. Отождествим состояние $i$ с точкой $z_{i}$ на прямой, где $0=z_{0}<\cdots <z_{r}$, а расстояние от $z_{i}$ до $z_{i+1}$ в $q_{i} / p_{i}$ раз больше расстояния от $z_{i-1}$ до $z_{i}$. Для функции $\varphi$ на $S$ рассмотрим соответствующую функцию $\hat{\varphi }$ на [ $0, z_{r}$ ], определённую в точках $z_{i}$ равенством $\hat{\varphi }\left(z_{i}\right)=\varphi (i)$, а между ними — линейной интерполяцией. Покажите, что $\varphi$ эксцессивна тогда и только тогда, когда $\hat{\varphi }$ вогнута. Покажите, что вероятность поглощения в $r$ при начальном состоянии $i$ равна $t_{i-1} / t_{r-1}$, где $t_{i}= \sum_{k=0}^{i} q_{1} \cdot q_{k} / p_{1} \cdots p_{k}$. Выведите (7.7). Покажите, что в новой шкале ожидаемое смещение на каждом шаге равно 0.

Предположим, что конечная цепь неприводима и непериодична. Покажите с помощью Теоремы 8.9, что эксцессивная функция обязательно постоянна.

Закон нуля и единицы. Пусть пространство состояний $S$ содержит $s$ точек, и предположим, что $\epsilon_{n}=\sup_{i j}\left|p_{i j}^{(n)}-\pi_{j}\right| \rightarrow 0$, как это имеет место при условиях Теоремы 8.9. Для $a \leq b$ пусть $\mathscr {G}_{a}^{b}$ — $\sigma$-алгебра, порождённая множествами $\left[X_{a}=u_{a}, \ldots , X_{b}=u_{b}\right]$. Пусть $\mathscr {T}_{a}=\sigma \left(\bigcup_{b=a}^{\infty } \mathscr {G}_{a}^{b}\right)$ и $\mathscr {T}=\bigcap_{a=1}^{\infty } \mathscr {T}_{a}$. Покажите, что $\left|P(A \cap B)-P(A) P(B)\right| \leq s\left(\epsilon_{n}+\epsilon_{b+n}\right)$ для $A \in \mathscr {H}_{0}^{b}$ и $B \in \mathscr {A}_{b-n}^{b+m}$; слагаемое $\epsilon_{b+n}$ можно отбросить, если начальные вероятности стационарны. Покажите, что это выполняется для $A \in \mathscr {G}_{0}^{b}$ и $B \in \mathscr {T}_{b+n}$. Покажите, что из $C \in \mathscr {T}$ следует, что $P(C)$ равно 0 или 1.

${ }^{\dagger }$ Измените цепь из Примера 8.13 так, чтобы $q_{0}=1-p_{0}=1$ (остальные $p_{i}$ и $q_{i}$ по-прежнему положительны). Пусть $\beta =\lim_{n} p_{1} \cdots p_{n}$, и предположим, что $\beta >0$. Определим функцию выигрыша: $f(0)=1$ и $f(i)=1-f_{i 0}$ при $i>0$. Если $X_{0}, \ldots , X_{n}$ положительны, положим $\sigma_{n}=n$; в противном случае пусть $\sigma_{n}$ — наименьшее $k$, для которого $X_{k}=0$. Покажите, что $E_{j}\left[f\left(X_{\sigma_{n}}\right)\right] \rightarrow 1$ при $n \rightarrow \infty$, так что $v(i) \equiv 1$. Таким образом, носитель есть $M=\left\{ 0\right\}$, а для начального состояния $i>0$ вероятность когда-либо попасть в $M$ равна $f_{i 0}<1$.

Для произвольного конечного момента остановки $\tau$ выберем $n$ так, чтобы $P_{i}\left[\tau <n=\sigma_{n}\right]>0$. Тогда $E_{i}\left[f\left(X_{\tau }\right)\right] \leq 1-f_{i+n, 0} P_{i}\left[\tau <n=\sigma_{n}\right]<1$. Таким образом, ни одна стратегия не достигает значения $v(i)$ (кроме, разумеется, случая $i=0$).

↑ Пусть цепь такая же, как в предыдущей задаче, но предположим, что $\beta =0$, так что $f_{i 0}=1$ для всех $i$. Предположим, что $\lambda_{1}, \lambda_{2}, \ldots$ превосходят 1 и что $\lambda_{1} \cdots \lambda_{n} \rightarrow \lambda < \infty$; положим $f(0)=0$ и $f(i)=\lambda_{1} \cdots \lambda_{i-1} / p_{1} \cdots p_{i-1}$. Для произвольного (конечного) момента остановки $\tau$ событие $[\tau =n]$ должно иметь вид $\left[\left(X_{0}, \ldots , X_{n}\right) \in I_{n}\right]$ для некоторого множества $I_{n}$ последовательностей состояний длины $(n+1)$. Покажите, что для каждого $i$ существует не ${ }^{\dagger }$ Три последние задачи этого раздела касаются математических ожиданий случайных величин с бесконечной областью значений. более одного $n \geq 0$, такого что $(i, i+1, \ldots , i+n) \in I_{n}$. Если такого $n$ нет, то $E_{i}\left[f\left(X_{\tau }\right)\right]=0$. Если оно есть, то

и, следовательно, единственно возможные значения $E_{\mathrm{i}}\left[f\left(X_{\tau }\right)\right]$ таковы:

Таким образом, $v(i)=f(i) \lambda / \lambda_{1} \cdots \lambda_{i-1}$ при $i \geq 1$; ни одна стратегия не достигает этого значения. Носитель есть $M=(0)$, и момент попадания $\tau_{0}$ в $M$ конечен, но $E_{i}\left[f\left(X_{\tau_{0}}\right)\right]=0$.

$5.12 \hat{i}$ Рассмотрим неприводимую непериодическую положительно возвратную цепь. Пусть $\tau_{j}$ — наименьшее $n$, такое что $X_{n}=j$, и пусть $m_{i j}=E_{i}\left[\tau_{j}\right]$. Покажите, что существует такое $r$, что $p=P_{j}\left[X_{1} \neq j, \ldots , X_{r-1} \neq j, X_{r}=i\right]$ положительно; из $f_{j j}^{(n+r)} \geq p f_{i j}^{(n)}$ и $m_{j,}<\infty$ заключите, что $m_{i}<\infty$ и $n_{i j}=\sum_{n=0}^{\infty } P_{i}\left[\tau_{j}>n\right]$. Исходя из $p_{i,}^{(i)}= \sum_{s=1}^{t} f_{i j}^{(s)} p_{\prime \prime }^{(i-s)}$, покажите, что

Используя признак Вейерштрасса, покажите, что

Если $i=J$, это снова даёт $m_{j j}=1 / \pi_{j}$; если $i \neq j$, это показывает, как в принципе можно вычислить $m_{i j}$ по матрице переходных вероятностей и стационарным вероятностям.