マルコフ連鎖とランダムウォーク

この章の目標

• マルコフ連鎖を推移確率で記述し、マルコフ性・強マルコフ性を使って計算できる
• 状態を再帰・過渡・周期で分類し、単純ランダムウォークの再帰性（ポリアの定理）を証明できる
• 定常分布の存在と一意性、カップリングによる収束定理、エルゴード定理を証明できる
• 詳細つり合いと可逆性を理解し、メトロポリス法の原理を説明できる

前提：第1章、第2章（大数の強法則）、第5章（停止時刻）、06-measure-integration 第5章（フビニの定理）

6.1 マルコフ連鎖

ランダムウォーク、ギャンブラーの所持金、壺の中の玉の数などでは、次の状態が確率的に決まり、その法則が現在の状態だけに依存して過去の経緯によらない。これがマルコフ連鎖である。以下 $S$ を有限または可算な集合（状態空間）とする。

定義 6.1（マルコフ連鎖, Markov chain）$p\colon S \times S \to [0, 1]$ が $\sum_{y}p(x, y) = 1$（$x \in S$）を満たすとき推移確率という。確率変数列 $(X_n)_{n \geq 0}$ が、$S$ 上の確率分布 $\nu$ と推移確率 $p$ について、すべての $n$ と $x_0, \dots, x_n \in S$ で

$$P(X_0 = x_0, X_1 = x_1, \dots, X_n = x_n) = \nu(x_0)p(x_0, x_1)\cdots p(x_{n-1}, x_n)$$

を満たすとき、初期分布 $\nu$、推移確率 $p$ のマルコフ連鎖という。$\nu = \delta_x$ のときの確率と期待値を $P_x$、$E_x$ と書く。

これは $P(X_{n+1} = y \mid X_0 = x_0, \dots, X_n = x_n) = p(x_n, y)$（条件の確率が正のとき）と同値である。存在は、i.i.d. の一様乱数 $U_1, U_2, \dots$ と適当な関数 $f$ で $X_{n+1} = f(X_n, U_{n+1})$ とおけば構成でき（$S$ を並べて区間 $[0,1)$ を $p(x, \cdot)$ の比に分ける）、以下の計算もすべてこの形の連鎖で行ってよい。

例 6.2 (1) $\mathbb{Z}^d$ 上の単純ランダムウォーク：$p(x, x \pm e_j) = 1/(2d)$。(2) 連結な有限グラフ上のランダムウォーク：隣接する頂点に等確率で移る、$p(x, y) = 1/\deg(x)$。(3) エーレンフェストの壺：二つの壺に計 $N$ 個の玉があり、毎回 1 個を無作為に選んで反対の壺に移す。壺 1 の玉の数は $p(k, k-1) = k/N$、$p(k, k+1) = 1 - k/N$ の連鎖である。(4) 2 状態の連鎖：$S = \lbrace 1, 2 \rbrace$、$p(1,2) = a$、$p(2,1) = b$（$0 < a, b \leq 1$）。

命題 6.3（チャップマン–コルモゴロフの等式）$p^n$ を行列 $p$ の $n$ 乗とすると $P_\nu(X_n = y) = \sum_x \nu(x)p^n(x, y)$ であり、$p^{m+n}(x, y) = \sum_z p^m(x, z)p^n(z, y)$。

証明. 定義の等式を $x_0, \dots, x_{n-1}$ について足せば前半を得る。後半は行列の積の結合法則である。$\square$

2 状態の連鎖では $p$ の固有値が $1$ と $1 - a - b$ なので、$p^n(1,1) = \frac{b}{a+b} + \frac{a}{a+b}(1 - a - b)^n$ である。$\lvert 1 - a - b \rvert < 1$ なら $p^n(x, \cdot)$ は出発点によらない分布 $(\frac{b}{a+b}, \frac{a}{a+b})$ に指数関数的に収束する。$a = b = 1$ なら状態は交互に入れ替わり、収束しない。この二つの現象の一般論がこの章の後半の主題である。

6.2 マルコフ性と強マルコフ性

$\mathcal{F}_n = \sigma(X_0, \dots, X_n)$ とし、道の空間 $S^{\mathbb{Z}_{\geq 0}}$ に座標写像で生成される σ-加法族を入れる。

