応用

2026年10月15日14分で読めますAI生成教科書『基礎理論』第15章マルコフ連鎖の長時間の振る舞い

詳細つり合いと可逆性
MCMC と Metropolis 法
多次元の状態空間を1次元へ還元する
確認テスト
木下の層

AI 生成・木下が未勉強

確率論入門　第15章 §15.5　★★ 詳細つり合いを満たすように遷移を設計すると、目的の分布を定常分布にもつ連鎖が作れる（MCMC）。対称性を使えば大きな状態空間の連鎖を1次元の連鎖へ還元できる

詳細つり合いと可逆性

定常分布を求めるには $\pi P=\pi$ を解けばよいが、状態が多いと連立方程式は大きくなる。次の条件は、より強いが確かめやすい十分条件である。

命題 15.26（詳細つり合い ★★★）

確率分布 $\pi$ が、すべての $i,j$ について

$\pi_ip_{ij}=\pi_jp_{ji}\tag{15.32}$

を満たすなら、 $\pi$ は定常分布である。

証明

(15.32) を $i$ について足すと

$\sum_i\pi_ip_{ij}=\pi_j\sum_ip_{ji}=\pi_j$

である。

(15.32) は「定常状態で、2つの状態のあいだを行く確率の流れと帰る流れが釣り合う」ことを表す。このとき $X_0\sim\pi$ の連鎖は、時間を逆向きにたどっても同じ法則に従う。実際、経路の確率に (15.32) を繰り返し使うと

$P(X_0=i_0,\dots,X_n=i_n)=\pi_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}=\pi_{i_n}p_{i_ni_{n-1}}\cdots p_{i_1i_0}$

となる。このような連鎖を可逆であるという。

定常分布があっても、詳細つり合いが成り立つとは限らない（確認テスト 15.5-1）。

例

出生死滅連鎖。 $\{0,1,2,\dots\}$ 上で隣にしか移らない連鎖

$p_{i,i+1}=b_i,\qquad p_{i,i-1}=d_i,\qquad p_{ii}=1-b_i-d_i$

を考える。(15.32) は隣どうしの式 $\pi_ib_i=\pi_{i+1}d_{i+1}$ だけになり、

$\pi_k=\pi_0\prod_{\ell=0}^{k-1}\frac{b_\ell}{d_{\ell+1}}$

と順に決まる。右辺の総和が有限なら、規格化して定常分布が得られる。例題 15.5 のグラフ上のランダムウォークも可逆である。隣どうしなら

$\pi_ip_{ij}=\frac{\deg i}{2E}\cdot\frac{1}{\deg i}=\frac1{2E}=\pi_jp_{ji}$

となるからである。

MCMC と Metropolis 法

有限集合 $S$ 上の分布 $\pi$ から標本を作りたいとする。ただし $\pi$ は定数倍を除いてしか分からない。

$\pi_i=\frac{w_i}{Z},\qquad Z=\sum_iw_i$

重み $w_i>0$ は計算できるが、規格化定数 $Z$ は状態が多すぎて計算できない、という状況である。統計力学の Boltzmann 分布 $w_i=\mathrm{e}^{-\beta E_i}$ が典型例である。

マルコフ連鎖モンテカルロ法（MCMC）は、 $\pi$ を定常分布にもつ既約な連鎖を作って長く走らせる。そしてエルゴード定理 15.25 により、時間平均から $\sum_j\pi_jf(j)$ を推定する。

定理 15.27（Metropolis 法 ★★★）

$q=(q_{ij})$ を既約な遷移確率行列とし、対称 $q_{ij}=q_{ji}$ であるとする。これを提案の行列と呼ぶ。 $i\ne j$ について

$p_{ij}=q_{ij}\min\Bigl(1,\frac{w_j}{w_i}\Bigr),\qquad p_{ii}=1-\sum_{j\ne i}p_{ij}\tag{15.33}$

と定める。この $P$ は、 $\pi_i=w_i/Z$ について詳細つり合いを満たし、既約である。したがって $\pi$ は $P$ のただ1つの定常分布である。

証明

