Markov連鎖

同義語：マルコフ連鎖Markov chain

概要

Markov連鎖（Markov chain）とは、可算集合に値をとる確率変数の列 $X_0,X_1,\dots$ で、過去の経過が与えられたときに次の状態の確率が現在の状態だけで決まるもののことである。その確率 $p_{ij}$ を並べた推移行列 $P$ と初期分布 $\mu$ から、時刻 $n$ の分布は $\mu P^n$ と行列の積で計算できる。$\pi P=\pi$ を満たす分布（定常分布）は状態が有限個なら必ず存在し、既約ならただ 1 つだが、周期が 2 以上の連鎖では分布がそこへ収束しないことがある。確率漸化式、グラフの上のランダムウォーク、ギャンブラーの破産などを統一的に扱う枠組みである。

$$\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}} $$

前提知識: 確率空間, 確率変数, 条件付き確率, 行列

高校の確率漸化式では、「晴れの翌日は確率 $\frac23$ で晴れ、雨の翌日は確率 $\frac12$ で晴れ」のような設定から、$n$ 日目に晴れる確率 $p_n$ について $p_{n+1}=\frac23p_n+\frac12(1-p_n)$ を立てる。この式が立つのは、明日の天気の確率が今日の天気だけで決まり、昨日以前の天気によらないと仮定しているからである。この「次の状態の確率は現在の状態だけで決まる」という仮定を満たす確率変数の列を Markov 連鎖という。状態が有限個の場合の推移行列・定常分布・収束の定理は 確率漸化式と定常分布 で扱われている。この記事では、状態が可算無限個の場合も含めて Markov 連鎖を定義し、多段の推移確率、状態の分類（到達可能性・既約性・周期）、定常分布の存在と一意性、吸収的な連鎖の計算を述べる。

定義

以下、状態の集合 $S$ は空でない可算集合（有限集合または可算無限集合）とする。$S$ で添字づけた実数の族 $(v_i)_{i\in S}$ を行ベクトル、$(a_{ij})_{i,j\in S}$ を $S\times S$ 型の行列と呼び、$S=\{1,\dots,m\}$ のときは通常の行ベクトル・行列と同じものである。

推移行列と分布
  1. $S\times S$ 型の行列 $P=(p_{ij})_{i,j\in S}$ が推移行列（確率行列）であるとは、すべての成分が $p_{ij}\ge0$ で、各行について $\sum_{j\in S}p_{ij}=1$ となることをいう。
  2. 行ベクトル $\mu=(\mu_i)_{i\in S}$ が $S$ 上の分布（確率ベクトル）であるとは、すべての $\mu_i\ge0$ で $\sum_{i\in S}\mu_i=1$ となることをいう。

$S$ が無限集合のとき、和 $\sum_{j\in S}$ は $0$ 以上の項の級数なので、$S$ をどの順に並べても値（$+\infty$ を含む）は変わらない。以下の行列の積 $(AB)_{ij}:=\sum_{k\in S}a_{ik}b_{kj}$ も、成分が $0$ 以上の行列についてだけ使うので、つねに意味をもつ。推移行列 $P,Q$ の積 $PQ$ は推移行列であり（$\sum_j\sum_kp_{ik}q_{kj}=\sum_kp_{ik}\sum_jq_{kj}=1$。$0$ 以上の項の 2 重和は順序を入れ替えてよい）、分布 $\mu$ と推移行列 $P$ の積 $\mu P$ は分布である。$P^0$ は単位行列 $I$ とし、$P^{n+1}:=P^nP$ と定める。

Markov 連鎖

確率空間 $(\Omega,\mathcal{F},\Pr)$ の上の、$S$ に値をとる確率変数の列 $X_0,X_1,X_2,\dots$ が、推移行列 $P=(p_{ij})$ と分布 $\mu$ をもつ Markov 連鎖であるとは、次の 2 条件が成り立つことをいう。
(R1) すべての $i\in S$ について $\Pr(X_0=i)=\mu_i$。
(R2) すべての $n\ge0$ と $i_0,\dots,i_n,j\in S$ について、$\Pr(X_0=i_0,\dots,X_n=i_n)>0$ ならば
$$ \Pr(X_{n+1}=j\mid X_0=i_0,\dots,X_n=i_n)=p_{i_nj}. $$
$\mu$ を初期分布、$P$ を推移行列、$S$ を状態空間、$p_{ij}$ を $i$ から $j$ への推移確率という。

条件 (ii) を Markov 性という。左辺は過去の経過 $i_0,\dots,i_n$ 全体を条件にした確率だが、それが現在の状態 $i_n$ だけで決まり、しかも時刻 $n$ によらない。時刻によらないことを強調して「時間的に一様な」Markov 連鎖と呼ぶこともある。確率変数 $X_n$ が離散的な値をとるので、条件付き確率は通常の定義（条件付き確率 の記事の定義「条件付き確率」）で足り、条件の事象の確率が $0$ の場合は条件 (ii) に何も要求しない。
分布を行ベクトルとし、$p_{ij}$ を「$i$ から $j$ へ」の確率とする流儀は 確率漸化式と定常分布 の記事（注意「行ベクトルと列ベクトル」）と同じである。

経路の確率による特徴づけ

