到達可能性・既約性・閉集合・周期

確率論入門　第14章 §14.5　★★★ 状態空間を「行き来できる」関係でクラスに分け、出られない集合と戻る歩数の周期を見る

到達可能性と連結

マルコフ連鎖が長い時間のあとにどう振る舞うかは、どの状態からどの状態へ行けるかという、遷移確率の正負の模様でかなりの部分が決まる。この節ではその模様を整理する。

$p^{(0)}_{ii}=1$ なので、どの状態も自分自身に到達可能である。$n\ge1$ では

$$p^{(n)}_{ij}=\sum_{i_1,\dots,i_{n-1}}p_{ii_1}p_{i_1i_2}\cdots p_{i_{n-1}j}$$

で、非負の項の和が正であることは、正の遷移確率だけをたどる経路 $i\to i_1\to\cdots\to j$ が1本はあることと同値である。

状態を頂点とし、$p_{ij}>0$ のときに矢印を引いた有向グラフを遷移図と呼ぶ。遷移図の上で、$i\to j$ は「矢印をたどって行ける」ことを意味する。

到達時刻 $T_j=\inf\{n\ge1:X_n=j\}$（命題 14.6）を使うと、$j\ne i$ のとき

$$i\to j\iff P_i(T_j<\infty)>0\tag{14.14}$$

である。事象 $\{T_j<\infty\}$ は $\bigcup_{n\ge1}\{X_n=j\}$ に等しい。可算和の確率が正であることは、どれかの項の確率が正であることと同値である。つまりある $n$ で $p^{(n)}_{ij}>0$ となることと同値である。

証明

反射律 $i\leftrightarrow i$ は $p^{(0)}_{ii}=1$ から、対称律は定義から明らかである。推移律を示すには、次を示せばよい。

$$i\to k\ \text{かつ}\ k\to j\ \Longrightarrow\ i\to j$$

$p^{(m)}_{ik}>0$、$p^{(n)}_{kj}>0$ とすると、(14.13) から次が成り立つ。

$$p^{(m+n)}_{ij}\ge p^{(m)}_{ik}p^{(n)}_{kj}>0$$

この結果を両向きに使えば、連結の推移律が出る。

ランダムウォーク（$0<p<1$）と Ehrenfest の壺は既約である。ギャンブラーの破産（$0<p<1$、$M\ge2$）は、次の3つのクラスに分かれる。

$$\{0\},\qquad\{M\},\qquad\{1,\dots,M-1\}$$

両端の 0 と $M$ からはどこへも出られない。中間の状態からは、両端のどちらにも行ける。

閉集合

証明

後者を仮定する。$i\in C$、$j\notin C$ について次が成り立つ。

$$p_{ij}=P_i(X_1=j)\le P_i(X_1\notin C)=0$$

逆に $C$ が閉じているとし、$i\in C$ をとる。$P_i(X_n\in C)=1$ を時刻についての帰納法で示す。$n=0$ は明らかである。$P_i(X_n\in C)=1$ なら

$$P_i(X_{n+1}\notin C)=\sum_{k\in C}P_i(X_n=k)\sum_{j\notin C}p_{kj}=0.$$

したがって $P_i(X_{n+1}\in C)=1$ である。可算個の確率 1 の事象の共通部分は確率 1 なので（第1章 §1.4）、すべての $n$ で $X_n\in C$ となる確率も 1 である。

閉じた集合 $C$ の上では、遷移確率行列をその集合に制限した行列も確率行列になる（各行の和が 1）。したがって $C$ だけを状態空間とする連鎖と見ることができる。

クラスについては、閉じていることが到達可能性で言い換えられる。クラス $C$ が閉じていないとは、その中の状態 $i$ と外の状態で、次を満たすものがあることである。

$$p_{ij}>0$$

このとき $j\to i$ は成り立たない。成り立てば $j$ も同じクラスに入るからである。

つまり閉じていないクラスからは、二度と戻れない所へ正の確率で出ていく。第15章 §15.1 では、閉じていないクラスの状態が過渡的（いずれ戻らなくなる）であることを示す。

証明

2つのクラスについて、一方のある状態から他方のある状態に到達可能なとき、$C\preceq C'$ と書く。推移律（命題 14.27 の証明）から、これは代表元の選び方によらない。

1. 任意のクラス $C_1$ から出発する。閉じていなければ、その外の状態 $j$ へ1歩で行ける。$j$ のクラスを $C_2$ とする。これは出発したクラスから到達可能で、それとは異なる。
2. $C_2$ が閉じていなければ同様に $C_3$ をとり、これを続ける。
3. 同じクラスが2度現れることはない。もし $C_k=C_l$（$k<l$）なら、次の鎖ができる。

$$C_k\preceq C_{k+1}\preceq\cdots\preceq C_l=C_k$$

このとき隣り合う2つのクラスの状態は互いに到達可能になり、同じクラスになってしまう。4. クラスは有限個しかないので、この列は有限回で止まる。最後のクラスは閉じている。

無限の状態空間では閉じたクラスが無いこともある。$S=\mathbb{N}_0$ で $p_{i,i+1}=1$（必ず右へ1つ進む）とすると、各状態が単独でクラスをなし、どのクラスも閉じていない。

周期

対称単純ランダムウォークは、偶数歩でしか出発点に戻れない。このような戻りの歩数の規則性を周期として定める。

$p_{ii}>0$ なら $1\in A_i$ なので、その状態は非周期的である。周期が $d$ のとき、戻りは $d$ の倍数の歩数でしか起きない。しかし $d$ の倍数の歩数すべてで戻れるとは限らない。たとえば $A_i=\{4,6,8,10,\dots\}$ なら $d(i)=2$ だが、2 歩では戻れない。

