@Lawasintegrity
前提知識
線形代数，確率論
前書き
MCMCについて書きます．ここではマルコフ連鎖を理論的に考え，その実行計算時間をディリクレ形式を通じて解析することにします．通常，マルコフ連鎖は実行時間はあまり考えられずに用いられることが多いですよね．
内容
マルコフ連鎖
まずは簡単にマルコフ連鎖の話をします．
ここでは有限な状態空間を考えます．その状態空間を$\Omega$と書くことにします．マルコフ連鎖は$\Omega$上の確率分布の遷移を考えることになります．
$P$を確率推移行列とします．つまり，前の状態が次の状態へどれくらいの確率で推移するのかの情報が含まれています．
また，$\pi$を定常分布とします．任意の$y \in \Omega$について，
$$\pi(y) = \sum_{x \in \Omega} \pi(x) P(x,y)$$が成立しています．また，詳細釣り合い条件，
$$\pi(x) P(x,y) = \pi(y)P(y,x)$$も成立しているとします．
MCMC
次にMCMCについて書きます．今，欲しい定常分布は分かっているものの，そこからサンプリングは難しいものとします．例えば，各$x \in \Omega$に対して$\pi(x)$の計算は簡単にできるが，$\sum \pi(x)$の計算は大変だとします．ここで$\pi$に従って$\Omega$からサンプリングしたいとします．そのとき，MCMCを次のように設計してみます．
現在$x \in \Omega$にいるとします．次に$y \in \Omega$を一様ランダムに選び，そこへ移るかどうかについて考えます．もし$\pi(y) \neq 0$なら確率$\frac{1}{2}\min(1,\frac{\pi(y)}{\pi(x)})$で移すように考えます．もし$\pi(y) = 0$なら$x$に留まります．そのように考えると，このマルコフ連鎖の定常分布は$\pi$になります．つまり，適当な場所からスタートさせてこの操作をたくさん繰り返せば良いということです．
mixing time
$\Omega$上の確率分布$\mu,\nu:\Omega \to \mathbb{R}_{+}$について，total variationとは，
$$\| \nu -\mu \|_{TV} := \frac{1}{2}\sum_{x \in \Omega} |\nu(x)-\mu(x)|$$のことです．
$X$を$r$から生成される確率変数とします．$\| r -\pi \|_{TV} \leq \epsilon$を満たすとき，$X$は$\pi$の$\epsilon$-近似のサンプリングと呼びます．
$x \in \Omega$，$\epsilon > 0$について，
$$\tau_x(\epsilon):=\min \{ t \mid \| P^t(x,\cdot) -\pi \|_{TV} \leq \epsilon \}$$を推移確率$P$,$\pi$に対する$x$からスタートしたときのmixing timeという．
ここで，$P^t(x,\cdot)$は$x$からスタートさせて$P$に従って$t$回推移させたときの分布のことです．
ディリクレ形式
さて，今，定常分布$\pi$が作る内積を定義します．それは，$f,g:\Omega \to \mathbb{R}$について，
$$\langle f,g \rangle_{\pi} : = \mathrm{E}_{\pi}[f \cdot g] =\sum_{x \in \Omega} \pi(x) f(x) g(x)$$とします．さらにここで，$\| f\|_{\pi} : = \langle f,f \rangle_{\pi}$と書くことにします．
$f:\Omega \to \mathbb{R}$に対するディリクレ形式$\mathcal{E}_{\pi}(f,f)$とは，
$$\mathcal{E}_{\pi}(f,f) := \frac{1}{2} \sum_{x,y \in \Omega} (f(x)-f(y))^2 P(x,y) \pi(x)$$のことです．また，計算すれば分かるのですが，確率行列からラプラシアン行列を$L:=I-P$のように作ると，ディリクレ形式は，
$$\mathcal{E}_{\pi}(f,f) := \langle f,Lf \rangle_{\pi} $$と書くことができます．(当然一般的には$\mathcal{E}_{\pi}(f,g)$を定義します．)
ディリクレ形式がどういうものかというと，状態が少しだけずれたときの変化の差を表しています．
また，ディリクレ形式とは別のもので，$f$の$\pi$で見た分散を
$$\mathrm{Var}_{\pi}(f) := \| f - \mathrm{E}_{\pi}[f] \|_{\pi}^2 = \sum_{x \in \Omega} (f(x)-\mathrm{E}_{\pi}[f])^2 \pi(x)$$とします．
Poincare定数
Poincare定数 $p$ は次のように定義される．
$$p:=\inf_{f : \Omega \to \mathbb{R}} \frac{\mathcal{E}_{\pi}(f,f)}{\mathrm{Var}_{\pi}(f)}.$$マルコフ連鎖がreversibleなら、$1-p$は$P$の第二固有値である．
上の定理から$\lambda$はspectol gapとも呼ばれます．なぜなら，$P$の第一固有値は$1$で，最大固有値と第二最大固有値の差が$\lambda$そのものだからです．
$P$の第一固有値が$1$なことはPerron Frobeniusの定理から分かります．また，その時の固有ベクトルは定常分布$\pi$です．
MCMCの計算量
さて，このPoincare定数がMCMCの計算量の解析で役に立つのですが，そのイメージを簡単に説明します．べき乗法を知っていると分かりやすいかもしれません．マルコフ連鎖では，初期の分布から何回か$P$で状態を推移させて，それで定常分布に近づけさせます．その時，徐々に最大固有値以外の成分は小さくなって行きます．ここで，どれくらいのペースで小さくなっていくのかは第一固有値と第二固有値の差に依存していそうです．
今考えている確率推移行列$P$の固有値を大きい順に$\lambda_1,\lambda_2,...,\lambda_n$とします。また、$\lambda^*=\max(\lambda_2,|\lambda_n|)$と書きます。ここで、確率推移行列の性質から$\lambda_1=1$で、また、MCがirreducibleであるなら、$\lambda_2 < 1$になり、MCが非周期的なら、$\lambda_2>-1$になります。よってこの状況なら、$\lambda^* < 1$になります。
irreducibleかつ非周期的な推移確率$P$について，任意の初期値$x \in \Omega$に対して，
$$\tau_{x}(\epsilon) \leq \frac{1}{1-\lambda^*} \left(\ln \frac{1}{\epsilon} + \frac{1}{2}\ln \frac{1}{4 \pi(x)} \right)$$が成立する．
ここでマルコフ連鎖がlazyである場合、つまり、マルコフ連鎖の確率行列がある確率行列$P$を使って$(I+P)/2$と書ける場合を考えます。このとき、$P$の固有値は全て$-1$よりも大きいため、$(I+P)/2$の固有値は全て非負です。よって、このときは$\lambda^*=\lambda_2$です。ゆえに、次が成り立ちます。
irreducibleかつ非周期的で、lazyな推移確率$P$について，任意の初期値$x \in \Omega$に対して，
$$\tau_{x}(\epsilon) \leq \frac{1}{p} \left(\ln \frac{1}{\epsilon} + \frac{1}{2}\ln \frac{1}{4 \pi(x)} \right)$$が成立する．[by Diaconis and D. Stroock 1991]
この定理を考えることで，MCMCの計算時間を見積もることができます．あとは、この$\lambda^*$の上からのbound、または、$p$の下からのboundを求めればよいです。
参考文献
P. Diaconis and D. Stroock. Geometric bounds for eigenvalues of Markov chains. $\textit{The Annals of Applied Probability}$, pages 36–61, 1991.