定理 6.4（マルコフ性）$A \in \mathcal{F}_n$、$x \in S$、$B \subset S^{\mathbb{Z}_{\geq 0}}$ を可測集合とすると

$$P_\nu\left(A \cap \lbrace X_n = x \rbrace \cap \lbrace (X_{n+k})_{k \geq 0} \in B \rbrace\right) = P_\nu(A \cap \lbrace X_n = x \rbrace)\ P_x((X_k)_{k \geq 0} \in B)$$

証明. $A = \lbrace X_0 = x_0, \dots, X_n = x_n \rbrace$（$x_n = x$）かつ $B = \lbrace \omega_0 = y_0, \dots, \omega_k = y_k \rbrace$ ならば、両辺とも定義 6.1 の積の形で計算でき、一致する。$A$ を固定すると両辺は $B$ の有限測度であり、このような柱状集合の全体は（空集合を加えれば）σ-加法族を生成する π-系なので、測度の一意性（06-measure-integration 第1章 定理 1.31）よりすべての $B$ で一致する。一般の $A \in \mathcal{F}_n$ はこの形の $A$ の可算個の非交和である。$\square$

時刻 $n$ に $x$ にいるという条件のもとで、未来は過去と独立に、$x$ から出発した連鎖として振る舞う。これは停止時刻（第5章 定義 5.10）でも成り立つ。

定理 6.5（強マルコフ性）$T$ を停止時刻、$A \in \mathcal{F}_T$ とすると

$$P_\nu\left(A \cap \lbrace T < \infty, X_T = x \rbrace \cap \lbrace (X_{T+k})_{k \geq 0} \in B \rbrace\right) = P_\nu(A \cap \lbrace T < \infty, X_T = x \rbrace)\ P_x((X_k)_{k \geq 0} \in B)$$

証明. 左辺を $\lbrace T = n \rbrace$ ごとに分けると、$A \cap \lbrace T = n \rbrace \in \mathcal{F}_n$ なので定理 6.4 が使え、$n$ について足せばよい。$\square$

6.3 再帰と過渡

$T_y = \inf\lbrace n \geq 1 \mid X_n = y \rbrace$（$y$ への到達時刻。$X_0 = y$ なら戻る時刻）、$\rho_{xy} = P_x(T_y < \infty)$、$N(y) = \sum_{n \geq 1}\mathbf{1}_{\lbrace X_n = y \rbrace}$（訪問回数）とおく。

定義 6.6 $\rho_{yy} = 1$ のとき状態 $y$ は再帰的 (recurrent)、$\rho_{yy} < 1$ のとき過渡的 (transient) であるという。

補題 6.7 $k \geq 1$ について $P_x(N(y) \geq k) = \rho_{xy}\rho_{yy}^{k-1}$。

証明. $k - 1$ 回目の訪問時刻は停止時刻で、そこでの状態は $y$ である。強マルコフ性より、その後にもう一度 $y$ を訪れる確率は $\rho_{yy}$ なので、$P_x(N(y) \geq k) = P_x(N(y) \geq k - 1)\rho_{yy}$。$\square$

定理 6.8 $y$ が再帰的 $\Leftrightarrow$ $\sum_{n \geq 1}p^n(y, y) = \infty$。$y$ が再帰的なら $P_y(N(y) = \infty) = 1$、過渡的なら $E_x[N(y)] = \rho_{xy}/(1 - \rho_{yy}) < \infty$。

証明. 補題 6.7 より $E_x[N(y)] = \sum_{k \geq 1}P_x(N(y) \geq k) = \sum_{k \geq 1}\rho_{xy}\rho_{yy}^{k-1}$ で、一方 $E_y[N(y)] = \sum_{n \geq 1}p^n(y, y)$。$\rho_{yy} = 1$ なら $P_y(N(y) \geq k) = 1$ がすべての $k$ で成り立つ。$\square$

定理 6.9 $x$ が再帰的で $\rho_{xy} > 0$ ならば、$y$ も再帰的で $\rho_{yx} = \rho_{xy} = 1$。