$S$ に値をとる確率変数の列 $(X_n)$ が推移行列 $P$、初期分布 $\mu$ の Markov 連鎖であることは、すべての $n\ge0$ と $i_0,\dots,i_n\in S$ について
$$ \Pr(X_0=i_0,X_1=i_1,\dots,X_n=i_n)=\mu_{i_0}\,p_{i_0i_1}\,p_{i_1i_2}\cdots p_{i_{n-1}i_n} $$
が成り立つことと同値である。

要点：条件付き確率の定義 $\Pr(A\cap B)=\Pr(B)\Pr(A\mid B)$ を 1 歩ずつ使うと、Markov 性から経路の確率は推移確率の積になる。逆に積の形なら、1 歩延ばした経路の確率を割り算して Markov 性が出る。

詳しい証明を開く

事象 $\{X_0=i_0,\dots,X_n=i_n\}$ を $E(i_0,\dots,i_n)$ と書く。

Markov 連鎖なら式が成り立つことを $n$ に関する帰納法で示す。$n=0$ は (i) である。$n$ で成り立つとする。$\Pr(E(i_0,\dots,i_n))>0$ なら、(ii) と条件付き確率の定義から

$$\Pr(E(i_0,\dots,i_n,j))=\Pr(E(i_0,\dots,i_n))\,p_{i_nj}=\mu_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}p_{i_nj}$$

である。$\Pr(E(i_0,\dots,i_n))=0$ なら、$E(i_0,\dots,i_n,j)\subset E(i_0,\dots,i_n)$ から左辺は $0$ であり、帰納法の仮定から右辺も $0$ である。

逆に式が成り立つとする。$n=0$ の式が (i) である。$\Pr(E(i_0,\dots,i_n))>0$ なら、条件付き確率の定義と式から

$$\Pr(X_{n+1}=j\mid E(i_0,\dots,i_n))=\frac{\mu_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}p_{i_nj}}{\mu_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}}=p_{i_nj}$$

であり、(ii) が成り立つ。$\square$

したがって、Markov 連鎖の $X_0,\dots,X_n$ に関する確率は、初期分布と推移行列だけで決まる。どんな初期分布と推移行列に対しても、それをもつ Markov 連鎖は存在する。

Markov 連鎖の存在

$S$ 上の任意の分布 $\mu$ と推移行列 $P$ に対し、ある確率空間の上に、初期分布 $\mu$、推移行列 $P$ の Markov 連鎖 $(X_n)_{n\ge0}$ が存在する。

要点：区間 $[0,1)$ の上の一様な確率（長さ）を使い、$[0,1)$ を長さ $\mu_i$ の区間に分け、その各区間を長さの比が $p_{ij}$ の区間にさらに分け、…と分け続ける。点 $\omega$ が第 $n$ 段でどの区間に入るかを $X_n(\omega)$ とすればよい。

詳しい証明を開く

$S$ の元を 1 列に並べ、$S=\{s_0,s_1,\dots\}$ とする。確率空間として、$[0,1)$ の Lebesgue 可測集合全体と Lebesgue 測度 $\lambda$ をとる（確率空間 の記事の例「区間 [0,1] 上の一様な確率」と同じ。$1$ 点の測度は $0$ なので右端を除いてもよい）。区間の長さは $\lambda([a,b))=b-a$ である（Lebesgue測度 の記事の定理「区間の外測度は長さに等しい」と命題「区間とBorel集合の可測性・不変性」）。

各 $n$ と $i_0,\dots,i_n\in S$ について、半開区間 $J(i_0,\dots,i_n)=[a,a+\ell)$、$\ell=\mu_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}$ を帰納的に定める（$\ell=0$ なら空集合）。$n=0$ では、$J(s_k):=[\sum_{l< k}\mu_{s_l},\ \sum_{l\le k}\mu_{s_l})$ とする。$J(i_0,\dots,i_n)=[a,a+\ell)$ が定まったら、$J(i_0,\dots,i_n,s_k):=[a+\ell\sum_{l< k}p_{i_ns_l},\ a+\ell\sum_{l\le k}p_{i_ns_l})$ とする。$\sum_lp_{i_ns_l}=1$ なので、左端は単調に増加して $a+\ell$ に収束し、$[a,a+\ell)$ の各点はこれらの区間のちょうど 1 つに入る。つまり第 $n+1$ 段の区間は第 $n$ 段の各区間を分割する。$n=0$ でも $\sum\mu_{s_l}=1$ から同様に $[0,1)$ が分割される。

$\omega\in[0,1)$ に対し、第 $n$ 段で $\omega$ を含むただ 1 つの区間を $J(i_0,\dots,i_n)$ として、$X_n(\omega):=i_n$ と定める。分割が入れ子になっているので、$X_0(\omega),\dots,X_n(\omega)$ はこの $i_0,\dots,i_n$ に等しく、$\{X_0=i_0,\dots,X_n=i_n\}=J(i_0,\dots,i_n)$ である。特に $\{X_n=i\}$ は可算個の区間の和なので可測で、$X_n$ は確率変数である。その確率は区間の長さ $\mu_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}$ なので、prop-markov-chain-paths により $(X_n)$ は求める Markov 連鎖である。$\square$

状態が有限個で時刻も有限の範囲 $X_0,\dots,X_n$ だけを考えるなら、経路の全体 $S^{n+1}$ に prop-markov-chain-paths の式で確率を与えた有限の確率空間で足りる（確率漸化式と定常分布 の記事の定義「有限 Markov 連鎖」）。無限に続く列を 1 つの確率空間の上で扱うには、上のような構成が要る。以下、$\Pr_i$ は初期分布が「状態 $i$ に確率 $1$」の場合の確率を表す。

