推移行列

同義語:遷移行列推移確率行列確率行列transition matrixstochastic matrix

概要

推移行列(transition matrix)とは、有限個の状態をもつ Markov 連鎖で状態 $i$ から状態 $j$ へ 1 歩で移る確率 $p_{ij}$ を並べた正方行列のことで、成分が $0$ 以上で各行の和が $1$ の行列(確率行列)として特徴づけられる。冪 $P^n$ の成分は $n$ 歩の推移確率であり、初期分布 $\mu$ から出発した時刻 $n$ の分布は $\mu P^n$ である。推移行列の固有値はすべて絶対値 $1$ 以下で、絶対値 $1$ の固有値の Jordan 細胞はすべて 1 次であり、既約なら固有値 $1$ は単根で定常分布はただ 1 つである。周期 $d$ の既約な推移行列では、$1$ の $d$ 乗根がすべて固有値になる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Markov連鎖, 行列, eigenvalue

有限個の状態の間を確率的に移り変わる Markov連鎖 では、状態 $i$ から状態 $j$ へ 1 歩で移る確率 $p_{ij}$ を並べた正方行列 $P$ が、初期分布とともに連鎖のふるまいをすべて決める。この行列を 推移行列(transition matrix)という。各行は「$i$ から次にどこへ行くか」の分布なので、成分は $0$ 以上で各行の和は $1$ である。推移行列の積は何歩か先への推移を、分布の行ベクトルに右から掛けることは時間を 1 歩進めることを表すので、連鎖の長い時間のふるまいは $P$ の冪と固有値の問題になる。
この記事では、推移行列の基本性質(prop-tmat-basic)と、行列の演算が表す確率的な意味(prop-tmat-meaning)を述べたあと、推移行列の固有値はすべて絶対値 $1$ 以下で、絶対値 $1$ の固有値には大きさ $2$ 以上の Jordan 細胞がなく、既約なら固有値 $1$ は単根であること(thm-tmat-spectrum)、周期 $d$ の既約な連鎖では $1$ の $d$ 乗根がすべて固有値になること(prop-tmat-period)、成分が正の分布について詳細釣り合いを満たす推移行列は実数の固有値で対角化できること(prop-tmat-reversible)を証明する。各列の和も $1$ である二重確率行列は例で扱う。

定義

以下、状態の集合を $S=\{1,\dots,m\}$($m\ge1$)とする。状態の上の分布は行ベクトル、状態の上の関数は列ベクトルで表す。$\mathbf 1$ は成分がすべて $1$ の列ベクトルである。

推移行列・分布・既約性
  1. $m$ 次の実正方行列 $P=(p_{ij})$ が 推移行列(確率行列)であるとは、すべての成分が $p_{ij}\ge0$ で、各行の和が $\sum_{j=1}^mp_{ij}=1$ であることをいう。行の和の条件は $P\mathbf 1=\mathbf 1$ と書ける。
  2. 成分が $0$ 以上で和が $1$ の行ベクトル $\mu=(\mu_1,\dots,\mu_m)$ を $S$ 上の 分布(確率ベクトル)という。$\pi P=\pi$ を満たす分布 $\pi$ を $P$ の 定常分布 という。
  3. $P^0:=I$、$P^{n+1}:=P^nP$ とし、$P^n=(p^{(n)}_{ij})$ と書く。どの $i,j\in S$ についても $p^{(n)}_{ij}>0$ となる $n\ge0$ があるとき、$P$ は 既約 であるという。$p^{(n)}_{ii}>0$ となる $n\ge1$ があるとき、そのような $n$ 全体の最大公約数を状態 $i$ の 周期 という。

推移行列 $P$ に対し、$i$ から $j$ への推移確率が $p_{ij}$ である Markov 連鎖 $(X_n)_{n\ge0}$ が、どの初期分布についても存在する(Markov連鎖 の命題「Markov 連鎖の存在」)。逆に、Markov 連鎖の推移確率を並べた行列は推移行列である。$\Pr_i$、$E_i$ は、初期分布が「状態 $i$ に確率 $1$」の連鎖での確率と期待値を表す。
$p^{(n)}_{ij}=\sum_{k_1,\dots,k_{n-1}}p_{ik_1}p_{k_1k_2}\cdots p_{k_{n-1}j}$ は $0$ 以上の項の和なので、$p^{(n)}_{ij}>0$ は $p_{ik_1},p_{k_1k_2},\dots,p_{k_{n-1}j}$ がすべて正となる状態の列があることと同値である。したがって既約性と周期は、どの成分が正かだけで決まる。既約な連鎖では、どの状態も同じ周期をもつ(Markov連鎖 の命題「互いに到達可能な状態の周期は等しい」)。
行と列の流儀について、分布を列ベクトルで表して各列の和が $1$ の行列(この記事の $P$ の転置)を推移行列と呼ぶ文献もある。以下の主張はすべて、転置をとれば列の流儀に読み替えられる。