証明. $x$ から $y$ への正の確率の最短の道は途中で $x$ を通らないので $P_x(T_y < T_x) > 0$。強マルコフ性より $0 = P_x(T_x = \infty) \geq P_x(T_y < T_x)(1 - \rho_{yx})$ だから $\rho_{yx} = 1$。$p^j(y, x) > 0$、$p^l(x, y) > 0$ となる $j, l$ をとると $p^{j+n+l}(y, y) \geq p^j(y, x)p^n(x, x)p^l(x, y)$ で、$n$ について足せば定理 6.8 より $y$ は再帰的である。$x$ と $y$ の役割を入れ替えて $\rho_{xy} = 1$。$\square$

すべての $x, y$ で $\rho_{xy} > 0$ のとき連鎖は既約 (irreducible) であるという。既約な連鎖の状態はすべて再帰的かすべて過渡的であり、再帰的なら定理 6.9 より $\rho_{xy} = 1$（どこからでもどこへでも確率 1 で到達する）。

例 6.10 有限な既約連鎖は再帰的である。実際 $\sum_{y \in S}N(y) = \infty$ なので、ある $y$ で $E_x[N(y)] = \infty$ となり、定理 6.8 より $y$ は再帰的である。

定義 6.11（周期）$d(x) = \gcd\lbrace n \geq 1 \mid p^n(x, x) > 0 \rbrace$ を $x$ の周期といい、$d(x) = 1$ のとき非周期的 (aperiodic) という。

既約なら周期はすべての状態で等しい。実際 $p^j(x, y), p^l(y, x) > 0$ なら $j + l$ と、$p^n(y, y) > 0$ となる $n$ について $j + n + l$ はともに $x$ への帰還時刻になりうるので $d(x) \mid n$、よって $d(x) \mid d(y)$ で、対称性から等しい。単純ランダムウォークは周期 2 であり、$p(x, x) > 0$ となる $x$ があれば非周期的である。

補題 6.12 $I \subset \mathbb{N}$ が加法で閉じていて $\gcd I = 1$ ならば、十分大きな整数はすべて $I$ に属する。

証明. 有限個の $i_1, \dots, i_k \in I$ で最大公約数が 1 になるものがあり、ベズーの等式より $1 = \sum_j c_ji_j$（$c_j \in \mathbb{Z}$）。$a = \sum_{c_j > 0}c_ji_j$、$b = \sum_{c_j < 0}\lvert c_j \rvert i_j$ とすると $a = b + 1$ で、$b = 0$ なら $1 \in I$ で明らか。$b \geq 1$ なら $b, b + 1 \in I$ で、$n \geq b^2$ を $n = qb + r$（$0 \leq r < b \leq q$）と書けば $n = (q - r)b + r(b + 1) \in I$。$\square$

$I = \lbrace n \mid p^n(x, x) > 0 \rbrace$ はチャップマン–コルモゴロフの等式より加法で閉じているので、$x$ が非周期的なら十分大きなすべての $n$ で $p^n(x, x) > 0$ である。

6.4 ランダムウォークの再帰性

酔っ払いが格子の上を無作為に歩くとき、いつかは家に戻れるだろうか。答えは次元による。

定理 6.13（ポリアの定理, Pólya）$\mathbb{Z}^d$ 上の単純ランダムウォークは $d = 1, 2$ で再帰的、$d \geq 3$ で過渡的である。

証明. 定理 6.8 により $\sum_n p^n(0, 0)$ の収束・発散を調べればよい。奇数回では原点に戻れない。

$d = 1$：$2n$ 歩のうち右と左がちょうど $n$ 回ずつなので、スターリングの公式より $p^{2n}(0, 0) = \binom{2n}{n}2^{-2n} \sim 1/\sqrt{\pi n}$ で、和は発散する。

$d = 2$：$(X_n, Y_n)$ を 45 度回転させた $U_n = X_n + Y_n$、$V_n = X_n - Y_n$ は、各歩で $(\pm 1, \pm 1)$ の 4 通りに等確率で動くので、独立な 1 次元の単純ランダムウォークである。$\lbrace (X_n, Y_n) = 0 \rbrace = \lbrace U_n = V_n = 0 \rbrace$ より $p^{2n}(0, 0) = \left(\binom{2n}{n}2^{-2n}\right)^2 \sim 1/(\pi n)$ で、和は発散する。

$d \geq 3$：1 歩の特性関数は $\phi(\theta) = \frac{1}{d}\sum_{j=1}^{d}\cos\theta_j$ である。$x \in \mathbb{Z}^d$ について $\int_{[-\pi, \pi]^d}e^{i\langle \theta, x \rangle}\ d\theta = (2\pi)^d\mathbf{1}_{\lbrace x = 0 \rbrace}$ なので、フビニの定理より