多段の推移確率

Chapman–Kolmogorov の等式

$(X_n)$ を推移行列 $P$、初期分布 $\mu$ の Markov 連鎖とし、$P^n=(p^{(n)}_{ij})$ と書く。

  1. $P^{m+n}=P^mP^n$、すなわち $p^{(m+n)}_{ij}=\sum_{k\in S}p^{(m)}_{ik}p^{(n)}_{kj}$。
  2. すべての $m,n\ge0$ と $i_0,\dots,i_m,j\in S$ について
    $$ \Pr(X_0=i_0,\dots,X_m=i_m,\ X_{m+n}=j)=\Pr(X_0=i_0,\dots,X_m=i_m)\,p^{(n)}_{i_mj}. $$
    特に、$\Pr(X_m=i)>0$ ならば $\Pr(X_{m+n}=j\mid X_m=i)=p^{(n)}_{ij}$ であり、$\Pr_i(X_n=j)=p^{(n)}_{ij}$ である。
  3. 時刻 $n$ の分布は $\bigl(\Pr(X_n=j)\bigr)_{j\in S}=\mu P^n$ である。

要点：時刻 $m$ と $m+n$ の間の途中の状態 $k_1,\dots,k_{n-1}$ で場合を分け、prop-markov-chain-paths の積の式を足し合わせると、途中の和がちょうど行列の積 $P^n$ の成分になる。

詳しい証明を開く

1：行列の積の結合法則 $(AB)C=A(BC)$ は、成分が $0$ 以上の行列では 2 重和の順序の入れ替え $\sum_l\sum_ka_{ik}b_{kl}c_{lj}=\sum_ka_{ik}\sum_lb_{kl}c_{lj}$ で成り立つ。これと定義 $P^{n+1}=P^nP$ から、$n$ に関する帰納法で $P^{m+n}=P^mP^n$ が従う。

2：事象 $\{X_0=i_0,\dots,X_m=i_m,X_{m+n}=j\}$ は、途中の状態 $k_1,\dots,k_{n-1}$ ごとの事象 $\{X_0=i_0,\dots,X_m=i_m,X_{m+1}=k_1,\dots,X_{m+n-1}=k_{n-1},X_{m+n}=j\}$ の、互いに交わらない可算個の和である。可算加法性と prop-markov-chain-paths により

$$\Pr(X_0=i_0,\dots,X_m=i_m,X_{m+n}=j)=\mu_{i_0}p_{i_0i_1}\cdots p_{i_{m-1}i_m}\sum_{k_1,\dots,k_{n-1}}p_{i_mk_1}p_{k_1k_2}\cdots p_{k_{n-1}j}$$

であり、右辺の和は行列の積の定義から $p^{(n)}_{i_mj}$ である（$n=0$ では $p^{(0)}_{i_mj}$ は $j=i_m$ のとき $1$、それ以外 $0$ で、式は明らか）。前の因子は prop-markov-chain-paths により $\Pr(X_0=i_0,\dots,X_m=i_m)$ である。後半は、この式を $i_0,\dots,i_{m-1}$ について足して $\Pr(X_m=i,X_{m+n}=j)=\Pr(X_m=i)\,p^{(n)}_{ij}$ を得て、$\Pr(X_m=i)$ で割ればよい。

3：2 で $m=0$ とすると $\Pr(X_0=i,X_n=j)=\mu_ip^{(n)}_{ij}$ であり、$i$ について足すと $\Pr(X_n=j)=\sum_i\mu_ip^{(n)}_{ij}=(\mu P^n)_j$ である。$\square$

2 は、過去の経過 $i_0,\dots,i_m$ が分かっていても、$n$ 歩先の状態の確率は現在の状態 $i_m$ と $P^n$ だけで決まることを言っている。1 は「$m+n$ 歩で $i$ から $j$ へ行く確率は、$m$ 歩目にいる状態 $k$ で場合分けして足したもの」という式である。有限の場合の同じ主張は 確率漸化式と定常分布 の記事の命題「分布の時間発展」にある。$P^n$ の成分が確率を表すことは、隣接行列と道の数 の記事の定理「隣接行列の累乗の成分は道筋の数」で隣接行列の冪の成分が道筋の数を表すことと同じ形の計算である。

2 状態の連鎖

$S=\{1,2\}$、$0\le a,b\le1$、$a+b>0$ として
$$ P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix},\qquad P^n=\frac1{a+b}\begin{pmatrix}b&a\\b&a\end{pmatrix}+\frac{(1-a-b)^n}{a+b}\begin{pmatrix}a&-a\\-b&b\end{pmatrix} $$
である（$n=0$ で $I$ になり、右から $P$ を掛けると $n$ が $1$ 増えることを確かめれば、帰納法で示せる）。$0< a+b<2$ なら $\lvert1-a-b\rvert<1$ で、$P^n$ はすべての行が $\bigl(\frac b{a+b},\frac a{a+b}\bigr)$ の行列に収束する。$a=b=1$ なら $(1-a-b)^n=(-1)^n$ で $P^n$ は収束しない。この計算は 確率漸化式と定常分布 の記事の定理「2 状態の連鎖」で詳しく扱われている。冒頭の天気の例は $a=\frac13$、$b=\frac12$ の場合で、晴れの確率は $\frac{b}{a+b}=\frac35$ に近づく。

