Глава 4. Неразложимость и возвратность

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

Возвратность и транзиентность

Напомним, что момент первого возвращения в множество $A$ обозначается как $\tau_A^+$, а $k$-й момент прохождения — как $\tau^{(k)}_A$, и что это моменты остановки. Вероятность достижения обозначается как $h_A(x)$. Когда $A=\{y\}$, мы обозначаем эти функции без фигурных скобок, например, $h_y(x)\equiv h_{\{y\}}(x)$.

Мы также можем ввести случайные величины \[ \mathcal{N}_t(x):= |\{ s \le t \st X_s=x \}| = \sup \{k \in \mathbb{N} \st \tau_x^{(k)} \le t \} \in \{0,\ldots, t\}, \qquad \mathcal{N}(x):= \lim_{t\to \infty} \mathcal{N}_t(x) \in \mathbb{N}\cup \{\infty\} \] как число раз (до момента времени $t$ и в целом), когда процесс посещает точку $x$.

Лемма 1 Для $x\in S$ положим $q_x:=\mathbb{P}_x(\tau^+_x<\infty)$.

если $q_x=1$, то есть возврат в $x$ происходит почти наверное, тогда $\mathbb{P}_x(\mathcal{N}(x)=+\infty)=1$;
если $q_x <1$, то при условии $\mathbb{P}_x$ случайная величина $\mathcal{N}(x)$ имеет геометрическое распределение с параметром $1-q_x$, а именно $\mathbb{P}_x(\mathcal{N}(x)=k)= (1-q_x) q_x^{k}$ для $k\ge 0$. В частности, $\mathbb{P}_x(\mathcal{N}(x)<\infty)=1$.

В частности, \[ \sum_{t=0}^\infty \mathbb{P}_x(X_t=x)=\mathbb{E}_x[\mathcal{N}(x)]= \begin{cases} + \infty & \text{если $q_x=1$} \\ 1/(1-q_x) & \text{если $q_x<1$} \end{cases} \tag{1}\]

Доказательство. Зафиксируем $x\in S$ и $k \ge 1$: \[ q_x^{(k+1)}:=\mathbb{P}_x(\tau_{x}^{(k+1)}<\infty)= \mathbb{P}_x(\tau_{x}^{(k+1)}<\infty \mid \tau_{x}^{(k)}<\infty ) \mathbb{P}_x(\tau_{x}^{(k)}<\infty) = \mathbb{P}_x(\tau_{x}^{+}<\infty ) \mathbb{P}_x(\tau_{x}^{(k)}<\infty) = q_x \,q_x^{(k)} \] где в первом равенстве мы использовали включение $\{\tau_{x}^{(k+1)}<\infty \} \subset \{ \tau_{x}^{(k)}<\infty \}$, а во втором — сильное свойство Маркова с $F=\mathbf{1}_{\tau_{x}^{+}<\infty}$, $\mu=\delta_x$ и $\sigma = \tau_x^{(k)}$.

В частности, поскольку $q_x^{(0)}=1$, имеем $q_x^{(k)}= q_x^k$, и следовательно \[ \mathbb{P}_x(\mathcal{N}(x)=+\infty)=\mathbb{P}_x(\cap_k \{\tau_{x}^{(k)}<\infty \})= \lim_k \mathbb{P}_x(\tau_{x}^{(k)}<\infty) = \begin{cases} 1 & \text{если $q_x=1$} \\ 0 & \text{если $q_x<1$} \end{cases} \]

Это завершает рассмотрение случая $q_x=1$. Если же $q_x<1$, то \[ \mathbb{P}_x(\mathcal{N}(x)=k)=\mathbb{P}_x(\tau_x^{(k+1)}=\infty, \tau_x^{(k)}<\infty) = \mathbb{P}_x(\tau_x^{(k)}<\infty) - \mathbb{P}_x(\tau_x^{(k+1)}<\infty) = q_x^k - q_x^{k+1} \] и, очевидно, $\sum_{k\ge 1} q_x^{(k)}=1$, откуда $c_x=1-q_x$.

Осталось проверить Уравнение 1. Действительно, по теореме о монотонной сходимости, \[ \sum_{t=0}^\infty \mathbb{P}_x(X_t=x)= \sum_{t=0}^\infty \mathbb{E}_x[\mathbf{1}_x(X_t) ]= \mathbb{E}_x[\sum_{t=0}^\infty \mathbf{1}_x(X_t)]= \mathbb{E}_x[\mathcal{N}(x)] \]