天気の推移行列

晴れ(状態 $1$)の翌日は確率 $\frac23$ で晴れ、雨(状態 $2$)の翌日は確率 $\frac12$ で晴れとすると
$$ P=\begin{pmatrix}\frac23&\frac13\\\frac12&\frac12\end{pmatrix},\qquad P^2=\begin{pmatrix}\frac{11}{18}&\frac7{18}\\\frac7{12}&\frac5{12}\end{pmatrix} $$
である。晴れた日の 2 日後に晴れる確率は $p^{(2)}_{11}=\frac23\cdot\frac23+\frac13\cdot\frac12=\frac{11}{18}$ で、翌日の天気で場合を分けた和になっている。$\pi=\bigl(\frac35,\frac25\bigr)$ は $\pi P=\pi$ を満たす定常分布である。$P$ の固有値は $1$ と $\operatorname{tr}P-1=\frac16$ である。

基本性質

推移行列の基本性質

$P,Q$ を $m$ 次の推移行列とする。

  1. $PQ$ は推移行列である。とくにすべての $n\ge0$ で $P^n$ は推移行列である。また $0\le t\le1$ なら $tP+(1-t)Q$ も推移行列である。
  2. 分布 $\mu$ について $\mu P$ は分布である。
  3. 行ベクトル $x$ について $\|xP\|_1\le\|x\|_1$ であり、複素数を成分とする列ベクトル $f$ について $\|Pf\|_\infty\le\|f\|_\infty$ である。ここで $\|x\|_1:=\sum_i\lvert x_i\rvert$、$\|f\|_\infty:=\max_i\lvert f_i\rvert$ とする。
行の和が 1 であることを使う

1:$PQ$ の成分は $0$ 以上の項の和なので $0$ 以上で、$PQ\mathbf 1=P\mathbf 1=\mathbf 1$ である。$P^0=I$ は推移行列なので、帰納法で $P^n$ も推移行列である。$tP+(1-t)Q$ の成分は $0$ 以上で、$(tP+(1-t)Q)\mathbf 1=t\mathbf 1+(1-t)\mathbf 1=\mathbf 1$ である。
2:$(\mu P)_j=\sum_i\mu_ip_{ij}\ge0$ で、成分の和は $\mu P\mathbf 1=\mu\mathbf 1=1$ である。
3:$\|xP\|_1=\sum_j\bigl\lvert\sum_ix_ip_{ij}\bigr\rvert\le\sum_i\lvert x_i\rvert\sum_jp_{ij}=\|x\|_1$ である。また各 $i$ で $\lvert(Pf)_i\rvert\le\sum_jp_{ij}\lvert f_j\rvert\le\|f\|_\infty\sum_jp_{ij}=\|f\|_\infty$ である。$\blacksquare$

1 から、$m$ 次の推移行列全体は $m^2$ 次元の空間の有界閉な凸集合で、積について閉じている。3 は、2 つの分布の差 $\mu-\nu$ が 1 歩ごとに $\ell^1$ ノルムで増えないことを言っている。

行列の演算の確率的な意味

$(X_n)$ を推移行列 $P$、初期分布 $\mu$ の Markov 連鎖とする。

  1. $P^{r+n}=P^rP^n$($r,n\ge0$)であり、$p^{(n)}_{ij}=\Pr_i(X_n=j)$ である。
  2. 時刻 $n$ の分布 $\bigl(\Pr(X_n=j)\bigr)_{j\in S}$ は $\mu P^n$ である。
  3. 状態の上の関数 $f$ を列ベクトルとみると、$(P^nf)_i=E_i[f(X_n)]$ である。

1 と 2 は Markov連鎖 の定理「Chapman–Kolmogorov の等式」の 1〜3 である($P^{r+n}=P^rP^n$ は行列の積の結合法則にほかならない)。3 は 1 から $E_i[f(X_n)]=\sum_j\Pr_i(X_n=j)f(j)=\sum_jp^{(n)}_{ij}f(j)=(P^nf)_i$ である。$\blacksquare$