$i\ne j$ とし、 $w_j\le w_i$ と仮定しても一般性を失わない。このとき $p_{ij}=q_{ij}w_j/w_i$ 、 $p_{ji}=q_{ji}\cdot1$ なので

$\pi_ip_{ij}=\frac{w_i}{Z}\,q_{ij}\frac{w_j}{w_i}=\frac{w_jq_{ij}}{Z},\qquad\pi_jp_{ji}=\frac{w_j}{Z}\,q_{ji}=\frac{w_jq_{ij}}{Z}$

で、両者は等しい。

次に、 $P$ が確率行列であることを見る。 $\sum_{j\ne i}p_{ij}\le\sum_{j\ne i}q_{ij}\le1$ なので、 $p_{ii}\ge0$ である。

重みは正なので、 $q_{ij}>0$ なら $p_{ij}>0$ である。よって提案の行列が既約なら $P$ も既約である。命題 15.26 と系 15.20 から結論を得る。

アルゴリズムとしては、次の手順をくり返す。

現在の状態 $i$ から、候補 $j$ を提案の行列に従って選ぶ。
確率 $\min(1,w_j/w_i)$ で受け入れて、候補に移る。
受け入れなければ、今の状態に留まる。

重みの比 $w_j/w_i$ しか使わないので、 $Z$ は要らない。重みが増える提案は必ず受け入れ、減る提案は比の確率でだけ受け入れる。提案が対称でないときは、受け入れ確率を

$\min\Bigl(1,\frac{w_jq_{ji}}{w_iq_{ij}}\Bigr)$

に変えればよい（Metropolis–Hastings 法、確認テスト 15.5-5）。

落とし穴

連鎖の標本は独立でない。 時間平均は (15.31) により収束するが、隣り合う標本は相関しているので、同じ個数の独立な標本より推定の誤差は大きい。
初期値の影響が残る。 定理 15.21 の収束は漸近的なので、最初のしばらくの値を捨ててから平均をとることが多い。
留まる確率 $p_{ii}>0$ があると非周期的になる。 受け入れを拒む確率が正の状態が1つでもあれば、既約な連鎖は非周期的で、各時刻の分布も $\pi$ に収束する。

例題 15.7　3状態の Metropolis 法 ★★

オリジナル $S=\{1,2,3\}$ 上の分布 $\pi_i\propto i$ を目標とし、提案は「今の状態以外の2つから等確率で1つ選ぶ」とする。

Metropolis 法の遷移確率行列 $P$ を書き、 $\pi P=\pi$ を確かめよ。
連鎖を長く走らせたときの $X_k$ の時間平均の極限を求めよ。

解答

(1) 目標は $\pi=(\frac16,\frac26,\frac36)$ である。提案は、異なる2状態のあいだで $q_{ij}=\frac12$ である。(15.33) から、遷移確率は次のとおりである。

重みが増える向きは $p_{ij}=\frac12$ である。
重みが減る向きは $p_{ij}=\frac12\cdot\frac ji$ である。

$P=\begin{pmatrix}0&\frac12&\frac12\\[3pt]\frac14&\frac14&\frac12\\[3pt]\frac16&\frac13&\frac12\end{pmatrix}$

対角成分は、各行の和が 1 になるように決めた。

$p_{22}=1-\frac14-\frac12=\frac14,\qquad p_{33}=1-\frac16-\frac13=\frac12$

$\pi P$ の各成分は

$\begin{aligned}(\pi P)_1&=\tfrac16\cdot0+\tfrac26\cdot\tfrac14+\tfrac36\cdot\tfrac16=\tfrac1{12}+\tfrac1{12}=\tfrac16,\\ (\pi P)_2&=\tfrac16\cdot\tfrac12+\tfrac26\cdot\tfrac14+\tfrac36\cdot\tfrac13=\tfrac1{12}+\tfrac1{12}+\tfrac16=\tfrac13,\\ (\pi P)_3&=\tfrac16\cdot\tfrac12+\tfrac26\cdot\tfrac12+\tfrac36\cdot\tfrac12=\tfrac12\end{aligned}$

で、 $\pi P=\pi$ である。