Определение 1 (Возвратные и транзиентные состояния) Элемент $x\in S$ является возвратным, если $\mathbb{P}_x(\tau^+_x<\infty)=1$, то есть (ввиду Лемма 1) цепь Маркова возвращается в $x$ бесконечное число раз п.н.

$x\in S$ является транзиентным, если $\mathbb{P}_x(\tau^+_x<\infty)<1$, то есть если цепь проходит через $x$ лишь конечное число раз п.н.

Сообщающиеся классы

Для однородной по времени цепи Маркова с переходными вероятностями $(p_{x,y})$, для $x,y\in S$ мы пишем $x\rightarrow y$, если выполняется любое из эквивалентных условий:

Существует $t\ge 0$ такое, что $p^{(t)}_{x,y}>0$.
Существует путь в $D(S)$, начинающийся в $x$ и проходящий через $y$.
Существуют $t\ge 0$, $x_0=x,x_1,\ldots, x_t=y$ такие, что $p_{x_{i-1},x_{i}}>0$ для $i=1,\ldots, t$.
$\mathbb{P}_x(\tau_y < \infty)>0$.

Если $x \rightarrow y$ и $y \rightarrow x$, мы пишем $x \leftrightarrow y$. Легко проверить, что $\leftrightarrow$ является отношением эквивалентности. Классы эквивалентности получили название, хорошо соответствующее интуиции.

Определение 2 (Сообщающиеся классы) Классы эквивалентности $S/\leftrightarrow$ называются сообщающимися классами цепи Маркова.

Рассмотрим множество $S_x:=\{y \in S \st x \rightarrow y \}$ точек, достижимых из $x$. Если $x\rightarrow y$, то $S_x \supset S_y$, так что если $x\leftrightarrow y$, то $S_x=S_y$.

Определение 3 (Замкнутый класс) Сообщающийся класс $C$ является замкнутым, если выполняется любое из следующих эквивалентных условий:

$S_x=C$ для всех $x\in C$.
$S_x=C$ для некоторого $x\in C$.
$p_{x,y}=0$ для всех $x\in C$ и $y\not \in C$.
$\mathbb{P}_x(X_t\in C, \, \forall t\ge 0)=1$ для всех $x\in C$.

Примечание. Если число сообщающихся классов конечно (в частности, если $S$ конечно), то по крайней мере один из них является замкнутым. Действительно, пусть $C_0$ — любой сообщающийся класс. Если он замкнут, мы закончили, в противном случае существуют $x_0\in C_0$, $x_1\in C_1\neq C_0$ такие, что $x_0 \rightarrow x_1$, но $x_1\not \rightarrow x_0$. Повторяя, мы находим последовательность различных классов $C_0, C_1,\ldots, C_n$. Эта последовательность конечна (поскольку мы предположили, что классов конечное число), и легко видеть, что последний элемент $C_n$ является замкнутым.

С другой стороны, если классов бесконечно много, замкнутый класс может не существовать. Например, $S=\mathbb{N}$ и $p_{n,n+1}=1$. В этом случае каждый синглетон является (незамкнутым) сообщающимся классом.

Упражнение 1 В следующем ориентированном графе нарисованы стрелки, соответствующие строго положительным переходным вероятностям. Найдите соответствующие сообщающиеся классы и определите замкнутые.

стрелки представляют переходы с положительной вероятностью — Рисунок 1

Решение

Классы: $\{a,b,c,f,g\}$, $\{d,e\}$, $\{h\}$, $\{i,l\}$. $\{d,e\}$ и $\{i,l\}$ являются замкнутыми.

Рисунок 2

Сообщающиеся классы, неразложимость и возвратность

Существует тесная связь между возвратностью и замкнутостью класса.

Теорема 1 (Возвратность и транзиентность для сообщающихся классов) Пусть $C$ — сообщающийся класс, и напомним, что $h_{C^c}(x)=\mathbb{P}_x(\tau_{C^c}<\infty)$.

Если $C$ не замкнут, то $h_{C^c}(x)>0$ для всех $x\in C$. В частности, каждая точка $x\in C$ транзиентна.
Если $\inf_{x\in C} h_{C^c}(x)>0$, то $\mathbb{P}_x(\tau_{C^c}<\infty)=1$ для всех $x \in C$. В частности, цепь Маркова в конечном итоге покинет любой конечный и не замкнутый класс.
Если $C$ замкнут, то $h_{C^c}(x)=0$. И либо каждая точка $x\in C$ возвратна, либо каждая точка $x\in C$ транзиентна. Таким образом, возвратность и транзиентность — это свойство замкнутого класса $C$, а не каждой отдельной точки в $C$.
Если $C$ конечен и замкнут, то это возвратный класс.

