A Blog Entry on Bayesian Computation by an Applied Mathematician
$$
$$
導入
Markov 過程のエルゴード性
空間 \(E\) 上の Markov連鎖は，\(E\) 上の確率測度の空間 \(\mathcal{P}(E)\) 上に力学系 \(((P^*)^n\mu)_{n\in\mathbb{N}}\) を定める．その不動点 \(P^*\mu=\mu P=\mu\) が不変確率分布（平衡分布）である．
これは，Markov 連鎖の 確率核 \(P\) の 左作用 \(P:\mathcal{L}_b(E)\to\mathcal{L}_b(E)\) の随伴作用素 \(P^*:\mathcal{P}(E)\to\mathcal{P}(E)\) が \(\mathcal{P}(E)\) に作用して得られる力学系ともみれる．
この力学系 \((\mathcal{P}(E),P^*)\) は不動点を持つか？持つならば，どのようなノルムについてどのくらいの速さで収束するか？
これが Markov 連鎖のエルゴード性の議論である．
通常，Markov 過程のエルゴード性は全変動ノルムについて考慮されるが，近年は弱位相に関する議論も進んでいる．
再起過程
非負確率変数の独立同分布 \(\{T_n\}\subset\mathcal{L}(\Omega)_+\) について，
- \(\{T_n\}\) が定めるランダムウォーク \[S_0=0,\qquad S_n:=T_1+\cdots+T_n,\qquad n\ge1,\] を 再起過程 または再生過程という． \(\{T_n\}\) を待ち時間 (interarrival times)，\(S_n\) を \(n\) 回目到着時刻という．
- 再起過程 \(\{S_n\}\) の 再起回数過程 とは， \[N_t:=\sum_{n=0}^\infty1_{[0,t]}(S_n)=\sup_{n\in\mathbb{N}\mid S_n\le t}\] をいう．\(t\mapsto\operatorname{E}[N_t]\) を再起関数という．
再起過程 \(\{S_n\}\) は通常，繰り返し起こる事象の発生時間をモデル化するために用いられる．
その代表的なものが，待ち時間 \(\{T_n\}\) を指数分布に取った場合である Poisson 過程である．
再起過程は OR を中心として，多くの応用先を持つ：
付随する待ち時間の Markov 過程
再起過程 \(\{S_n\}\) は，ある Markov 過程 \(\{X_t\}\) が原点に戻る時刻の列と捉えることで，エルゴード性を議論することができる．
このときの Markov 過程 \(\{X_t\}\) を，本稿では 待ち時間の Markov 過程 と呼ぶことにする．
以下，第 2 節では離散時間で状態空間も離散 \(\mathbb{N}\) の場合，第 3 節では連続時間で状態空間も連続 \(\mathbb{R}_+\) の場合について，この待ち時間の Markov 過程 \(X\) のエルゴード性を調べる．
待ち時間の Markov 連鎖
まず，待ち時間 \(T_n\) は非負整数 \(\mathbb{N}=\{0,1,\cdots\}\) 値とし，その分布を \((p_i)\sim\mathcal{P}(\mathbb{N})\) とする．
これが定める再生過程 \(\{S_n\}\) は，次の遷移確率 \((p_{ij})\) を持つ \(\mathbb{N}\) 上の Markov 連鎖 \(X\) が原点 \(0\) に到着する時刻の列と同分布である： \[
p_{(i+1)i}=1,\qquad p_{0i}=p_i,\qquad i\in\mathbb{N}.
\]
このとき，（無限次元の）確率行列 \(P\) は Frobenius の同伴行列 の転置の形をしている．
エルゴード定理
上で定義した Markov 連鎖 \(X=\{X_n\}_{n\in\mathbb{N}}\) について，
- 任意の状態 \(i\in\mathbb{N}\) に関して \(p_i>0\) が成り立つとする．このとき，\(X\) は既約で非周期的であり，再帰的である．
- さらに，\(\sum_{j=1}^\infty jp_j<\infty\) も満たすとき，\(X\) は不変確率測度 \[\mu_i=\frac{\sum_{j=i}^\infty p_j}{1+\sum_{j=1}^\infty jp_j}\] をもち，正に再帰的である．そうでないときは零再帰的である．
分布 \((p_i)\) が偶数の上にしか台を持たないなど，\(\mathrm{supp}\;(p)\) に周期がある場合は \(X\) は周期的になってしまうが，任意の \(i\in\mathbb{N}\) に関して \(p_i>0\) ならば，任意の状態 \(i\in\mathbb{N}\) は本質的であり，互いに行き来できるため既約であり，周期も持たない．必ず有限時間内に原点に戻ってくるため，再帰的でもある．
原点 \(0\) に初めて帰ってくる時刻を \(T_0\) とすると， \[\begin{align*}
\operatorname{E}_0[T_0]&=\sum_{j=0}^\infty(j+1)p_j\\
&=1+\sum_{j=0}^\infty jp_j\\
&=1+\sum_{j=1}^\infty jp_j.
\end{align*}\] よって，正に再帰的であること \(\operatorname{E}_0[T_0]<\infty\) は，\(\sum_{j=1}^\infty jp_j<\infty\) に同値． このとき，離散エルゴード定理より，ただ一つの不変測度 \((\mu_n)\in\mathcal{P}(\mathbb{N})\) を持ち， \[\mu_i=\frac{1}{\operatorname{E}_i[T_i]},\qquad i\in\mathbb{N},\] と表せる．これにより \(i=0\) の場合はすぐに計算できるが，\(i>0\) の場合は少し計算の見通しが良くない．そこで，必要条件 \[\mu_i=\mu_{i+1}+\mu_0p_i,\qquad i\in\mathbb{N},\] に注目すると，これを再帰的に適用することで， \[\begin{align*}
\mu_{i-1}&=\mu_{i-1}-\mu_0p_{i-1}\\
&=\mu_{i-2}-\mu_0p_{i-2}-\mu_0p_{i-1}\\
&=\cdots\\
&=\mu_0-\mu_0\sum_{j=0}^{i-1}p_j\\
&=\mu_0\sum_{j=i}^\infty p_j.
\end{align*}\]
Markov 連鎖の概念は次節で解説しているので，証明を読む前にぜひチェックしてください．
離散 Markov 連鎖の概念
まず，離散状態空間 \(E\) 上の Markov 連鎖は，各状態 \(i\in E\) の分類から始まる．
\(E\) を可算集合，\(\{X_n\}\) を \(E\) 上の Markov 連鎖とする．状態 \(i\in E\) について， \[
\tau_i:=\inf\{n\ge1\mid X_n=i\}
\] を到着時刻とする．
- \(i\) が 再帰的 な状態であるとは，Markov 連鎖 \(\{X_n\}\) が \(i\in E\) からスタートした場合，必ずいずれ戻ってくることをいう： \[
\operatorname{P}_i[\tau_i<\infty]=1.
\] そうでない場合，\(i\in E\) は 推移的 であるという．
- 再帰的な状態 \(i\in E\) がさらに 正に再帰的 であるとは，帰ってくる時刻の期待値が有限であることをいう： \[
\operatorname{E}_i[\tau_i]<\infty.
\] そうでない場合は 零再帰的 であるという．
続いて，この状態 \(i\in E\) 毎に定義した性質が，Markov 連鎖 \(\{X_n\}\) 全体の性質に直接に影響するためには，次の「既約性」の条件が必要である．
状態 \(i\in E\) から \(j\in E\) へ 到達可能 であるとは，ある \(n\in\mathbb{N}\) が存在して \(p_{ij}^n>0\) を満たすことをいう．これを \(i\to j\) と表す．
\(E\) を可算集合，\(\{X_n\}\) を \(E\) 上の Markov 連鎖とし，その遷移確率を \(p_{ij}^n=\operatorname{P}_i[X_n=j]\) と表す．
- 状態 \(i\in E\) が 本質的 であるとは，任意の到達可能な状態 \(i\to j\) に対して，\(j\to i\) でもあることをいう．
- Markov 連鎖 \(X\) が 既約 であるとは，任意の本質的な状態 \(i,j\in E\) が互いに到達可能であることをいう：\(i\leftrightarrow j\)．
\(X\) の遷移確率 \(p\) は，\(E\) の本質的な状態 \(E_\mathrm{ess}\) 上に，互いに到達可能であるという関係 \(\leftrightarrow\) を通じて同値類 \(E_\mathrm{ess}/\leftrightarrow\) を定めることが示せる．この同値類が１つに縮退することを，既約というのである．
また，周期 \[
d(i):=\gcd\{n\ge1\mid p_{ii}^n>0\}
\] は，先述の同値類 \(E_\mathrm{ess}/\leftrightarrow\) 上に関数を定める．この関数 \(d:(E_\mathrm{ess}/\leftrightarrow)\to\mathbb{N}^+\) が 定値関数 \(1\) となるとき，\(X\) を 非周期的 という．
任意の \(i,j,k\in E\) について，必ず \[
p^{n+m}_{ik}\ge p^n_{ij}p^m_{jk}
\] が成り立つ．\(i\to j\) かつ \(j\to k\) であるとき，ある \(n,m\ge1\) が存在して \(p^n_{ij}>0\) かつ \(p^m_{jk}>0\) であるから，\(p^{n+m}_{ik}>0\) である．よって，\(i\to j\)．これより \(\leftrightarrow\) は推移的である．反射性は \(p_{ii}^0=1>0\) であるため，定義上成り立つ．対称性も成り立つ．
続いて，\(i\leftrightarrow j\) ならば，\(d(i)=d(j)\) を示す． \[
N_i:=\gcd\{n\ge1\mid p_{ii}^n>0\}
\] と表すと，\(i\leftrightarrow j\) ならば \(N_i\ne\emptyset\) である．任意の \(s\in N_i\) を取ると，仮定 \(i\leftrightarrow j\) より，先ほどの議論と同様にして，ある \(n,m\ge1\) が存在して， \[
p^{n+m+ks}_{jj}\ge p^m_{ji}p^s_{ii}p^n_{ij}>0,\qquad k=1,2,\cdots.
\] よって，\(d(j)|s\) が必要であるから，\(d(j)\le d(i)\) が結論づけられる．逆も全く同様に議論できるから，\(d(j)=d(i)\)．
状態 \(i,j\in E\) は互いに到達可能であるとする：\(i\leftrightarrow j\)．このとき，\(i,j\) の推移性・零再帰性・正再帰性は一致する．特に，Markov 連鎖 \(X\) が既約ならば，全ての状態が同じ再帰性を持つ．
こうして，既約な Markov 連鎖 \(P\) の再帰性が議論できるようになる．推移的であるか，零再帰的であるか，正に再帰的であるかのいずれかである．
離散エルゴード定理
Markov 連鎖 \(X\) が再帰的であるためには，既約性と非周期性が十分条件である．加えて，極限が零測度でなければ，正に再帰的である．
\(X=\{X_n\}_{n\in\mathbb{N}}\subset L(\Omega;E)\) をMarkov連鎖，\(E\) を可算集合とする． \(X\) が既約で非周期的ならば，次が成り立つ：
- 任意の本質的な状態 \(i\in E\) について，次が成り立つ： \[
p^n_{ij}\xrightarrow{n\to\infty}\mu_j=\frac{1}{\operatorname{E}_j[\tau_j]},\qquad j\in E.
\] 特に，任意の開始地点 \(i\in E\) について，\((p_{i-}^n)\) は \(\mu\) に全変動収束する．
- 加えて \(X\) が正に再帰的であるならば，\(\mu:=\{\mu_i\}_{i\in\mathcal{X}}\) は \(X\) のただ一つの不変確率測度である．
- \(X\) が零再帰的である場合は \(\mu_i\equiv0\) であり，\(X\) の不変確率測度は存在しない．
状態空間 \(E\) が有限である場合，正に再帰的＝エルゴード的ならば，必ず収束は（全変動ノルムに関して）指数速度で起こる．
しかし，\(E\) が可算無限である場合，速度は様々である．
\(\mathbb{N}\) 上の待ち時間の Markov 連鎖が，その良い例となっている．
待ち時間の Markov 過程
過程の定義
待ち時間の分布 \(\nu\in\mathcal{P}(\mathbb{R}^+)\) は非零な１次の積率を持つとする．
\(\nu\) が定める再生過程を作り出す Markov 過程 \(\{X_t\}\) とは，離散時間の場合（第 2 節）と同様，
- \(\mathbb{R}^+\) 上で \(\dot{X}_t=-1\)．
- \(X_t=0\) のとき，次の瞬間 \(\nu\) に従って選択されたある正の値にジャンプする．
このとき，次が成り立つ：
上で定義した Markov 過程 \(\{X_t\}\) について，
- 生成作用素は次で定まる： \[
Lf(x)=-\frac{d f(x)}{d x},\qquad f\in\mathcal{D}(L),
\] \[
\mathcal{D}(L):=\left\{f\in\mathcal{L}^1(\nu)\,\middle|\,f(0)=\int^\infty_0f(x)\nu(dx)\right\}.
\]
- 次で定まる確率分布 \(\mu_*\in\mathcal{P}(\mathbb{R}_+)\) は \(\{X_t\}\) に関して不変である： \[
\mu_*(dx)=c\nu([x,\infty])dx,
\] \[
c:=\int^\infty_0y\nu(dy)\in(0,\infty).
\]
収束 \[
\frac{P_tf(x)-f(x)}{t}\to-\frac{d f(x)}{d x}\qquad t\to\infty,
\] は，\(x\ne0\) の場合直ちに成り立つ．
これが \(x=0\) の場合も含めて一様に成り立つことと，\((\nu|f)=f(0)\) は同値である．
任意の \(f\in C_c^1(\mathbb{R}_+)\cap\mathcal{D}(L)\) について，次のようにして \((\mu_*|Lf)=0\) が示せるためである： \[\begin{align*}
(\mu_*|Lf)&=-\int^\infty_0f'(x)\mu_*(dx)=-c\int^\infty_0f'(x)\nu([x,\infty))\,dx\\
&=-c\biggl[f(x)\nu([x,\infty))\biggr]^\infty_0-c\int^\infty_0f(x)\nu(dx)=cf(0)-cf(0)=0.
\end{align*}\]
多項式エルゴード性
待ち時間の分布は \(\nu\ll\ell_1\) で密度 \(p\) をもち，ある \(\zeta>2\) が存在して \(p\) は \(x^{-\zeta}\) のレートを持つとする： \[
\frac{c_-}{x^\zeta}\le p(x)\le\frac{c_+}{x^\zeta}
\] このとき，次の多項式エルゴード性が成り立つ： \[
\|P^t(x,-)-\mu_*\|_\mathrm{TV}\le C\frac{x^\alpha}{t^{\alpha-1}},
\] \[
t\ge0,x\in\mathbb{R}_+,\alpha\in(0,\zeta-1).
\] 加えて，次が成り立つ： \[
\lim_{t\to\infty}\frac{\log\|P_t(x,-)-\mu_*\|_\mathrm{TV}}{\log t}=2-\xi.
\]
\(V(x):=x^{\alpha}\;\mathrm{on}\;[1,\infty)\;(\alpha>0)\) という形の関数であって，\(V\in\mathcal{D}(L)\) を満たすものが存在する．
\(\alpha\in(0,\zeta-1)\) を満たすように取れば， \[
\int^\infty_0V(x)\nu(dx)=\int^1_0V(x)p(x)dx+c_+\int_1^\infty x^{\alpha-\xi}dx<\infty
\] より，この値を \(V(0)\) とし，\((0,\infty)\) 上で \(C^1\)-級になるように繋げば良い．
このとき， \[
LV(x)=-\alpha x^{\alpha-1}=-\alpha V(x)^{1-\frac{1}{\alpha}}\qquad\mathrm{on}\;[1,\infty)
\] が成り立つ．即ち，Lyapunov関数 \(\varphi(x):=\alpha x^{1-\frac{1}{\alpha}}\) に関する劣線型ドリフト条件を満たす．スケルトンの議論を通じて，多項式エルゴード定理より，\(\frac{(1-1/\alpha)}{1-(1-1/\alpha)}=\alpha-1\) のレートで収束する： \[
\|P^t(x,-)-\mu_*\|_\mathrm{TV}\le C\frac{\lvert x\rvert^\alpha}{t^{\alpha-1}}.
\] ここで \(\alpha\in(0,\zeta-1)\) は任意の値であったから， \[
\log\|P^t(x,-)-\mu_*\|_\mathrm{TV}\le\log C+\alpha\log x-(\alpha-1)\log t
\] \[
\therefore\qquad\limsup_{t\to\infty}\frac{\log\|P^t(x,-)-\mu_*\|_\mathrm{TV}}{\log t}\le\limsup_{\alpha<\zeta-1}-(\alpha-1)=2-\zeta.
\]
最後の主張を示す．まず，\(LV\) は上に有界であるから， \[
\frac{d }{d t}P_tV(x)=P_tLV(x)\le C
\] \[
\therefore\qquad P_tV(x)\le Ct+x^\alpha=:g(x,t).
\] 続いて，\(\frac{c_-}{x^\zeta}\le p(x)\) より，\(\mu_*\) の密度は下から評価できる： \[
\frac{\mu_*(dx)}{dx}=\int^\infty_xp(y)\,dy\ge\int^\infty_x\frac{c_-}{y^\zeta}\,dy=cx^{1-\zeta}.
\] これより， \[
\mu_*[V>R]=\mu_*[x>R^{1/\alpha}]\ge CR^{-\frac{\zeta-2}{\alpha}}=:f(R)
\] を得る．以上の評価とから， \[
\frac{1}{2}\|P^t(x,-)-\mu_*\|_\mathrm{TV}\ge f(R)-\frac{g(x,t)}{R}=CR^{-\frac{\zeta-2}{\alpha}}-\frac{\lvert x\rvert^\alpha+Ct}{R}
\] \(R>0\) について最適化することで， \[
\|P^t(x,-)-\mu_*\|_\mathrm{TV}\ge C\biggr(\lvert x\rvert^\alpha+Ct\biggl)^{\frac{\zeta-2}{\zeta-2-\alpha}}.
\] 同様にして，\(\alpha\nearrow\zeta-1\) を考えることで結論が従う．
References
Aalen, O. (1978).
Nonparametric inference for a family of counting processes.
The Annals of Statistics,
6(4), 701–726.
Mitov, K. V., and Omey, E. (2014).
Renewal processes. Springer Cham.
Resnick, S. I. (2002).
Adventures in stochastic processes. Birkhäuser Boston.
Robert, C. P., and Casella, G. (2004). Monte carlo statistical methods. Springer New York.