$0 < s < 1$ について $n$ で和をとると $\sum_n s^np^n(0,0) = (2\pi)^{-d}\int (1 - s\phi(\theta))^{-1}\ d\theta$ で、$s \uparrow 1$ とすると、$\lbrace \phi \geq 0 \rbrace$ 上では単調収束定理、$\lbrace \phi < 0 \rbrace$ 上では被積分関数が 1 以下なので有界収束定理より

である。$\lvert t \rvert \leq \pi$ で $1 - \cos t = 2\sin^2(t/2) \geq 2t^2/\pi^2$ なので $1 - \phi(\theta) \geq 2\lvert \theta \rvert^2/(d\pi^2)$ であり、右辺は $\frac{d\pi^2}{2}(2\pi)^{-d}\int_{[-\pi,\pi]^d}\lvert \theta \rvert^{-2}\ d\theta$ 以下である。極座標（06-measure-integration 第5章 定理 5.17）で $\int_{\lvert \theta \rvert \leq r}\lvert \theta \rvert^{-2}\ d\theta = c_d\int_0^r \rho^{d-3}\ d\rho$ は $d \geq 3$ で有限だから、和は収束する。$\square$

3 次元の単純ランダムウォークが原点に戻る確率は約 $0.34$ であることが知られている。「酔っ払いは家に帰れるが、酔った鳥は帰れないかもしれない」（角谷静夫によるとされる）。なお $d = 1$ でも $E_0[T_0] = \infty$ である（第5章 例 5.14 と例 6.19 を参照）。

6.5 定常分布

連鎖を長く走らせたとき、状態の分布は落ち着くだろうか。落ち着き先の候補が、1 歩進めても変わらない分布である。

定義 6.14（定常分布）$\pi\colon S \to [0, \infty)$（恒等的に 0 でない）が $\sum_x \pi(x)p(x, y) = \pi(y)$（$y \in S$）を満たすとき定常測度、さらに $\sum_x \pi(x) = 1$ のとき定常分布 (stationary distribution) という。

$X_0 \sim \pi$ ならすべての $n$ で $X_n \sim \pi$ である。2 状態の連鎖では $\pi = (\frac{b}{a+b}, \frac{a}{a+b})$、グラフ上のランダムウォークでは $\pi(x) \propto \deg(x)$、エーレンフェストの壺では二項分布 $B(N, 1/2)$、$\mathbb{Z}^d$ 上の単純ランダムウォークでは数え上げ測度が定常測度である（後の 3 つは 6.8 節の詳細つり合いから確かめられる）。

定理 6.15（存在）既約な連鎖の状態 $x$ が再帰的ならば、$x$ を出てから戻るまでの $y$ への平均訪問回数

$$\mu_x(y) = E_x\left[\sum_{n=0}^{T_x - 1}\mathbf{1}_{\lbrace X_n = y \rbrace}\right] = \sum_{n \geq 0}P_x(X_n = y, T_x > n)$$

は定常測度で、$\mu_x(x) = 1$、$0 < \mu_x(y) < \infty$、$\sum_y \mu_x(y) = E_x[T_x]$ を満たす。

証明. $\lbrace T_x > n \rbrace \in \mathcal{F}_n$ なのでマルコフ性より

$z \neq x$ なら、$X_{n+1} = z$ のとき $T_x > n$ と $T_x > n + 1$ は同じなので右辺は $\sum_{m \geq 1}P_x(X_m = z, T_x > m) = \mu_x(z)$（$m = 0$ の項は 0）。$z = x$ なら右辺は $\sum_n P_x(T_x = n + 1) = \rho_{xx} = 1 = \mu_x(x)$。$\mu_x = \mu_xp^n$ より $1 = \mu_x(x) \geq \mu_x(y)p^n(y, x)$、$\mu_x(y) \geq p^n(x, y)$ で、既約性から $0 < \mu_x(y) < \infty$。最後の等式は $\sum_y \mu_x(y) = \sum_n P_x(T_x > n)$ による。$\square$

定理 6.16（一意性）既約かつ再帰的な連鎖の定常測度は、定数倍を除いて一意である。