Доказательство. Докажем по пунктам.

Зафиксируем $x\in C$. Если $C$ не замкнут, то существует $y \in C^c$ и $t>0$ такие, что $p^{(t)}_{x,y}>0$. Однако, поскольку $y \not \rightarrow C$, \[ \mathbb{P}_x(\tau_C^c<\infty) \le 1 -\mathbb{P}_x(X_t=y)= 1- p^{(t)}_{x,y}<1 \]
Пусть $r(x) = 1- h_{C^c}(x)$ — вероятность того, что цепь никогда не покинет класс $C$, стартуя из $x$. Мы предполагаем, что $R:=\sup_{x\in C} r(x)<1$, и хотим доказать, что $r(x)\equiv 0$. Поскольку $h_{C^c}$ решает линейную задачу, $r$ решает \[ \begin{cases} (I-P)r = 0 & \text{на $C$} \\ r =0 & \text{на $C^c$} \end{cases} \] Теперь заметим, что, поскольку $r(x)=0$ вне $C$, $r=Pr$ выполняется всюду на $S$. Итерируя $r=P^t r$, а именно для $t\ge 0$ \[ r(x)=\sum_{y \in S} p^{(t)}_{x,y} r(y) =\sum_{y \in C} p^{(t)}_{x,y} r(y) \le R \sum_{y \in C} p^{(t)}_{x,y} \] где мы использовали $r(y)=0$ для $y\not \in C$ во втором равенстве. Однако при $t\to \infty$, поскольку вероятности непрерывны на возрастающих множествах \[ \sum_{y \in C} p^{(t)}_{x,y} = \mathbb{P}_x(\tau_{C^c} > t) \downarrow \mathbb{P}_x(\tau_{C^c}= \infty) = r(x) \] Следовательно, переходя к пределу, мы получаем $r(x)\le R r(x)$, и, таким образом, $r(x)=0$, так как $R<1$.
Если $C$ замкнут, то $r(x)=1$ по последнему пункту Определение 3. Пусть $x,y\in C$, и предположим, что $x$ возвратно. Достаточно показать, что тогда и $y$ возвратно. Действительно, так как $x\leftrightarrow y$, существуют $s,t>0$ такие, что $p^{(s)}_{y,x}>0$ и $p^{(t)}_{x,y}>0$. Однако вероятность не вернуться в $y$ меньше, чем вероятность достичь $x$ за $s$ шагов и не достичь $y$ из $x$ за $t$ шагов каждый раз, когда мы посещаем $x$: \[ \mathbb{P}_y(\tau_{y}^+ \le \tau_{x}^{(k)}+t+s) \ge 1- p^{(s)}_{y,x} (1-p^{(t)}_{x,y})^k \tag{2}\] Поскольку $x$ возвратно, $\tau_{x}^{(k)} <\infty$ п.н., то $\{\tau_{y}^+ < \infty\} = \cup_k \{\tau_{y}^+\le \tau_{x}^{(k)}+t+s \}$. И следовательно, \[ \mathbb{P}_y(\tau_{y}^+ < \infty) = \lim_k \mathbb{P}_y(\tau_{y}^+ \le \tau_{x}^{(k)}+t+s) \ge 1 \]
Поскольку $C$ конечно, по крайней мере одна точка посещается бесконечное число раз. А из предыдущего пункта следует, что и каждая точка тоже.

Упражнение 2 Приведите пример цепи Маркова, которая имеет не замкнутый класс $C$ такой, что $\mathbb{P}_x(\tau_{C^c}<\infty)<1$ для некоторого $x\in C$.

Упражнение 3 Используйте сильное марковское свойство, чтобы дать детальное доказательство того, что если $x,y$ сообщаются, то $x$ возвратно т. и т. т., когда $y$ возвратно.

Цепь Маркова в конечном итоге покинет любой конечный не замкнутый класс. Таким образом, по крайней мере на конечных пространствах состояний, она в конечном итоге войдёт в некоторый замкнутый класс и останется там навсегда. В предыдущей главе мы видели, как вычислить вероятность того, что цепь войдёт в данное множество, в частности, в данный замкнутый класс. Следующим естественным шагом является понимание поведения внутри замкнутого класса. Для этой цели достаточно изучить цепь Маркова, определённую на замкнутом классе, поскольку замкнутые классы составляют независимые строительные блоки цепи.