1 の $p^{(r+n)}_{ij}=\sum_kp^{(r)}_{ik}p^{(n)}_{kj}$ は、「$r+n$ 歩で $i$ から $j$ へ行く確率は、$r$ 歩目の状態 $k$ で場合を分けて足したもの」と読める。分布は左から、関数は右から掛ける。定常分布は $\pi P=\pi$、すなわち固有値 $1$ の左固有ベクトルで、成分が $0$ 以上で和が $1$ のものである。有限な状態の推移行列は必ず定常分布をもつ(Markov連鎖 の定理「有限な連鎖の定常分布の存在」)。右固有ベクトル $Pf=f$ は、1 歩先の期待値が現在の値に等しい関数(調和関数)である。

固有値

推移行列の固有値

$P$ を $m$ 次の推移行列とする。

  1. $1$ は $P$ の固有値で、$P\mathbf 1=\mathbf 1$ である。$P$ の複素数の固有値 $\lambda$ はすべて $\lvert\lambda\rvert\le1$ を満たす。
  2. $\lvert\lambda\rvert=1$ である固有値 $\lambda$ について、すべての $k\ge1$ で $\ker(P-\lambda I)^k=\ker(P-\lambda I)$ である。したがって $\lambda$ の広義固有空間は固有空間に一致し、$\lambda$ の代数的重複度(固有多項式の根としての重複度)は幾何的重複度(固有空間の次元)に等しい。
  3. $P$ が既約なら、$Pf=f$ を満たす複素数の列ベクトル $f$ は定数ベクトル $c\mathbf 1$ に限る。さらに固有値 $1$ は固有多項式の単根であり、$\pi P=\pi$ を満たす行ベクトル $\pi$ は定数倍を除いてただ 1 つである。とくに定常分布はただ 1 つである。
冪が有界であることと最大値の伝播

1:$P\mathbf 1=\mathbf 1$ は行の和の条件である。$Pf=\lambda f$、$f\ne0$ とすると、prop-tmat-basic の 3 から $\lvert\lambda\rvert\|f\|_\infty=\|Pf\|_\infty\le\|f\|_\infty$ であり、$\|f\|_\infty>0$ で割って $\lvert\lambda\rvert\le1$ を得る。
2:まず $\ker(P-\lambda I)^2\subset\ker(P-\lambda I)$ を示す。$(P-\lambda I)^2g=0$ とし、$v:=(P-\lambda I)g$ とおく。$(P-\lambda I)v=0$、すなわち $Pv=\lambda v$ であり、$Pg=\lambda g+v$ である。$n$ に関する帰納法で
$$ P^ng=\lambda^ng+n\lambda^{n-1}v\qquad(n\ge1) $$
が成り立つ($P^{n+1}g=P(\lambda^ng+n\lambda^{n-1}v)=\lambda^n(\lambda g+v)+n\lambda^nv$)。$P^n$ は推移行列なので(prop-tmat-basic の 1)、prop-tmat-basic の 3 により $\|P^ng\|_\infty\le\|g\|_\infty$ である。一方 $\lvert\lambda\rvert=1$ から
$$ \|P^ng\|_\infty\ge n\|v\|_\infty-\|g\|_\infty $$
なので、すべての $n$ で $n\|v\|_\infty\le2\|g\|_\infty$ となり、$v=0$ である。よって $g\in\ker(P-\lambda I)$ である。
次に $k$ に関する帰納法で $\ker(P-\lambda I)^k\subset\ker(P-\lambda I)$ を示す。$k\le2$ は済んだ。$k\ge2$ で成り立つとし、$(P-\lambda I)^{k+1}g=0$ とする。$h:=(P-\lambda I)^{k-1}g$ は $(P-\lambda I)^2h=0$ を満たすので、前段により $(P-\lambda I)h=0$、すなわち $(P-\lambda I)^kg=0$ であり、帰納法の仮定から $g\in\ker(P-\lambda I)$ である。逆向きの包含は明らかである。$\lambda$ の広義固有空間は $\ker(P-\lambda I)^m$ であり、その次元は $\lambda$ の代数的重複度に等しい(Jordan標準形 の補題「広義固有空間への分解」)ので、後半を得る。
3:$P$ は実行列なので、$Pf=f$ なら $f$ の実部と虚部も同じ式を満たす。よって $f$ が実数の列ベクトルの場合に示せばよい。$M:=\max_if_i$ とし、$A:=\{i\in S:f_i=M\}$ とおく。$i\in A$ なら
$$ M=f_i=\sum_jp_{ij}f_j\le\sum_jp_{ij}M=M $$
で等号が成り立つので、$p_{ij}>0$ となるすべての $j$ で $f_j=M$、すなわち $j\in A$ である。これを繰り返すと、$i\in A$ で $p_{ik_1}p_{k_1k_2}\cdots p_{k_{n-1}j}>0$ なら $j\in A$ である。$A$ は空でなく、既約性によりどの $j$ も $A$ の元から到達できるので、$A=S$、すなわち $f=M\mathbf 1$ である。
したがって固有値 $1$ の固有空間は $\mathbf 1$ で張られる 1 次元の空間で、2 により代数的重複度も $1$、すなわち単根である。$\pi P=\pi$ は $P^{\top}\pi^{\top}=\pi^{\top}$ と同じで、$P^{\top}$ は $P$ と同じ固有多項式をもつから、$P^{\top}$ の固有値 $1$ の固有空間の次元は $1$ 以上で代数的重複度 $1$ 以下、すなわち $1$ である。定常分布はこの 1 次元の空間の元で成分の和が $1$ のものなので、あればただ 1 つであり、有限な状態の推移行列には定常分布がある(Markov連鎖 の定理「有限な連鎖の定常分布の存在」)。$\blacksquare$

