Глава 7.1. Избранные темы: Формализм древовидных структур и последний проход

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

В этой главе мы хотим дать явную характеризацию инвариантных мер и вероятностей попадания для конечных неприводимых цепей Маркова.

Рассмотрим цепь Маркова на пространстве состояний $S$. Как обычно, мы сопоставляем цепи ориентированный граф, в котором ребро $(x,y)$ присутствует, если $p_{x,y}>0$, и рассматриваем вероятности как веса на ориентированных рёбрах. Теперь представим, что в момент времени $t=0$ в каждой точке $S$ находится дружелюбная частица. Каждая частица совершает движение согласно цепи Маркова с вероятностями переходов $p_{x,y}$. Более того, они не видят дальше вершины, которую занимают в данный момент, поэтому каждая частица просто движется независимо, пока не встретит другую частицу в той же вершине $S$. Поскольку они очень дружелюбны, как только две или более частиц встречаются, они продолжают своё случайное путешествие вместе; в этом случае обычно говорят, что частицы коалесцируют. Заметим, что каждая частица по-прежнему движется как цепь Маркова с теми же вероятностями перехода, за исключением того, что они не являются независимыми.

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

В $S$ есть два типа вершин: занятые частицами, которые мы будем называть корнями и которые не имеют исходящих нарисованных стрелок; и пустые, из которых исходит ровно одна нарисованная стрелка (стрелка, исходящая из $x$, будет указывать на вершину, в которую перепрыгнула последняя группа частиц, покинувшая $x$).
Существует как минимум один корень.
Из каждой вершины $x$ существует ровно один путь из нарисованных стрелок от $x$ к корню (этот путь имеет длину $0$, если $x$ сама является корнем). Таким образом, эта процедура индуцирует случайное разбиение $S$ на подмножества, где все точки, которые могут достичь одного и того же корня, находятся в одной компоненте разбиения. Каждая компонента тогда называется входящей арборесценцией.
Если мы будем считать, что нарисованные стрелки являются подмножеством множества исходных рёбер $S$, мы увидим, что рассматриваем подграф исходного графа, который содержит все вершины, но лишь некоторые из рёбер исходного графа. Более того, каждая входящая арборесценция (каждая компонента связности) имеет ровно на одно ребро меньше, чем число вершин, и как таковая является ациклической (нет замкнутых «нарисованных» путей).
Подграф с этими свойствами, точно описанными ниже в математических терминах, называется остовным входящим лесом (как объединение входящих арборесценций).

Если исходная цепь конечна и апериодична, и если мы подождём достаточно долго, все частицы встретятся, и мы увидим единственную входящую арборесценцию, случайно эволюционирующую во времени. Примечательно, что динамика входящих лесов (или одной входящей арборесценции), несмотря на сохранение воспоминаний о прошлой истории частиц (ребро, через которое они перепрыгнули в последний раз, покидая вершину), сама является цепью Маркова. Для этой «производной» цепи Маркова многие величины (например, инвариантная мера) могут быть записаны с помощью явных формул. Хотя эти формулы комбинаторно сложны, они дают выражения, поддающиеся анализу в определённых режимах, см. Упражнение 1.

Рисунок 1: Мы на самом деле не уточнили, движутся ли частицы все вместе на каждом шаге, или мы случайно выбираем частицу для перемещения на каждом шаге: эти процедуры дают немного разные результаты, но получающийся подграф является входящей арборесценцией в обоих случаях. Для простоты коалесценция представлена частицами/цветами с меньшими номерами, заменяющими частицы с большими номерами в том же узле. В момент времени $t=0$ каждая вершина является входящей арборесценцией. С течением времени входящие арборесценции (различаемые по цветам) коалесцируют, пока не останется лес, состоящий всего из одной входящей арборесценции, которая эволюционирует случайным образом (точное описание этой случайной динамики приведено ниже).

Арборесценции

Определение 1 (входящая арборесценция) Пусть $S$ — конечный ориентированный граф. Остовный входящий лес $\mathfrak{F}$ — это подграф $S$, такой что