状態の分類

到達可能性・既約性・吸収状態・周期

推移行列 $P$ の状態 $i,j\in S$ について、次のように定める。

  1. ある $n\ge0$ で $p^{(n)}_{ij}>0$ となるとき、$j$ は $i$ から到達可能であるといい、$i\to j$ と書く。$i\to j$ かつ $j\to i$ のとき、$i$ と $j$ は互いに到達可能であるという。
  2. どの 2 状態も互いに到達可能であるとき、$P$（または対応する Markov 連鎖）は既約であるという。
  3. $p_{ii}=1$ である状態 $i$ を吸収状態という。
  4. $p^{(n)}_{ii}>0$ となる $n\ge1$ が存在するとき、そのような $n$ 全体の最大公約数を $i$ の周期という。周期が $1$ の状態を非周期的という。

$p^{(n)}_{ij}>0$ は、$p_{ik_1}p_{k_1k_2}\cdots p_{k_{n-1}j}>0$ となる途中の状態の列があること、つまり状態を頂点とし、$p_{kl}>0$ となる組 $(k,l)$ を辺 $k\to l$ とする有向グラフで、$i$ から $j$ へ辺を $n$ 本たどって行けることと同じである。したがって到達可能性・既約性・周期は、推移確率が正かどうかだけで決まり、値の大きさにはよらない。互いに到達可能であることは $S$ 上の同値関係であり（推移律は $p^{(m+n)}_{ik}\ge p^{(m)}_{ij}p^{(n)}_{jk}$ から従う）、既約とは同値類が 1 つだけということである。

互いに到達可能な状態の周期は等しい

状態 $i$ と $j$ が互いに到達可能で、$i$ に周期 $d_i$ があれば、$j$ にも周期 $d_j$ があり、$d_i=d_j$ である。

$i=j$ なら示すことはないので $i\ne j$ とし、$p^{(a)}_{ij}>0$、$p^{(b)}_{ji}>0$ となる $a,b\ge1$ をとる。thm-markov-chain-ck の 1 から $p^{(a+b)}_{jj}\ge p^{(b)}_{ji}p^{(a)}_{ij}>0$ なので $j$ にも周期がある。同様に $p^{(a+b)}_{ii}\ge p^{(a)}_{ij}p^{(b)}_{ji}>0$ なので $d_i$ は $a+b$ を割り切る。$p^{(n)}_{jj}>0$ となる任意の $n\ge1$ について $p^{(a+n+b)}_{ii}\ge p^{(a)}_{ij}p^{(n)}_{jj}p^{(b)}_{ji}>0$ なので、$d_i$ は $a+n+b$ も割り切り、したがって差の $n$ を割り切る。よって $d_i$ は $d_j$ を割り切る。$i$ と $j$ を入れ替えて $d_j$ は $d_i$ を割り切り、$d_i=d_j$ である。$\square$

したがって既約な連鎖では（周期があれば）すべての状態の周期が等しく、それを連鎖の周期という。

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

孤立した頂点のない有限の単純グラフ（頂点の集合 $V$、辺の集合 $E$）の上で、各時刻に今いる頂点の隣の頂点へ等しい確率で移る連鎖を考える。隣接行列を $A=(a_{ij})$、頂点 $i$ の次数を $d(i)=\sum_ja_{ij}$ とすると、推移確率は $p_{ij}=\frac{a_{ij}}{d(i)}$、行列で書けば $P=D^{-1}A$（$D$ は次数を並べた対角行列）である。$A^n$ の成分が長さ $n$ の道筋の数であること（隣接行列と道の数 の記事の定理「隣接行列の累乗の成分は道筋の数」）から、$p^{(n)}_{ij}>0$ は $i$ から $j$ への長さ $n$ の道筋があることと同値である。

  1. 連結なグラフの上のランダムウォークは既約である。
  2. 行ベクトル $\pi_i:=\frac{d(i)}{2\lvert E\rvert}$ は分布であり（次数の和は辺の数の 2 倍）、$\pi P=\pi$ を満たす。実際、$a_{ij}=a_{ji}$ から $(\pi P)_j=\sum_i\frac{d(i)}{2\lvert E\rvert}\cdot\frac{a_{ij}}{d(i)}=\frac{\sum_ia_{ji}}{2\lvert E\rvert}=\frac{d(j)}{2\lvert E\rvert}=\pi_j$ である。
  3. 頂点を 2 色に塗り分けて辺がつねに異なる色を結ぶ（2 部グラフ）なら、長さが奇数の閉じた道筋はないので周期は $2$ である。三角形を含む連結グラフでは、長さ $2$ と $3$ の閉じた道筋があるので、その頂点の周期は $1$、したがって prop-markov-chain-period によりすべての頂点の周期は $1$ である。
    たとえば頂点 $1,2,3,4$ と辺 $\{1,2\},\{1,3\},\{2,3\},\{3,4\}$ のグラフ（三角形に 1 本の辺が付いた形）では、次数は $2,2,3,1$、$\pi=\bigl(\frac14,\frac14,\frac38,\frac18\bigr)$ である。

定常分布

定常分布

$S$ 上の分布 $\pi$ で $\pi P=\pi$、すなわちすべての $j\in S$ について $\sum_{i\in S}\pi_ip_{ij}=\pi_j$ を満たすものを、推移行列 $P$（または対応する Markov 連鎖）の定常分布という。