Определение 4 (Неразложимая цепь Маркова) Цепь Маркова неразложима, если её пространство состояний является замкнутым сообщающимся классом, а именно, если $x \leftrightarrow y$ для всех $x,y \in S$.

В дальнейшем мы будем в основном рассматривать неразложимые, однородные цепи.

Возвратность на $\mathbb{Z}^d$

Благодаря Лемма 1, для неразложимой цепи мы имеем следующий критерий:

Неразложимая цепь является возвратной тогда и только тогда, когда $\sum_{t=0}^\infty \mathbb{P}_x(X_t=x)=\infty$ для некоторого (что эквивалентно, для любого) $x\in S$.

Прежде чем продолжить, напомним формулу Стирлинга \[ n^n e^{-n} \sqrt{2\pi n} e^{1/(12 n+1)}\le n! \le n^n e^{-n} \sqrt{2\pi n} e^{1/(12 n)} \tag{3}\]

Пример 1 Рассмотрим цепь Маркова на $\mathbb{Z}$, где на каждом временном шаге $X_t$ может увеличиться на $1$ с вероятностью $p$ и уменьшиться с вероятностью $1-p$. Другими словами, $p_{x,x+1}=1-p_{x,x-1}=p$. Тогда цепь

является транзиентной, если $p\neq 1/2$.
является возвратной, если $p=1/2$.

Действительно, цепь неразложима, и для простоты обозначений мы можем начать с $X_0=0$. $X_t$ может быть равно $0$ с положительной вероятностью т. и т. т., когда $t$ чётно, скажем $t=2n$. Тогда $X_t$ будет равно $0$ т. и т. т., когда ровно $n$ раз мы увеличили на $1$ и $n$ раз уменьшили на $1$. Следовательно, по Уравнение 3 \[ \mathbb{P}_0(X_{2n}=0)= \binom{2n}{n} p^n (1-p)^n = \frac{(4p(1-p))^n}{\sqrt{\pi n}}(1+o_n(1)) \] Теперь, поскольку $4p(1-p) < 1$ для $p \neq 1/2$, ряд в этом случае сходится. Однако, если $p=1/2$, то $\mathbb{P}_0(X_{2n}=0)=\frac{1}{\sqrt{\pi n}}(1+o_n(1))$, и, следовательно, ряд расходится.

Примечание. Рассмотрим цепь Маркова на $\mathbb{Z}^d$, где на каждом шаге мы прибавляем некоторый случайный вектор из $\mathbb{Z}^d$: \[ X_t=x+\sum_{s=1}^t Z_s \] где $Z_s$ — н.о.р.в. (независимые одинаково распределённые величины). Предположим, что \[ \mathbb{E}[|Z_1|]< \infty, \mathbb{E}[Z_1] :=m\neq 0 \]

Тогда случайное блуждание $\mathbf{X}$ является транзиентным. Действительно, по закону больших чисел \[ \mathbb{P}(\lim_t X_t/t=m)=1 \] Следовательно, с вероятностью $1$, $X_t$ посещает каждую точку в $\mathbb{Z}^d$ лишь конечное число раз.

Если $S$ — счётный неориентированный граф, мы пишем $x\sim y$, чтобы обозначить, что $x$ и $y$ являются соседями. Степень $d(x)$ точки $x$ — это число её соседей. Граф называется локально конечным, если $d(x)$ конечна для всех $x\in S$.

Определение 5 Пусть $S$ — локально конечный граф. Простое случайное блуждание на $S$ — это случайное блуждание с переходными вероятностями \[ p_{x,y}= \begin{cases} 1/d(x) & \text{если $y\sim x$} \\ 0 & \text{в противном случае} \end{cases} \]

Например, простое случайное блуждание на $\mathbb{Z}^d$ на каждом шаге перемещается с вероятностью $1/(2d)$ к каждому из $2d$ соседей $X_t$. Например, если $d=2$, на каждом шаге мы можем прибавить $(1,0)$, $(-1,0)$, $(0,1)$ или $(0,-1)$, каждое с вероятностью $1/4$. Предыдущее замечание не помогает нам определить, является ли это случайное блуждание возвратным или нет, так как математическое ожидание смещения $m$ равно нулю. Однако мы уже видели, что для $d=1$ блуждание является возвратным.

Утверждение 1 Простое случайное блуждание на $\mathbb{Z}^d$ является

возвратным, если $d=1,2$.
транзиентным, если $d\ge 3$.

Или, как сказал Пойа, пьяница в конце концов найдёт дорогу домой, а вот пьяная птица может затеряться навсегда.