$\mathfrak{F}$ содержит все вершины из $S$ (свойство остовности). В частности, мы отождествляем $\mathfrak{F}$ с подмножеством рёбер исходного графа.
Каждая вершина $x\in S$ имеет не более одной исходящей стрелки в $\mathfrak{F}$.
$\mathfrak{F}$ ацикличен.

Вершина $z\in S$, не имеющая входящих рёбер, называется листом $\mathfrak{F}$. Вершина $r \in S$, не имеющая исходящих рёбер в $\mathfrak{F}$, называется корнем. Множество вершин $x$, таких что $x\rightarrow r$ в $\mathfrak{F}$, называется корневой входящей арборесценцией¹, и $r$ является корнем этой входящей арборесценции.

Остовный входящий лес с единственным корнем $r$ называется остовной входящей арборесценцией с корнем в $r$. Эквивалентно, остовная входящая арборесценция с корнем в $r$ — это подграф $\theta$ графа $S$, такой что

$\theta$ содержит все вершины из $S$.
Для каждой вершины $x\in S\setminus \{r\}$ существует ровно одно исходящее ребро из $x$, тогда как из $r$ нет исходящих стрелок.
Для каждой вершины $x\in S$ существует ориентированный путь $x\rightarrow r$.

Чтобы получить представление, если мы изобразим данную цепь Маркова взвешенным ориентированным графом

то ниже представлены все остовные входящие арборесценции $\theta$ с корнем в $r=0$

Корневые остовные арборесценции — Рисунок 3

а ниже — все остовные леса из входящих арборесценций с двумя корнями, одним в $0$ и одним в $2$.

Примечание. Остовная входящая арборесценция содержит ровно $|S|-1$ рёбер и не содержит циклов. Более того, условие c. эквивалентно требованию, чтобы $\theta$ была слабо связной (т.е. связной, если игнорировать направление рёбер).

Множество $\Theta_x$ непусто тогда и только тогда, когда любой $y \in S$ может достичь $x$. Таким образом, для неприводимых цепей $\Theta_x$ непусто для всех $x$. И наоборот, если цепь имеет более одного замкнутого класса, $\Theta$ пусто, так как ни одно состояние не достижимо из всех остальных.

В частности, далее мы предполагаем, что исходная цепь Маркова имеет единственный замкнутый класс. Читатель также может считать, что цепь неприводима, поскольку невозвратные состояния (transient states) не играют существенной роли.

Примечание. Остовная корневая входящая арборесценция (или, более обще, остовный корневой лес) идентифицируется своими рёбрами, так как все вершины $S$ находятся во входящей арборесценции. Таким образом, мы пишем $e\in \theta$, обозначая ребро $e=(x,y)$ во входящей арборесценции $\theta$. Например, $\prod_{e\in \theta} p_e$ — это (корректная) запись для произведения вероятностей $p_{x,y}$ по всем рёбрам $e=(x,y)$ в арборесценции $\theta$.

Обозначим через $\Theta$ пространство корневых остовных входящих арборесценций, и для $r\in S$ пусть $\Theta_r$ будет пространством входящих арборесценций $\theta \in \Theta$ с корнем в $r$. $\Theta=\sqcup_{r\in S} \Theta_r$ является дизъюнктным объединением $\Theta_r$, и, следовательно, корректно определено отображение $\imath \colon \Theta \to S$, сопоставляющее каждой остовной корневой входящей арборесценции $\theta$ её корень $\imath(\theta)$.

Цепь Маркова последних прохождений

Мы хотим определить вероятности переходов (и, следовательно, цепь Маркова) на $\Theta$, следуя простой идее: когда цепь находится в состоянии (входящей арборесценции) $\theta$, мы смотрим на все рёбра, исходящие из корня $r$ арборесценции $\theta$. Затем с вероятностью $p_{r,y}$ мы переходим к новой входящей арборесценции (с корнем в $y$), полученной следующим образом: мы добавляем к $\theta$ ребро $(r,y)$ и удаляем единственное ребро, исходящее из $y$. Определим это более точно.