1 は スペクトル半径 が $1$ であることを言っている。2 は、$P$ の冪が有界であるために、絶対値 $1$ の固有値のところで Jordan標準形 の細胞がすべて $1$ 次になる、ということである。大きさ $2$ 以上の細胞があれば $P^n$ の成分は有界でなくなるが、推移行列の冪の成分は $0$ と $1$ の間にある。3 の前半の議論(最大値をとる状態から正の推移確率をたどる)は離散版の最大値原理であり、定常分布の一意性の別証明になっている(Markov連鎖 の定理「既約な有限連鎖の定常分布」と比べよ)。3 の前半と定常分布の一意性は LPW17 Lemma 1.16・Corollary 1.17(pp. 12–13)、1 と 3 の前半は同書 Lemma 12.1(p. 161)にある。
既約で非周期的な(周期が $1$ の)推移行列は、ある冪のすべての成分が正になり(LPW17 Proposition 1.7、p. 7)、$1$ 以外の固有値の絶対値はすべて $1$ より小さい(Perron–Frobeniusの定理 の定理「原始行列の固有値」)。このとき $P^n$ は、すべての行が定常分布 $\pi$ の行列 $\mathbf 1\pi$ に収束する(確率漸化式と定常分布 の定理「正則な連鎖の収束」)。収束の速さの目安は、$1$ 以外の固有値の絶対値の最大値である(ex-tmat-circulant ではちょうどその冪の速さで収束する)。

周期と単位円の上の固有値

周期と単位円の上の固有値

$P$ を既約な推移行列とし、状態の周期を $d$ とする。$\omega:=e^{2\pi\sqrt{-1}/d}$ とおくと、$1,\omega,\omega^2,\dots,\omega^{d-1}$ はすべて $P$ の固有値である。とくに $d\ge2$ なら、$1$ 以外に絶対値 $1$ の固有値があり、$P^n$ は収束しない。

状態を周期の剰余で分類する

状態 $o$ を 1 つ固定する。各 $j\in S$ について、既約性により $p^{(a)}_{oj}>0$ となる $a\ge0$ がある。$p^{(a)}_{oj}>0$ かつ $p^{(b)}_{oj}>0$ なら $a\equiv b\pmod d$ であることを示す。$p^{(c)}_{jo}>0$ となる $c\ge1$ をとる($j\ne o$ なら既約性から、$j=o$ なら周期の定義からとれる)。すると
$$ p^{(a+c)}_{oo}\ge p^{(a)}_{oj}p^{(c)}_{jo}>0,\qquad p^{(b+c)}_{oo}\ge p^{(b)}_{oj}p^{(c)}_{jo}>0 $$
で、$a+c$ と $b+c$ は $1$ 以上なので、どちらも周期 $d$ の倍数である。よって $d$ は差 $a-b$ を割り切る。そこで $c(j)\in\{0,1,\dots,d-1\}$ を $a$ を $d$ で割った余りと定める。
$p_{jk}>0$ なら、$p^{(a+1)}_{ok}\ge p^{(a)}_{oj}p_{jk}>0$ なので $c(k)\equiv c(j)+1\pmod d$ である。$l=0,1,\dots,d-1$ について列ベクトル $f^{(l)}$ を $f^{(l)}_j:=\omega^{l\,c(j)}$ と定めると、$\omega^d=1$ から
$$ (Pf^{(l)})_j=\sum_{k:\,p_{jk}>0}p_{jk}\,\omega^{l(c(j)+1)}=\omega^l\,f^{(l)}_j $$
であり、$f^{(l)}\ne0$ なので $\omega^l$ は固有値である。$d\ge2$ のとき、$\omega$ の固有ベクトル $f^{(1)}$ について $P^nf^{(1)}=\omega^nf^{(1)}$ は収束しないので、$P^n$ も収束しない。$\blacksquare$