証明. 定常測度 $\nu$ は、$\nu(y) > 0$ となる $y$ について $\nu(x) \geq \nu(y)p^n(y, x) > 0$（既約性）なので、定数倍して $\nu(x) = 1$ としてよい。$\nu(z) = p(x, z) + \sum_{y \neq x}\nu(y)p(y, z)$ の右辺の $\nu(y)$ に同じ式を代入し続けると、帰納法により、各 $n$ で

$z \neq x$ なら右辺は $n \to \infty$ で $\sum_{m \geq 1}P_x(X_m = z, T_x > m) = \mu_x(z)$ に収束するので $\nu \geq \mu_x$。$\lambda = \nu - \mu_x \geq 0$ は定常で $\lambda(x) = 0$ だから、$0 = \lambda(x) = \sum_y \lambda(y)p^n(y, x)$ と既約性より $\lambda = 0$。$\square$

$E_x[T_x] < \infty$ のとき $x$ は正再帰的 (positive recurrent)、再帰的で $E_x[T_x] = \infty$ のとき零再帰的 (null recurrent) という。

定理 6.17 既約な連鎖について、定常分布が存在することと、ある（したがってすべての）状態が正再帰的であることは同値である。このとき定常分布は一意で

$$\pi(x) = \frac{1}{E_x[T_x]} \qquad (x \in S)$$

証明. 正再帰的な $x$ があれば $\mu_x/E_x[T_x]$ が定常分布である。逆に定常分布 $\pi$ があるとする。$\pi(y) > 0$ となる $y$ について、$\pi = \pi p^n$ を $n \geq 1$ について足すと、左辺は $\infty$、右辺は $\sum_x \pi(x)E_x[N(y)]$ である。$y$ が過渡的なら定理 6.8 より右辺は $1/(1 - \rho_{yy})$ 以下で矛盾するから、$y$ は再帰的で、既約性より連鎖は再帰的である。定理 6.16 より $\pi = c\mu_x$ で、$\pi(x) = c$、$1 = \sum_y \pi(y) = cE_x[T_x]$。既約性より $\pi(x) \geq \pi(y)p^n(y, x) > 0$ なので $E_x[T_x] = 1/\pi(x) < \infty$。$\square$

公式 $\pi(x) = 1/E_x[T_x]$（カックの公式）は、「平均して $E_x[T_x]$ 回に 1 回 $x$ にいる」ことを意味する（定理 6.21 で正当化する）。

例 6.18（エーレンフェストの壺と不可逆性）$\pi(k) = \binom{N}{k}2^{-N}$ なので、壺 1 が空の状態に戻るまでの平均時間は $E_0[T_0] = 2^N$、半々の状態 $N/2$ に戻る平均時間は $2^N/\binom{N}{N/2} \sim \sqrt{\pi N/2}$ である（$N = 100$ で約 $12.6$）。気体分子のように $N$ が $10^{23}$ 程度なら、偏った状態への回帰は事実上起こらない。力学法則が可逆でも巨視的には不可逆に見えることの、確率論的な説明である。

例 6.19 $\mathbb{Z}$ 上の単純ランダムウォークは再帰的で、定常測度は数え上げ測度の定数倍に限る（定理 6.16）。その総和は無限大なので定常分布は存在せず、定理 6.17 より零再帰的、すなわち $E_0[T_0] = \infty$ である。

6.6 収束定理

定理 6.20（収束定理）既約かつ非周期的な連鎖が定常分布 $\pi$ をもてば、すべての $x$ について

$$\sum_{y \in S}\lvert p^n(x, y) - \pi(y) \rvert \longrightarrow 0 \qquad (n \to \infty)$$

証明の着想はカップリングである。一方は $x$ から、他方は $\pi$ から、二つの連鎖を独立に走らせる。両者がいったん出会えば、以後は同じ分布で動くとみなせるので、分布の差は「まだ出会っていない確率」で抑えられる。

証明. $S \times S$ 上で $\overline{p}((x, y), (x', y')) = p(x, x')p(y, y')$ を推移確率とする連鎖 $(X_n, Y_n)$ を考える（二つの連鎖を独立に動かす）。