初期分布が定常分布なら、thm-markov-chain-ck の 3 により $X_n$ の分布は $\pi P^n=\pi$ で、時刻によらない。状態が有限個なら、$\pi P=\pi$ は $\pi$ が $P$ の固有値 $1$ の左固有ベクトルであることを言っている（固有値）。ただし定常分布であるには、成分がすべて $0$ 以上で和が $1$ でなければならない。

有限な連鎖の定常分布の存在

状態空間 $S$ が有限集合なら、どの推移行列 $P$ も定常分布をもつ。

$S=\{1,\dots,m\}$ とし、分布 $\mu$ を 1 つとる。時間平均 $a_N:=\frac1N\sum_{n=0}^{N-1}\mu P^n$（$N\ge1$）は分布の平均なので分布であり、
$$ a_NP-a_N=\frac1N\sum_{n=0}^{N-1}\bigl(\mu P^{n+1}-\mu P^n\bigr)=\frac1N\bigl(\mu P^N-\mu\bigr) $$
の各成分の絶対値は $\frac1N$ 以下である。分布の全体は $\mathbb{R}^m$ の有界閉集合なので（Bolzano–Weierstrassの定理 の記事の例「確率ベクトルの列」）、同じ記事の系「有界閉集合の点列コンパクト性」により、ある部分列 $a_{N_k}$ がある分布 $\pi$ に収束する。$\pi P-\pi$ の各成分は $a_{N_k}P-a_{N_k}$ の成分（$a_{N_k}$ の成分の 1 次式）の極限であり、その絶対値は $\frac1{N_k}\to0$ 以下なので、$\pi P=\pi$ である。$\square$

この証明は 確率漸化式と定常分布 の記事の定理「定常分布の存在」の証明と同じ筋である。分布 $\mu P^n$ そのものは収束するとは限らない（ex-markov-chain-ehrenfest）が、時間平均をとってから Bolzano–Weierstrass の定理で収束する部分列を取り出せば、極限の候補が必ず得られる。状態が無限個になると、成分が無限個あるので有限次元の Bolzano–Weierstrass の定理を使うこの議論は成り立たず、実際に定常分布が存在しないことがある（ex-markov-chain-counterexamples の 3）。

既約な有限連鎖の定常分布

$S$ が有限集合で $P$ が既約ならば、$P$ の定常分布はただ 1 つであり、そのすべての成分は正である。

正であること：$\pi$ を定常分布とする。$\pi=\pi P^n$ がすべての $n$ で成り立つ。成分の和が $1$ なので $\pi_i>0$ となる $i$ がある。任意の $j$ について、既約性により $p^{(n)}_{ij}>0$ となる $n$ があり、$\pi_j=\sum_k\pi_kp^{(n)}_{kj}\ge\pi_ip^{(n)}_{ij}>0$ である。
ただ 1 つであること：$\pi,\pi'$ を定常分布とする。前半によりすべての $\pi_i>0$ なので、$c:=\min_i\frac{\pi'_i}{\pi_i}$（$S$ が有限なので最小値がある）をとり、最小値をとる状態を $i_0$ とする。$\nu:=\pi'-c\pi$ はすべての成分が $0$ 以上で、$\nu_{i_0}=0$、$\nu P=\nu$ を満たす。成分の和は $1-c$ である。もし $1-c>0$ なら $\frac{\nu}{1-c}$ は定常分布で、成分 $i_0$ が $0$ なので前半に反する。成分が $0$ 以上なので $1-c\ge0$ であり、したがって $1-c=0$、すなわち成分がすべて $0$ 以上で和が $0$ の $\nu$ は $0$ である。よって $\pi'=c\pi=\pi$ である。$\square$

ex-markov-chain-graph の連結なグラフでは、定常分布は次数に比例する $\pi$ ただ 1 つである。既約でないと定常分布は 1 つとは限らない（ex-markov-chain-counterexamples の 2）。
定常分布への収束には、既約性だけでは足りない。ある $k\ge1$ で $P^k$ のすべての成分が正であるとき $P$ を正則といい、状態が有限個の正則な連鎖では、どの初期分布からも $\mu P^n$ は定常分布に収束する（確率漸化式と定常分布 の記事の定理「正則な連鎖の収束」、GS06 Theorem 11.7）。ex-markov-chain-graph の最後のグラフでは $P^4$ のすべての成分が正なので正則であり、どこから出発しても $n$ 歩後にいる頂点の分布は $\bigl(\frac14,\frac14,\frac38,\frac18\bigr)$ に近づく。正則な連鎖は既約であり、既約でも正則でない連鎖では、次の例のように分布が振動しうる。

Ehrenfest の壺