逆に、絶対値 $1$ の固有値はこの $d$ 個だけで、どれも単根である(Perron–Frobeniusの定理 の定理「周期と絶対値最大の固有値」)。$c(j)$ による分類で状態を並べ替えると、$P$ は「第 $r$ の組から第 $r+1$ の組へ($r=d-1$ なら第 $0$ の組へ)しか移らない」区分けされた形になる。

詳細釣り合いと実固有値

詳細釣り合いを満たす推移行列の固有値

推移行列 $P$ と、成分がすべて正の分布 $\pi$ が、すべての $i,j$ で
$$ \pi_ip_{ij}=\pi_jp_{ji} $$
(詳細釣り合い)を満たすとする。このとき $\pi$ は $P$ の定常分布である。さらに $P$ は実数の固有値をもつ対角化可能な行列で、固有値は $-1$ 以上 $1$ 以下、固有ベクトルは実数の列ベクトルでとれる。

対称行列に相似である

定常性:$(\pi P)_j=\sum_i\pi_ip_{ij}=\sum_i\pi_jp_{ji}=\pi_j$ である。
$D:=\mathrm{diag}(\pi_1,\dots,\pi_m)$ とし、$A:=D^{1/2}PD^{-1/2}$ とおく。$A_{ij}=\sqrt{\pi_i}\,p_{ij}/\sqrt{\pi_j}=\pi_ip_{ij}/\sqrt{\pi_i\pi_j}$ で、詳細釣り合いから $A_{ij}=A_{ji}$ であり、$A$ は実対称行列である。対称行列 の定理「直交対角化できる実行列」により、直交行列 $U$ と実対角行列 $\Lambda$ で $A=U\Lambda U^{\top}$ となるものがある。すると
$$ P=D^{-1/2}AD^{1/2}=(D^{-1/2}U)\,\Lambda\,(D^{-1/2}U)^{-1} $$
であり、$P$ は実対角行列 $\Lambda$ と相似で、$D^{-1/2}U$ の列が実数の固有ベクトルである。固有値が $[-1,1]$ に入ることは thm-tmat-spectrum の 1 による。$\blacksquare$

詳細釣り合いを満たす連鎖は、定常分布から出発すると時間を逆向きにたどっても同じ推移確率をもつので、可逆な連鎖ともいう。この命題は LPW17 Lemma 12.2(pp. 161–162)の証明の前半である。Markov連鎖モンテカルロ法 では、目標の分布 $\pi$ について詳細釣り合いを満たす推移行列を作る(Markov連鎖モンテカルロ法 の命題「詳細釣り合いなら定常」)。

例

二重確率行列と一様分布

推移行列 $P$ で、各列の和も $1$($\mathbf 1^{\top}P=\mathbf 1^{\top}$)であるものを 二重確率行列 という。一様分布 $u:=\frac1m\mathbf 1^{\top}$ について $uP=\frac1m\mathbf 1^{\top}P$ なので、$P$ が二重確率行列であることと、一様分布が $P$ の定常分布であることは同値である。二重確率行列どうしの積も二重確率行列である($\mathbf 1^{\top}PQ=\mathbf 1^{\top}Q=\mathbf 1^{\top}$)。
置換行列 は二重確率行列であり、成分が $0$ と $1$ だけの二重確率行列は置換行列に限る。対称な推移行列($p_{ij}=p_{ji}$)も二重確率行列で、一様分布について詳細釣り合いを満たす。一般の二重確率行列は有限個の置換行列の凸結合(重みが $0$ 以上で和が $1$ の 1 次結合)として書ける(Hallの結婚定理 の定理「Birkhoff–von Neumann の定理」)。たとえば $\frac12\begin{pmatrix}1&1\\1&1\end{pmatrix}=\frac12I+\frac12\begin{pmatrix}0&1\\1&0\end{pmatrix}$ は置換行列ではない二重確率行列である(置換行列 の例「反例:二重確率行列は置換行列とは限らない」)。トランプを毎回同じ分布に従うランダムな置換で混ぜる操作の推移行列は、カードの並べ方全体の上の二重確率行列になり、一様分布はその定常分布である。混ぜ方が既約で周期 $1$ なら、並べ方の分布は一様分布に近づく。

