# Markov 連鎖と Poisson 過程：Doeblin のエルゴード定理から正準経路の比較まで > 離散時間 Markov 連鎖の Doeblin のエルゴード定理を縮小写像で証明し、Poisson 過程と跳び過程、一様化による連続時間 Markov 連鎖を構成する。Dirichlet 形式と正準経路でスペクトルギャップを比較する。 > https://rikai.mugen-giken.com/mathematics/probability/markov-chains-poisson ## 0. この記事の要点 天気が「今日が雨なら明日も雨になりやすい」ように、次の状態が今の状態だけで決まる仕組みを数学で扱うのがこの記事です。そうした仕組みを長く動かすと、出発点の違いはいつか忘れられ、決まった分布に落ち着きます。どんな条件でそうなるのか、どれだけ速いのかを、証明つきで示します。後半では、電話の着信のように連続した時間のなかでランダムに起きる出来事の数え方も作ります。 - **Markov 連鎖**は「未来は現在だけを通じて過去に依存する」確率過程で、遷移行列 $P$ だけで決まります。分布は $\mu\mapsto\mu P$ と変化します。 - **Doeblin のエルゴード定理**：ある $m$ ステップ後の遷移確率がすべての出発点から共通の分布 $\nu$ を $\delta$ 倍以上含む（$P^m(x,\cdot)\ge\delta\nu$）なら、定常分布 $\pi$ が一意に存在し、任意の初期分布からの全変動距離（二つの分布のずれを $0$ から $1$ で測る距離）が $(1-\delta)^{\lfloor n/m\rfloor}$ 以下の速さで $\pi$ に収束します（）。証明は縮小写像の原理（完備な距離空間で、距離を一定の割合以下に縮める写像には、動かない点がただ一つある）だけです。 - **Poisson 過程**は、独立な指数分布に従う待ち時間の和として到着時刻を並べたものです。時刻 $t$ までの到着数は $\mathrm{Poi}(\lambda t)$、増分は独立で定常になります（）。到着ごとに独立な大きさのジャンプを足すと**跳び過程**（複合 Poisson 過程）になります。 - **連続時間 Markov 連鎖**は、Poisson 過程の到着時刻に離散連鎖を動かす**一様化**で構成できます（）。遷移半群は $e^{tQ}$ で、Kolmogorov 方程式を満たします。 - 可逆な連鎖の収束の速さはスペクトルギャップ（収束の速さを表す一つの数）で決まり、**Dirichlet 形式**（関数の「でこぼこ」の大きさを測る量）で書けます。単純な参照連鎖との**正準経路による比較**で、ギャップを下から評価できます（）。 ## 1. 動機 [中心極限定理](/mathematics/probability/limit-theorems)までは独立な確率変数の和を扱いました。ところが現実の確率モデルでは、各時刻の値が前の時刻の値に依存します。天気の推移、待ち行列、物理系の確率的な時間発展、モンテカルロ法（Markov 連鎖モンテカルロ）の探索点がそうです。最も単純な依存は「次の値の分布が現在の値だけで決まる」というもので、これが Markov 性です。 Markov 連鎖に対して自然な問いが二つあります。 1. 長い時間のあとの分布はどうなるか。出発点を忘れて**定常分布**に近づくのか、近づくならどれだけ速いか（エルゴード定理）。 2. 時間が連続で、状態がランダムな時刻にジャンプする系はどう作るか（Poisson 過程と連続時間連鎖）。 この記事は、ほとんど条件なしに強い結論が出る Doeblin の定理で 1 に答え、指数分布の無記憶性を軸に 2 に答えます。最後に、速さを定量化する量であるスペクトルギャップを、複雑な連鎖から単純な連鎖との比較で評価する方法を示します。 以下、状態空間 $S$ は高々可算集合とし、確率ベクトル（$S$ 上の確率分布）を行ベクトル $\mu=(\mu(x))_{x\in S}$ と書きます。全変動距離は $\|\mu-\nu\|_{\mathrm{TV}}=\tfrac12\sum_x|\mu(x)-\nu(x)|\in[0,1]$ です。 ## 2. 離散時間 Markov 連鎖 行列 $P=(P(x,y))_{x,y\in S}$ が**遷移行列**（確率行列）であるとは、$P(x,y)\ge0$ かつ各行の和が $\sum_yP(x,y)=1$ であることをいう。$S$ 値の確率変数列 $(X_n)_{n\ge0}$ が**初期分布 $\mu$、遷移行列 $P$ の Markov 連鎖**であるとは、$P(X_0=x)=\mu(x)$ で、すべての $n$ と $x_0,\dots,x_n,y\in S$（左辺の条件の確率が正のもの）について $$ P(X_{n+1}=y\mid X_0=x_0,\dots,X_n=x_n)=P(x_n,y) $$ が成り立つことをいう。 条件つき確率を掛け合わせると、$P(X_0=x_0,\dots,X_n=x_n)=\mu(x_0)P(x_0,x_1)\cdots P(x_{n-1},x_n)$ です。この式を連鎖の定義と考えてもかまいません。 任意の初期分布 $\mu$ と遷移行列 $P$ に対し、$\mu$、$P$ の Markov 連鎖が存在する。 $S$ の元に $1,2,\dots$ と番号を付けます。区間 $[0,1)$ 上の独立な一様乱数の列 $U_0,U_1,\dots$ が取れます（確率測度の無限直積、）。$X_0$ を $U_0$ で $\mu$ に従うよう定め（$\mu(1)+\dots+\mu(x-1)\le U_0<\mu(1)+\dots+\mu(x)$ のとき $X_0=x$）、 $$ X_{n+1}=y\quad\Longleftrightarrow\quad\sum_{y' $(X_n)$ を初期分布 $\mu$、遷移行列 $P$ の Markov 連鎖とすると、$P(X_n=y)=(\mu P^n)(y)$、$P(X_{m+n}=y\mid X_m=x)=P^n(x,y)$。ここで行列の積は $(PQ)(x,y)=\sum_zP(x,z)Q(z,y)$（可算和）である。 $P(X_n=y)=\sum_{x_0,\dots,x_{n-1}}\mu(x_0)P(x_0,x_1)\cdots P(x_{n-1},y)$ は行列積の定義そのものです（和は非負項の可算和で、順序によらない。 の 1 を添字二つずつに繰り返し使う）。後半は同様に、$X_m=x$ の条件のもとでの再帰です。 確率分布 $\pi$ が $P$ の**定常分布**であるとは $\pi P=\pi$ のことをいう。$\pi(x)P(x,y)=\pi(y)P(y,x)$（すべての $x,y$）が成り立つとき、$\pi$ は $P$ に関して**詳細つり合い**を満たす（$P$ は $\pi$ について**可逆**である）という。 $\pi$ が $P$ に関して詳細つり合いを満たすなら、$\pi$ は $P$ の定常分布である。 $(\pi P)(y)=\sum_x\pi(x)P(x,y)=\sum_x\pi(y)P(y,x)=\pi(y)$。 $S$ を有限集合、$\pi$ を $S$ 上の正の確率分布（例：Boltzmann 分布 $\pi(x)\propto e^{-\beta H(x)}$）、$K$ を対称な遷移行列（提案）で既約（任意の 2 点が正の確率で結ばれる）とします。 $$ P(x,y)=K(x,y)\min\Bigl(1,\frac{\pi(y)}{\pi(x)}\Bigr)\ (y\ne x),\qquad P(x,x)=1-\sum_{y\ne x}P(x,y) $$ とすると、$\pi(x)P(x,y)=K(x,y)\min(\pi(x),\pi(y))$ が対称なので $\pi$ は詳細つり合いを満たし、定常分布です。$\pi$ の正規化定数を知らなくても $P$ が計算できる点が実用上の利点です。$K(x,y)>0$ なら $P(x,y)>0$ なので $P$ も既約です。 ## 3. Doeblin のエルゴード定理 次の縮小補題が、この節の鍵です。直観はこうです。条件 $Q(x,y)\ge\delta\nu(y)$ は、一歩進むとき割合 $\delta$ だけは出発点によらず共通の分布 $\nu$ から選ばれる、ということです。この部分では出発点の違いが消えます。残りの割合 $1-\delta$ の部分では、二つの分布の距離は増えません。だから、一歩ごとに距離が $1-\delta$ 倍以下になります。 $Q$ を遷移行列とし、確率分布 $\nu$ と $\delta\in(0,1]$ があって、すべての $x,y$ で $Q(x,y)\ge\delta\nu(y)$ とする。このとき、任意の確率分布 $\mu,\mu'$ に対し $$ \|\mu Q-\mu'Q\|_{\mathrm{TV}}\le(1-\delta)\,\|\mu-\mu'\|_{\mathrm{TV}} . $$ $\delta<1$ とします（$\delta=1$ なら $Q(x,\cdot)=\nu$ で $\mu Q=\mu'Q=\nu$、自明）。$Q'(x,y)=\dfrac{Q(x,y)-\delta\nu(y)}{1-\delta}$ は非負で各行の和が $1$ の遷移行列、$Q=\delta\mathbf 1\nu+(1-\delta)Q'$（$\mathbf 1\nu$ は各行が $\nu$ の行列）です。$\eta=\mu-\mu'$ とおくと $\sum_x\eta(x)=0$ なので $\eta\mathbf 1\nu=0$、したがって $\eta Q=(1-\delta)\eta Q'$ です。 $$ \sum_y|(\eta Q')(y)|\le\sum_y\sum_x|\eta(x)|Q'(x,y)=\sum_x|\eta(x)| $$ より $\|\eta Q'\|_{\mathrm{TV}}\le\|\eta\|_{\mathrm{TV}}$。両辺に $1-\delta$ を掛ければ主張です。 $P$ を $S$ 上の遷移行列とし、ある整数 $m\ge1$、確率分布 $\nu$、$\delta\in(0,1]$ があって、すべての $x,y\in S$ で $$ P^m(x,y)\ge\delta\,\nu(y) $$ が成り立つ（**Doeblin の条件**）とする。このとき 1. $P$ の定常分布 $\pi$ がただ一つ存在する。 2. 任意の初期分布 $\mu$ と $n\ge0$ に対し $$ \|\mu P^n-\pi\|_{\mathrm{TV}}\le(1-\delta)^{\lfloor n/m\rfloor} . $$ $\mathcal{P}$ を $S$ 上の確率分布全体とし、$\ell^1(S)$ の距離 $2\|\cdot\|_{\mathrm{TV}}$ を入れます。$\ell^1$ は完備（）で、$\mathcal{P}$ はその閉部分集合（各座標の収束と総和 $1$ の保存、$\ell^1$ 収束なら成り立つ）なので、$\mathcal{P}$ は完備距離空間です。 を $Q=P^m$ に適用すると、写像 $\mu\mapsto\mu P^m$ は $\mathcal{P}$ の縮小写像（縮小率 $1-\delta<1$）です。 により、$\pi P^m=\pi$ を満たす $\pi\in\mathcal{P}$ がただ一つ存在します。 $\pi P$ もまた $\mathcal{P}$ の元で、$(\pi P)P^m=(\pi P^m)P=\pi P$ なので $P^m$ の不動点です。一意性から $\pi P=\pi$。逆に $\pi'P=\pi'$ なる確率分布は $\pi'P^m=\pi'$ を満たすので $\pi'=\pi$。これが (1) です。 (2)：$n=km+r$（$0\le r を $k$ 回使って $$ \|\mu P^n-\pi\|_{\mathrm{TV}}=\|(\mu P^r)P^{km}-\pi P^{km}\|_{\mathrm{TV}}\le(1-\delta)^k\|\mu P^r-\pi\|_{\mathrm{TV}}\le(1-\delta)^k . $$ Doeblin の条件は、有限状態の既約な連鎖の多くで自動的に成り立ちます。 $S$ を有限集合、$P$ を既約（任意の $x,y$ に対し、ある $n$ で $P^n(x,y)>0$）な遷移行列とし、ある状態 $x_*$ で $P(x_*,x_*)>0$ とする。このとき、ある $m$ で $P^m$ の全成分が正であり、 の条件が成り立つ。したがって一意な定常分布 $\pi$ への指数的収束が成り立つ。 $x,y\in S$ に対し $n_1(x)$ を $P^{n_1}(x,x_*)>0$、$n_2(y)$ を $P^{n_2}(x_*,y)>0$ となる整数とします。$x$ から $x_*$ へ $n_1$ ステップ、$x_*$ に $k$ ステップ留まり（確率 $P(x_*,x_*)^k>0$）、$y$ へ $n_2$ ステップ進む経路があるので $P^{n_1(x)+k+n_2(y)}(x,y)>0$（$k\ge0$ は任意）です。$m_0=\max_{x}n_1(x)+\max_yn_2(y)$ とすると、$m\ge m_0$ で $P^m(x,y)>0$（$k=m-n_1(x)-n_2(y)\ge0$ を取る）。$S$ は有限なので $p_{\min}=\min_{x,y}P^{m_0}(x,y)>0$、$\nu$ を一様分布、$\delta=|S|\,p_{\min}$ とすれば、$P^{m_0}(x,y)\ge p_{\min}=\delta\nu(y)$ です。 自己ループ（または一般に非周期性）の仮定は外せません。2 点 $\{1,2\}$ の上の連鎖 $P(1,2)=P(2,1)=1$ は既約ですが、$X_n$ は 1, 2, 1, 2, … と動いて分布は収束せず、$P^m$ の成分は $m$ が偶数か奇数かで $0$ になります。定常分布 $\pi=(1/2,1/2)$ はありますが、$\mu P^n$ は $\pi$ に近づきません。各ステップで確率 $1/2$ でその場に留まる「怠け者の連鎖」$\frac12(I+P)$ にすれば自己ループができ、 が使えます。 $S=\{1,2\}$、$P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}$（$0 の評価は上の厳密な値と同じ速さです。 ## 4. Poisson 過程と跳び過程 ランダムな時刻に起きる出来事（電話の着信、放射性崩壊、故障）の最も基本的なモデルが Poisson 過程です。到着の間隔が独立で指数分布に従う、として作ります。指数分布 $\mathrm{Exp}(\lambda)$ は、密度 $\lambda e^{-\lambda x}$（$x>0$）、$P(\tau>r)=e^{-\lambda r}$ を持つ分布でした（[確率変数と期待値](/mathematics/probability/random-variables)の例）。これは**無記憶性** $P(\tau>s+r\mid\tau>s)=e^{-\lambda r}$ を持ちます。 $\lambda>0$ とし、$\tau_1,\tau_2,\dots$ を独立な $\mathrm{Exp}(\lambda)$ 確率変数、$S_0=0$、$S_n=\tau_1+\cdots+\tau_n$（$n$ 番目の到着時刻）とする。 $$ N_t=\#\{n\ge1:S_n\le t\}\qquad(t\ge0) $$ で定まる過程 $(N_t)_{t\ge0}$ を、強度 $\lambda$ の **Poisson 過程**という。 $S_n/n\to1/\lambda$ がほとんど確実に成り立つ（強法則、）ので $S_n\to\infty$ で、$N_t$ は有限です。 $S_n$ は密度 $f_n(s)=\dfrac{\lambda^ns^{n-1}e^{-\lambda s}}{(n-1)!}$（$s>0$）を持つ。 $n=1$ は指数分布の密度です。$n$ で成り立つとき、独立な和の密度は畳み込みなので（）、 $$ f_{n+1}(s)=\int_0^sf_n(u)\,\lambda e^{-\lambda(s-u)}du=\frac{\lambda^{n+1}e^{-\lambda s}}{(n-1)!}\int_0^su^{n-1}du=\frac{\lambda^{n+1}s^ne^{-\lambda s}}{n!} . $$ 各 $t\ge0$ で $N_t\sim\mathrm{Poi}(\lambda t)$。すなわち $P(N_t=k)=e^{-\lambda t}\dfrac{(\lambda t)^k}{k!}$。 $q_k(t)=e^{-\lambda t}(\lambda t)^k/k!$（$k\ge0$）、$q_{-1}=0$ とおくと、$q_k'=\lambda(q_{k-1}-q_k)$ です。$n\ge1$ に対し $G_n(t)=\sum_{k\ge n}q_k(t)$ は（項別微分が一様収束で正当化され）$G_n'=\lambda q_{n-1}$ を満たし、$G_n(0)=0$ です。一方、$\{N_t\ge n\}=\{S_n\le t\}$ なので、 より $\frac d{dt}P(N_t\ge n)=f_n(t)=\lambda q_{n-1}(t)$、$P(N_0\ge n)=0$。両者は同じ微分と初期値を持つので $P(N_t\ge n)=G_n(t)$、差を取って $P(N_t=n)=q_n(t)$ です。 増分の独立性は、「ある時刻から先は、白紙から始めた Poisson 過程と同じ」という次の補題から出ます。時刻 $s$ の時点で次の到着までの残り時間は、それまでに何回、いつ到着していたかによらず、また $\mathrm{Exp}(\lambda)$ に従う、というのが指数分布の無記憶性の言い換えです。補題の式は、そのことを「確率が積に分かれる」形で書いたものです。 $s>0$ を固定する。$N_s=n$ のとき、$R_1=S_{n+1}-s$（時刻 $s$ から次の到着までの残り時間）、$R_k=\tau_{n+k}$（$k\ge2$）とおく。任意の $n\ge0$、ボレル集合 $A\subset\mathbb{R}^n$、$r_1,\dots,r_m\ge0$ に対し $$ P\bigl(N_s=n,\ (S_1,\dots,S_n)\in A,\ R_1>r_1,\dots,R_m>r_m\bigr)=P\bigl(N_s=n,\ (S_1,\dots,S_n)\in A\bigr)\prod_{j=1}^me^{-\lambda r_j}. $$ $\{N_s=n\}=\{S_n\le sr_1\}=\{\tau_{n+1}>s+r_1-S_n\}$ です。$(\tau_1,\dots,\tau_n)$ と $(\tau_{n+1},\tau_{n+2},\dots)$ が独立なので、左辺は $\tau_{n+1}$ について先に積分でき（）、$S_n\le s$ では $P(\tau_{n+1}>s+r_1-S_n)=e^{-\lambda r_1}e^{-\lambda(s-S_n)}$、$\tau_{n+2},\dots$ は独立に $e^{-\lambda r_j}$ ($j\ge2$) を与えます。よって $$ \text{左辺}=\prod_{j=1}^me^{-\lambda r_j}\cdot E\Bigl[\mathbf 1_{\{(S_1,\dots,S_n)\in A,\,S_n\le s\}}e^{-\lambda(s-S_n)}\Bigr]. $$ この期待値は、同じ計算を $m=0$ ($r_j$ なし) に行った $P(N_s=n,(S_1,\dots,S_n)\in A)$ に等しいです。 補題が言うことは、$N_s=n$ と $S_1,\dots,S_n$ を条件にとっても、$(R_1,R_2,\dots)$ は独立同分布の $\mathrm{Exp}(\lambda)$ 列のままだ、ということです（有限次元の裾確率が因数分解し、これが有限次元分布を決める）。 $(N_t)$ を強度 $\lambda$ の Poisson 過程とし、$0=t_0 $s>0$ とし、$N'_t=N_{s+t}-N_s$ とおきます。$N_s=n$ のとき $N'_t=\#\{j\ge1:R_1+\cdots+R_j\le t\}$ です。事象 $\{N'_{u_1}=a_1,\dots,N'_{u_l}=a_l\}$ は $R_1,\dots,R_{a_l+1}$ だけで決まるので、 から、任意の $n$ と $A$ に対し $$ P\bigl(N_s=n,\ (S_1,\dots,S_n)\in A,\ N'_{u_1}=a_1,\dots,N'_{u_l}=a_l\bigr)=P\bigl(N_s=n,\ (S_1,\dots,S_n)\in A\bigr)\,P\bigl(N_{u_1}=a_1,\dots,N_{u_l}=a_l\bigr). $$ ($R$ の有限次元分布が $\tau$ のものと同じであるため。) ところが $u\le s$ での $N_u$ は $N_s$ と $S_1,\dots,S_{N_s}$ の関数（$N_u=\#\{i\le N_s:S_i\le u\}$）なので、$(N'_t)_{t\ge0}$ は $(N_u)_{u\le s}$ と独立で、$(N_t)_{t\ge0}$ と同じ有限次元分布を持ちます。 これを $s=t_{k-1}$ に適用すると、最後の増分 $N_{t_k}-N_{t_{k-1}}=N'_{t_k-t_{k-1}}$ は $N_{t_k-t_{k-1}}\sim\mathrm{Poi}(\lambda(t_k-t_{k-1}))$ と同じ分布で、前の増分たち（$(N_u)_{u\le t_{k-1}}$ の関数）と独立です。$k$ に関する帰納法で全体の独立性が出ます。
S1 S2 S3 S4 S5 N t
### 4.1. 跳び過程 Poisson 過程の到着のたびに、独立な大きさのジャンプを足します。 $(N_t)$ を強度 $\lambda$ の Poisson 過程、$Y_1,Y_2,\dots$ を $N$ と独立な、独立同分布の実確率変数列とする。 $$ X_t=\sum_{k=1}^{N_t}Y_k\qquad(t\ge0) $$ を**跳び過程**（**複合 Poisson 過程**）という（$N_t=0$ のとき $X_t=0$）。 $\varphi_Y$ を $Y_k$ の特性関数とすると、 $$ E\bigl[e^{iuX_t}\bigr]=\exp\bigl(\lambda t\,(\varphi_Y(u)-1)\bigr). $$ さらに $E|Y|<\infty$ なら $E[X_t]=\lambda t\,E[Y]$、$E[Y^2]<\infty$ なら $\mathrm{Var}(X_t)=\lambda t\,E[Y^2]$。増分 $X_{t_i}-X_{t_{i-1}}$ は独立で、$X_{t_i-t_{i-1}}$ と同じ分布を持つ。 $N_t=n$ のとき $X_t=Y_1+\cdots+Y_n$ の特性関数は $\varphi_Y(u)^n$（独立和、 (4)）です。$N$ と $Y$ の独立性と から $$ E\bigl[e^{iuX_t}\bigr]=\sum_{n\ge0}e^{-\lambda t}\frac{(\lambda t)^n}{n!}\varphi_Y(u)^n=\exp\bigl(\lambda t(\varphi_Y(u)-1)\bigr). $$ $E[Y^2]<\infty$ のとき $E[X_t^2]=\sum_nP(N_t=n)E[(Y_1+\cdots+Y_n)^2]\le\sum_nP(N_t=n)\,n^2E[Y^2]<\infty$ なので（コーシー・シュワルツ）、積率は $u=0$ での微分（ (5)）で出ます：$\frac d{du}$ して $i\lambda tE[Y]$、二階で $-\lambda t E[Y^2]+(i\lambda tE[Y])^2$ より $E[X_t]=\lambda tE[Y]$、$E[X_t^2]=\lambda tE[Y^2]+(\lambda tE[Y])^2$。増分の独立性は、$N$ を与えると各区間の増分 $X_{t_i}-X_{t_{i-1}}=\sum_{N_{t_{i-1}}）から従います。 各到着を、独立に確率 $p$ で「赤」、確率 $1-p$ で「青」に塗り分けます。時刻 $t$ までの赤・青の到着数を $N^{r}_t,N^{b}_t$ とすると、$N_t=n$ のとき赤の数は $\mathrm{Bin}(n,p)$ なので $$ P(N^r_t=a,N^b_t=b)=e^{-\lambda t}\frac{(\lambda t)^{a+b}}{(a+b)!}\binom{a+b}ap^a(1-p)^b=\Bigl[e^{-p\lambda t}\frac{(p\lambda t)^a}{a!}\Bigr]\Bigl[e^{-(1-p)\lambda t}\frac{((1-p)\lambda t)^b}{b!}\Bigr]. $$ 積の形に分解されるので、$N^r_t\sim\mathrm{Poi}(p\lambda t)$ と $N^b_t\sim\mathrm{Poi}((1-p)\lambda t)$ は独立です。 ## 5. 連続時間 Markov 連鎖と一様化 連続時間で状態が飛び移る系を、**Poisson 過程の到着時刻に離散連鎖を一歩進める**ことで作ります。まず系を指定する量を定義します。 行列 $Q=(q(x,y))_{x,y\in S}$ が**レート行列**であるとは、$q(x,y)\ge0$（$x\ne y$）、$q(x,x)=-\sum_{y\ne x}q(x,y)$ であることをいう。$q(x)=-q(x,x)$ を状態 $x$ の**ジャンプ率**といい、ここでは $\Lambda_0=\sup_xq(x)<\infty$ とする（有界なレート）。 直観的には、状態 $x$ にいる系は、微小時間 $h$ のあいだに確率 $q(x,y)h+o(h)$ で $y\ne x$ へ移ります。 $Q$ をレート行列、$\Lambda\ge\Lambda_0$（$\Lambda>0$）とし、$P=I+Q/\Lambda$ とおく。$P$ は遷移行列である（$P(x,x)=1-q(x)/\Lambda\ge0$）。$(Y_n)_{n\ge0}$ を遷移行列 $P$ の Markov 連鎖、$(N_t)$ を強度 $\Lambda$ の Poisson 過程で $Y$ と独立なものとし、 $$ X_t=Y_{N_t}\qquad(t\ge0) $$ とおく。ポアソン重み $w_n(t)=e^{-\Lambda t}(\Lambda t)^n/n!$ を使って $P_t=\sum_{n\ge0}w_n(t)P^n$ と定める。このとき 1. **Markov 性**：$s,t\ge0$ と $\sigma(X_u:u\le s)$ に属する任意の事象 $E$ について $P(E\cap\{X_{s+t}=y\})=E\bigl[\mathbf 1_EP_t(X_s,y)\bigr]$。 2. **半群性**：$P_{s+t}=P_sP_t$、$P_0=I$。 3. **Kolmogorov 方程式**：$\dfrac{d}{dt}P_t=QP_t=P_tQ$。すなわち $P_t=e^{tQ}$。 **(2)(3)**　Poisson の和の公式 $w_n(s+t)=\sum_{j+k=n}w_j(s)w_k(t)$（二項定理）から $P_{s+t}=\sum_{j,k}w_j(s)w_k(t)P^{j+k}=P_sP_t$ です（成分ごとに見ると非負項の和で、$P^{j+k}$ の成分は $1$ 以下なので総和は $\sum_jw_j(s)\sum_kw_k(t)=1$ 以下です。よって絶対収束し、 の 2 により $j+k=n$ ごとにまとめてよく、行列積の中間の状態についての和との順序交換も同じ定理によります）。各 $P^n$ の行和は $1$ で、項別微分は一様に収束します。$w_n'=\Lambda(w_{n-1}-w_n)$ ($w_{-1}=0$) から $$ P_t'=\Lambda\sum_n(w_{n-1}-w_n)P^n=\Lambda(P-I)P_t=QP_t, $$ $P$ と $P_t$ は可換なので $P_tQ$ にも等しいです。$P_t=e^{-\Lambda t}e^{\Lambda tP}=e^{tQ}$ も同じ計算から従います。 **(1)**　$s$ を固定し、$K=N_s$、$N'_t=N_{s+t}-N_s$ とします。$N'$ は $(N_u)_{u\le s}$ と独立で $N$ と同じ分布を持ちます（）。$E\in\sigma(X_u:u\le s)$ は $(N_u)_{u\le s}$ と $(Y_0,\dots,Y_K)$ だけで決まります。$K=k$ の部分を $E_k=\{(N_u)_{u\le s}\in B_k\}\cap\{(Y_0,\dots,Y_k)\in C_k\}$ と書くと、$X_{s+t}=Y_{k+N'_t}$ ($K=k$ のとき) であり、$Y$ と $N$ の独立性、$N'$ と $(N_u)_{u\le s}$ の独立性から $$ P(E_k\cap\{K=k\}\cap\{N'_t=j\}\cap\{X_{s+t}=y\})=P\bigl((N_u)_{u\le s}\in B_k,K=k\bigr)\,P(N'_t=j)\,P\bigl((Y_0..Y_k)\in C_k,\ Y_{k+j}=y\bigr). $$ 最後の因子は、$Y$ の Markov 性と により $E\bigl[\mathbf 1_{C_k}(Y_0,\dots,Y_k)P^j(Y_k,y)\bigr]$ です。$j$ で和を取ると $\sum_jw_j(t)P^j(Y_k,y)=P_t(Y_k,y)$、さらに $k$ で和を取って $X_s=Y_K$ に注意すれば (1) です。 (1) は、$(X_t)$ が遷移半群 $(P_t)$ の連続時間 Markov 連鎖であることを表します：$P(X_{t_1}=y_1,\dots,X_{t_k}=y_k)=\sum_x\mu(x)P_{t_1}(x,y_1)P_{t_2-t_1}(y_1,y_2)\cdots$。(2) は **Chapman–Kolmogorov 方程式**です。(3) の $Q$ は $P_t$ の**生成子**で、$\frac{d}{dt}P_t|_{t=0}=Q$ です。 $X_0=x$ とし、$q(x)>0$ とする。最初に別の状態に移る時刻を $J=\inf\{t:X_t\ne x\}$ とすると、$J\sim\mathrm{Exp}(q(x))$、移った先 $X_J$ は $P(X_J=y)=q(x,y)/q(x)$ ($y\ne x$) で、$J$ と $X_J$ は独立である。 $K=\min\{n\ge1:Y_n\ne x\}$ とおくと、$J=S_K$（$N$ の $K$ 番目の到着時刻）です。$p=1-P(x,x)=q(x)/\Lambda$ として、$P(K=k,Y_K=y)=P(x,x)^{k-1}P(x,y)=(1-p)^{k-1}p\cdot\dfrac{P(x,y)}p$ と因数分解されるので、$K$ は[幾何分布](/mathematics/hs-probability/distributions-and-inference#def-geometric-distribution)、$Y_K$ はその確率が $P(x,y)/p=q(x,y)/q(x)$ で、$K$ と独立です。$Y$ と $N$ が独立なので、$(K,N)$ と $Y_K$ は独立、したがって $J=S_K$ と $Y_K=X_J$ は独立です。 $J$ の分布：指数分布 $\mathrm{Exp}(\Lambda)$ の特性関数は $\varphi(u)=\int_0^\infty\Lambda e^{-\Lambda x}e^{iux}dx=\Lambda/(\Lambda-iu)$ なので、 $$ E[e^{iuJ}]=\sum_{k\ge1}(1-p)^{k-1}p\,\varphi(u)^k=\frac{p\varphi}{1-(1-p)\varphi}=\frac{p\Lambda}{p\Lambda-iu}, $$ これは $\mathrm{Exp}(p\Lambda)=\mathrm{Exp}(q(x))$ の特性関数です。一意性（）により $J\sim\mathrm{Exp}(q(x))$ です。 こうして、連続時間連鎖は「状態 $x$ に $\mathrm{Exp}(q(x))$ だけ滞在し、確率 $q(x,y)/q(x)$ で $y$ に飛ぶ」ことの繰り返しで、これは跳び過程（$Y_k$ が状態の差）の一般化です。 上の設定で、$P=I+Q/\Lambda$ が Doeblin の条件 $P^m\ge\delta\nu$（$0<\delta<1$）を満たすとする。このとき $P$ の定常分布 $\pi$ は $\pi Q=0$ および $\pi P_t=\pi$ ($t\ge0$) を満たす唯一の確率分布で、任意の初期分布 $\mu$ に対し $$ \|\mu P_t-\pi\|_{\mathrm{TV}}\le\frac1{1-\delta}\exp\Bigl(-\Lambda t\bigl(1-(1-\delta)^{1/m}\bigr)\Bigr). $$ の $\pi$ は $\pi P=\pi$ を満たすので $\pi Q=\Lambda(\pi P-\pi)=0$、$\pi P_t=\sum w_n(t)\pi P^n=\pi$ です。$\pi'P_t=\pi'$ ($t$ 小で微分して) なら $\pi'Q=0$、すなわち $\pi'P=\pi'$ で $\pi'=\pi$（一意性）。評価は、$\pi=\pi P^n$ なので $$ \|\mu P_t-\pi\|_{\mathrm{TV}}\le\sum_nw_n(t)\|\mu P^n-\pi\|_{\mathrm{TV}}\le\sum_nw_n(t)(1-\delta)^{\lfloor n/m\rfloor}\le\frac{1}{1-\delta}\sum_nw_n(t)\bigl((1-\delta)^{1/m}\bigr)^n, $$ 最後は $\lfloor n/m\rfloor\ge n/m-1$ によります。右辺の和は $e^{-\Lambda t}\exp(\Lambda t(1-\delta)^{1/m})$ です。 ## 6. Dirichlet 形式・スペクトルギャップ・正準経路 収束の速さを、連鎖の「幾何」で評価します。ここでは $S$ を有限集合、$\pi$ を $S$ 上の正の確率分布とします。$f,g\colon S\to\mathbb{R}$ に対し $\langle f,g\rangle_\pi=\sum_x\pi(x)f(x)g(x)$、$\pi(f)=\langle f,1\rangle_\pi$、$\mathrm{Var}_\pi(f)=\langle f-\pi(f),f-\pi(f)\rangle_\pi=\min_{c\in\mathbb{R}}\sum_x\pi(x)(f(x)-c)^2$ とします。$P$ を $\pi$ に関して可逆な遷移行列とします。 $$ \mathcal{E}_P(f,f)=\langle f,(I-P)f\rangle_\pi=\frac12\sum_{x,y}\pi(x)P(x,y)\bigl(f(x)-f(y)\bigr)^2 $$ を $P$ の **Dirichlet 形式**、 $$ \lambda(P)=\min\Bigl\{\frac{\mathcal{E}_P(f,f)}{\mathrm{Var}_\pi(f)}:\ \mathrm{Var}_\pi(f)>0\Bigr\} $$ を**スペクトルギャップ**という。レート行列 $Q$（$\pi$ に関して可逆：$\pi(x)q(x,y)=\pi(y)q(y,x)$）については $\mathcal{E}_Q(f,f)=-\langle f,Qf\rangle_\pi=\frac12\sum\pi(x)q(x,y)(f(x)-f(y))^2$ と $\lambda(Q)$ を同様に定める。 $\mathcal{E}_P(f,f)$ は、関数 $f$ が遷移で結ばれた点どうしでどれだけ値を変えるかの総和で、$f$ が一様に近いほど小さくなります。スペクトルギャップは、これを分散で割った比の最小値です。 2 つ目の等式は、可逆性 $\sum_x\pi(x)P(x,y)=\pi(y)$ を使った展開 $\frac12\sum\pi(x)P(x,y)\bigl(f(x)^2+f(y)^2-2f(x)f(y)\bigr)=\sum\pi f^2-\sum\pi(x)P(x,y)f(x)f(y)$ から従います。$\mathcal{E}$ は $f$ に定数を足しても変わらず、$P$ の「$f$ の滑らかさ」を測る量です。 次の命題は、ギャップを固有値で書き直します。可逆な $P$ は一般には対称行列ではありませんが、$\pi$ の平方根で左右から挟んで $D^{1/2}PD^{-1/2}$ とすると実対称行列になります。対称行列なら、固有値が実数で、固有ベクトルの正規直交基底が取れるので、比の最小値を固有値の言葉で計算できます。証明ではこの変形を使います。 1. $P$ の固有値は実数で、$1=\beta_0\ge\beta_1\ge\cdots\ge\beta_{|S|-1}\ge-1$ と並べられ、$\lambda(P)=1-\beta_1$。 2. $Q$ を $\pi$ に関して可逆なレート行列とする。$Q$ の固有値は $0=-\kappa_0\ge-\kappa_1\ge\cdots$ と実数で、$\lambda(Q)=\kappa_1$。さらに連続時間連鎖の半群について、任意の $f$ と $t\ge0$ で $$ \mathrm{Var}_\pi(P_tf)\le e^{-2\lambda(Q)t}\,\mathrm{Var}_\pi(f). $$ $D=\mathrm{diag}(\pi)$ とし、$S_P=D^{1/2}PD^{-1/2}$、すなわち $S_P(x,y)=\sqrt{\pi(x)}P(x,y)/\sqrt{\pi(y)}$ とします。可逆性から $S_P$ は実対称行列です。したがって により、実固有値を持つ正規直交固有ベクトルの基底があります。$v_0=\sqrt\pi=(\sqrt{\pi(x)})_x$ について $(S_Pv_0)(x)=\sqrt{\pi(x)}\sum_yP(x,y)=v_0(x)$ なので $v_0$ は固有値 $1$ の固有ベクトルで、$\|v_0\|=1$ です。$P$ の固有値は $|\beta|\le1$ ($\|P\|_\infty=1$)。 $g=D^{1/2}f$ と対応させると、$\langle f,f\rangle_\pi=|g|^2$、$\langle f,Pf\rangle_\pi=g^{\mathsf T}S_Pg$、$\pi(f)=\langle g,v_0\rangle$ です。$g=cv_0+g_\perp$ ($g_\perp\perp v_0$) と分解すると、$\mathrm{Var}_\pi(f)=|g_\perp|^2$、$\mathcal{E}_P(f,f)=g_\perp^{\mathsf T}(I-S_P)g_\perp$（$S_Pv_0=v_0$ より $c$ の項は消える）。$v_0^\perp$ 上で $S_P$ の固有値は $\beta_1\ge\dots$ なので、 の形のレイリー商の最小化により $\min\mathcal{E}/\mathrm{Var}=1-\beta_1$ です。 $Q$ についても $S_Q=D^{1/2}QD^{-1/2}$ は実対称で、同様に $\lambda(Q)=\kappa_1$（$S_Q$ の固有値 $-\kappa_k$、$\kappa_0=0$）。半群は $P_t=e^{tQ}$ なので、$g$ を $S_Q$ の固有基底で展開すると、$v_0$ 成分は変わらず（$\pi(P_tf)=\pi(f)$）、他の成分は $e^{-\kappa_kt}\le e^{-\kappa_1t}$ 倍に縮みます。ゆえに $|g_\perp(t)|^2\le e^{-2\kappa_1t}|g_\perp(0)|^2$ です。 これで、Dirichlet 形式を下から評価すれば収束の速さが言えるようになりました。複雑な連鎖 $P$ を、スペクトルギャップの分かっている単純な連鎖 $\tilde P$ と**正準経路**で結んで比べるのが次の定理です。 次の定理の $A$ は、辺の「混み具合」の最大値です。参照連鎖の遷移 $(x,y)$ ごとに、$P$ の辺をたどる経路 $\gamma_{xy}$ を一つ決めます。$P$ の各辺 $(z,w)$ について、その辺を通る経路に割り当てられた参照連鎖側の重み（経路の長さも掛ける）を足し合わせ、$P$ 自身のその辺の重み $\pi(z)P(z,w)$ で割ったものが混み具合です。どの辺も混んでいなければ $A$ は小さく、$P$ は参照連鎖に近いギャップを持ちます。 $P,\tilde P$ をそれぞれ正の確率分布 $\pi,\tilde\pi$ に関して可逆な $S$ 上の遷移行列とする。$\tilde P(x,y)>0$、$x\ne y$ なる各対 $(x,y)$ に、$P$ で実現可能な経路 $\gamma_{xy}=(x=x_0,x_1,\dots,x_k=y)$（$P(x_{i-1},x_i)>0$）を一つ選び、その長さを $|\gamma_{xy}|=k$ と書く。 $$ A=\max_{(z,w):\,P(z,w)>0,\ z\ne w}\ \frac1{\pi(z)P(z,w)}\sum_{(x,y):\ \gamma_{xy}\ni(z,w)}|\gamma_{xy}|\,\tilde\pi(x)\tilde P(x,y),\qquad a=\min_x\frac{\tilde\pi(x)}{\pi(x)} $$ とおく（和は、経路 $\gamma_{xy}$ が辺 $(z,w)$ を通る対にわたる）。このとき $$ \mathcal{E}_{\tilde P}(f,f)\le A\,\mathcal{E}_P(f,f),\qquad\lambda(P)\ge\frac aA\,\lambda(\tilde P). $$ $\mathcal{E}_{\tilde P}(f,f)=\frac12\sum_{x\ne y}\tilde\pi(x)\tilde P(x,y)(f(x)-f(y))^2$ です。経路 $\gamma_{xy}$ に沿って $f(x)-f(y)=\sum_{e\in\gamma_{xy}}\bigl(f(e^-)-f(e^+)\bigr)$（$e=(e^-,e^+)$ は経路の辺）と書き、コーシー・シュワルツの不等式 で $$ \bigl(f(x)-f(y)\bigr)^2\le|\gamma_{xy}|\sum_{e\in\gamma_{xy}}\bigl(f(e^-)-f(e^+)\bigr)^2 . $$ これを代入して和の順序を辺 $e=(z,w)$ ごとに並べ替えると、 $$ \mathcal{E}_{\tilde P}(f,f)\le\frac12\sum_{(z,w)}\bigl(f(z)-f(w)\bigr)^2\sum_{\gamma_{xy}\ni(z,w)}|\gamma_{xy}|\tilde\pi(x)\tilde P(x,y)\le\frac12\sum_{(z,w)}A\,\pi(z)P(z,w)\bigl(f(z)-f(w)\bigr)^2=A\,\mathcal{E}_P(f,f). $$ 次にギャップ。$\mathrm{Var}_{\tilde\pi}(f)=\min_c\sum_x\tilde\pi(x)(f(x)-c)^2\ge a\min_c\sum_x\pi(x)(f(x)-c)^2=a\,\mathrm{Var}_\pi(f)$ です。したがって、$\mathrm{Var}_\pi(f)>0$ の $f$ に対し、 $$ \mathcal{E}_P(f,f)\ge\frac1A\mathcal{E}_{\tilde P}(f,f)\ge\frac{\lambda(\tilde P)}A\mathrm{Var}_{\tilde\pi}(f)\ge\frac{a\,\lambda(\tilde P)}A\mathrm{Var}_\pi(f) . $$ $n=2m+1$ ($m\ge1$) 点の円周 $\mathbb{Z}/n$ 上で、$P(x,x\pm1)=\tfrac12$ の単純ランダムウォークを考えます。$\pi$ は一様分布です。参照連鎖として $\tilde P(x,y)=1/n$（すべての $x,y$、$x=y$ を含む）を取ります。$\tilde\pi=\pi$、$a=1$ で、 $$ \mathcal{E}_{\tilde P}(f,f)=\frac1{2n^2}\sum_{x,y}(f(x)-f(y))^2=\mathrm{Var}_\pi(f) $$ なので $\lambda(\tilde P)=1$ です。各対 $(x,y)$ に、$y=x+\ell$ ($1\le\ell\le m$) なら前進する $\ell$ 歩、$y=x-\ell$ なら後退する $\ell$ 歩の短い弧を経路として選びます。前進辺 $(z,z+1)$ を通る対は、長さ $\ell$ の弧ごとに $\ell$ 個あるので、 $$ \frac{1}{\pi(z)P(z,z+1)}\sum_{\ell=1}^m\ell\cdot\ell\cdot\frac1{n^2}=2n\cdot\frac{1}{n^2}\cdot\frac{m(m+1)(2m+1)}6=\frac{m(m+1)}3=\frac{n^2-1}{12}. $$ 後退辺も対称です。よって $A=(n^2-1)/12$ で、 から $$ \lambda(P)\ge\frac{12}{n^2-1}. $$ 真の値は $\lambda(P)=1-\cos(2\pi/n)$（ の $\beta_1$ は $S_P=P$ の最大の非自明固有値 $\cos(2\pi/n)$）です。 | $n$ | $12/(n^2-1)$ | $1-\cos(2\pi/n)$ | |---|---|---| | 3 | 1.5000 | 1.5000 | | 5 | 0.5000 | 0.6910 | | 7 | 0.2500 | 0.3765 | | 11 | 0.1000 | 0.1587 | $n=3$ では等号が成り立ち、大きい $n$ でも評価は真の値の約 $0.6$ 倍（$12/(2\pi^2)\approx0.61$）で、オーダー $1/n^2$ は正確です。連続時間版（ (2)）を使えば、連続時間版のこのウォーク（レート $1/2$ で左右に飛ぶ）の $L^2$ 距離が $e^{-\lambda t}$ で減ることになるので、緩和の時間スケールは $1/\lambda\approx n^2$ のオーダーです。 比較定理は、実際の計算で次のように使われます。直接解析できない連鎖（相互作用のあるスピン系のダイナミクスなど）の Dirichlet 形式を、座標を独立に取り替える単純な連鎖（ギャップが明示的）と比べます。経路を上手に選ぶ（辺の通過数を均等に散らす）ほど $A$ が小さくなり、良い評価になります。連続時間版（レート行列）でも、証明はまったく同じです。 ## 7. 演習 無向グラフ $G$ の頂点上のランダムウォーク（隣接する頂点へ等確率で移る）$P(x,y)=1/\deg(x)$ は、$\pi(x)=\deg(x)/\sum_z\deg(z)$ に関して可逆であることを示せ。3 頂点の直線 $1-2-3$ について $\pi$ を求めよ。 隣接する $x,y$ について $\pi(x)P(x,y)=\dfrac{\deg x}{2|E|}\cdot\dfrac1{\deg x}=\dfrac1{2|E|}$（$|E|$ は辺数）で、$x,y$ について対称なので詳細つり合いが成り立ちます（隣接しないなら両辺 $0$）。直線 $1-2-3$ では $\deg=(1,2,1)$、$\sum\deg=4$ で $\pi=(1/4,1/2,1/4)$。確認：$\pi_1P(1,2)=1/4\cdot1=1/4=\pi_2P(2,1)=1/2\cdot1/2$。この連鎖は 2 部グラフなので周期 $2$ で、分布は収束しません（）。 強度 $\lambda$ の Poisson 過程で、$N_t=1$ という条件のもとで最初の到着時刻 $S_1$ の分布は $[0,t]$ 上の一様分布であることを示せ。 $0 の独立増分と より $$ P(S_1\le s,N_t=1)=\lambda se^{-\lambda s}\cdot e^{-\lambda(t-s)}=\lambda se^{-\lambda t} . $$ $P(N_t=1)=\lambda te^{-\lambda t}$ で割ると $P(S_1\le s\mid N_t=1)=s/t$ で、一様分布の分布関数です。 $S=\{1,2,3\}$、$P=\begin{pmatrix}1/2&1/4&1/4\\1/3&1/3&1/3\\0&1/2&1/2\end{pmatrix}$ とする。$m=1$ の Doeblin の条件の $\delta$ を求め、定常分布 $\pi$ を計算し、初期分布 $\delta_1$ から出発したとき $\|\mu P^n-\pi\|_{\mathrm{TV}}\le(1-\delta)^n$ を $n=1$ で確かめよ。 $\delta=\sum_y\min_xP(x,y)$ で、第 1 列の最小は $0$、第 2 列は $1/4$、第 3 列は $1/4$ なので $\delta=1/2$ です。$\pi P=\pi$：第 1 成分 $\pi_1=\frac12\pi_1+\frac13\pi_2$ から $\pi_2=\frac32\pi_1$、第 3 成分 $\pi_3=\frac14\pi_1+\frac13\pi_2+\frac12\pi_3$ から $\pi_3=\frac32\pi_1$。和が $1$ なので $\pi_1=1/4$、$\pi=(1/4,3/8,3/8)$（第 2 成分も $\frac14\cdot\frac14+\frac13\cdot\frac38+\frac12\cdot\frac38=\frac38$ で確認できる）。$\mu=\delta_1$ なら $\mu P=(1/2,1/4,1/4)$ で、 $$ \|\mu P-\pi\|_{\mathrm{TV}}=\tfrac12\bigl(\tfrac14+\tfrac18+\tfrac18\bigr)=\tfrac14\le\tfrac12=(1-\delta)^1 . $$ レート行列 $Q=\begin{pmatrix}-a&a\\b&-b\end{pmatrix}$（$a,b>0$）の遷移半群が $$ P_t=e^{-ct}I+(1-e^{-ct})\Pi,\qquad c=a+b,\quad\Pi=\begin{pmatrix}\frac b{c}&\frac ac\\\frac bc&\frac ac\end{pmatrix} $$ であることを、一様化（）を $\Lambda=c$ で適用して示せ。 $\Lambda=c=a+b\ge\max(a,b)$ とすると $P=I+Q/c=\begin{pmatrix}1-a/c&a/c\\b/c&1-b/c\end{pmatrix}=\begin{pmatrix}b/c&a/c\\b/c&a/c\end{pmatrix}=\Pi$ です（$1-a/c=b/c$）。$\Pi$ は各行が同じ確率ベクトル $\pi=(b/c,a/c)$ なので $\Pi^2=\Pi$（$\Pi\Pi(x,y)=\sum_z\Pi(x,z)\pi(y)=\pi(y)$）、したがって $n\ge1$ で $\Pi^n=\Pi$ です。 $$ P_t=w_0(t)I+\sum_{n\ge1}w_n(t)\Pi=e^{-ct}I+(1-e^{-ct})\Pi . $$ ここで $\sum_nw_n=1$ を使いました。この連鎖の TV 距離は $|\mu_1-\pi_1|e^{-ct}$ で、 の結果の連続時間版です。 ## 参考文献 - J. R. Norris『Markov Chains』Cambridge University Press、1997 — 第 1 章（離散時間）、第 2 章（連続時間 Markov 連鎖、Poisson 過程）。 - David A. Levin, Yuval Peres, Elizabeth L. Wilmer『Markov Chains and Mixing Times』（第 2 版）American Mathematical Society、2017 — 第 4 章（収束定理）、第 12–13 章（スペクトルギャップ、比較法）。 - Persi Diaconis, Laurent Saloff-Coste, "Comparison theorems for reversible Markov chains", *Annals of Applied Probability* 3 (1993), 696–730. - Wolfgang Doeblin, "Éléments d'une théorie générale des chaînes simples constantes de Markoff", *Annales scientifiques de l'École Normale Supérieure* 57 (1940), 61–111. - Pierre Brémaud『Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues』Springer、1999 — 第 3–4 章。