2 つの壺に合わせて $M$ 個（$M\ge1$）の玉が入っている。各時刻に $M$ 個の玉から 1 個を等しい確率で選び、もう一方の壺へ移す。第 1 の壺の玉の数を状態とすると、$S=\{0,1,\dots,M\}$ で
$$ p_{k,k-1}=\frac kM,\qquad p_{k,k+1}=\frac{M-k}M $$
（ほかは $0$）である。どの $k$ からも $k\pm1$ へ移れるので既約であり、1 歩ごとに状態の偶奇が変わるので周期は $2$ である。二項係数の分布 $\pi_k=\binom Mk2^{-M}$ は定常分布である。実際、$\pi_kp_{k,k+1}=\binom Mk\frac{M-k}M2^{-M}=\binom M{k+1}\frac{k+1}M2^{-M}=\pi_{k+1}p_{k+1,k}$（隣り合う状態の間の行き来が釣り合う）から
$$ (\pi P)_j=\pi_{j-1}p_{j-1,j}+\pi_{j+1}p_{j+1,j}=\pi_jp_{j,j-1}+\pi_jp_{j,j+1}=\pi_j $$
となる（端の $j=0,M$ では存在しない項を $0$ とする）。thm-markov-chain-irreducible により定常分布はこれだけである。しかし状態 $0$ から出発すると、偶数の時刻には奇数の状態にいる確率が $0$、奇数の時刻には偶数の状態にいる確率が $0$ なので、$\mu P^n$ は $\pi$ に収束しない。

$M=4$ の場合の数値を開く

状態 $0$ から出発した分布は $(1,0,0,0,0)$、$(0,1,0,0,0)$、$\bigl(\frac14,0,\frac34,0,0\bigr)$、$\bigl(0,\frac58,0,\frac38,0\bigr)$、$\bigl(\frac5{32},0,\frac34,0,\frac3{32}\bigr)$、$\bigl(0,\frac{17}{32},0,\frac{15}{32},0\bigr)$、… であり、定常分布は $\bigl(\frac1{16},\frac14,\frac38,\frac14,\frac1{16}\bigr)$ である。

吸収的な連鎖

吸収的な連鎖

$S$ を有限集合とする。推移行列 $P$ が吸収的であるとは、吸収状態が少なくとも 1 つあり、どの状態からもいずれかの吸収状態へ到達可能であることをいう。吸収状態でない状態を過渡状態という。

吸収状態の集合を $A$、過渡状態の集合を $T$（空でないとする）とし、状態を $T$ の元、$A$ の元の順に並べると、推移行列は区分けされた形（行列 の記事の定義「行列の区分け」）
$$ P=\begin{pmatrix}Q&R\\O&I\end{pmatrix} $$
に書ける。$Q$ は過渡状態どうしの推移確率を並べた $T\times T$ 型、$R$ は過渡状態から吸収状態への推移確率を並べた $T\times A$ 型の行列、$O$ は零行列、$I$ は単位行列である。吸収状態に着いた時刻を $\tau:=\min\{n\ge0\mid X_n\in A\}$（着かなければ $\tau=\infty$）とする。

吸収的な連鎖の基本行列

$P$ を上の形の吸収的な推移行列とし、$i,j\in T$、$k\in A$ とする。

  1. $\Pr_i(X_n=j)=(Q^n)_{ij}$ であり、$n\to\infty$ で $Q^n\to O$ となる。また $\Pr_i(\tau<\infty)=1$ である。
  2. $I-Q$ は逆行列をもち、$N:=(I-Q)^{-1}=\sum_{n=0}^\infty Q^n$ である。$N$ の $(i,j)$ 成分は、$i$ から出発した連鎖が $j$ にいる回数（時刻 $0$ を含む）の期待値である。
  3. $i$ から出発して吸収されるまでの時間の期待値 $\mathrm{E}_i[\tau]$ は、列ベクトル $t:=N\mathbf 1$（$\mathbf 1$ は成分がすべて $1$ の列ベクトル）の第 $i$ 成分である。
  4. $i$ から出発して吸収状態 $k$ に吸収される確率 $\Pr_i(X_\tau=k)$ は、行列 $B:=NR$ の $(i,k)$ 成分である。
    $N$ を $P$ の基本行列という。

吸収状態 $k$ について $\Pr(X_n=k,\ X_{n+1}\ne k)=\Pr(X_n=k)(1-p_{kk})=0$ なので、確率 $1$ で、一度吸収状態に入った連鎖はそこにとどまる。以下の事象の等式は、確率 $0$ の事象を除いて成り立つという意味である。
1：区分けされた行列の積を計算すると、帰納法で $P^n=\begin{pmatrix}Q^n&R_n\\O&I\end{pmatrix}$（$R_n$ はある行列）となるので、thm-markov-chain-ck の 2 から $\Pr_i(X_n=j)=(Q^n)_{ij}$ である。吸収状態に入った連鎖はそこにとどまるので、$\Pr_i(X_n\in T)$ は $n$ について増えない。各 $i\in T$ について、到達可能性から $\Pr_i(X_{L_i}\in A)>0$ となる $L_i$ があり、$L:=\max_iL_i$ とおくと、$\rho:=\max_{i\in T}\Pr_i(X_L\in T)<1$ である。これは $Q^L$ の各行の和が $\rho$ 以下であることを言っている。$Q$ の各行の和は $1$ 以下なので、$Q^{qL+r}=(Q^L)^qQ^r$ の各行の和は $\rho^q$ 以下である。

詳細

成分が $0$ 以上の行列 $C,D$ で、$C$ の各行の和が $\alpha$ 以下、$D$ の各行の和が $\beta$ 以下なら、$CD$ の第 $i$ 行の和は $\sum_l c_{il}\sum_jd_{lj}\le\beta\sum_lc_{il}\le\alpha\beta$ である。これを繰り返し使う。