(2) 連鎖は既約なので、エルゴード定理 15.25 を $f(i)=i$ に使える。時間平均は

$\sum_i\pi_i\,i=\frac{1+4+9}{6}=\frac73$

に収束する。

多次元の状態空間を1次元へ還元する

状態空間が大きくても、知りたい量が状態の一部の情報だけで決まり、その情報がそれ自体でマルコフ連鎖になっていれば、小さな連鎖で計算できる。

定理 15.28（集約できる条件 ★★★）

状態空間の分割 $S=\bigsqcup_{a}B_a$ をとる。各状態にそのブロックの名前を返す関数を $\phi$ と書く。つまり $i\in B_a$ なら $\phi(i)=a$ である。すべての $a,b$ について

$\sum_{j\in B_b}p_{ij}\ \text{が}\ i\in B_a\ \text{によらない}\tag{15.34}$

とき、その値を $\hat p_{ab}$ と書く。このとき、もとの連鎖がどの初期分布から出発しても、 $Y_n=\phi(X_n)$ は遷移確率 $\hat p_{ab}$ のマルコフ連鎖である。

証明

事象 $\{Y_0=a_0,\dots,Y_n=a_n\}$ は、事象 $\{X_0\in B_{a_0},\dots,X_n\in B_{a_n}\}$ と同じである。これを、時刻 $n$ の値 $X_n=i$ で排反に分ける。マルコフ性から、各部分の上で

$P(X_{n+1}\in B_b\mid X_0\in B_{a_0},\dots,X_{n-1}\in B_{a_{n-1}},X_n=i)=\sum_{j\in B_b}p_{ij}=\hat p_{a_nb}$

である。右辺は $i$ によらないので、部分ごとの確率を足し合わせても

$P(Y_{n+1}=b\mid Y_0=a_0,\dots,Y_n=a_n)=\hat p_{a_nb}$

となる。

(15.34) は、同じブロックに属する状態はどれも、次にどのブロックに移るかについて区別がつかないという条件である。状態空間の対称性からこの条件が出ることが多い。

例題 15.8　Ehrenfest の壺 ★★

オリジナル2つの壺 A、B に、区別できる $N$ 個の玉が入っている。各時刻に $N$ 個の玉から1個を等確率で選び、もう一方の壺へ移す。

全体の状態を、各玉がどちらの壺にあるかを表す $x\in\{0,1\}^N$ とする。この $2^N$ 状態の連鎖が、壺 A の玉の数 $K=\sum_\ell x_\ell$ の連鎖に集約できることを示せ。また $K$ の遷移確率を求めよ。
$K$ の定常分布を詳細つり合いから求めよ。
$N=4$ とする。壺 A が空の状態から出発して、再び空になるまでの平均時間 $m_0$ を求めよ。また $m_2$ を求めよ。

解答

(1) 全体の連鎖は、 $x$ の成分を1つ選んで反転させる連鎖である。A に $k$ 個の玉がある状態から1個を選ぶ。

A にある $k$ 個のどれかを選べば、A の玉は1個減る。
B にある $N-k$ 個のどれかを選べば、A の玉は1個増える。

よって

$\sum_{y:\,K(y)=k-1}p_{xy}=\frac kN,\qquad\sum_{y:\,K(y)=k+1}p_{xy}=\frac{N-k}{N}$

で、どちらも $K(x)=k$ にしかよらない。条件 (15.34) が成り立つので、定理 15.28 から $K$ は次の遷移確率の連鎖である。

$\hat p_{k,k-1}=\frac kN,\qquad \hat p_{k,k+1}=\frac{N-k}N$

(2) 出生死滅連鎖なので、詳細つり合い $\pi_k\frac{N-k}{N}=\pi_{k+1}\frac{k+1}{N}$ を使う。これから

$\frac{\pi_{k+1}}{\pi_k}=\frac{N-k}{k+1}=\frac{\binom{N}{k+1}}{\binom Nk}$

となり、 $\pi_k=\binom Nk2^{-N}$ である。これは二項分布 $\mathrm{Bin}(N,\frac12)$ で、各玉が独立に確率 $\frac12$ でどちらかの壺にある状態に対応する。