3 状態の対称な連鎖

$S=\{1,2,3\}$ で、確率 $\frac12$ でその場にとどまり、確率 $\frac14$ ずつでほかの 2 状態へ移る連鎖を考える。$J$ を成分がすべて $1$ の $3$ 次正方行列とし、$E:=\frac13J$ とおくと、
$$ P=\begin{pmatrix}\frac12&\frac14&\frac14\\\frac14&\frac12&\frac14\\\frac14&\frac14&\frac12\end{pmatrix}=E+\frac14(I-E) $$
である。$J^2=3J$ から $E^2=E$、$E(I-E)=(I-E)E=O$、$(I-E)^2=I-E$ なので、2 項展開の交差項が消えて
$$ P^n=E+4^{-n}(I-E)\qquad(n\ge0) $$
となる。$E$ のすべての行は一様分布 $\bigl(\frac13,\frac13,\frac13\bigr)$ であり、$P^n$ の各成分は $4^{-n}\cdot\frac23$ 以下の差で $\frac13$ に近づく。$P$ の固有値は $1$(固有ベクトル $\mathbf 1$)と $\frac14$($\mathbf 1$ に直交する 2 次元の空間)で、収束の速さは 2 番目の固有値 $\frac14$ の冪である。$P$ は対称なので二重確率行列であり、prop-tmat-reversible の $\pi$ として一様分布がとれる。

グラフの上のランダムウォーク

頂点 $1,2,3$ と辺 $\{1,2\},\{2,3\}$ からなる道のグラフの上で、隣の頂点へ等しい確率で移る連鎖の推移行列は
$$ P=\begin{pmatrix}0&1&0\\\frac12&0&\frac12\\0&1&0\end{pmatrix} $$
である。$\pi:=\bigl(\frac14,\frac12,\frac14\bigr)$(次数 $1,2,1$ に比例)は $\pi_ip_{ij}=\pi_jp_{ji}$ を満たす(たとえば $\pi_1p_{12}=\frac14=\pi_2p_{21}$)。$f=(1,0,-1)^{\top}$ で $Pf=0$、$g=(1,-1,1)^{\top}$ で $Pg=-g$ なので、固有値は $1,0,-1$ の実数で、prop-tmat-reversible のとおりである。このグラフは 2 部グラフ(頂点 $2$ と頂点 $1,3$ に分かれる)なので周期は $2$ で、固有値 $-1$ は prop-tmat-period の $\omega=-1$ にあたり、$g$ は 2 つの組で符号を変える関数 $f^{(1)}$ である。一般の有限グラフの上のランダムウォークについては Markov連鎖 の例「グラフの上のランダムウォーク」を見よ。

怠惰な連鎖

推移行列 $P$ について $Q:=\frac12(I+P)$ も推移行列で、各時刻に確率 $\frac12$ でその場にとどまり、残りの確率で $P$ に従って移る連鎖を表す。$Q-\frac{1+\lambda}2I=\frac12(P-\lambda I)$ なので、$Q$ の固有値は $P$ の固有値 $\lambda$ を $\frac{1+\lambda}2$ に移したものである。$\lvert\lambda\rvert\le1$ のとき $\bigl\lvert\frac{1+\lambda}2\bigr\rvert=1$ となるのは $\lambda=1$ のときに限る(三角不等式 $\lvert1+\lambda\rvert\le1+\lvert\lambda\rvert\le2$ の等号条件)。よって $Q$ の絶対値 $1$ の固有値は $1$ だけである。$P$ が既約なら $Q$ も既約で、$q_{ii}\ge\frac12>0$ から周期は $1$ である。ex-tmat-graph の周期 $2$ の連鎖も、怠惰にすれば固有値が $1,\frac12,0$ となり、$Q^n$ は定常分布に収束する。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなること
成分が $0$ 以上$\begin{pmatrix}2&-1\\0&1\end{pmatrix}$(各行の和は $1$)固有値の絶対値が $1$ 以下、分布を分布に移す
各行の和が $1$(各列の和だけが $1$)$\begin{pmatrix}1&1\\0&0\end{pmatrix}$分布を分布に移す
既約性$2$ 次の単位行列 $I$固有値 $1$ が単根、定常分布がただ 1 つ
周期が $1$$\begin{pmatrix}0&1\\1&0\end{pmatrix}$$1$ 以外の固有値の絶対値が $1$ 未満、$P^n$ が収束する
状態が有限個$\{0,1,2,\dots\}$ の上で $p_{i,i+1}=1$定常分布が存在する
表の反例の確かめ
5 行の確かめを開く