Доказательство. Доказательство на самом деле довольно простое. Опять же, для простоты обозначений мы можем рассмотреть случай $X_0=0$, так как в силу трансляционной инвариантности $\mathbb{P}_{x}(X_t=x)$ не зависит от $x$ (или, в любом случае, транзиентность и возвратность не зависят от $x$ для неразложимых блужданий). Чтобы вернуться в $0$ в момент времени $t$, нам, безусловно, необходимо, чтобы $t=2n$, более того, в каждом направлении мы должны были прибавить $+1$ столько же раз, сколько вычли $-1$. Таким образом, \[ \mathbb{P}_0(X_{2n}=0)= \sum_{k_1+k_2+\ldots+k_d=n} \frac{(2n)!}{(k_1!)^2 (k_2!)^2\cdots (k_d!)^2}(2d)^{-2n} \] Случай $d=1$ мы уже рассмотрели в Пример 1.

Для $d=2$ мы можем использовать комбинаторное тождество $\sum_{k=0}^n \left(\binom{n}{k}\right)^2 =\binom{2n}{n}$, чтобы получить \[ \mathbb{P}_0(X_{2n}=0)= (4)^{-2n} \sum_{k=0}^n \frac{(2n)!}{(k!)^2 ((n-k)!)^2} = 4^{-2n} \binom{2n}{n} \sum_{k=0}^n \left(\binom{n}{k}\right)^2 = \left(\binom{2n}{n} 4^{-n} \right)^2 \] Это в точности квадрат результата для одномерного случая, так что \[ \mathbb{P}_0(X_{2n}=0)= \frac{1}{\pi n} (1+o_n(1)) \] и, следовательно, ряд расходится, и блуждание является возвратным.

Для $d=3$ это простое степенное правило не работает (а именно, вероятность не является точной степенью одномерной формулы). Тем не менее, применение формулы Стирлинга даёт $\mathbb{P}_0(X_{2n}=0)=c n^{-3/2}(1+o_n(1))$, и, таким образом, ряд сходится, а блуждание является транзиентным.

Для $d\ge 4$ использовать формулу Стирлинга становится уже громоздко, хотя можно доказать, что $\mathbb{P}_0(X_{2n}=0)=c_d n^{-d/2} (1+o_d(1))$. Но нам такое вычисление не нужно. Действительно, легко видеть, что чем выше размерность, тем, так сказать, более транзиентным является блуждание. Пусть $X_t$ — простое случайное блуждание в $\mathbb{Z}^4$. Если мы будем рассматривать только первые три компоненты $X_t$ и учитывать только те моменты времени, когда он движется, мы получим последовательность $Y_t$, которая в точности является 3-мерным простым случайным блужданием. Поскольку $Y_t$ проходит через $0$ конечное число раз, то же самое делает и $X_t$. Тот же аргумент работает для всех более высоких размерностей.

Рисунок 3

Упражнение 4 Рассмотрим неразложимое, транзиентное случайное блуждание с $p_{x,y}=p_{y,x}$. Докажите, что \[ d(x,y)= -\log \mathbb{P}_x(\tau_y<\infty) \] является расстоянием на $S$.

Абстракция

Мы можем упомянуть некоторые более продвинутые результаты.

A. Рассмотрим случайное блуждание в $\mathbb{Z}^d$, $X_t=\sum_{s=1}^t Z_s$ с $(Z_s)$ — н.о.р.в. последовательностью в $\mathbb{Z}^d$ такой, что $\mathbb{P}(Z_t=x)=\mathbb{P}(Z_t=-x)= \Theta(\|x\|^{-s})$ (что означает, что эта вероятность убывает как $\|x\|^{-s}$ при больших $\|x\|$). Тогда блуждание является возвратным т. и т. т., когда $d=1,2$ и $s<d$ или $s>2d$.

B. Рассмотрим случайное блуждание на конечно порождённой группе $S$ такое, что

Оно инвариантно относительно группы: $p_{x,y}=p_{gx,gy}$ для всех $g\in S$.
Оно имеет конечный второй момент: $\sum_x d(e,x)^2 p_{e,x}<\infty$ (легко видеть, что это условие не зависит от конечного набора образующих, используемых для определения расстояния Кэли $d(x,y)$). Тогда случайное блуждание является возвратным т. и т. т., когда группа $S$ конечна или виртуально изоморфна $\mathbb{Z}$ или $\mathbb{Z}^2$.

Возвратность и транзиентность

Сообщающиеся классы

Сообщающиеся классы, неразложимость и возвратность

Возвратность на \(\mathbb{Z}^d\)