したがって $Q^n$ の成分は $0$ 以上で $\rho^{\lfloor n/L\rfloor}$ 以下となり、$Q^n\to O$ である。事象 $\{\tau>n\}=\{X_n\in T\}$ は $n$ について減少し、その確率 $\sum_{j\in T}(Q^n)_{ij}$ は $0$ に近づくので、確率の連続性（確率空間 の記事の命題「確率の連続性」）により $\Pr_i(\tau=\infty)=0$ である。
2〜4 の要点：$N=\sum_nQ^n$ は 1 の評価で収束し、$(I-Q)N=I$ となる。$N_{ij}=\sum_n\Pr_i(X_n=j)$ は $j$ にいる回数の期待値、その行の和は過渡状態にいる回数すなわち $\tau$ の期待値、$\sum_n(Q^nR)_{ik}$ は「時刻 $n$ に過渡状態にいて次に $k$ へ移る」確率の和である。
2〜4 の詳しい証明を開く

2：1 の評価から $\sum_nQ^n$ の各成分は $0$ 以上の項の収束する級数であり、和を $N$ とすると、$(I-Q)\sum_{n=0}^{K-1}Q^n=I-Q^K$ で $K\to\infty$ として $(I-Q)N=I$ である。正方行列なので $N=(I-Q)^{-1}$ である。$j$ にいる回数は $V_j:=\sum_{n\ge0}1_{\{X_n=j\}}$ で、部分和は $n$ について増加するので、期待値（積分）と極限を交換できて（Lebesgue積分 の記事の定理「単調収束定理」）$\mathrm{E}_i[V_j]=\sum_n\Pr_i(X_n=j)=\sum_n(Q^n)_{ij}=N_{ij}$ である。

3：出発点が過渡状態なら、$X_n\in T$ となるのは $n<\tau$ のときに限る（吸収状態から出ないため）。したがって $\tau=\sum_{j\in T}V_j$ であり、2 から $\mathrm{E}_i[\tau]=\sum_jN_{ij}=(N\mathbf 1)_i$ である。

4：$i\in T$ から出発すると、「$X_\tau=k$」は、互いに交わらない事象 $\{X_n\in T,\ X_{n+1}=k\}$（$n\ge0$）の和である（$\tau=n+1$ で $k$ に着く）。thm-markov-chain-ck の 2 から $\Pr_i(X_n=j,X_{n+1}=k)=(Q^n)_{ij}R_{jk}$ なので、可算加法性により $\Pr_i(X_\tau=k)=\sum_n\sum_{j\in T}(Q^n)_{ij}R_{jk}=(NR)_{ik}$ である。$\square$

2 の $N=\sum Q^n$ は、実数の等比級数 $\frac1{1-q}=\sum q^n$（$\lvert q\rvert<1$）の行列版である。3 の式 $t=N\mathbf 1$ は $(I-Q)t=\mathbf 1$、すなわち $t_i=1+\sum_{j\in T}q_{ij}t_j$ と同じであり、これは「最初の 1 歩で場合を分ける」式（期待値の漸化式と停止 の記事の定理「最初の 1 歩で分ける式」）である。4 も同様に $B=R+QB$ と書ける。

ギャンブラーの破産

所持金 $0,1,\dots,M$ を状態とし、$1\le i\le M-1$ からは確率 $p$ で $i+1$ へ、確率 $1-p$ で $i-1$ へ移り、$0$ と $M$ を吸収状態とする（ギャンブラーの破産 の記事の定義「ギャンブラーの破産の設定」）。$M=4$、$p=\frac12$ では、過渡状態 $1,2,3$ について
$$ Q=\begin{pmatrix}0&\frac12&0\\\frac12&0&\frac12\\0&\frac12&0\end{pmatrix},\quad R=\begin{pmatrix}\frac12&0\\0&0\\0&\frac12\end{pmatrix},\quad N=\begin{pmatrix}\frac32&1&\frac12\\1&2&1\\\frac12&1&\frac32\end{pmatrix} $$
（$R$ の列は吸収状態 $0,4$ の順）であり、$t=N\mathbf 1=(3,4,3)^{\top}$、$B=NR$ の第 2 列（$4$ に着く確率）は $\bigl(\frac14,\frac12,\frac34\bigr)^{\top}$ である。これは ギャンブラーの破産 の記事の定理「目標に達する確率」の $\frac iM$ と、定理「終わるまでの回数の期待値」の $i(M-i)$ に一致する。$M=3$、$p=\frac23$ では $N=\begin{pmatrix}\frac97&\frac67\\\frac37&\frac97\end{pmatrix}$、$t=\bigl(\frac{15}7,\frac{12}7\bigr)^{\top}$、$3$ に着く確率は $\bigl(\frac47,\frac67\bigr)^{\top}$ で、これも同じ記事の公式（$r=\frac{1-p}p=\frac12$）に一致する。

反例：仮定を外すと何が崩れるか

