Листок 2

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

Что разрешено делать:

Что вы обязаны делать:

Что запрещено делать:

Задачи

Упражнение 1 Пусть \(P\) — марковский оператор неприводимой цепи Маркова на конечном пространстве состояний \(S\). Пусть \(m\) — её инвариантная мера, а \(P^\dagger\) — сопряжённый оператор к \(P\) в \(L^2(m)\).

  1. Проверьте, что если \(P\), \(Q\) — марковские операторы, то \(PQ\) и \(\alpha P+(1-\alpha)Q\) также являются марковскими операторами. В частности, \(PP^\dagger\) и \(P^2\) — марковские операторы.
  2. Найдите инвариантную меру для \(PP^\dagger\) и \(P^2\). Приведите пример, где \(P\) неприводима, но \(PP^\dagger\) и \(P^2\) не являются таковыми.
  3. Приведите пример, где \(P\) неприводима, но \(P^2\) и \(PP^\dagger\) не являются неприводимыми.
  4. Докажите, что если \(P\) неприводима и апериодична, то \(P^2\) неприводима и апериодична.
  5. Докажите, \(PP^\dagger\) апериодична и каждый класс общения закрыт.
  6. Предположим, что \(P\) неприводима и апериодична. Пусть \(X_t\) и \(Y_t\) — цепи Маркова с марковскими операторами \(P^2\) и \(PP^\dagger\) соответственно; докажите, что \(X_t\) сходится к своему «равновесию» быстрее, чем \(Y_t\), в следующем смысле. Пусть \(\mu_t^x\) (соответственно \(\nu_t^x\)) — закон распределения \(X_t\) при условии \(X_0=x\) (соответственно \(Y_t\) при \(Y_0=x\)). Докажите, что \[ \sup_x \lim_{t\to\infty} \tfrac{1}{t} \log \| \mu_t^x - m\|_{TV} \le \sup_x \lim_{t\to\infty} \tfrac{1}{t} \log \| \nu_t^x - m\|_{TV} \]
  1. Пусть \(R=PQ\), тогда \(r_{x,z}=\sum_y p_{x,y} q_{y,z}\). Меняя порядок суммирования, имеем \(r_{x,z}\ge 0\) и \(\sum_z r_{x,z}= \sum_y p_{x,y} \sum_z q_{y,z}=\sum_y p_{x,y}=1\). Что касается выпуклой комбинации, доказательство следует непосредственно из линейности.
  2. Инвариантной мерой всех этих операторов является \(m\). В общем случае, если \(P,Q\) имеют одну и ту же инвариантную меру, то \(m((PQ)f)=m(P(Qf))=m(Qf)=m(f)\). Таким образом, \(m\) инвариантна для \(PQ\).
  3. Мы можем взять единственный цикл \(S=\mathbb{Z}_{2k}\) с чётным числом точек, \(P\) соответствует движению по часовой стрелке с вероятностью \(1\), \(p_{x,x+1}=1\) (суммы понимаются \(\pmod{2k}\)). Тогда \(P\) неприводима, так как существует путь, соединяющий любые две точки. \(PP^\dagger\) соответствует выполнению одного шага по часовой стрелке и одного против часовой стрелки, то есть \(PP^\dagger=I\), блуждание просто не движется. \(P^2\) соответствует выполнению двух шагов по часовой стрелке \(p^{(2)}_{x,x+2}=1\). Таким образом, не существует пути, соединяющего точки с разной чётностью.
  4. Для неприводимой апериодической цепи на конечном пространстве состояний существует достаточно большое \(T\), такое что \(p^{(t)}_{x,y}>0\) для всех \(t>T\) и \(x,y\in S\). В частности, то же самое верно, если заменить \(T\) на \(T'=\lceil T/2 \rceil\), для элементов \(P^2\).
  5. Обозначим через \((q_{x,y})\) элементы \(Q=PP^\dagger\). \(q_{x,z}>0\) тогда и только тогда, когда существует \(y\in S\), такое что \(p_{x,y},p_{z,y}>0\). В частности, \(q_{x,z}>0\) тогда и только тогда, когда \(q_{z,x}>0\) и \(q_{x,x}>0\) для всех \(x\in S\) (так как каждая точка \(x\) имеет по крайней мере одного преемника \(y_x\), такого что \(p_{x,y_x}>0\)). В частности, каждый класс сообщающихся состояний \(Q\) замкнут.
  1. Согласно теореме об экспоненциальной сходимости, нам нужно проверить, что \(|\lambda_1(P^2)|\le |\lambda_1(PP^\dagger)|\), где \(\lambda_1(Q)\) — наибольшее (по модулю) собственное число неприводимого марковского оператора \(Q\), за исключением \(\lambda_0=1\); или, что эквивалентно, наибольшее собственное число \(Q\), ограниченного на функции \(f\) с \(m(f)=0\), где \(m\) — инвариантная мера \(Q\).

Для \(P^2\) имеем \(\lambda_1(P^2)=\lambda_1(P)^2=\overline{\lambda_1(P^\dagger)}^2\). Возьмём \(f_1\) — ассоциированную (комплексную) собственную функцию (с \(m(f_1)=0\)) оператора \(P^\dagger\), так что \(P^\dagger f_1=\overline{\lambda_1(P^\dagger)}f_1\). Тогда, так как \(PP^\dagger\) симметричен, \(\lambda_1(PP^\dagger)>0\), и, обозначая через \(\langle \cdot,\cdot \rangle\) эрмитово скалярное произведение в \(L^2(m)\), имеем \[ |\lambda_1(PP^\dagger)| = \sup_{f\,\st m(f)=0} \frac{\langle f, PP^\dagger f \rangle}{m(|f|^2)}=\sup_{f\,\st m(f)=0} \frac{\langle P^\dagger f, P^\dagger f \rangle}{m(|f|^2)} \ge \frac{\langle P^\dagger f_1, P^\dagger f_1 \rangle}{m(|f_1|^2)} = \overline{\lambda_1(P^\dagger)} \lambda_1(P^\dagger)= |\lambda_1(P^2)| \]

Упражнение 2 Рассмотрим неприводимую цепь Маркова на конечном пространстве состояний \(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} \]

  1. Определите значение \(Z_x^\beta\) и проверьте, что цепь Маркова с вероятностями перехода \(p^\beta_{x,y}\) остаётся неприводимой.
  2. Объясните, почему мы можем предполагать, что \(\min_{y\st p^0_{x,y}>0} c(x,y)=0\), и проверьте, что в этом случае \[ \inf_y p^0_{x,y} \le Z_x^\beta \le 1 \]
  3. Пусть \(m^\beta\) — инвариантная вероятностная мера, ассоциированная с вероятностями перехода \(p^\beta\). Охарактеризуйте предел \(\lim_{\beta\to \infty} m^\beta\). Подсказка: Для простоты предположите, что значения \(\sum_{e\in \theta} c(e)\) различны для различных \(\theta\in\Theta\), где \(\Theta\) — пространство входящих остовных арборесценций с корнем.
  4. Дайте явный ответ в случае \(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\).

  1. Поскольку \(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\).

  2. Если мы заменим \(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 \]

  3. Мы знаем, что \[ 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\).

  4. Мы хотим показать, что в случае \(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\) не обратима.

Упражнение 3 Рассмотрим неприводимую цепь Маркова на конечном пространстве состояний \(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{1}\]

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

Биекция лесов
Рисунок 1: Пара \((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\).