スペクトルギャップを用いたランダムウォークの混交時間の解析は前々から知ってたけど対数ソボレフ不等式を用いた解析は知りたいなぁと長年思っていてようやく理解できてきたのでまとめてみました.
連結かつ非二部なグラフ上の離散時間単純ランダムウォーク(隣接点に一様ランダムに遷移するランダムウォーク)の分布は必ず定常分布と呼ばれる分布に収束することが知られており, その収束のレートを測る指標として混交時間(mixing time)が知られています. 時刻$t$においてランダムウォークが頂点$v$にいる確率を$p_t(v)$と書き, $\pi\in[0,1]^V$を定常分布とします (基本的にベクトルは行ベクトルとして扱います). 通常のランダムウォーク(一様ランダムな隣接点に遷移するランダムウォーク)では$\pi(v) = \frac{\deg(v)}{2|E|}$となることが知られています.
より一般に, 頂点$u$から$v$への遷移確率$P(u,v)$を成分として持つ行列を遷移確率行列(transition matrix)と呼び, $\pi P = \pi$を満たす分布$\pi$を定常分布(stationary distribution)と呼び, 定常分布が存在するランダムウォークを可逆(reversible)であると言います. 時刻$t$におけるランダムウォークの分布ベクトル$p_t$は$p_t = p_{t-1}P$を満たすので, この等式の両辺を$t\to\infty$をとれば確かに$p_t$が収束するとしたらそれは定常分布になりそうな感じがします.
可逆なランダムウォークは非常に重要なクラスであり, 定常分布が誘導するある計量を考えると遷移確率行列を対称行列として扱えるのが嬉しい性質で, 例えば$P$が実固有値を持つのでエクスパンダー性の議論などと相性が良いです (例えばこの記事参照). 基本的に無向グラフ上のランダムウォーク(辺重みがあっても良い)はこのクラスに属しますが, 有向グラフにすると可逆性が失われます. 本記事では主に可逆なランダムウォークを扱います.
$P(u,v)>0$のときに有向辺$(u,v)$を張って得られる有向グラフ$G$が強連結ならば$P$は既約(irreducible)であると言い, $G$の全ての有向閉路の長さのgcdが$1$であるならば非周期的(aperiodicity)であると言います (例えば二部グラフなら閉路長が偶数なので周期的). 既約ならば定常分布は一意に存在し, 非周期的ならばランダムウォークの分布は$\pi$に収束することが知られています (二部グラフ上のランダムウォークはステップ数の偶奇で分かれるので収束しない). ランダムウォークの文脈では確率$1/2$の自己ループによって長さ1の閉路を付与することで必ず非周期性を持たせられます. また, 連続時間ランダムウォークを考えると既約性だけで定常分布への収束性を保証できます. 自己ループ確率を$1/2$にすると遷移確率行列$P$が半正定値性を持ち, 例えば$\sqrt{P}$といった行列を考えることができるのが嬉しいポイントで, 例えば[Oliveira and Peres, 2019]ではこの分解を巧妙に使って到達時間(hitting time)のバウンドを証明しています.
混交時間の話に戻ります. 二つの分布$p_t,\pi\in[0,1]^V$の統計距離$d_{\mathrm{TV}}(p_t,\pi):=\frac{1}{2}\|p_t - \pi\|_1$を考え, 任意の初期分布$p_0$に対しこの値が$\epsilon$以下になるような最小の$t$を$\epsilon$-混交時間と呼び, $t_{\mathrm{mix}}(\epsilon)$で表します. すなわち
\begin{align*}
t_{\mathrm{mix}}(\epsilon) = \inf\{t\geq 0\colon d_{\mathrm{TV}}(p_t,\pi)\leq\epsilon\text{ for any }p_0\}.
\end{align*}
なお, 初期分布$p_0$は各頂点上のDirac測度の凸結合で表せるので, 最悪の頂点からスタートした場合の混交スピードを測るという意味で最悪時の指標になっています. 例えば初期状態が定常分布だった場合は$0$ステップで混交しているので平均時みたいなものはあまり考えません.
ランダムウォークとはグラフ上を局所的に遷移する過程ですので一般に解析が難しそうに見えますが, 時刻$1$から$T$を長さ$t_{\mathrm{mix}}(\epsilon)$の区間で区切るとそれぞれで分布が$\pi$に収束するため, それぞれの区間の最後では$\pi$からランダムに頂点を選んだものとみなすことができます. 例えば正則グラフを考えると$\pi$は一様分布となるので, $100n\log n$個の区間を考えるとそれぞれで固定した頂点$v$に行き着く確率はおおよそ$\pi(v)=1/n$なので, ランダムウォークが一度も頂点$v$を訪れない確率は$(1-1/n)^{100\log n}\leq n^{-100}$となり, $v$に関するunion boundをとれば全ての頂点を訪問することがわかります. すなわち混交時間を抑えることによって, 全訪問時間(cover time)も抑えることができます. こちらの記事で, このトピックに関する簡単なサーベイをまとめています.
このように, 混交時間を抑えることによって到達時間や全訪問時間といった他のパラメータに対する上界も得ることができるため, 混交時間の解析はランダムウォークにおいては非常に重要な研究課題となっています. 現代はマルコフ連鎖モンテカルロ法(MCMC)の解析, 特にIsing modelやPotts modelに対するGlauber dynamicsなどの混交時間の解析が大きな注目を集めています. また, Langevin dynamicsによって最適化問題を表現し, その混交時間が抑えられればその最適化問題に対するアルゴリズムを与えることができます.
混交時間を抑えるためには$d_{\mathrm{TV}}(p_t,\pi)$を上から抑える必要があります. 本記事では,
- Cauchy-Schwarzの不等式を使って$\chi^2$-ダイバージェンスで上から抑える (スペクトルギャップ)
- Pinskerの不等式を使ってKL-ダイバージェンスで上から抑える (修正された対数ソボレフ不等式)
という二つのよく知られる方法について, ダイバージェンスの観点から紹介します. スペクトルバウンドのみを理解したい場合はダイバージェンスを介さずとも良いのですが, 修正された対数ソボレフ不等式に基づく解析も理解するならば両方をダイバージェンスの縮小という観点で理解した方が見通しがよくなると思ったからです.
なお, オリジナルの対数ソボレフ不等式は元々は関数解析の分野の概念ですが, 本稿では関数解析には触れず, マルコル連鎖に焦点を絞って解説していきます.
スペクトルギャップに基づくバウンド
線形代数です. アイデアとしては, $\ell^1$ノルムを$\ell^2$ノルムで抑えて$\ell^2$ノルムをバウンドするためにスペクトルを使うというものです. $p_t-\pi = (p_{t-1} - \pi)P$であり, $p_{t-1}-\pi$は$P$の第一固有ベクトル$\mathbf{1}$と直交するので, $P$の第二固有値を見ることが肝要になります.
この議論をダイバージェンスの観点からと述べるために, $\chi^2$-ダイバージェンスと呼ばれる値を定義します. 確率変数$X$の台を$\mathsf{supp}(X)=\{x\colon \Pr[X=x]>0\}$で定めます.
定義1 ($\chi^2$-ダイバージェンス)
離散値をとり, $\mathsf{supp}(X) \subseteq \mathsf{supp}(Y)$を満たす二つの確率変数$X,Y$の$\chi^2$-ダイバージェンス$\chi^2(X||Y)$を以下で定義する:
\begin{align*}
\chi^2(X||Y) &= \sum_{a\in \mathsf{supp}(Y)} \Pr[Y=a]\left(\frac{\Pr[X=a]}{\Pr[Y=a]}-1\right)^2 \\
&= \mathbb{E}_{a\sim Y}\left[ \left( \frac{\Pr[X=a]}{\Pr[Y=a]} - 1 \right)^2 \right].
\end{align*}
また, $\mathsf{supp}(X)\not\subseteq \mathsf{supp}(Y)$であった場合は$\chi^2(X||Y)=\infty$と定める.
この量は二つの分布の乖離度を測る指標として知られているのですが, 距離の公理は満たしません (そもそも$\chi^2(X||Y) = \chi^2(Y||X)$は一般に成り立たない). イメージとしては確率変数$X,Y$がどれくらい識別しにくいかを表す指標だと思ってもらえれば十分です.
今回の記事では特に扱いませんが, ダイバージェンス全般において特筆すべき性質としては
- 非負性: $\chi^2(X||Y)\geq 0$.
- データ処理不等式: 任意の決定的アルゴリズム(関数)$f$に対し, $\chi^2(f(X)||f(X))\leq \chi^2(X||Y)$.
- 凸性: 確率変数をその分布ベクトルとみなし, $\chi^2$を二つの分布から実数値を返す関数とみなしたときに$\chi^2$は凸関数.
がよく知られています. 特に凸性はJensenの不等式との相性が良いので非常によく使います. また, $\chi^2$ダイバージェンスと統計距離との間には以下の関係が成り立ちます.
補題2.
離散値をとる二つの確率変数$X,Y$に対して
\begin{align*}
d_{\mathrm{TV}}(X,Y) \leq \frac{1}{2}\sqrt{\chi^2(X||Y)}.
\end{align*}
証明.
$Y$の台を$\Omega$とし, $x(a)=\Pr[X=a],y(a)=\Pr[Y=a]$とします. $\mathsf{supp}(X)\not\subseteq\mathsf{supp}(X)$の場合は右辺が$\infty$となり自明なので, $\mathsf{supp}(X)\subseteq\mathsf{supp}(Y)$を仮定すると,
\begin{align*}
d_{\mathrm{TV}}(X,Y) &= \frac{1}{2}\sum_{a\in \Omega}\left| x(a) - y(a) \right| \\
&= \frac{1}{2}\sum_{a\in\Omega} \sqrt{y(a)}\cdot \sqrt{y(a)} \left| \frac{x(a)}{y(a)} - 1 \right| \\
&\leq \frac{1}{2}\sqrt{\sum_{a\in\Omega}y(a)}\cdot \sqrt{\sum_{a\in\Omega}y(a)\left(\frac{x(a)}{y(a)} - 1 \right)^2} & & \text{the Cauchy--Schwarz inequality} \\
&= \frac{1}{2}\sqrt{\chi^2(X||Y)}.
\end{align*}
より主張を得ます. (証明終)
ランダムウォークに話を戻すと, 補題2より$\chi^2(p_t||\pi)$の上界が得られれば混交時間のバウンドを得ることができます. 以下の補題で$\chi^2(p_t||\pi)$を$\ell^2$ノルムで抑えます.
補題3.
定常分布$\pi$を持つ可逆なランダムウォークに対して, $\pi_{\min}:=\min_{v\in V}\pi(v)$とすると,
\begin{align*}
\chi^2(p_t||\pi) \leq \pi_{\min}^{-1}\cdot \|p_t - \pi\|_2^2.
\end{align*}
証明.
\begin{align*}
\chi^2(p_t||\pi) &= \sum_{v\in V}\pi(v)\cdot \left(\frac{p_t(v)}{\pi(v)}-1\right)^2 \\
&= \sum_{v\in V}\pi(v)\cdot\left(\frac{p_t(v)^2}{\pi(v)^2} - \frac{2 p_t(v)}{\pi(v)} + 1\right) \\
&= \sum_{v\in V}\pi(v)\left(\frac{p_t(v)}{\pi(v)} - 1\right)^2 \\
&= \sum_{v\in V}\frac{1}{\pi(v)}\cdot \left( p_t(v) - \pi(v) \right)^2 \\
&\leq \pi_{\min}^{-1}\cdot \|p_t - \pi\|_2^2.
\end{align*}
よって主張を得る. (証明終)
最後に行列$P$のスペクトルを用いた混交時間の上界を導出します.
定理4.
遷移確率行列$P$に従い, 定常分布$\pi$を持つ可逆なランダムウォークを考える. $\lambda(P)=\max_{\|x\|_2=1,x\bot \mathbf{1}}\|Px\|$とする. $\lambda(P)<1$ならば,
\begin{align*}
d_{\mathrm{TV}}(p_t,\pi) \leq \frac{\lambda(P)^t}{\sqrt{2\pi_{\min}}}.
\end{align*}
特に, スペクトルギャップ$\gamma:=1-\lambda(P)$に対し, $\tau_{\mathrm{mix}}(\epsilon) = O\left(\gamma^{-1}(\log(1/\epsilon) + \log(1/\pi_{\min}))\right)$.
Remark. $\lambda(P)$は$P$の非自明な第二固有値になります. すなわち, $P$の固有値を$1=\lambda_1 \geq \lambda_2\geq \dots \geq \lambda_{|V|}$としたときに$\lambda(P) = \max\{\lambda_2,|\lambda_{|V|}|\}$です. これはCourant-Fischerの定理(行列の固有値に関するmin-max定理)からわかります. エクスパンダーグラフの文脈では$\lambda(P)$が小さいグラフ (言い換えると$\gamma\approx 1$) を考えるのに対し, 例えば混交時間が多項式かどうかを気にするMCMCの文脈では$\gamma \geq 1/\mathrm{poly}(n)$かどうかを気にするので, $\gamma\to 0$の時の漸近挙動におけるオーダーを考えます.
証明. 分布$p_t$は等式$p_t = p_{t-1}P$を満たすので,
\begin{align*}
\|p_t - \pi\|_2 = \|(p_{t-1} - \pi) P\|_2 \leq \|p_{t-1} - \pi\|_2\cdot \lambda(P)
\end{align*}
を得る (最後の不等式ではベクトル$p_t-\pi$がall-one ベクトル$\mathbf{1}$に直交することを用いた).
補題2,3より,
\begin{align*}
d_{\mathrm{TV}}(p_t,\pi) &\leq \frac{1}{2\sqrt{\pi_{\min}}}\cdot \|p_t - \pi\|_2 \\
&\leq \frac{1}{2\sqrt{\pi_{\min}}} \cdot \lambda(P)^t \|p_0 - \pi\|_2 \\
&\leq \frac{\lambda(P)^t}{\sqrt{2\pi_{\min}}}
\end{align*}
特に, $\lambda(P)\leq 1-\gamma\leq\mathrm{e}^{-\gamma}$ならば$d_{\mathrm{TV}}(p_t,\pi) \leq \frac{\exp(-\gamma t)}{\sqrt{2\pi_{\min}}}\leq \epsilon$とおくと混交時間のバウンドを得る. (証明終)
修正された対数ソボレフ不等式
スペクトルギャップの章は線形代数でしたが, こちらは情報理論です. Pinskerの不等式を使って統計距離をKLダイバージェンスで抑え, KLダイバージェンス$\mathrm{KL}(p_t||\pi)$がexponentialにdecayする議論を紹介します. この時の指数のrateが修正された対数ソボレフ不等式となります. このことを述べるためにまず, Dirichlet形式と連続時間マルコフ連鎖を導入します.
KLダイバージェンスについて. 二つの分布$\mu,\nu\in[0,1]^V$に対し, それらのKLダイバージェンスを, $\mathsf{supp}(\mu)\subseteq\mathsf{supp}(\nu)$のとき
\begin{align*}
\mathrm{KL}(\mu||\nu) = \mathbb{E}_{v\sim\mu}\left[ \log \frac{\mu(v)}{\nu(v)}\right],
\end{align*}
$\mathsf{supp}(\mu)\not\subseteq\mathsf{supp}(\nu)$のとき, $\mathrm{KL}(\mu||\nu)=\infty$と定義します. すると, Pinskerの不等式より, $d_{\mathrm{TV}}(\mu,\nu)\leq \frac{1}{2}\sqrt{\mathrm{KL}(\mu||\nu)}$が成り立ちます. 混交時間の文脈では$d_{\mathrm{TV}}(p_t,\pi)\leq \frac{1}{2}\sqrt{\mathrm{KL}(p_t || \pi)}$より, $p_t$と$\pi$のKLダイバージェンスを抑えれば混交時間も抑えることができます.
Dirichlet形式について. 行列$M\in\mathbb{R}^{V\times V}$を線形作用素$M\colon\mathbb{R}^V\to\mathbb{R}^V$ととらえます. 定常分布$\pi$を持つ遷移確率行列$P$を考えます. 空間$\mathbb{R}^V$に内積$\langle \cdot,\cdot\rangle$を
\begin{align*}
\langle f,g\rangle = \sum_{v\in V}f(v)g(v)\pi(v) = \mathbb{E}_{v\sim\pi}[f(v)g(v)]
\end{align*}
を定めます.
定義5.
定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$に対し, そのDirichlet形式$\mathcal{E}\colon \mathbb{R}^V\times\mathbb{R}^V\to\mathbb{R}$を
\begin{align*}
\mathcal{E}(f,g) = \langle (I-P)f,g\rangle =\sum_{v\in V}\pi(v) (I-P)f(v) g(v)
\end{align*}
で定める.
正規化されたラプラシアン$L=I-P$を用いると, $\mathcal{E}(f,g)=\langle Lf,g \rangle$と表すことができます. 特に$f=g$のとき,
\begin{align*}
\mathcal{E}(f,f) &= \langle f,f\rangle - \langle Pf,f\rangle \\
&= \frac{1}{2}\mathbb{E}_{x\sim \pi,y\sim P(x,\cdot)}[f(x)^2 - 2f(x)f(y) + f(y)^2] \\
&= \frac{1}{2}\mathbb{E}_{x\sim\pi,y\sim P(x,\cdot)}[(f(x) - f(y))^2]
\end{align*}
となり, ランダムな辺$xy$を選んだときの$f$の二乗差の平均となります. これを, $\mathcal{E}(f,f)$は関数$f$のエネルギーのようなものだと思ってください.
連続時間マルコフ連鎖について. 可逆な遷移確率行列$P$に従う離散時間ランダムウォークを$(X_t)_{t=0,1,\dots}$とします. これを連続時間ランダムウォークに拡張します. 一般に状態空間が離散であるような連続時間のランダムウォークでは遷移時刻の間隔は平均$1$の指数分布$\mathrm{Exp}(1)$に従うものを考えます (指数分布とは$\Pr[\mathrm{Exp}(1)\geq t]=\mathrm{e}^{-t}$を満たす連続値をとる確率分布です). 以下でもう少しフォーマルに定義します. 確率変数$T_1,T_2,\dots$を$\mathrm{Exp}(1)$の独立なサンプルとし, $T_0=0$と定義します. 各$t$に対し$T_i \leq t < T_{i+1}$を満たす$i$を$i(t)$と書くことにします. 連続時間マルコフ連鎖とは, $Y_t=X_{i(t)}$で定義される連続時刻$t\in\mathbb{R}_{\geq 0}$で添字づけられた確率変数の族$(Y_t)_{t\in\mathbb{R}_{\geq 0}}$です. 連続時間ランダムウォークについても時刻$t$における分布$q_t\in[0,1]^V$を定義できます.
熱核について. $H_t = \mathrm{e}^{-t}\cdot \sum_{i=0}^\infty \frac{(tP)^i}{i!} = \mathrm{e}^{-t(I-P)}$とします. この行列はランダムウォークの分野では熱核(heat kernel)と呼ばれます (おそらく物理や微分方程式の文脈からきているのでしょうが私は専門外なので知りません). 証明は[Levin and Peres, 2017; Chapter 20]に譲りますが, $H_t(u,v)$は頂点$u$からスタートした連続時間ランダムウォークが時刻$t$において頂点$v$にいる確率を表します. 初期頂点の分布を$q_0$とすると, 時刻$t$におけるランダムウォークの分布は$q_t=q_0 H_t$と表すことができます. これを用いると連続時間ランダムウォークの$\epsilon$-混交時間$t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon)$を, 離散時間の場合と同様に
\begin{align*}
t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon) = \inf\{t\geq 0\colon d_{\mathrm{TV}}(q_t,\pi)\leq \epsilon \text{ for any $q_0$}\}
\end{align*}
で定義できます.
連続時間と離散時間の比較. 連続時間と離散時間は期待値の意味では時刻$T\in\mathbb{N}$においてどちらも$T$回の遷移を行うため, その時点でのランダムウォークの分布$p_T,q_T$はほぼ同じ性質を有します. 従って混交時間についても離散時間と連続時間でほぼ同じになります. このことは遷移回数の集中性を使って簡単に説明できます. 離散時間ランダムウォークの$(\epsilon/2)$-混交時間を$t^*$とおき, $10t^*$回目の遷移が発生した瞬間の時刻$T^*:=T_{10t^*}$を考えます. 時刻$T^*$は$10t^*$個の独立な指数分布$\mathrm{Exp}(1)$の和となり, この値は期待値$10t^*$に集中するため, 確率$1-2^{-\Theta(t^*)}$で$T^*\geq t^*$が成り立ちます. 従って
\begin{align*}
d_{\mathrm{TV}}(Y_{T^*},\pi) \leq d_{\mathrm{TV}}(X_{t^*},\pi) + \Pr[T^*<t^*] \leq \frac{\epsilon}{2} + 2^{-\Theta(t^*)}.
\end{align*}
を得ます. 適当な定数$c>0$に対して$t^*\geq c\log(1/\epsilon)$であれば$d_{\mathrm{TV}}(Y_{T^*},\pi)\leq\epsilon$が成り立つので, $t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon) = O(t_{\mathrm{mix}}(\epsilon/2) + \log(1/\epsilon))$を得ます ($\log(1/\epsilon)$の項は$t^*\ll \log(1/\epsilon)$の場合をケア). 逆方向の不等式も同様に証明できます.
修正された対数ソボレフ定数について. 上記の議論から, 連続時間における$\mathrm{KL}(q_t||\pi)$を抑えることによって元の離散時間における混交時間をバウンドできます. $\mathrm{KL}(q_t||\pi)$の減少を知りたいので, KLダイバージェンスを$t$で微分してみます. 関数$\phi_t \colon v\mapsto \frac{q_t(v)}{\pi(v)}$とすると,
\begin{align*}
\frac{\mathrm{d}}{\mathrm{d}t} \mathrm{KL}(q_t||\pi) &= -\mathcal{E}(\phi_t,\log \phi_t)
\end{align*}
を得ます. この式の右辺の減少スピードは, 以下で定義される修正された対数ソボレフ定数によって与えられます.
定義6.
定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$を考える. 関数$\phi\colon V\to\mathbb{R}_{>0}$に対し, $\mathrm{Ent}[\phi]$を
\begin{align*}
\mathrm{Ent}[\phi] = \mathbb{E}_{v\sim\pi}\left[ \phi(v) \log\frac{\phi(v)}{\mathbb{E}_{\pi}[\phi]} \right]
\end{align*}
とし, 修正された対数ソボレフ定数 (modified log-Sobolev constant) $\rho$を
\begin{align*}
\rho = \inf\left\{ \frac{\mathcal{E}(\phi, \log \phi)}{\mathrm{Ent}(\phi)} \colon \phi\geq 0,\mathrm{Ent}[\phi]\neq 0 \right\}
\end{align*}
で定める.
分布$q,\pi$のKLダイバージェンス$\mathrm{KL}(q||\pi)$は$\mathrm{KL}(q||\pi)=\mathrm{Ent}\left[\frac{q}{\pi}\right]$という関係が成り立ちます (このことからKLダイバージェンスを相対エントロピーと呼ぶのも納得ですね!). これを先ほどの微分の式に代入すると, $\rho$の定義より
\begin{align*}
\frac{\mathrm{d}}{\mathrm{d}t} \mathrm{Ent}[\phi_t] = -\mathcal{E}(\phi_t,\log \phi_t) \leq -\rho\cdot \mathrm{Ent}[\phi_t]
\end{align*}
を得ます. この微分方程式を解きます. $g(t) = \mathrm{Ent}[\phi_t]$とすると, 両辺を$g(t)$で割って
\[
\frac{\mathrm{d}}{\mathrm{d}t}\log g(t) \leq -\rho.
\]
積分定数$C_0$を使うと
\[
\log g(t) \leq -\rho t + C_0.
\]
従って$g(t) \leq \mathrm{e}^{-\rho t}\cdot g(0)$と表せます. 元々$g(t)=\mathrm{Ent}[\phi_t]=\mathrm{KL}(q_t||\pi)$だったので,
\[
\mathrm{KL}(q_t||\pi) \leq \mathrm{e}^{-\rho t}\mathrm{KL}(q_0||\pi)
\]
を得ます.
定理7.
定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$を考え, $\rho$を修正された対数ソボレフ定数とする. このとき,
\begin{align*}
t_{\mathrm{mix}}(\epsilon) = O(\rho^{-1}(\log(1/\epsilon) + \log\log(1/\pi_{\min}))).
\end{align*}
で定める.
証明.
ここでは, 離散時間と連続時間のランダムウォークの比較で主張していた関係を認め, $t_{\mathrm{mix}}(\epsilon) = O(t^{\mathrm{cont}}_\mathrm{mix}(\epsilon/2))$を認めることとします. 以後では$t^{\mathrm{cont}}_{\mathrm{mix}}(\epsilon/2)$を抑えるために, $q_t$を連続時間ランダムウォークの時刻$t$における分布とします. Pinskerの不等式および前段落の議論から
\begin{align*}
d_{\mathrm{TV}}(q_t,\pi) &\leq \frac{1}{2}\sqrt{\mathrm{KL}(q_t||\pi)} \\
&\leq \frac{1}{2}\mathrm{e}^{-\rho t / 2}\sqrt{\mathrm{KL}(q_0||\pi)} \\
&\leq \frac{1}{2}\mathrm{e}^{-\rho t / 2}\sqrt{\log(1/\pi_{\min})}.
\end{align*}
なお, 最後の式はKLダイバージェンスの定義から任意の分布$q$に対して$\mathrm{KL}(q||\pi)\leq \log(1/\pi_{\min})$が成り立つことを用いています. 従って, 適当な$t=O(\rho^{-1}(\log(1/\epsilon) + \log\log(1/\pi_{\min})))$に対して, この値は$\epsilon/2$以下になるので主張を得ます. (証明終)
スペクトルギャップと修正された対数ソボレフ定数の関係については以下の結果が知られています
定常分布$\pi$を持つ$V$上の可逆なマルコフ連鎖$P$を考え, $\gamma$をスペクトルギャップ, $\rho$を修正された対数ソボレフ定数とする. このとき,
\begin{align*}
\rho \leq 2\gamma
\end{align*}
が成り立つ.
したがって修正された対数ソボレフ定数の下界を得るのはスペクトルギャップ以上に難しいことが分かります. しかしながら定理4と定理7を比較すると, $1/\pi_{\min}$に対する依存が大きく異なっていることが分かります. 例えば$n$頂点のグラフ上での解析を考えると$\log n$と$\log\log n$の差しかないのでそこまで大きくはなさそうなのですが, イジングモデルなど状態空間が指数的に膨大ならばその差は非常に大きくなってくるので, 修正された対数ソボレフ不等式のテクニックが有用になってきます.
参考文献