(i) 既約性：$x, x', y, y'$ に対し $p^k(x, x') > 0$、$p^l(y, y') > 0$ となる $k, l$ をとる。補題 6.12 の後の注意より $n$ が十分大きければ $p^n(x, x') \geq p^k(x, x')p^{n-k}(x', x') > 0$ で、同様に $p^n(y, y') > 0$ なので $\overline{p}^n((x, y), (x', y')) > 0$。

(ii) $\pi \otimes \pi$ は $\overline{p}$ の定常分布なので、定理 6.17 と定理 6.9 より $(X_n, Y_n)$ は再帰的で、どこから出発しても対角線上の点 $(z, z)$ に確率 1 で到達する。

(iii) $X_0 = x$、$Y_0 \sim \pi$ とし、$T = \inf\lbrace n \mid X_n = Y_n \rbrace$ とすると (ii) より $T < \infty$ a.s.。$m \leq n$ について、時刻 $m$ でのマルコフ性（各成分は $p$ に従って動く）より

これを $m \leq n$ と $z$ について足すと $P(X_n = y, T \leq n) = P(Y_n = y, T \leq n)$ なので

$P(X_n = y) = p^n(x, y)$、$P(Y_n = y) = \pi(y)$ なので主張を得る。$\square$

非周期性は必要である。2 状態の連鎖で $a = b = 1$ なら $p^n(1, 1)$ は $0$ と $1$ を交互にとる。また零再帰的または過渡的な既約連鎖では $p^n(x, y) \to 0$ となることが知られている（主張のみ）。

6.7 エルゴード定理

時間平均は空間平均に等しい。これがエルゴード定理であり、マルコフ連鎖に対する大数の法則である。

定理 6.21（エルゴード定理）既約かつ再帰的な連鎖を任意の初期分布から走らせるとき、$y \in S$ について

$$\frac{1}{n}\sum_{k=0}^{n-1}\mathbf{1}_{\lbrace X_k = y \rbrace} \longrightarrow \frac{1}{E_y[T_y]} \qquad \text{a.s.}$$

（$1/\infty = 0$）。さらに定常分布 $\pi$ があり $\sum_y \lvert f(y) \rvert\pi(y) < \infty$ ならば、$\frac{1}{n}\sum_{k=0}^{n-1}f(X_k) \to \sum_y f(y)\pi(y)$ a.s.。

証明. $y$ を固定する。定理 6.9 より $R_0 = \inf\lbrace n \geq 0 \mid X_n = y \rbrace < \infty$ a.s.。$R_k = \inf\lbrace n > R_{k-1} \mid X_n = y \rbrace$ とする。強マルコフ性を $R_{k-1}$ で繰り返し使うと、遠足 (excursion) $(X_{R_{k-1}}, \dots, X_{R_k - 1})$（$k \geq 1$）は互いに独立で、$P_y$ のもとでの $(X_0, \dots, X_{T_y - 1})$ と同分布である（時刻 $R_{k-1}$ 以後の過程は $\mathcal{F}_{R_{k-1}}$ と独立な $y$ 出発の連鎖であり、それ以前の遠足は $\mathcal{F}_{R_{k-1}}$-可測である）。特に $R_k - R_{k-1}$ は $T_y$（$P_y$ のもと）と同分布の i.i.d. で、大数の強法則（定理 2.7、平均が無限大の場合は問題 2.3）より $R_k/k \to E_y[T_y]$ a.s.。

$N_n = \sum_{k< n}\mathbf{1}_{\lbrace X_k = y \rbrace}$ とすると $R_{N_n - 1} < n \leq R_{N_n}$ で、再帰性より $N_n \to \infty$ だから、$n/N_n \to E_y[T_y]$。これが前半である。

$f \geq 0$ とし、$F_k = \sum_{j=R_{k-1}}^{R_k - 1}f(X_j)$ とおくと、$F_k$ は i.i.d. で、$E[F_1] = E_y[\sum_{j < T_y}f(X_j)] = \sum_z f(z)\mu_y(z)$。$\sum_{k=1}^{N_n - 1}F_k \leq \sum_{j=R_0}^{n-1}f(X_j) \leq \sum_{k=1}^{N_n}F_k$ で、$N_n$ で割ると大数の強法則より両端は $E[F_1]$ に収束する。最初の $R_0$ 項の和は $n$ によらないので、$\frac{1}{n}\sum_{j< n}f(X_j) \to E[F_1]/E_y[T_y]$。定理 6.16 と定理 6.17 より $\mu_y/E_y[T_y] = \pi$ なので、極限は $\sum_z f(z)\pi(z)$ である（これは有限なので $E[F_1] < \infty$ でもある）。一般の $f$ は $f = f^{+} - f^{-}$ と分ければよい。$\square$

$f = \mathbf{1}_{\lbrace y \rbrace}$ の期待値をとると、有界収束定理より $\frac{1}{n}\sum_{k< n}p^k(x, y) \to \pi(y)$ となる。こちらは非周期性を仮定しなくても成り立つ。

6.8 可逆性とメトロポリス法

定義 6.22（詳細つり合い, detailed balance）$\pi\colon S \to [0, \infty)$ がすべての $x, y$ で $\pi(x)p(x, y) = \pi(y)p(y, x)$ を満たすとき、$\pi$ は詳細つり合いの条件を満たすという。

$x$ について足すと $\sum_x \pi(x)p(x, y) = \pi(y)\sum_x p(y, x) = \pi(y)$ なので、詳細つり合いを満たす $\pi$ は定常測度である。詳細つり合いは「$x \to y$ の流れと $y \to x$ の流れがつり合う」ことを意味し、$\pi$ が定常分布なら $P_\pi(X_0 = x_0, \dots, X_n = x_n) = P_\pi(X_0 = x_n, \dots, X_n = x_0)$、すなわち時間を逆向きに見ても同じ法則に従う（可逆, reversible）。定常測度を求めるには、まず詳細つり合いを解いてみるのが実用的である。たとえばグラフ上のランダムウォークでは $\deg(x) \cdot \frac{1}{\deg(x)} = 1 = \deg(y) \cdot \frac{1}{\deg(y)}$ より $\pi(x) = \deg(x)$ が、エーレンフェストの壺では $\binom{N}{k}\frac{N - k}{N} = \binom{N}{k+1}\frac{k+1}{N}$ より二項係数が、詳細つり合いを満たす。

例 6.23（メトロポリス法, Metropolis algorithm）有限集合 $S$ 上の分布 $\pi(x) = w(x)/Z$（$w > 0$）から標本を得たいが、正規化定数 $Z = \sum_x w(x)$ が計算できない（$S$ が巨大）とする。統計力学のボルツマン分布 $w(x) = e^{-H(x)/\tau}$ が典型例である。対称 $q(x, y) = q(y, x)$ で既約な推移確率 $q$（提案）をとり、$y \neq x$ について

とおく（$y$ を提案し、確率 $\min\lbrace 1, w(y)/w(x) \rbrace$ で受理、棄却なら留まる）。$\pi(x)p(x, y) = q(x, y)\min\lbrace \pi(x), \pi(y) \rbrace$ は $x, y$ について対称なので詳細つり合いが成り立ち、$\pi$ は定常分布である。$p$ は既約なので、エルゴード定理より $\frac{1}{n}\sum_{k< n}f(X_k) \to \sum_x f(x)\pi(x)$ a.s.。$Z$ を知らなくても比 $w(y)/w(x)$ だけで $\pi$ に関する期待値が計算できる。これがマルコフ連鎖モンテカルロ法 (MCMC) の基本原理であり、提案が対称でない場合への拡張がメトロポリス–ヘイスティングス法である。実用上は、収束定理の速さ（混合時間）の評価が重要な研究課題になる。

まとめ

• マルコフ連鎖は推移確率で決まり、（強）マルコフ性により停止時刻の後は新たに出発した連鎖として振る舞う。
• 状態は再帰的（$\sum_n p^n(y,y) = \infty$）か過渡的かに分かれ、既約な連鎖では全状態が同じ型をもつ。
• 単純ランダムウォークは $d = 1, 2$ で再帰的、$d \geq 3$ で過渡的である（ポリア）。
• 既約な連鎖が定常分布をもつことと正再帰的であることは同値で、そのとき $\pi(x) = 1/E_x[T_x]$（カック）。
• 既約・非周期的で定常分布をもてば $p^n(x, \cdot) \to \pi$（カップリングによる証明）。時間平均は $\pi$ に関する平均に収束する（エルゴード定理）。
• 詳細つり合いを満たす分布は定常分布であり、メトロポリス法はこれを利用して望みの分布を定常分布にもつ連鎖を作る。

演習問題