証明

$i=j$ なら明らかなので $i\ne j$ とする。次を満たす $a,b\ge1$ をとる。

$$p^{(a)}_{ij}>0,\qquad p^{(b)}_{ji}>0$$

(14.13) から $p^{(a+b)}_{ii}\ge p^{(a)}_{ij}p^{(b)}_{ji}>0$ である。したがって $a+b\in A_i$ であり、$d(i)$ はこの和を割り切る。次に $n\in A_j$ を任意にとる。(14.13) を2回使うと

$$p^{(a+n+b)}_{ii}\ge p^{(a)}_{ij}\,p^{(n)}_{jj}\,p^{(b)}_{ji}>0$$

なので $a+n+b\in A_i$ で、$d(i)$ はこの数を割り切る。$a+b$ も割り切るので、差の $n$ も割り切る。

したがって $d(i)$ は、集合 $A_j$ のすべての元の公約数である。よって $d(i)\mid d(j)$ である。2つの状態の役割を入れ替えると $d(j)\mid d(i)$ となる。したがって $d(i)=d(j)$ を得る。

この定理から、既約な連鎖ではすべての状態の周期が等しい。それを連鎖の周期と呼び、周期 1 の既約な連鎖を非周期的な連鎖と呼ぶ。

非周期的であることの使い道は、次の数論の補題を通して現れる。

証明

$A$ の元の最大公約数は、有限個の元 $a_1,\dots,a_r\in A$ の最大公約数として実現される。最大公約数は元を加えるたびに減るか変わらないかで、正の整数なので有限回で止まるからである。

Bézout の等式から、整数 $c_1,\dots,c_r$ で $\sum_lc_la_l=1$ となるものがある。正の係数の項の和を $Q$ とし、負の係数の項の絶対値の和を $R$ とする。このとき $Q-R=1$ である。

$Q$ は集合の元の正の整数係数の和なので、加法で閉じていることから $A$ に入る。$R$ についても、正なら同じ理由で $A$ に入る。

• $R=0$ のとき。$1=Q\in A$ となり、すべての正の整数が $A$ に入る。
• $R\ge1$ のとき。$n\ge R^2$ を $R$ で割り、商と余りで次のように書く。

$$n=qR+s\qquad(0\le s<R)$$

$q\ge R>s$ なので

$$n=qR+s(Q-R)=(q-s)R+sQ,\qquad q-s\ge1,\ s\ge0$$

と書ける。右辺は $A$ の元の正の整数係数の和なので $n\in A$ である。$n_0=R^2$ とすればよい。

証明

(i) $A_i$ は (14.13) から加法で閉じている（$p^{(m+n)}_{ii}\ge p^{(m)}_{ii}p^{(n)}_{ii}>0$）。補題 14.34 を使えばよい。(ii) 各状態 $i$ に (i) の $n_0(i)$ をとる。各組 $(i,j)$ に、$p^{(m_{ij})}_{ij}>0$ となる歩数をとる。$n\ge n_0(i)$ なら

$$p^{(n+m_{ij})}_{ij}\ge p^{(n)}_{ii}\,p^{(m_{ij})}_{ij}>0$$

である。そこで次のように置く。

$$N=\max_i n_0(i)+\max_{i,j}m_{ij}$$

$n\ge N$ なら $n-m_{ij}\ge n_0(i)$ となるので、すべての成分が正である。状態が有限個なので最大値は有限である。

周期 $d\ge2$ の既約な連鎖では、状態空間が組 $G_0,G_1,\dots,G_{d-1}$ に分かれる（主張と筋）。連鎖は次のように巡回的に移る。

$$G_0\to G_1\to\cdots\to G_{d-1}\to G_0$$

組の分け方は次のとおりである。状態 $i_0$ を1つ固定する。$p^{(n)}_{i_0j}>0$ となる歩数を周期で割った余りは、行き先の状態ごとに一意に定まる。その余りで組を分ける。

このとき $P^d$ を各 $G_r$ に制限した連鎖は非周期的になる。第15章 §15.3 では、周期を持つ連鎖の $P^n$ が収束しないことを述べる。収束するのは $d$ ステップおきの $p^{(nd)}_{jj}$ だけであり、この分解がその理由である。

確認テスト

オリジナル

1. 14.5-1 状態 $i$ が吸収状態であることと、$\{i\}$ が1つのクラスで、かつ閉じていることが同値であることを示せ。
2. 14.5-2 $S=\{1,2,3,4\}$ 上の連鎖で、正の遷移確率が次のものだけであるとする。

$$p_{12}=1,\qquad p_{21}=p_{23}=p_{24}=\tfrac13,\qquad p_{34}=1,\qquad p_{43}=1$$

クラスに分け、閉じているかと周期を答えよ。3. 14.5-3 次の既約な連鎖の周期を求めよ。

1. (a) 遷移図が $1\to2\to3\to1$ と $1\to4\to1$ の2つの閉路からなる連鎖。
2. (b) 遷移図が $1\to2\to1$ と $1\to3\to4\to5\to1$ の2つの閉路からなる連鎖。
3. 14.5-4 長さ $m\ge3$ の円周の上を、1歩ずつ左右に動く連鎖を考える。状態空間は $S=\{0,1,\dots,m-1\}$ で、$0<p<1$ について

$$p_{i,i+1\bmod m}=p,\qquad p_{i,i-1\bmod m}=1-p$$

とする。この連鎖の周期を、$m$ の偶奇で分けて求めよ。5. 14.5-5 球が4個の Ehrenfest の壺（$M=4$）が既約で周期 2 であることを示せ。また $p^{(2)}_{00}$ と $p^{(4)}_{00}$ を求めよ。