A Blog Entry on Bayesian Computation by an Applied Mathematician
$$
$$
1 概要
- マルチンゲールによる導出
- Lyapunov 型の条件が簡単に十分条件を与えるような，再帰時刻による取り扱い
(Kulik, 2018, pp. 45–) では，安定性の定理の証明に，マルチンゲールを用いた議論を用いている．エルゴード性を持つ Markov 連鎖は必ず
- 局所的な集合上で良い攪拌性を持ち，
- その他の点に行ってしまった場合でも，「十分早く」その局所的な集合に戻ってくる
という２つのモードを持つ．これを別々に解析する見通しの良い議論を与えてくれるのがマルチンゲールによる議論であるとしている (Kulik, 2018, p. 71) が，似たような議論をしているのが本論文 (Butkovsky and Veretennikov, 2013) である．1
2 背景
一様エルゴード性を strongly ergodic とも呼んでいる： \[ \sup_{x\in E}\|P^n(x,-)-\pi\|_\mathrm{TV}\le Ce^{-\lambda n}. \]
一方で，各点 \(x\in E\) で \[ \|P^n(x,-)-\pi\|_\mathrm{TV}\to0 \] が成り立つことを weakly ergodic と呼んでいる．
本論文では，\(\lambda\) を推定する (Diaconis and Stroock, 1991) 理論を，weakly ergodic の場合と非対称な場合に拡張する．
すると，(Diaconis and Stroock, 1991) 理論では遷移確率核 \(P\) のスペクトルギャップであった \(\lambda\) は，一般の設定の下でもある一般化した半群生成作用素のスペクトル半径に関係することがわかった．
2.1 (Diaconis and Stroock, 1991) 理論
一様エルゴード性の収束速度 \(\lambda\) を定量化するアプローチの１つ．
有限状態空間 \(E\) 上の \(P\)-一様 Markov 連鎖は，既約かつ対称ならば， \[ \lambda<\log\operatorname{Gap}(P) \] \[ \operatorname{Gap}(P):=\max\left\{\lvert\lambda\rvert\in\mathbb{R}_+\mid 1>\lambda\in\mathrm{Sp}(P)\right\} \]
- 対称ならば \(P=P^*\)．
- スペクトルギャップは一般の正作用素に定義できる．
2.2 (Vaserstein, 1969) による最適カップリングの構成
これを一般化したという．
最適な Markov カップリングよりも，カップリング確率が高いカップリングがあるらしい（しかし Markov にならない）．この稿 に書いた．
2.3 Lyapunov 型の条件
(Douc et al., 2004), (Kalashinikov, 1973), (Lamperti, 1960), (Rosenthal, 2002), (Tweedie, 1981) による．
3 本論
3.1 カップリング補題
本論に入る前に，次の結果を準備している：
\(X_1,X_2\) を確率核 \(P\) を持つ Markov 連鎖，\(Z=(X_1,X_2)\) をその最適 Markov カップリングを \[ X_n^1=:\xi_n1_{\left\{\zeta_n=0\right\}}+\eta_n^11_{\left\{\zeta_n=1\right\}} \] \[ X_n^2=:\xi_n1_{\left\{\zeta_n=0\right\}}+\eta_n^21_{\left\{\zeta_n=1\right\}} \] とする．このとき， \[ \operatorname{P}[X_n^1\ne X_n^2]\le\biggr(1-p_0\biggl)\operatorname{E}\left[\prod_{k=0}^{n-1}\biggr(1-p(\eta_k^1,\eta_k^2)\biggl)\right] \] \[ p(x_1,x_2):=1-\frac{1}{2}\|P(x_1,-)-P(x_2,-)\|_\mathrm{TV} \] \[ p_0:=1-\frac{1}{2}\|\operatorname{P}^{X_0^1}-\operatorname{P}^{X_0^2}\|_\mathrm{TV}=\operatorname{P}[X_0^1=X_0^2] \] が成り立つ．
基本的な考え方は \[ \begin{align*} \operatorname{P}[X^1_n\ne X_n^2]&\le\operatorname{P}[\zeta_0=1,\zeta_1=1,\cdots,\zeta_{n}=1]\\ &=\operatorname{E}[1_{\left\{\zeta_0=1\right\}}1_{\left\{\zeta_1=1\right\}}\cdots1_{\left\{\zeta_{n}=1\right\}}] \end{align*} \] である．これは，\(X_n^1\ne X_n^2\) ならば \(\zeta_n=1\) が必要であるため， \[ \begin{align*} \left\{X_n^1\ne X_n^2\right\}&\subset\left\{\zeta_n=1\right\}\\ &=\left\{\zeta_0=1,\zeta_1=1,\cdots,\zeta_{n}=1\right\} \end{align*} \] であるが，逆は必ずしも成り立たないためである．
これに，\(\mathcal{F}_n:=\sigma[X_n^1,X_n^2]\) について， \[ \begin{align*} &\operatorname{E}\left[\prod_{i=k}^n1_{\left\{\zeta_i=1\right\}}\,\middle|\,\mathcal{F}_{k-1}\right]\\ &=\operatorname{E}\left[\prod_{i=k-1}^{n-1}\biggr(1-p(\eta^1_i,\eta_i^2)\biggl)\,\middle|\,\mathcal{F}_{k-1}\right]1_{\left\{\zeta_{k-1}=1\right\}} \end{align*} \] の \(k=1\) の場合を併せて結論を得る．この等式自体は降下法により示す．
\(k=n\) の場合の式 \[ \operatorname{E}[1_{\left\{\zeta_n=1\right\}}\,|\,\mathcal{F}_{n-1}]=\biggr(1-p(\eta_{n-1}^1,\eta_{n-1}^2)\biggl)1_{\left\{\zeta_{n-1}=1\right\}} \] は明らかである．\(k<n\) の場合，帰納法の仮定と，\(\mathcal{F}_{k-1}\) の下で \(\zeta_k\) と \((\eta_k^1,\eta_k^2)\) は条件付き独立であるから，次のように式変形できる： \[ \begin{align*} &\quad\operatorname{E}\left[\prod_{i=k}^n1_{\left\{\zeta_i=1\right\}}\,\middle|\,\mathcal{F}_{k-1}\right]\\ &=\operatorname{E}\left[1_{\left\{\zeta_k=1\right\}}\operatorname{E}\left[\prod_{i=k+1}^n1_{\left\{\zeta_i=1\right\}}\,\middle|\,\mathcal{F}_k\right]\,\middle|\,\mathcal{F}_{k-1}\right]\\ &=\operatorname{E}\left[1_{\left\{\zeta_k=1\right\}}\operatorname{E}\left[\prod_{i=k}^{n-1}\biggr(1-p(\eta^1_i,\eta^2_i)\biggl)\,\middle|\,\mathcal{F}_k\right]\,\middle|\,\mathcal{F}_{k-1}\right]\\ &=\operatorname{E}[1_{\left\{\zeta_k=1\right\}}\,|\,\mathcal{F}_{k-1}]\operatorname{E}\left[\prod_{i=k}^{n-1}\biggr(1-p(\eta^1_i,\eta^2_i)\biggl)\,\middle|\,\mathcal{F}_{k-1}\right]\\ &=1_{\left\{\zeta_{k-1}=1\right\}}\biggr(1-p(\eta^1_{k-1},\eta^2_{k-1})\biggl)\operatorname{E}\left[\prod_{i=k}^{n-1}\biggr(1-p(\eta^1_i,\eta^2_i)\biggl)\,\middle|\,\mathcal{F}_{k-1}\right]\\ &=1_{\left\{\zeta_{k-1}=1\right\}}\operatorname{E}\left[\prod_{i=k-1}^{n-1}\biggr(1-p(\eta^1_i,\eta^2_i)\biggl)\,\middle|\,\mathcal{F}_{k-1}\right]\\ \end{align*} \]
この補題により，確率核 \(P\) を共有する２つの Markov 過程 \((X_n^1),(X_n^2)\) が与えられたとき，これらのカップリング \((\widetilde{X}^1_n),(\widetilde{X}^2_n)\) を同一の確率空間 \((\Omega,\mathcal{F},\operatorname{P})\) 上に構成し，\((\widetilde{X}_n^1)\overset{\text{d}}{=}(X_n^1),(\widetilde{X}_n^2)\overset{\text{d}}{=}(X_n^2)\) であるが，全変動距離を \(\operatorname{P}\) によって評価できるようになる．
3.2 スペクトルギャップによる一様エルゴード速度
次の積分作用素 \(A:\mathcal{L}_b(E^2)\to\mathcal{L}_b(E^2)\) を考える： \[ Af(x):=\biggr(1-p(x)\biggl)\operatorname{E}[f(\eta_1)\,|\,\eta_0=x] \] \[ \eta_i=\begin{pmatrix}\eta_i^1\\\eta_i^2\end{pmatrix},\quad x=\begin{pmatrix}x^1\\x^2\end{pmatrix}. \] このスペクトル半径 \[ r(A):=\limsup_{n\to\infty}\sqrt[n]{\|A^n\|} \] が一様エルゴード性を引き起こすのである．
なお，この定義式は，後述の \(r(A)\le1\) と併せると，任意の \(\epsilon>0\) に対して，ある \(C>0\) が存在して，\(r(A)\le r(A)^{1-\epsilon}\) であるから， \[ \begin{align*} \|A^n\|&\le C\left(r(A)^{1-\epsilon}\right)^n\\ &=Ce^{n(1-\epsilon)\log r(A)}\\ &=Ce^{-n(1-\epsilon)\log\lvert r(A)\rvert} \end{align*} \] を含意することに注意．
実は次の定理の証明は，次の不等式を導いているのみである： \[ \frac{1}{2}\|P^n(x,-)-P^n(y,-)\|_\mathrm{TV}\le\|A^{n}\|. \]
この２式より，直ちに証明が完成する．
ただし，作用素ノルム \(\|A^n\|\) は任意の \(\|1\|=1\) を満たす関数ノルムに関して構成して良い．\(C_b(E^2)\) を考えることも有用である．
いずれにしろ， \[ \|A\|_\infty=1-\inf_{x\in E^2}p(x)\le1 \] という条件式は変わらない．作用素ノルムの劣乗法性から \[ r(A)=\limsup_{n\to\infty}\sqrt[n]{\|A^n\|_\infty}\le\|A\|_\infty\le1 \] であることに注意．
- \(A:\mathcal{L}_b(E^2)\to\mathcal{L}_b(E^2)\) は有界作用素であり，\(r(A)\le1\) を満たす．
- \(r(A)<1\) ならば，\(X\) はただ一つの不変確率測度を持ち，任意の \(\epsilon>0\) に対して，初期分布 \(X_0^1,X_0^2\) に依らないある \(C>0\) が存在して， \[ \|\operatorname{P}^{X_n^1}-\operatorname{P}^{X_n^2}\|_\mathrm{TV}\le C(1-p_0)e^{-n\lvert\log r(A)\rvert(1-\epsilon)}. \]
一般に，任意の \(f\in\mathcal{L}_b(E^2)\) に対して，\((\eta_k)\) のMarkov性より， \[ \begin{align*} \operatorname{E}\left[f(\eta_n)\prod_{i=0}^{n-1}\biggr(1-p(\eta_i)\biggl)\right]&=\operatorname{E}\left[\operatorname{E}\left[f(\eta_n)\prod_{i=0}^{n-1}\biggr(1-p(\eta_i)\biggl)\,\middle|\,\eta_0,\cdots,\eta_{n-1}\right]\right]\\ &=\operatorname{E}\left[\prod_{i=0}^{n-2}\biggr(1-p(\eta_i)\biggl)\cdot\biggr(1-p(\eta_{n-1})\biggl)\operatorname{E}[f(\eta_n)\,|\,\eta_{n-1}]\right]\\ &=\operatorname{E}\left[\prod_{i=0}^{n-2}\biggr(1-p(\eta_i)\biggl)\cdot Af(\eta_{n-1})\right]=\operatorname{E}[A^nf(\eta_0)]. \end{align*} \] これより，\(\left\{\eta_n=0\right\}\supset\left\{\prod_{k=0}^{n-1}\biggr(1-p(Z_k)\biggl)=0\right\}\) に注意すれば，次の評価を得る： \[ \begin{align*} \|P^n(x,-)-P^n(y,-)\|_\mathrm{TV}&\le2\operatorname{P}_{(x,y)}^Q[X_n\ne Y_n]\le2\operatorname{E}_{(x,y)}^{Q_\perp}\left[\prod_{k=0}^{n-1}\biggr(1-p(Z_k)\biggl)\right]\\ &=2\operatorname{E}_{(x,y)}^{Q_\perp}\left[\delta_1(\eta_n)\prod_{k=0}^{n-1}\biggr(1-p(Z_k)\biggl)\right]=2\operatorname{E}_{(x,y)}^{Q_\perp}[A^{n-1}\delta_1(\eta_1)](1-p(\eta_0))\\ &\le2\delta_{x,y}\|A^{n-1}\|_\infty \end{align*} \] よって，\(\frac{1}{2}\|P^n(x,-)-P^n(y,-)\|\) はちょうど作用素ノルム \(\|A^{n-1}\|\) を評価する問題に帰着する．
3.3 再帰性と非一様エルゴード速度
\[ \|A\|_\infty=1-\inf_{x\in E^2}p(x)=1 \] の場合に当たるものであるが， \[ K(\epsilon):=\left\{x\in E^2\mid p(x)\ge\epsilon\right\} \] に無限回再帰するとき，その頻度に依存して，指数的か多項式的か決まる．4 この頻度は，次の帰着時間 \(\tau^B,T^B\) の積率条件で記述される： \[ \tau^B:=\inf\left\{n\ge 1\mid\eta_n\in B\right\} \] \[ T^B:=\inf\left\{n\ge 1\mid(X_n^1,X_n^2)\in B\right\} \] ただし，\(B\in\mathcal{E}^{\otimes2}\)．
ある \(\epsilon,\lambda,M>0\) と \(\mathcal{E}^{\otimes2}\ni B\subset K(\epsilon)\) について，次が成り立つとする：
- \(Q:=\operatorname{E}[e^{\lambda\tau^B}]<\infty\)．
- 任意の \(x\in B\) について，\(\operatorname{E}_x[e^{\lambda\tau^B}]\le M\)．
このとき，\(X\) はただ一つの不変確率測度 \(\pi\) をもち，またある初期分布 \((X_0^1,X_0^2)\) に依らない \(C>0\) が存在して， \[ \|\operatorname{P}^{X_n^1}-\operatorname{P}^{X_n^2}\|_\mathrm{TV}\le CQe^{-n\theta} \] \[ \theta:=\frac{\lvert\log(1-\epsilon)\rvert\lambda}{\log M+\lvert\log(1-\epsilon)\rvert} \]
ある \(\epsilon>0,\lambda>0,M>0,\mathcal{E}^{\otimes2}\ni B\subset K(\epsilon)\) について，次が成り立つとする：
- \(Q_2:=\operatorname{E}[e^{\lambda T^B}]<\infty\)．
- 任意の \(x\in B\setminus K(1)\) について，\(\operatorname{E}_x[e^{\lambda T^B}]<M\)．
このとき，過程 \(X\) はただ一つの不変確率分布 \(\pi\) をもち，ある初期分布 \((X_0^1,X_0^2)\) に依存しない定数 \(C>0\) が存在して， \[ \|\operatorname{P}^{X_n^1}-\operatorname{P}^{X_n^2}\|_\mathrm{TV}\le CQ_2e^{-n\theta_1} \] \[ \theta_1:=\frac{\lvert\log(1-\epsilon)\rvert\lambda}{\log M+3\lvert\log(1-\epsilon)\rvert}. \]
ある \(\epsilon>0,\lambda\ge1,M>0,\mathcal{E}^{\otimes2}\ni B\subset K(\epsilon)\) について，次が成り立つとする：
- \(Q_3:=\operatorname{E}[(T^B)^\lambda]<\infty\)．
- 任意の \(x\in B\setminus K(1)\) に対して，\(\operatorname{E}_x[(T^B)^\lambda]<M\)．
このとき，過程 \(X\) はただ一つの不変確率分布 \(\pi\) をもち，任意の \(\lambda_1\in(0,\lambda)\) に対して，ある初期分布 \((X_0^1,X_0^2)\) に依存しない定数 \(C>0\) が存在して， \[ \|\operatorname{P}^{X_n^1}-\operatorname{P}^{X_n^2}\|_\mathrm{TV}\le CQ_3n^{-\lambda_1} \]
4 例
あ
References
Footnotes
それと (Durmus et al., 2016) を挙げている．↩︎
(Butkovsky and Veretennikov, 2013) 定理2.1．↩︎
前節から判る通り，局所Dobrushin条件を満たす集合（small set ともいう）上では常に指数収束である．↩︎