Глава 7.3. Избранные темы: Количественные предельные теоремы
Предположим, мы наблюдаем простое случайное блуждание на \(\mathbb{Z}\) и отслеживаем количество раз, которое частица пересекает (направленное) ребро (например, добавляя одну карту в стопку при каждом пересечении). С течением времени на больших временных масштабах мы будем наблюдать формирование случайного профиля высоты стопки карт.
Например, в симметричном случае мы видели, что для этой конкретной цепи Маркова число пересечений ребра \((n,n+1)\) (во время экскурсии из \(0\)) является процессом Гальтона-Ватсона (индексированным \(n\)). Таким образом, пока мы наблюдаем за цепью в течение длительного времени, кривая будет распределена как сумма независимых процессов Гальтона-Ватсона. Более того, в этом примере по положению случайного блуждания в конечный момент времени можно точно определить разность между числом пересечений ребра \((n,n+1)\) и числом пересечений \((n+1,n)\) (т.е. разность между синими и оранжевыми столбцами на видео). Например, если конечное положение \(X_T=5\), то частица пересекла рёбра \((n,n+1)\) и \((n+1,n)\) при \(n<0\) или \(n\ge 5\) одинаковое число раз; в то время как при \(0 \le n\le 4\) ребро \((n,n+1)\) было пересечено на один раз больше, чем \((n+1,n)\).
Более интересным примером является случайное блуждание на \(\mathbb{Z}_N\).
В этом случае разность между синими и оранжевыми столбцами (см. видео) даст нам число оборотов, совершённых частицей по циклу (петле) — информацию, которую невозможно восстановить, зная только конечное положение.
Если мы посмотрим на цепи Маркова на большом графе, встроенном в многообразия более высокой размерности, то все станет интереснее.
Предварительные сведения о марковских потоках
В общем случае для цепи Маркова на конечном или счётном пространстве состояний \(S\) мы можем рассмотреть случайную наблюдаемую, которая считает, сколько раз цепь проходит через данное ребро.
Обозначения для вероятностей на рёбрах
Обозначим через \(E\) пространство рёбер в графе, индуцированном переходными вероятностями \((p_{x,y})\), то есть \(E:=\{(x,y) \st p_{x,y}>0\}\). Как обычно, предполагаем, что \(p_{x,y}\) зафиксированы с самого начала, и обозначаем через \(e\in E\) произвольное ребро. Как и вероятности на вершинах, вероятность на пространстве рёбер отождествляется с набором \((\jmath_e)_{e\in E}\), где \(\jmath_e\ge 0\) и \(\sum_e \jmath_e=1\). Пространство \(\mathcal{P}(E)\) вероятностных мер на \(E\) снабжено своим собственным расстоянием Леви; если \(|E|\) конечно, это обычная топология симплекса \(\{\jmath_e\ge 0, \sum_e \jmath_e=1\}\), рассматриваемого как подмножество \(\mathbb{R}^{|E|}\), или, в более общем случае (если \(E\) счётно), расстояние Леви топологически эквивалентно (после нумерации рёбер \(\{e_0,e_1,\ldots\}\)) \[ d(\jmath,\jmath')=\sum\nolimits_{k} |\jmath_{e_k}- \jmath_{e_k}'| 2^{-k} \tag{1}\] То есть последовательность \(\jmath^n\) сходится к \(\jmath\) тогда и только тогда, когда сходятся все значения \(\jmath^n_e\).
Для \(\mu \in \mathcal{P}(S)\) и \(f\colon S\to \mathbb{R}\) мы обычно обозначаем интеграл \(\mu(f)=\sum_x \mu_x f(x)\). Аналогично для \(\jmath \in \mathcal{P}(E)\) и \(\xi \colon E\to \mathbb{R}\) обозначим \(\jmath(\xi):=\sum_{e\in E} \jmath_e \xi(e)\).
Если \(\jmath\) — вероятность на рёбрах, то обозначим через \(\mu^\jmath \in \mathcal{P}(S)\) вероятность на вершинах, задаваемую формулой \[ \mu^\jmath_x=\sum_{y \st (x,y)\in E} \jmath_{x,y} \tag{2}\] а через \(p^\jmath\) — переходные вероятности \[ p^\jmath_{x,y}=\jmath_{x,y}/\mu^\jmath_{x} \tag{3}\]
Потоки как вероятности на рёбрах
Приведённый выше пример побуждает нас рассмотреть меру на рёбрах \[ \begin{aligned} & J^T:= \frac{1}{T} \sum\nolimits_{t=0}^{T-1} \delta_{(X_t,X_{t+1})} \\ & J^T_{x,y} \equiv \frac{|\{t \le T-1 \st X_t=x, X_{t+1}=y \}|}{T} \end{aligned} \] Другими словами, \(J^T_e\) считает количество раз, которое цепь прошла через (направленное) ребро \(e\) до момента времени \(T\), нормированное на общее число скачков (то есть \(T\)). \(J^T\) является вероятностной мерой на пространстве рёбер \(E\) пространства \(S\). Мы можем рассматривать \(J^T\) как отображение на пространстве путей Скорохода \[ J^T \colon D(S)\to \mathcal{P}(E) \] сопоставляющее каждому пути вероятность на рёбрах в соответствии с тем, сколько раз путь \(\mathbf{X}\) пересекал каждое ребро до момента времени \(T\).
Примечание. \(J^T\) — это более богатая наблюдаемая величина, чем мера пребывания \(\pi^T:=\sum_{t=0}^{T-1} \delta_{X_t}\), которая кодирует (нормированное) число посещений цепью каждой вершины. В самом деле \[ \mu^{J^T}_x:=\sum\nolimits_{y} J^T_{x,y}=\pi^T_x \tag{4}\] поэтому мы можем восстановить \(\pi^T\) из \(J^T\). Если рассматривать \(J^T\) как вероятность на \(S\times S\), это говорит нам о том, что \(\pi^T\) — это просто её проекция на первую компоненту. Из-за сходства с 1-потоками на многообразиях, иногда \(J^T\) называют потоком (current).
Задачи и интересующие оценки
Мы уже знаем, что \(\pi^T\) сходится к инвариантной мере \(m\) (для неприводимых, положительно возвратных цепей) при \(T\to \infty\). Каждый раз, когда цепь посещает вершину \(x\), существует вероятность \(p_{x,y}\) пересечь ребро \((x,y)\); и при \(T\to \infty\) (неприводимая, положительно возвратная) цепь Маркова \(\mathbf{X}\) будет посещать \(x\) долю времени \(m_x\). Таким образом, мы ожидаем, что \[ \lim_T J^T_{x,y}=m_x p_{x,y} \tag{5}\] что действительно согласуется с Уравнение 4.
В этой главе мы хотим получить более количественный результат о сходимости для \(J^T\), который, в свою очередь, повлечёт за собой Уравнение 5, а через Уравнение 4 — и аналогичные оценки для \(\pi^T\). Это глубоко мотивированная задача; рассмотрим пример, который может дать некоторое представление1.
Пример 1 В протоколе управления передачей (TCP) для интернет-коммуникации сервер \(x\) выбирает следующий напрямую подключенный сервер \(y\) для отправки полученного пакета данных в зависимости от конечного пункта назначения пакета (это определяется по маске подсети, так что пакет действительно проходит через множество серверов и не следует по оптимальному геодезическому пути). Справедливо предположить, что пакеты совершают цепь Маркова с некоторыми переходными вероятностями \(p_{x,y}\). Пара \((x,y)\) напрямую соединённых серверов будет иметь максимальную пропускную способность \(C_{x,y}\), определённую для малого промежутка времени, и передача не удастся, если эта способность будет превышена. Если мы наблюдаем за трафиком в течение некоторого периода времени, мы можем очень точно оценить \(p_{x,y}\) и, возможно, захотим узнать, как назначить пропускные способности \(C_{x,y}\), чтобы минимизировать вероятность сбоев. То есть нам нужно знать для произвольного распределения \(C_{x,y}\) \[ \mathbb{P}(J^T_{x,y} \le C_{x,y}, \forall x,y \in S) \approx ? \]
Основные результаты: Формулировки
Определение 1 Вспомним Уравнение 2, Уравнение 3 и определим функцию \(I\colon \mathcal{P}(E)\to [0,\infty]\) \[ I(\jmath):= \begin{cases} \sum\nolimits_{x,y} \mu^{\jmath}_x p^\jmath_{x,y} \log(p^\jmath_{x,y}/p_{x,y}) & \text{если $\sum_y \jmath_{x,y}=\sum_y \jmath_{y,x}$} \\ +\infty & \text{иначе} \end{cases} \tag{6}\]
Определение 2 (Функционал Донскера-Варадхана) Определим функцию2 \(I_{DV}\colon \mathcal{P}(E)\to [0,\infty]\) \[ I_{DV}(\mu):= \inf \{I(\jmath), \jmath \in \mathcal{P}(E) \st \mu^\jmath =\mu \} \tag{7}\]
В Упражнение 3, Упражнение 4 и Упражнение 5 приведены более явное выражение и некоторые свойства \(I_{DV}\).
Примечание. Принимая во внимание определение относительной энтропии \(H(\cdot|\cdot)\), функционал \(I(\cdot)\) можно также записать как \[ I(\jmath):= \begin{cases} \sum\nolimits_x \mu^\jmath_x H(p^\jmath_{x,\cdot}|p_{x,\cdot}) & \text{если $\sum_y \jmath_{x,y}=\sum_y \jmath_{y,x}$} \\ +\infty & \text{иначе} \end{cases} \tag{8}\]
Наш основной результат заключается в следующем:
Теорема 1 Рассмотрим неприводимую цепь Маркова на конечном пространстве состояний. Тогда для любого замкнутого множества \(\mathcal{C}\subset \mathcal{P}(E)\) выполняется \[ \mathbb{P}(J^T\in \mathcal{C}) \le e^{-T \inf_{\jmath\in \mathcal{C}} I(\jmath) + o(T)} \tag{9}\]
Это, в свою очередь, влечёт экспоненциальную версию Уравнение 5 (по вероятности) и, через Уравнение 4, аналогичный результат для \(\pi^T\).
Следствие 1 Определим типичный поток как \(\bar{\jmath}_{x,y}:=m_x p_{x,y}\). Тогда, при тех же условиях, что и в Теорема 1, \(I(\jmath)=0\) тогда и только тогда, когда \(\jmath=\bar{\jmath}\). В частности, для каждого \(\varepsilon>0\) существует константа \(c_\varepsilon>0\), такая что \[ \mathbb{P}\left(\sum\nolimits_{e \in E} |J^T_e - \bar{\jmath}_e| \ge \varepsilon \right) \le e^{-T (c_\varepsilon + o(1))} \]
Следствие 2 При тех же предположениях, что и в Теорема 1, для любого замкнутого множества \(\mathcal{C}\subset \mathcal{P}(S)\) выполняется \[ \mathbb{P}(\pi^T\in \mathcal{C}) \le e^{-T \inf_{\mu\in \mathcal{C}} I_{\mathrm{DV}}(\mu) + o(T)} \tag{10}\]
Можно доказать (что выходит за рамки данной заметки), что \(I\) оптимальна в следующем смысле: для каждого измеримого \(\mathcal{A} \subset \mathcal{P}(E)\) \[ e^{-T \inf_{\jmath\in \mathrm{Interior}(\mathcal{A})} I(\jmath) + o(T)} \le \mathbb{P}(J^T\in \mathcal{A}) \le e^{-T \inf_{\jmath\in \mathrm{Closure}(\mathcal{A})} I(\jmath) + o(T)} \] (и аналогичное утверждение справедливо для \(I_{DV}\)), где \(\mathrm{Interior}\) — внутренность, а \(\mathrm{Closure}\) — замыкание множества.
Примечание. Условие \(\sum_y \jmath_{x,y}=\sum_y \jmath_{y,x}\) означает, что мера \(\mu^\jmath\) инвариантна для индуцированных переходных вероятностей \(p^\jmath\). Таким образом, Теорема 1 можно интерпретировать следующим образом: вероятность того, что наблюдаемый поток \(J^T\) флуктуирует вблизи данного \(\jmath\), убывает экспоненциально как \(\exp(-T I(\jmath))\). Функция уклонений \(I(\jmath)\) представляет собой относительную энтропию модифицированной динамики \(p^\jmath\) по отношению к исходной динамике \(p\), усреднённую по \(p^\jmath\)-инвариантной мере \(\mu^\jmath\).
Аналогично, Следствие 2 количественно характеризует редкость наблюдения эмпирической меры \(\pi^T\), близкой к \(\mu\) (где \(\mu\) не обязательно является инвариантной мерой). Стоимость задаётся величиной \(I_{DV}(\mu)\), которая количественно выражает «отсутствие \(P\)-инвариантности» у \(\mu\), см., например, оценку Упражнение 4.
Основные результаты: Доказательства
Этот раздел посвящён доказательству Теорема 1, Следствие 1, Следствие 2.
Определение 3 Функция \(F\colon \mathcal{P}(E)\to [0,\infty]\) называется полунепрерывной снизу (или пнс для краткости), если для каждого \(c\ge 0\) множество \(\{\jmath \in \mathcal{P}(E) \st F(\jmath)\le c\}\) замкнуто.
Следующая лемма утверждает, что если мы докажем неравенство типа Уравнение 9, заменив \(I\) некоторой функцией \(I_\alpha\), зависящей от параметра, то мы можем получить то же неравенство, оптимизируя по \(\alpha\). Это не просто следствие взятия \(\inf\) по \(\alpha\) с обеих сторон неравенства, так как нам нужно поменять местами \(\sup_\alpha\) (появляющийся из-за знака минус в экспоненте) и \(\inf_{\jmath}\).
Лемма 1 Пусть \(\mathcal{U}\) — произвольное множество индексов, и для \(\alpha \in \mathcal{U}\) пусть \(I_\alpha \colon \mathcal{P}(E)\to [0,\infty]\) — пнс функция. Предположим, что для каждого \(\alpha \in \mathcal{U}\) выполняется Уравнение 9 с заменой \(I\) на \(I_\alpha\), то есть \[ \varlimsup_T \frac{1}{T} \log \mathbb{P}(J^T \in \mathcal{C}) \le - \inf_{\jmath \in \mathcal{C}} I_\alpha(\jmath), \qquad \text{для всех замкнутых $\mathcal{C}$} \tag{11}\] Тогда Уравнение 9 выполняется с заменой \(I\) на \[ \hat{I}(\jmath):=\sup_{\alpha \in \mathcal{U}} I_\alpha(\jmath) \]
Доказательство. Согласно общим принципам теории больших уклонений, существует оптимальная полунепрерывная снизу функция \(\overline{I}\), такая что Уравнение 11 выполняется (с \(\overline{I}\) вместо \(I_\alpha\)) на компактных множествах. Поскольку мы предположили, что \(E\) конечно, \(\mathcal{P}(E)\) компактно, и, следовательно, каждое замкнутое множество компактно. Поэтому Уравнение 11 читается как \[ \overline{I} \ge I_\alpha \qquad \text{для всех $\alpha \in \mathcal{U}$} \] откуда \(\overline{I} \ge \sup_{\alpha\in \mathcal{U}} I_\alpha\).
Лемма 2 Для \(\xi \in C(E)\) определим \(\phi_\xi \in C(S)\) как \[ \phi_\xi(x):= \log \left(\sum\nolimits_{y} e^{\xi(x,y)} p_{x,y}\right) \] Тогда \[ \mathbb{E}\left[\exp\left(\sum_{t=0}^{T-1}\xi(X_t,X_{t+1}) - \phi_\xi(X_t) \right) \right]=1 \tag{12}\]
Доказательство. Определим \(q_{x,y}:= e^{\xi(x,y) - \phi_\xi(x)}p_{x,y}\). Тогда \(q_{x,y}\ge 0\) и \(\sum_y q_{x,y}=1\). Следовательно, \((q_{x,y})\) являются марковскими переходными вероятностями, и мы можем построить меру \(\mathbb{Q}\) на \(D(S)\). Имеем \[ \mathbb{Q}(X_0=x_0,\ldots,X_T=x_T)= \exp\left(\sum_{t=0}^{T-1}\xi(x_t,x_{t+1}) - \phi_\xi(x_t) \right) \mathbb{P}(X_0=x_0,\ldots,X_T=x_T) \] Таким образом, Уравнение 12 есть просто математическое ожидание постоянной функции \(\ind{}\) по мере \(\mathbb{Q}\).
Лемма 3 Для \(\xi, \phi_\xi\) как в Лемма 2, и \(\mathcal{A} \subset \mathcal{P}(E)\) \[ \mathbb{P}(J_T\in \mathcal{A}) \le \exp( - \inf_{\jmath\in \mathcal{A}} \jmath(\xi) - \mu^\jmath(\phi_\xi) ) \]
Доказательство. Показатель экспоненты в Уравнение 12 можно записать как \(J^T(\xi)-\pi^T(\phi_\xi)\). Вспоминая Уравнение 4 и просто умножая и деля на один и тот же множитель, получаем \[ \begin{aligned} \mathbb{P}(J^T\in \mathcal{A}) & = \mathbb{E}\left[ e^{-T( J^T(\xi) -\mu^{J^T}(\phi_\xi)) } e^{\sum_{t=0}^{T-1}\xi(X_t,X_{t+1}) - \phi_\xi(X_t)} \ind{\mathcal{A}}(J^T)\right] \\ & \le \sup_{\jmath \in \mathcal{A}} e^{- T (\jmath(\xi) - \mu^\jmath(\phi_\xi) )} \mathbb{E}\left[ e^{\sum\nolimits_{t=0}^{T-1}\xi(X_t,X_{t+1}) - \phi_\xi(X_t)} \ind{\mathcal{A}}(J^T)\right] \\ & \le \exp( - T \inf_{\jmath \in \mathcal{A}} ( \jmath(\xi) - \mu^\jmath(\phi_\xi)) )\, \mathbb{E}\left[ e^{\sum\nolimits_{t=0}^{T-1}\xi(X_t,X_{t+1}) - \phi_\xi(X_t)}\right] \end{aligned} \] что совпадает с утверждением в силу Лемма 2.
Для функции \(f\colon S\to \mathbb{R}\) пусть \(df(x,y):= f(y)-f(x)\). Определим \[ \mathcal{P}_\ast(E):= \left\{ \jmath \in \mathcal{P}(E) \st \jmath(df)=0, \text{ для всех $f\in C(S)$ } \right\} = \left\{ \jmath \in \mathcal{P}(E) \st \sum\nolimits_{y} \jmath_{x,y} = \sum\nolimits_{z} \jmath_{z,x}, \text{ для всех $x \in S$ } \right\} \]
Лемма 4 Для любого компактного множества \(\mathcal{K} \subset \mathcal{P}(E)\) такого, что \(\mathcal{K} \cap \mathcal{P}_\ast(E) =\emptyset\), выполняется \[ \mathbb{P}(J^T \in \mathcal{K}) =0, \qquad \text{для всех $T$ достаточно больших.} \]
Доказательство. Для данного \(T\ge 1\) пусть \(y_0=X_T,\ldots,y_N=X_0\) — путь в \(D(S)\), соединяющий \(X_T\) с \(X_0\) за минимальное число шагов (следовательно, не более \(|E|\) шагов). Определим поток \[ \tilde{J}^T=\frac{1}{T+N}\sum_{t=0}^{T+N-1}\delta_{(X_t,X_{t+1})} \]
Телескопируя сумму, получаем \[ \begin{aligned} & J^T(df) =\frac{1}{T}\sum_{t=0}^{T-1} f(X_{t+1})-f(X_t) = (f(X_T)-f(X_0))/T \\ & \tilde{J}^T(df)=0 \end{aligned} \] С другой стороны, согласно Уравнение 1, \(d(J^T,\tilde{J}^T)\le |E|/T\). В частности, \(J^T\) находится на расстоянии не более \(|E|/T\) от \(\mathcal{P}_\ast(E)\) с вероятностью \(1\). Поскольку \(\mathcal{K}\) компактно, а \(\mathcal{P}_\ast(E)\) замкнуто (на самом деле компактно, так как мы предполагаем конечность \(S\)), если эти два множества не пересекаются, они находятся на строго положительном расстоянии. Следовательно, \(J^T\notin \mathcal{K}\) с вероятностью \(1\) при достаточно малом \(|E|/T\).
Доказательство (Теорема 1). Лемма 3 можно интерпретировать так: Уравнение 9 выполняется при замене \(I\) на \[ I_\xi(\jmath):=\jmath(\xi) - \mu^\jmath(\phi_\xi) \] Лемма 4 можно интерпретировать так: Уравнение 9 выполняется при замене \(I\) на \[ I_\ast(\jmath):= \begin{cases} 0 & \text{если $\jmath \in \mathcal{P}_\ast(E)$.} \\ +\infty & \text{иначе.} \end{cases} \]
\(I_\xi\) непрерывна (в частности, пнс), \(I_\ast\) пнс на \(\mathcal{P}(E)\). Следовательно, по Лемма 1 неравенство Уравнение 9 выполняется с функцией уклонений \[ \hat{I}(\jmath)= \begin{cases} \sup_{\xi} I_\xi(\jmath) & \text{если $\jmath \in \mathcal{P}_\ast(E)$.} \\ +\infty & \text{иначе.} \end{cases} \]
Теперь возьмём \(\xi(x,y)= \log(\jmath_{x,y}/p_{x,y})\) (определение \(\xi(x,y)\) при \(\jmath_{x,y}=0\) несущественно). Получим \[ \begin{aligned} I_\xi(\jmath) & = \sum\nolimits_{x,y} \jmath_{x,y} \log(\jmath_{x,y}/p_{x,y}) - \sum\nolimits_{x} \mu^\jmath_x \log \left(\sum\nolimits_{z} \jmath_{x,z}\right) \\ & = \sum\nolimits_{x,y} \mu^{\jmath}_x p^\jmath_{x,y} \log(\mu^\jmath_x p^{\jmath}_{x,y} / p_{x,y}) - \sum\nolimits_{x} \mu^\jmath_x \log \mu^\jmath_x \\ & = \sum\nolimits_{x,y} \mu^{\jmath}_x p^\jmath_{x,y} \log(p^\jmath_{x,y}/p_{x,y}) = I(\jmath) \end{aligned} \]
Следовательно, для \(\jmath \in \mathcal{P}_\ast(E)\) имеем \(\hat{I}(\xi)=\sup_{\xi} I_\xi(\jmath)\ge I(\jmath)\). Поскольку вне \(\mathcal{P}_\ast(E)\) неравенство выполняется тривиально (\(+\infty=+\infty\)), то Уравнение 9 справедливо.
Доказательство (Следствие 1). Для двух вероятностей \(\mu,\nu \in \mathcal{P}(S)\) функция \(\nu \mapsto \sum_y \nu_y \log \nu_y/\mu_y\) достигает минимума при \(\nu=\mu\) (где она обращается в ноль). Поэтому в Уравнение 6 каждое слагаемое в сумме по \(x\) неотрицательно.
Если \(I(\jmath)=0\), то должно выполняться \(p^{\jmath}_{x,y}=p_{x,y}\) для всех \(y\) и всех \(x\), таких что \(\mu_x^\jmath>0\) (\(p^\jmath\) не определено, если \(\mu_x^\jmath=0\), поэтому мы можем произвольно положить \(p^{\jmath}_{x,y}=p_{x,y}\) везде). Но тогда условие \(\jmath \in \mathcal{P}_\ast(E)\) означает, что \(\mu^\jmath\) инвариантна для \(p^\jmath_{x,y}\equiv p_{x,y}\), и так как (в силу неприводимости) \(m\) является единственной инвариантной вероятностью для \((p_{x,y})\), то \(\mu^\jmath=m\). Таким образом, \(\jmath_{x,y}=\mu^\jmath_{x} p^\jmath_{x,y}=m_x p_{x,y}=\bar{\jmath}_{x,y}\).
Теперь множество \(\mathcal{K}_\varepsilon := \{ \jmath \st \sum_{e} |\jmath_{e}- \bar{\jmath}_e|\ge \varepsilon\}\) является компактным множеством, находящимся на положительном расстоянии от \(\bar{\jmath}\). Следовательно, \(c_\varepsilon:=\inf_{\jmath \in \mathcal{K_\varepsilon}} I(\jmath)>0\), поскольку \(I\) полунепрерывна снизу.
Доказательство. Для замкнутого \(\mathcal{C} \subset \mathcal{P}(S)\) определим \(\mathcal{C'}:=\{ \jmath \st \mu^\jmath \in \mathcal{C}\}\) (это просто прообраз \(\mathcal{C}\) относительно отображения \(\jmath \mapsto \mu^\jmath\)). Множество \(\mathcal{C}'\) замкнуто в \(\mathcal{P}(E)\), и поэтому, так как \(\pi^T=\mu^{J^T}\), \[ \mathbb{P}(\pi^T\in \mathcal{C}) = \mathbb{P}(J^T \in \mathcal{C}' ) \le e^{-T \inf_{\jmath\in \mathcal{C}'} I(\jmath) + o(T)} = e^{-T \inf_{\mu\in \mathcal{C}} I_{\mathrm{DV}}(\mu) + o(T)} \tag{13}\]
Дополнительные Задачи
Упражнение 1 Найдите явную оценку (аналогичную Уравнение 9) для \(h^T\) — числа оборотов (намоток) ближайшего случайного блуждания на \(\mathbb{Z}_N\). Подсказка: выразите число оборотов \(h^T\) через \(J^T\).
Упражнение 2 Пусть \(F \colon \mathcal{P}(E) \to \mathbb{R}\) непрерывна (и ограничена, что следует из конечности \(E\)). Докажите, что \[ \mathbb{E}\left[e^{T F(J^T)} \right] \le e^{T \sup_{\jmath} (F(\jmath)-I(\jmath)) + o(T)} \]
Упражнение 3 Докажите формулу \[ I_{DV}(\mu) = \sup_{u\in C(S), u>0} \sum_x \mu_x \log\left(\frac{u(x)}{(Pu)(x)} \right) \tag{14}\]
В принципе, эту задачу можно решить с помощью множителей Лагранжа и громоздких, но элементарных вычислений. Однако несколько более абстрактное применение техники позволяет найти более быстрый подход.
Инфимум в определении Уравнение 7 можно брать по \(\jmath\in \mathcal{P}_\ast(E)\), так как иначе \(I(\jmath)=+\infty\). Поэтому можно записать \(\jmath_{x,y}=\mu_x q_{x,y}\), где марковские переходные вероятности \(Q=(q_{x,y})_{x,y}\) удовлетворяют \(\mu Q=\mu\) (из \(\jmath\in \mathcal{P}_\ast(E)\)).
Мы можем использовать произвольную функцию \(f\in C(S)\) в качестве множителя Лагранжа, чтобы наложить ограничение \(\mu Q=\mu\). Действительно, для \(Q=(q_{x,y})_{x,y}\) \[ I_{DV}(\mu)= \inf_{Q} \sup_{f\in C(S)} \sum_{x,y} \mu_x q_{x,y} \log\left(\frac{q_{x,y}}{p_{x,y}} \right) +\mu((I-Q)f) \] где теперь инфимум берётся по произвольным переходным вероятностям \(Q=(q_{x,y})_{x,y}\), так как супремум по \(f\) равен \(+\infty\), если не выполнено условие \(\mu=\mu Q\).
Ключевой момент заключается в следующем. Выражение в правой части, для которого мы берём \(\inf_Q \sup_f\), является:
- выпуклым (следовательно, непрерывным) по \(Q\), для \(Q\) из выпуклого компактного множества \(\sum_{y} q_{x,y}=1\), \(q_{x,y}\ge 0\).
- аффинным (следовательно, непрерывным) по \(f\), для \(f\in C(S)\).
Поэтому мы можем использовать принцип минимакса Сиона и поменять порядок \(\inf\) и \(\sup\), чтобы получить \[ I_{DV}(\mu)= \sup_{f\in C(S)} \inf_{Q} \sum_{x,y} \mu_x q_{x,y} \log\left(\frac{q_{x,y}}{p_{x,y}} \right) +\mu((I-Q)f) = \sup_{f\in C(S)} \mu(f) + \inf_{Q} \mu_x q_{x,y} \log\left(\frac{q_{x,y}}{p_{x,y}e^{f(y)}}\right) \] Теперь инфимум по \(q_{x,y}\) вычисляется легко (так как нам не нужно накладывать «сложное» условие \(\mu=Q\mu\), только \(\sum_y q_{x,y}=1\)), и мы получаем \[ I_{DV}(\mu)= \sup_{f\in C(S)} \sum_x \mu_x f(x) - \mu_x \log\left(\sum_y p_{x,y} e^{f(y)}\right) \] что даёт искомое выражение, если положить \(u=e^f\).
Это доказательство в конечном итоге наводит на мысль, что если бы мы повторили доказательство Теорема 1 для \(\pi^T\) вместо \(J^T\), было бы достаточно оптимизировать по \(\xi(x,y)=f(y)\) (зависящей только от \(y\), а не от произвольной функции \(x\) и \(y\)), что согласуется с тем фактом, что оценка для \(\pi^T\) является более слабым результатом и, по сути, может быть выведена из экспоненциальной оценки для \(J^T\).
Упражнение 4 Докажите явные оценки \[ \mathcal{E}(\sqrt{\varrho},\sqrt{\varrho}) \le I_{DV}(\mu) \le \sum_{x,y} \mu_x \mu_y \log\left(\frac{\mu_y}{p_{x,y}}\right) \tag{15}\] где \(\mathcal{E}\) — форма Дирихле, а \(\varrho_x:=\mu_x/m_x\) — плотность \(\mu\) относительно инвариантной меры \(m\).
Следуя началу Упражнение 3, мы можем записать \(I_{DV}\) как инфимум по марковским переходным вероятностям \(Q=(q_{x,y})\), оставляющим \(\mu\) инвариантной: \(\mu=\mu Q\). Выбор \(q_{x,y}=\mu_y\) оставляет \(\mu\) инвариантной, что легко проверяется, и даёт указанную верхнюю оценку для \(I_{DV}\).
Что касается нижней оценки, в Уравнение 14 возьмём \(u=\sqrt{\varrho}\) (случай, когда \(\varrho\) обращается в ноль в некоторой точке, легко разбирается, так как эти точки несущественны, и можно положить \(u(x)=1\), если \(\varrho(x)=0\)). Выражение в Уравнение 14 для этого конкретного выбора \(u\) не больше супремума по \(u\), следовательно \[ I_{DV}(\mu) \ge \sum_x \mu_x \log\left(\frac{\sqrt{\varrho}(x)}{(P\sqrt{\varrho})(x)} \right)= - \sum_x m_x \log\left( 1- \frac{((I-P) \sqrt{\varrho})(x)}{\sqrt{\varrho(x)}}\right) \] Применим \(-\log(1-z)\ge z\) к каждому слагаемому суммы и получим \[ I_{DV}(\mu) \ge \sum_x m_x \varrho(x) \frac{((I-P) \sqrt{\varrho})(x)}{\sqrt{\varrho(x)}} \] что упрощается до требуемого неравенства.
Упражнение 5 Докажите, что \(I_{DV}(\mu)=0\) тогда и только тогда, когда \(\mu=m\) является инвариантной мерой (вспомните, что мы предполагали неприводимость цепи). Выведите, как и в Следствие 1, что для некоторого \(c_\varepsilon>0\) \[ \mathbb{P}\left(\sum\nolimits_{x \in S} |\pi^T_x - m_x| \ge \varepsilon \right) \le e^{-T (c_\varepsilon + o(1))} \] где \(o(1)\) стремится к нулю при \(T\to \infty\).
Поскольку \(m=\mu^{\bar{\jmath}}\) и \(I(\bar{\jmath})=0\), \[ 0\le I_{DV}(\mu)\le I(\bar{\jmath})=0 \]
Обратно, если \(I_{DV}(\mu)=0\), то \(\mathcal{E}(\sqrt{\varrho},\sqrt{\varrho})=0\). Так как мы предполагали неприводимость цепи, это означает, что \(\varrho\) постоянна, согласно пункту c. Предложения о формах Дирихле при \(f=g\). Это эквивалентно \(\mu=m\), так как они обе являются вероятностями.
Экспоненциальная оценка следует из того же рассуждения, что и в Следствие 1, так как используется только то, что \(I(\cdot)\) имеет единственный корень.
Сноски
Флуктуации математических объектов такого типа (например, \(J^T\)) имеют довольно глубокий смысл, предоставляя универсальное динамическое определение понятия энтропии в сложных системах.↩︎
Это называется функционалом Донскера-Варадхана, в честь известной серии статей математиков из NYU М.Д.Донскера и С.Р.С.Варадхана в 70-х годах. Статьи в основном посвящены марковским процессам с непрерывным временем (поэтому могут быть довольно технически сложными), но адаптация для дискретного времени проста.↩︎