Для $\theta\in \Theta_r$ и $r'\in S$, таких что $p_{r,r'}>0$, определим $\theta^{r,r'}$ как граф, полученный из $\theta$ добавлением ориентированного ребра $(r,r')$ и удалением единственного ребра в $\theta$, исходящего из $r'$. Этот новый граф $\theta^{r,r'}$ обладает следующими свойствами:

Он содержит все вершины из $S$.
Из каждой вершины $x\in S\setminus\{r'\}$ исходит ровно одно ребро.
Из каждой вершины $x\in S$ существует ориентированный путь к $r'$. Действительно, либо в $\theta$ был путь из $x$ в $r$, проходящий через $r'$ (и в этом случае $x$ всё ещё связан с $r'$, поскольку удалённое ребро не использовалось в этом пути), либо в $\theta$ был путь из $x$ в $r$, не проходящий через $r'$ (и в этом случае тот же путь плюс ребро $(r,r')$ образуют путь из $x$ в $r'$).

Таким образом, $\theta^{r,r'}\in \Theta_{r'}$. Тогда мы определяем вероятности перехода на $\Theta$ как \[ q_{\theta,\theta'}= \begin{cases} p_{x,y} & \text{если $\theta \in \Theta_x$ и $\theta'=\theta^{x,y}$ для некоторых $x,y\in S$} \\ 0 & \text{иначе} \end{cases} \tag{1}\] и пусть $Q$ — соответствующий марковский оператор $Q=(q_{\theta,\theta'})$. Чтобы зафиксировать идеи, обозначим через $\mathbf{X}=(X_t)_{t\in \mathbb{N}}$ обычную цепь Маркова на $S$, а через $\boldsymbol{\xi}=(\xi_t)_{t\in \mathbb{N}}$ — обычную цепь Маркова на $\Theta$.

Один переход блуждания по входящим арборесценциям — Рисунок 5: Цепь Маркова на $\Theta$ работает следующим образом. Когда состоянием является входящая арборесценция $\theta$ слева, мы можем выбрать любую стрелку, исходящую из корня $0$, с вероятностью, заданной исходной цепью Маркова (пунктирные рёбра). Скажем, мы выбираем стрелку $(0,2)$ (красное пунктирное ребро). Тогда мы добавляем эту стрелку и удаляем ту, которая исходит из $2$. Результатом является входящая арборесценция справа.

Мы можем определить корневое отображение $\imath \colon \Theta \to S$, которое сопоставляет входящей арборесценции $\theta$ её корень $\imath(\theta)$. Важно отметить, что корень цепи Маркова на $\Theta$ совершает цепь Маркова на $S$ с вероятностями перехода, заданными исходными $p_{x,y}$. Более формально, для всех функций $f\colon S\to \mathbb{R}$ \[ Q (f\circ \imath) = (Pf)\circ \imath \tag{2}\]

Другими словами, мы можем сцепить цепи Маркова так, что $X_t=\imath(\xi_t)$. В частности, если $\mu$ является инвариантной мерой для $Q$ (то есть для цепи Маркова $\boldsymbol{\xi}$ на $\Theta$), то $m= \mu \circ \imath^{-1}$ инвариантна для $P$ (то есть для исходной цепи Маркова $\mathbf{X}$ на $S$).

Рисунок 6: Если мы посмотрим на корень цепи Маркова $\xi_t$ на $\Theta$, мы увидим исходную цепь Маркова $X_t$ на $S$ (с теми же вероятностями перехода). С другой стороны, ребро $(x,y)$ присутствует во входящей арборесценции $\theta\in \Theta$ тогда и только тогда, когда в последний раз, когда цепь Маркова $X_t$ посещала $x$, она перепрыгнула в $y$. Таким образом, входящая арборесценция $\xi_t$ кодирует информацию о последнем прохождении $\mathbf{X}$ вплоть до момента времени $t$.

Далее мы хотим проверить, что если исходная цепь Маркова неприводима, то таковой является и цепь Маркова на $\Theta$.

Утверждение 1 Предположим, что исходная цепь Маркова имеет единственный замкнутый класс ($\Theta$ пусто в противном случае). Цепь Маркова на $\Theta$ неприводима тогда и только тогда, когда каждое невозвратное состояние в исходной цепи Маркова имеет единственное исходящее ребро.

Прежде чем переходить к доказательству, введём некоторые обозначения и предварительный результат. Для данных $\theta\in \Theta$ и $x\neq \imath(\theta)$ обозначим через $e^{\theta,+}(x)$ единственное ребро, исходящее из $x$ в $\theta$, а через $e^{\theta,-}(x)$ — единственное ребро, входящее в $\imath(\theta)$ на пути $x\rightarrow \imath(\theta)$ в $\theta$ (последнее ребро этого пути).

Лемма 1 Предположим, что исходная цепь $\mathbf{X}$ неприводима. Тогда для любой $\theta \in \Theta$ и начальной точки $z\in S$ существует конечный путь в $S$, начинающийся в $z$ и заканчивающийся в $r$, такой что для всякого $x \neq r$ последний выход из $x$ на этом пути происходит по ребру $e^{(\theta,+)}(x)$, исходящему из $x$ в $\theta$.

Доказательство. Мы можем упорядочить точки в $S$ как $r=x_0,x_1,x_2,\ldots,x_{|S|-1}$, так, чтобы минимальное число шагов, необходимых для достижения $x_i$ из $r$, не убывало по $i$. Чтобы определить желаемый путь, сначала идём от $z$ к $r$, а затем строим путь рекурсивно, сцепляя $|S|-1$ циклов. Сначала идём от $r$ к $x_{|S|-1}$ по пути минимальной длины, а затем обратно к $r$, следуя единственному пути $x_{|S|-1}\rightarrow r$ в $\theta$. Затем продолжаем рекурсивно для $|S|-1$ циклов: $i$-й цикл начинается в $r$, идёт к $x_{|S|-i}$ по пути минимальной длины, затем обратно к $r$ вдоль единственного пути $x_{|S|-i} \rightarrow r$ в $\theta$. Поскольку мы следуем путям минимальной длины, в $i$-м цикле путь никогда не проходит через $x_k$ для $k > |S|-i$, тогда как на обратном пути $x_{|S|-i}\rightarrow r$ мы используем только рёбра из $\theta$. Следовательно, для каждого $i$ в последний раз, когда путь проходил через $x_i$, он покидал $x_i$ по ребру из $\theta$.

Доказательство (Утверждение 1). Сначала докажем, что если цепь неприводима, каждое невозвратное состояние имеет единственное исходящее ребро. Поскольку существует единственный замкнутый класс $C$, невозвратные состояния — это состояния из $S \setminus C$, и в исходном графе они обязательно имеют по крайней мере одно исходящее ребро (будучи невозвратными). Все элементы $\Theta$ имеют корни в $C$ (поскольку $\Theta_x$ пусто для невозвратного $x$). Поскольку $C$ замкнут, исходящие рёбра в $C$ указывают на элементы самого $C$. Таким образом, цепь Маркова на $\Theta$ никогда не меняет рёбер, исходящих из невозвратных состояний. А именно, если $\theta \rightarrow \theta'$, все исходящие рёбра в невозвратных состояниях одинаковы для $\theta$ и $\theta'$. Следовательно, если блуждание по $\Theta$ неприводимо, каждое невозвратное состояние имеет единственное исходящее ребро.

Далее докажем, что если каждое невозвратное состояние имеет единственное исходящее ребро (и есть единственный замкнутый класс), то эти рёбра являются частью каждой входящей арборесценции в $\Theta$, и, таким образом, достаточно ограничиться динамикой на замкнутом классе. Другими словами, достаточно доказать, что если исходная цепь неприводима, то цепь на $\Theta$ неприводима. Для этого рассмотрим путь $(\theta_0,\theta_1,\ldots)$ в $\Theta$ и путь его корня $r_t:=\imath(\theta_t)$. Для данного $t\ge 0$ ребро $(x,y)$ находится в $\theta_t$ тогда и только тогда, когда:

$(x,y)$ было в $\theta_0$ и корень никогда не проходил через $x$ до момента $t$: $r_s\neq x$ для $s\le t$.
в последний (наибольший) момент времени $s<t$, когда $r_s=x$, он покинул $x$ через $y$. Другими словами, $r_{s_x+1}=y$, где $s_x=\max\{s<t : r_s=x \}$.

Следовательно, для любой фиксированной начальной входящей арборесценции $\theta_0$ и целевой $\theta$ мы можем использовать конечный путь $(z_0,z_1,\ldots,z_N)$, построенный в Лемма 1, и следовать переходам $\theta_1=\theta_0^{z_0,z_1},\ldots, \theta_t=\theta_{t-1}^{z_{t-1},z_t},\ldots$. Корень посетит все элементы $S$, покидая их в последний раз по ребру из $\theta$, и, таким образом, $\theta_N=\theta$.

Явная инвариантная мера

Утверждение 2 Мера \[ \mu_\theta:= \prod_{e\in \theta} p_{e} \tag{3}\] является инвариантной для цепи Маркова на $\Theta$. В частности, мера \[ m_x:= \sum_{\theta \in \Theta_x} \prod_{e\in \theta} p_{e} \] является инвариантной для цепи Маркова на $S$.

Примечание. Для каждой $\theta \in \Theta$, с корнем, скажем, в $r=\imath(\theta)$, существует взаимно однозначное соответствие между рёбрами $(r,y)$, исходящими из $r$ в исходном графе (с $p_{r,y}>0$), и входящими арборесценциями $\theta'$, такими что $q_{\theta',\theta}>0$. Действительно, мы можем сопоставить ребру $(r,y)$ входящую арборесценцию $\theta'$, полученную добавлением ребра $(r,y)$ к $\theta$ и удалением ребра $e^{\theta,-}(y)$. Это отображение взаимно однозначно, и, в обозначениях Уравнение 1, $\theta=(\theta')^{r,y}$. В частности \[ \sum_{\theta' : q_{\theta',\theta}>0} p_{e^{\theta',+}(r)}=\sum_{y\in S} p_{r,y}=1 \tag{4}\]

Доказательство (Утверждение 2). Зафиксируем $\theta\in \Theta$ и скажем, что её корнем является $r\in S$. Нам нужно доказать, что \[ \sum_{\theta'\in \Theta} \mu_{\theta'} q_{\theta',\theta} = \mu_\theta \] В левой части слагаемые в сумме с $q_{\theta',\theta}=p_{\imath(\theta'),r}>0$ соответствуют всем арборесценциям $\theta'$, которые могут достичь $\theta$ за один шаг (с положительной вероятностью). То есть тем арборесценциям $\theta'$, для которых $\theta$ получается из $\theta'$ добавлением ребра $(\imath(\theta'),r)$ и удалением единственного ребра, исходящего из $r$ в $\theta'$, обозначаемого $e^{\theta'}(r)$. Тогда, согласно Уравнение 3, имеем \[ \mu_{\theta'} q_{\theta',\theta}= \mu_{\theta} p_{e^{\theta'}(r)} \] Следовательно, с учётом Уравнение 4 \[ \sum_{\theta' \in \Theta} \mu_{\theta'} q_{\theta',\theta}= \mu_{\theta} \sum_{\theta' \in \Theta} p_{e^{\theta'}(r)}= \mu_\theta \] Таким образом, $\mu_\theta$ инвариантна для цепи Маркова на $\Theta$.

Поскольку $\imath$ проецирует цепь на $\Theta$ в исходную цепь на $S$, см. Уравнение 2, $m=\mu \circ \imath^{-1}$ инвариантна для цепи на $S$.

Дополнительные Задачи

Упражнение 1 Рассмотрим неприводимую цепь Маркова на конечном пространстве состояний $S$ с вероятностями перехода $p^0_{x,y}$. Пусть $c(x,y)\in \mathbb{R}$ определена для всех рёбер $(x,y)$, таких что $p_{x,y}>0$. Зафиксируем $\beta>0$ и определим наклонённые вероятности перехода

\[ p^{\beta}_{x,y}:= \frac{e^{-\beta c(x,y)}}{Z_x^\beta} p^0_{x,y} \]

Определите значение $Z_x^\beta$ и проверьте, что цепь Маркова с вероятностями перехода $p^\beta_{x,y}$ остаётся неприводимой.
Объясните, почему мы можем предполагать, что $\min_{y\st p^0_{x,y}>0} c(x,y)=0$, и проверьте, что в этом случае \[ \inf_y p^0_{x,y} \le Z_x^\beta \le 1 \]
Пусть $m^\beta$ — инвариантная вероятностная мера, ассоциированная с вероятностями перехода $p^\beta$. Охарактеризуйте предел $\lim_{\beta\to \infty} m^\beta$. Подсказка: Для простоты предположите, что значения $\sum_{e\in \theta} c(e)$ различны для различных $\theta\in\Theta$, где $\Theta$ — пространство входящих остовных арборесценций с корнем.
Дайте явный ответ в случае $c(x,y)=(V(y)-V(x))^+$, где $V\colon S\to \mathbb{R}$ — заданная инъективная функция, а для $a\in \mathbb{R}$, $a^+=\max(a,0)$. Подсказка: Для простоты предположите, что $p^0_{x,y}>0$ всякий раз, когда $p^0_{y,x}>0$.

Решение

Поскольку $p^{\beta}_{x,\cdot}$ является вероятностью, имеем \[ Z_x^\beta:=\sum_y e^{-\beta c(x,y)} p^0_{x,y} \] Цепь Маркова остаётся неприводимой, так как $p^{\beta}_{x,y}>0$ тогда и только тогда, когда $p^{0}_{x,y}>0$.
Если мы заменим $c(x,y)$ на $c(x,y)-a(x)$, то $p^{\beta}_{x,y}$ не изменится, независимо от $a(x)$. Следовательно, для упрощения вычислений мы можем взять $a(x)=\min_y c(x,y)$. Другими словами, мы просто предполагаем, что $\min_y c(x,y)=0$. В частности, \[ \inf_y p^0_{x,y} \le \max_y e^{-\beta c(x,y)} p^0_{x,y} \le Z_x^\beta \le \sum_y e^{-0} p^0_{x,y}=1 \]
Мы знаем, что \[ m^\beta_x= c^\beta \sum_{\theta \in \Theta_x} w^\beta(\theta), \qquad w^\beta(\theta):= \prod_{e\in \theta} p^\beta_e \] где $c^\beta>0$ — подходящая нормировочная константа (которая представляет собой ту же сумму по $\theta\in \Theta$). Используя определение $p^\beta_{x,y}$, имеем \[ m^\beta_x= c^\beta \sum_{\theta \in \Theta_x} \frac{e^{-\beta\sum_{e\in \theta} c(e)}}{\prod_{y\neq x} Z^\beta_y} w^0(\theta) \] где произведение в знаменателе пробегает все $y\in S$, из которых есть исходящее ребро, а именно все $y\in S$, кроме корня $x$. Для $Z^\beta:=\prod_x Z^\beta_x$ и $c(\theta):= \sum_{e\in \theta} c(e)$: \[ m^\beta_x= \frac{c^\beta}{Z^\beta} \sum_{\theta \in \Theta_x} Z^\beta_x e^{-\beta c(\theta)} w^0(\theta) \] Мы знаем, что для неприводимой цепи $\Theta_x$ непусто для любого $x\in S$. И просто оценивая сумму наибольшим слагаемым (как выше), имеем \[ Z^\beta_x \max_{\theta \in \Theta_x} e^{-\beta c(\theta)} w^0(\theta) \le m^\beta_x \frac{Z^\beta}{c^\beta} \le |\Theta_x| Z^\beta_x \max_{\theta \in \Theta_x} e^{-\beta c(\theta)} w^0(\theta) \] и, таким образом, используя оценку из пункта b, \[ \min_y p^0_{x,y} \min_{\theta\in \Theta_x} w^0(\theta) e^{-\beta \min_{\theta\in \Theta_x} c(\theta)} \le m^\beta_x \frac{Z^\beta}{c^\beta} \le |\Theta_x| \max_{\theta\in \Theta_x} w^0(\theta) e^{-\beta \min_{\theta\in \Theta_x} c(\theta)} \]

Это означает, что $m^\beta_x$ концентрируется (экспоненциально быстро при $\beta\to \infty$) в точке $x$, которая несёт минимальную остовную арборесценцию для стоимости $c(x,y)$, то есть в корне дерева $\theta$, минимизирующего $c(\theta)$. Действительно, для таких $x$ и $y\neq x$, $m^\beta_y/m^\beta_x\to 0$ при $\beta\to \infty$.
Мы хотим показать, что в случае $c(x,y)=(V(y)-V(x))^+$ корнем минимальной остовной арборесценции является минимизатор $V(\cdot)$ (который единственен, так как мы предположили, что $V$ инъективна). В этом случае можно привести комбинаторное доказательство, используя $c(x,y)-c(y,x)=V(y)-V(x)$. Вместо этого приведём доказательство с использованием цепей Маркова, эффективно используя тот факт, что минимальная остовная арборесценция не зависит от значений $p^0_{x,y}$, а только от рёбер, на которых эта вероятность отлична от нуля.

Сначала предположим, что инвариантная мера $m^0$ цепи $(p^0_{x,y})$ обратима, тогда $m^\beta_x:= c^\beta e^{-\beta V(x)} Z^\beta_x m^0_x$ обратима для $(p^\beta_{x,y})$, так как \[ m^\beta_x p^\beta_{x,y}= Z^\beta_x e^{-\beta V(x)}\frac{e^{-\beta (V(y)-V(x))^+}}{Z^\beta_x} m^0_x p^0_{x,y} = e^{-\beta \max(V(x),V(y))} m^0_x p^0_{x,y} = e^{-\beta \max(V(x),V(y))} m^0_y p^0_{y,x}= m^\beta_y p^{\beta}_{y,x} \] Таким образом, поскольку $V(x)+(V(y)-V(x))^+=\max(V(y),V(x))$, рассуждая как выше, \[ m^\beta_x = c^\beta m^0_x \sum_y e^{-\beta \max(V(y),V(x))} p^0_{x,y} \] концентрируется в точках $x$, минимизирующих \[ x\mapsto \min_{y \st p^0_{x,y}>0} \max(V(y),V(x)) \] В частности, если $p^0_{x,x}>0$, мера концентрируется на минимизаторе $V(x)$.

Если $m^0$ не обратима, мы можем заменить $p^0_{x,y}$ на $q^0_{x,y}:=p^0_{x,y}+p^0_{y,x}m^0_y/m^0_x$ (для которой $m^0$ обратима) без изменения минимальной остовной арборесценции (которая зависит только от $c(x,y)$), поэтому ответ не меняется даже когда $m^0$ не обратима.

Упражнение 2 Рассмотрим неприводимую цепь Маркова на конечном пространстве состояний $S$ с вероятностями перехода $(p_{x,y})$. Напомним, что мы рассматриваем $S$ как граф, где рёбрами являются $e=(x,y)$, такие что $p_{x,y}>0$. Весом входящего остовного леса с корнями $F$ называется произведение \[ w(F):= \prod_{e\in F} p_e \] Для непустого $A\subset S$, пусть $\mathfrak{F}_A$ — множество входящих остовных лесов с корнями, множеством корней которых является в точности $A$. Для $x\in S$ и $r \in A$, определим $\mathfrak{F}_A(x\rightarrow r)$ как множество лесов $F\in \mathfrak{F}_A$, таких что $x$ находится во входящей арборесценции с корнем в $r$ (другими словами, следуя по единственному пути в $F$, выходящему из $x$, можно достичь $r \in A$).

Пусть теперь $r\in A \subset S$. Так как цепь неприводима и конечна, $\mathbb{P}(\tau_A<\infty)=1$, и пусть $h(x)\equiv h_{r,A}(x):=\mathbb{P}_x(X_{\tau_A}=r)$. Докажите, что \[ h(x) = \frac{\sum_{F \in \mathfrak{F}_{A}(x\rightarrow r)} w(F)}{\sum_{F \in \mathfrak{F}_{A}} w(F)} \tag{5}\]

Решение

Так как цепь Маркова неприводима и имеет инвариантную меру (поскольку пространство состояний конечно), $h$ является единственным решением задачи для неизвестной $u$ \[ (I-\ind{A^c} P)u= \ind{r} \] Пусть $g(x)$ — правая часть Уравнение 5, покажем, что $g$ также удовлетворяет этому уравнению, следовательно $g=h$.

Очевидно, $g(x)=\ind{r}(x)$ для $x\in A$, поэтому нам нужно лишь проверить, что $g(x)=(Pg)(x)$ для $x\notin A$. Знаменатель $\sum_{F \in \mathfrak{F}_{A}} w(F)$ сокращается в обеих частях этого уравнения, так что остаётся проверить \[ \sum_{G \in \mathfrak{F}_{A}(x\rightarrow r)} w(G) =^? \sum_y p_{x,y} \sum_{F \in \mathfrak{F}_{A}(y\rightarrow r)} w(F), \qquad x\notin A \] Так как $\sum_{y}p_{x,y}=1$, мы можем записать это как \[ \sum_{z\neq x} \sum_{G \in \mathfrak{F}_{A}(x\rightarrow r)} p_{x,z} w(G) =^? \sum_{y\neq x} \sum_{F \in \mathfrak{F}_{A}(y\rightarrow r)} p_{x,y} w(F), \qquad x\notin A \] Мы можем сопоставить слагаемые в обеих частях, построив биекцию между индексами $(z,G)$ (при условии $x\rightarrow r$ в $G$) слева и $(y,F)$ (при условии $y\rightarrow r$ в $F$) справа следующим образом.

Если $z\rightarrow r$ в $G$, то мы берём $y=z$ и $G=F$, другими словами, эти члены присутствуют в обеих частях.
Если $z\not \rightarrow r$, то $(x,z)$ не содержится в $G$. Мы сопоставляем такую пару $(z,G)$ элементу $(y,F)$ в правой части, где $y$ — единственная вершина, такая что $(x,y)\in G$; а $F$ — это лес, полученный из $G$ удалением $(x,y)$ и добавлением $(x,z)$.

Это биекция между слагаемыми в левой части и правой части, и очевидно, что $p_{x,z} w(G)= p_{x,y} w(F)$.

Биекция лесов — Рисунок 7: Пара $(z,G)$ с $G \in \mathfrak{F}_{A}(x\rightarrow r)$ и $z\not\rightarrow r$, биективно отображается в $(y,F)$ с $F \in \mathfrak{F}_{A}(y\rightarrow r)$, просто меняя местами последователя $x$.

Сноски

Арборесценция: этимология происходит от латинских arbor (дерево), arborescere (расти в дерево), слов с праиндоевропейскими корнями. В математике термин дерево обычно относится к неориентированным ациклическим графам, тогда как арборесценция является ориентированным эквивалентом. Обычно арборесценция или исходящая арборесценция имеет рёбра, направленные наружу от корня, тогда как входящая арборесценция (наш случай) имеет рёбра, направленные «к» корню. Входящие леса и входящие арборесценции иногда называют анти-лесами и анти-арборесценциями в теории графов, подчеркивая направление рёбер.↩︎