外す条件反例成り立たなくなること
正則性（既約だけでは足りない）交互に入れ替わる 2 状態の連鎖、Ehrenfest の壺どの初期分布からも定常分布に収束する
既約性状態 $1,2$ が吸収状態の連鎖定常分布がただ 1 つである
状態が有限個整数全体の上の単純ランダムウォーク定常分布が存在する
状態をまとめない3 状態の巡回の 2 状態をまとめた過程Markov 連鎖である
反例の確認
  1. 正則性を外す：$P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ は既約で、定常分布は $\bigl(\frac12,\frac12\bigr)$ だけだが、状態 $1$ から出発すると分布は $(1,0),(0,1),(1,0),\dots$ と交互になり収束しない（確率漸化式と定常分布 の記事の例「反例：交互に入れ替わる連鎖」）。一般に、既約な連鎖が正則なら周期は $1$ であり、したがって周期 $2$ の既約な連鎖は正則でない。ex-markov-chain-ehrenfest も周期 $2$ で、同じ理由で収束しない。「既約である」を満たし「分布が定常分布に収束する」を満たさない。
    正則なら周期が 1 であることの詳細

    $P^k$ の成分がすべて正なら、既約性から $P$ の各列に正の成分があるので、$P^{k+1}=P^kP$ の成分もすべて正になる。$p^{(k)}_{ii}>0$ かつ $p^{(k+1)}_{ii}>0$ なので、周期は $k$ と $k+1$ の公約数、すなわち $1$ である。

  2. 既約性を外す：確率漸化式と定常分布 の記事の例「反例：定常分布が一つでない連鎖」の 3 状態の連鎖（状態 $1,2$ が吸収状態で、状態 $3$ からは確率 $\frac12$ ずつで $1$ か $2$ へ移る）では、$(1,0,0)$ も $(0,1,0)$ も定常分布である。状態 $1$ から $2$ へ到達できないので既約でない。有限なので定常分布は存在するが（thm-markov-chain-existence）、ただ 1 つではない。
  3. 状態を無限個にする：$S=\mathbb{Z}$ で $p_{i,i+1}=p_{i,i-1}=\frac12$ とする。この連鎖は既約である。定常分布 $\pi$ があるとすると、$\pi_j=\frac12(\pi_{j-1}+\pi_{j+1})$ から $\pi_{j+1}-\pi_j=\pi_j-\pi_{j-1}$ がすべての $j$ で成り立つので、差は定数 $d$ で $\pi_j=\pi_0+jd$ である。すべての $j\in\mathbb{Z}$ で $\pi_j\ge0$ なので（$j\to\pm\infty$ を考えて）$d=0$ であり、$\pi$ は定数となる。定数の列の和は $0$ か $+\infty$ で $1$ にならないので、定常分布は存在しない。「既約である」を満たし「定常分布をもつ」を満たさず、thm-markov-chain-existence から有限性を外すと結論が破れる。
  4. 状態をまとめる：$S=\{1,2,3\}$ で $1\to2\to3\to1$ と確率 $1$ で巡回する連鎖を、初期分布 $\bigl(\frac13,\frac13,\frac13\bigr)$ で考え、$Y_n:=a$（$X_n=1$ のとき）、$Y_n:=b$（$X_n\in\{2,3\}$ のとき）とおく。$\Pr(Y_0=a,Y_1=b)=\Pr(X_0=1)=\frac13$、$\Pr(Y_0=b,Y_1=b)=\Pr(X_0=2)=\frac13$ はどちらも正で、
    $$ \Pr(Y_2=a\mid Y_0=a,Y_1=b)=0,\qquad\Pr(Y_2=a\mid Y_0=b,Y_1=b)=1 $$
    である（前者では $X_1=2$ なので $X_2=3$、後者では $X_1=3$ なので $X_2=1$）。現在の値 $Y_1=b$ が同じでも、次に $a$ になる確率が過去の値によって違うので、$(Y_n)$ はどんな推移行列についても def-markov-chain の条件 (ii) を満たさない。Markov 連鎖の関数は Markov 連鎖とは限らない。

補足

より一般の設定

推移確率が時刻 $n$ によってよい連鎖（時間的に一様でない Markov 連鎖）、時刻が連続な過程、状態空間が $\mathbb{R}$ のような非可算集合の過程も、「現在が与えられれば未来は過去によらない」という同じ考え方で定義される。これらには測度論的な条件付き期待値が必要になり、この記事の範囲を超える。
既約な有限連鎖では、周期があっても、状態 $j$ にいた時間の割合が定常分布の成分 $\pi_j$ に確率の意味で近づく（GS06 Theorem 11.12。同書では証明していない）。これは独立な試行についての大数の法則（大数の法則とさいころの平均）の、Markov 連鎖への一般化である。

文献

GS06 第 11 章は有限の Markov 連鎖を扱う。thm-markov-chain-irreducible は、同書が正則な連鎖に帰着させて示している Theorem 11.10 を、最小の比をとる方法で直接示したものである。

定理・例の所在を開く

$P^n$ の成分が $n$ 歩の推移確率であること（Theorem 11.1、p. 407）、分布が $\mu P^n$ であること（Theorem 11.2、p. 409）、Ehrenfest の壺（Example 11.8、p. 410。既約だが正則でない例として Example 11.17、p. 433）、吸収的な連鎖の定義（Definition 11.1、p. 416）、吸収される確率が $1$ であること（Theorem 11.3、p. 417）、基本行列（Theorem 11.4、p. 418）、吸収までの時間（Theorem 11.5、p. 419）、吸収確率（Theorem 11.6、p. 420）、既約（同書では ergodic）と正則の定義（Definition 11.4・11.5、p. 433）、正則な連鎖の収束（Theorem 11.7、p. 434）、既約な連鎖の定常分布の一意性と正であること（Theorem 11.10、p. 438）がある。

関連項目

参考文献

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

Mathpediaを支援する
Markov連鎖