1 行目:$P=\begin{pmatrix}2&-1\\0&1\end{pmatrix}$ は $P\mathbf 1=\mathbf 1$ を満たすが、上三角なので固有値は $2$ と $1$ である。分布 $(1,0)$ を $(2,-1)$ に移し、これは分布でない。

2 行目:$C=\begin{pmatrix}1&1\\0&0\end{pmatrix}$ の成分は $0$ 以上で各列の和は $1$ だが、第 1 行の和は $2$ である。分布 $(1,0)$ は $(1,1)$ に移り、成分の和が $2$ になる。列の流儀で読めば $C$ は推移行列の転置であり、分布を列ベクトルとして左から掛ければよい。

3 行目:$I$ は推移行列で、どの分布も定常分布である。状態 $1$ から $2$ へ到達できないので既約でなく、固有値 $1$ は重根である。それでも thm-tmat-spectrum の 2 のとおり、固有値 $1$ の Jordan 細胞は 1 次である。

4 行目:$P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ は既約で周期 $2$、固有値は $1$ と $-1$ で、$P^n$ は $I$ と $P$ を交互にとり収束しない。定常分布は $\bigl(\frac12,\frac12\bigr)$ だけである(thm-tmat-spectrum の 3)。

5 行目:状態が可算無限個でも、成分が $0$ 以上で各行の和が $1$ の行列を推移行列という(rem-tmat-infinite)。$p_{i,i+1}=1$(ほかは $0$)なら $(\pi P)_0=0$、$(\pi P)_j=\pi_{j-1}$($j\ge1$)なので、$\pi P=\pi$ から $\pi_0=0$、$\pi_j=\pi_{j-1}$ となり $\pi=0$ である。よって定常分布は存在しない。有限なら定常分布は必ず存在する(Markov連鎖 の定理「有限な連鎖の定常分布の存在」)。

補足

状態が可算無限個の場合

$S$ が可算無限集合のときも、成分が $0$ 以上で各行の和が $1$ の $S\times S$ 型の行列を推移行列といい、prop-tmat-basic と prop-tmat-meaning は、$x$ を $\ell^1$ の元、$f$ を有界な関数に限り、$|f|_\infty$ の $\max$ を $\sup$ に読み替えれば同じ証明で成り立つ($0$ 以上の項の級数は順序によらない。Markov連鎖 の「定義」の節)。一方、固有値の議論は有限次元の線形代数を使うので、そのままでは成り立たない。定常分布が存在しないこともあり(ex-tmat-counterexamples の 5 行目)、その存在は状態の再帰性と結びつく(ランダムウォーク の定義「再帰的と過渡的」)。

使われる場面。 吸収状態をもつ連鎖では、推移行列を過渡状態の部分 $Q$ と吸収への部分 $R$ に区分けし、$(I-Q)^{-1}$ から吸収の確率と時間を計算する(Markov連鎖 の定理「吸収的な連鎖の基本行列」)。既約な推移行列の固有値 $1$ と定常分布についての結果は、成分が $0$ 以上の既約な行列一般の Perron–Frobeniusの定理 からも導ける(Perron–Frobeniusの定理 の例「確率行列と定常分布」)。

関連項目

参考文献

[1]
David A. Levin, Yuval Peres (with contributions by Elizabeth L. Wilmer), Markov Chains and Mixing Times, 2nd ed., American Mathematical Society, 2017, Proposition 1.7(p. 7)、Lemma 1.16(p. 12)・Corollary 1.17(p. 13)、Lemma 12.1・Lemma 12.2(pp. 161–162)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する