(3) $K$ の連鎖は既約で有限なので、定理 15.19 から

$m_k=\frac1{\pi_k}=\frac{2^N}{\binom Nk}$

である。 $N=4$ では

$m_0=16,\qquad m_2=\frac{16}{6}=\frac83$

である。玉を増やすと $m_0=2^N$ は急速に増える。100 個なら $2^{100}\approx1.3\times10^{30}$ である。片方の壺が空の状態は再帰的なので必ず戻ってくるが、玉の数が多いと実際には観測できないほど先になる。

吸収を問う問題と長時間を問う問題の見分け

「いつか〜に達する確率」「〜より先に」「達するまでの平均時間」を問うとき。 吸収状態か到達先の集合 $A$ を決め、一次ステップ解析（定理 15.10・15.11）を使う。有限なら基本行列 $N=(I-Q)^{-1}$ でまとめて計算できる。
「長い時間のうち〜にいる割合」「十分時間がたったときの確率」「平均再帰時間」を問うとき。 既約で正再帰的かを確かめ、 $\pi P=\pi$ （または詳細つり合い）を解く。各時刻の分布の極限には非周期性を確かめる。
閉じたクラスが複数あり、過渡的な状態もあるとき。 2つを組み合わせる。閉じたクラス $C$ が非周期的・正再帰的で、定常分布 $\pi^C$ をもつとする。 $i$ から出発してそのクラスの状態 $j$ にいる確率の極限は

$\lim_{n\to\infty}p^{(n)}_{ij}=P_i(\tau_C<\infty)\,\pi^C_j$

である。第1因子は一次ステップ解析で求め、第2因子は定常分布で求める。クラスに入ったあとは、強マルコフ性でクラスの中の連鎖になるからである。

確認テスト

オリジナル

15.5-1 $S=\{1,2,3\}$ で $p_{12}=p_{23}=p_{31}=1$ の連鎖を考える。この連鎖は一様分布を定常分布にもつが、詳細つり合いを満たさないことを示せ。
15.5-2 $S=\{0,1,2,3\}$ 上の分布 $\pi_k\propto2^{-k}$ を目標とする。提案は左右の隣を確率 $\frac12$ ずつ選び、範囲の外を選んだら必ず拒んでその場に留まるとする。Metropolis 法の遷移確率をすべて求めて、詳細つり合いを確かめよ。また $X_k$ の時間平均の極限を求めよ。
15.5-3 例題 15.8 で $N=6$ とする。 $\pi_3$ と $m_3$ を求めよ。また $m_0$ を求めよ。
15.5-4 円周 $\mathbb{Z}_5=\{0,1,2,3,4\}$ の上を2つの粒子が独立に動く。各時刻にそれぞれが、確率 $\frac12$ ずつで左右に1動く（法5）。差 $D_n=X_n-Y_n\pmod5$ がマルコフ連鎖であることを示し、遷移確率を求めよ。また $D_0=1$ から、2つの粒子が初めて同じ点に来るまでの時間の期待値を求めよ。
15.5-5 提案 $q$ が対称とは限らない場合を考える。 $i\ne j$ かつ $q_{ij}>0$ のとき

$p_{ij}=q_{ij}\min\Bigl(1,\frac{w_jq_{ji}}{w_iq_{ij}}\Bigr)$

と定めると、詳細つり合いが成り立つことを示せ。

木下の勉強ステータス

木下はまだこの記事を勉強していません。

AI（Claude）が書いた教材を、木下が勉強しながら公開しています。式と数値は検算していますが、誤りが残っているかもしれません。誤りのご指摘・削除のご依頼をいただければ直します。連絡先：support@tecktom.com

この記事が含まれている連載

連載AI生成教科書『基礎理論』量子力学・統計熱力学・信号処理などの入門を、分野ごとに AI（Claude）が書き、木下が勉強しながら公開しています。上の段は AI が書いた本文、下の段は木下が勉強したあとに書いた文です。961本の記事・木下智貴

← AI生成教科書『基礎理論』の記事一覧へ