再帰と過渡

確率論入門　第15章 §15.1　★★★ 出発点に確率1で戻る状態が再帰的、戻らない可能性のある状態が過渡的で、遷移確率の和が発散するかどうかで判定できる

第14章では、マルコフ連鎖を遷移確率行列で記述し、$n$ ステップの遷移確率を行列の積で計算する方法を整えた。この章では、時刻 $n$ を大きくしたときの連鎖の振る舞いを調べる。問いは次の4つに分かれる。

1. 出発点に戻ってくるか（§15.1）。戻ってくる確率が 1 の状態を再帰的、1 未満の状態を過渡的と呼び、遷移確率の和（Green 関数）で判定する。1次元・2次元の対称なランダムウォークは再帰的で、3次元では過渡的になる。第7章 確認テスト 7.4-5 で前提にした「対称な単純ランダムウォークはいつか必ず $+1$ に達する」もこの節で示す。
2. どこに吸収されるか、いつ吸収されるか（§15.2）。最初の1歩で場合を分けると、吸収確率と平均到達時間が連立1次方程式の解として得られる。
3. 分布はどこへ落ち着くか（§15.3）。既約で正再帰的な連鎖には定常分布がただ1つあり、その値は平均再帰時間の逆数である。周期が 1 なら、$n$ ステップの遷移確率は定常分布に収束する。
4. 時間平均は何に収束するか（§15.4）。1本の見本路に沿った時間平均が、定常分布による平均にほとんど確実に収束する（エルゴード定理）。証明には、再生過程と再生報酬定理を使う。

§15.5 では、これらの結果の応用として、目的の分布からの標本をマルコフ連鎖で作る方法（MCMC と Metropolis 法）と、大きな状態空間をもつ連鎖を1次元の連鎖へ還元する方法を扱う。

第14章から借りる定義と結果

状態空間 $S$ は有限または可算の集合とする。$(X_n)_{n\ge0}$ は遷移確率行列

$$P=(p_{ij})_{i,j\in S}$$

をもつマルコフ連鎖とする。すなわち、すべての $n$ と状態の列について

$$P(X_{n+1}=j\mid X_0=i_0,\dots,X_{n-1}=i_{n-1},X_n=i)=p_{ij}\tag{15.1}$$

が成り立つ（条件の確率が正のとき）。出発点を $X_0=i$ とした確率を $P_i$ と書く。その期待値は $E_i$ と書く。初期分布が $\mu$ のときは $P_\mu$ と書く。

$n$ ステップの遷移確率を $p^{(n)}_{ij}=P_i(X_n=j)$ と書く。これは行列 $P^n$ の成分に等しい。これは Chapman–Kolmogorov 方程式

$$p^{(m+n)}_{ij}=\sum_{k\in S}p^{(m)}_{ik}\,p^{(n)}_{kj},\qquad p^{(m+n)}_{ij}\ge p^{(m)}_{ik}\,p^{(n)}_{kj}\tag{15.2}$$

を満たす（$p^{(0)}_{ij}=\delta_{ij}$）。自然なフィルトレーションは $\mathcal F_n=\sigma(X_0,\dots,X_n)$ である。集合 $A\subset S$ への到達時刻を、時刻 0 を数えるものと数えないものの2種類で

$$\tau_A=\inf\{n\ge0:X_n\in A\},\qquad T_A=\inf\{n\ge1:X_n\in A\},\qquad T_j=T_{\{j\}}\tag{15.3}$$

と書く（$\inf\emptyset=\infty$）。どちらも停止時刻である（第14章 §14.1）。

第14章 §14.4 の強マルコフ性を次の形で使う。$\tau$ を停止時刻とする。事象 $A$ は、すべての $m\ge0$ で

$$A\cap\{\tau=m\}\in\mathcal F_m$$

を満たすとする。このとき

$$P\bigl(A,\ \tau<\infty,\ X_\tau=i,\ X_{\tau+1}=j_1,\dots,X_{\tau+n}=j_n\bigr)=P(A,\ \tau<\infty,\ X_\tau=i)\,P_i(X_1=j_1,\dots,X_n=j_n)\tag{15.4}$$

が成り立つ。言葉で言えば、停止時刻で連鎖を切ると、その後は $X_\tau$ から出発した新しい連鎖と同じ法則に従い、それまでの経路と独立である。

第14章 §14.5 の状態の分類を、式の形で書いておく。

• 次の条件を満たすとき、$j$ は $i$ から到達可能であるという。

$$\text{ある } n\ge0 \text{ で } p^{(n)}_{ij}>0$$

これを $i\to j$ と書く。両向きに到達可能な2つの状態は連絡するといい、$i\leftrightarrow j$ と書く。$\leftrightarrow$ は同値関係で、その同値類をクラスと呼ぶ。

• クラスが1つだけのとき、連鎖は既約であるという。集合 $C\subset S$ から出る遷移が無い、すなわち

$$i\in C,\ p_{ij}>0\ \Longrightarrow\ j\in C$$

を満たすとき、$C$ は閉じているという。

• 状態 $i$ の周期を $d(i)=\gcd\{n\ge1:p^{(n)}_{ii}>0\}$ で定める。$d(i)=1$ の状態を非周期的と呼ぶ。同じクラスの状態は同じ周期をもつ。

この章の結果のうち、全変動距離による収束（§15.3）には第5章 §5.5 の全変動距離

$$d_{\mathrm{TV}}(\mu,\nu)=\frac12\sum_j\left\vert \mu_j-\nu_j\right\vert$$

を使う。エルゴード定理（§15.4）には第12章 §12.2 の Kolmogorov の強法則を使う。これは、独立同分布で $E\left\vert X_1\right\vert <\infty$ なら標本平均が $E[X_1]$ にほとんど確実に収束する、という定理である。ランダムウォークの計算では、第8章 §8.1 の確率母関数の考え方を使う。

初到達の確率と分解公式

状態 $i$ から出発して状態 $j$ をめざす。時刻 $n$ に初めて達する確率を $f^{(n)}_{ij}$ と書く。いつか達する確率を $f_{ij}$ と書く。式では

$$f^{(n)}_{ij}=P_i(T_j=n),\qquad f_{ij}=P_i(T_j<\infty)=\sum_{n=1}^\infty f^{(n)}_{ij}\tag{15.5}$$

である。$i=j$ の場合の $f_{jj}$ は「出発点をいったん出たあと、そこへ戻ってくる確率」である。

時刻 $n$ に $j$ にいるという事象を、初めてそこに達した時刻で分ける。初めて達したあとは $j$ から出発し直すので、次の分解が成り立つ。

証明

$X_n=j$ なら $T_j\le n$ なので、次は排反な和である。

$$\{X_n=j\}=\bigcup_{m=1}^n\{T_j=m,\ X_n=j\}$$

事象 $\{T_j=m\}=\{X_1\ne j,\dots,X_{m-1}\ne j,\ X_m=j\}$ は $\mathcal F_m$ に属する。その上では $X_m=j$ である。定まった時刻 $m$ でのマルコフ性（第14章 §14.4）から

$$P_i(T_j=m,\ X_n=j)=P_i(T_j=m)\,P_j(X_{n-m}=j)=f^{(m)}_{ij}\,p^{(n-m)}_{jj}$$

となる。$m=1,\dots,n$ について足せば (15.6) を得る。

(15.6) は畳み込みの形をしているので、母関数に移ると積になる。$\left\vert s\right\vert <1$ について

$$P_{ij}(s)=\sum_{n=0}^\infty p^{(n)}_{ij}s^n,\qquad F_{ij}(s)=\sum_{n=1}^\infty f^{(n)}_{ij}s^n\tag{15.7}$$

と置く。どちらの係数も $[0,1]$ に入るので、級数は $\left\vert s\right\vert <1$ で絶対収束する。(15.6) の両辺に $s^n$ を掛けて $n\ge1$ で足す。$n=0$ の項 $p^{(0)}_{ij}=\delta_{ij}$ を補うと

$$P_{jj}(s)=1+F_{jj}(s)\,P_{jj}(s),\qquad P_{ij}(s)=F_{ij}(s)\,P_{jj}(s)\quad(i\ne j)\tag{15.8}$$

を得る。前者を解くと

$$P_{jj}(s)=\frac{1}{1-F_{jj}(s)}$$

である。

再帰と過渡の定義と Green 関数

$j$ を訪れる回数を、時刻 0 も数えて

$$N_j=\sum_{n=0}^\infty\mathbf 1_{\{X_n=j\}}$$

と置く。その期待値

$$G(i,j)=E_i[N_j]=\sum_{n=0}^\infty p^{(n)}_{ij}\tag{15.9}$$

を Green 関数と呼ぶ。2つ目の等号は、非負の項の和と期待値の交換（第5章 §5.2 の単調収束定理）による。

証明

(1) $k$ 回目の滞在の時刻を $\sigma_k$ と置く。$\sigma_1=0$ である。$k$ 回目が無ければ $\sigma_k=\infty$ とする。

$\sigma_k$ は停止時刻で、$\{N_j\ge k\}=\{\sigma_k<\infty\}$ である。$\sigma_k<\infty$ のとき $X_{\sigma_k}=j$ である。$k+1$ 回目の滞在が起きるのは、時刻 $\sigma_k$ のあとに再び戻ってくるときである。強マルコフ性 (15.4) を $\tau=\sigma_k$、$A=\Omega$ で使い、その後の経路について和をとると

$$P_j(N_j\ge k+1)=P_j(\sigma_k<\infty)\,P_j(T_j<\infty)=P_j(N_j\ge k)\,f_{jj}$$

を得る。$P_j(N_j\ge1)=1$ から帰納法で $P_j(N_j\ge k)=f_{jj}^{\,k-1}$ である。

(2) $f_{jj}=1$ なら、(1) から $P_j(N_j\ge k)=1$ がどの回数でも成り立つ。確率の上からの連続性（第1章 §1.4）により

$$P_j(N_j=\infty)=\lim_kP_j(N_j\ge k)=1$$

である。したがって $G(j,j)=E_j[N_j]=\infty$ である。

(3) $f_{jj}<1$ なら

$$P_j(N_j=k)=f_{jj}^{\,k-1}-f_{jj}^{\,k}=f_{jj}^{\,k-1}(1-f_{jj})$$

で、これは幾何分布である。非負整数値の確率変数の期待値は $E[N]=\sum_{k\ge1}P(N\ge k)$ で計算できるので

$$G(j,j)=\sum_{k=1}^\infty f_{jj}^{\,k-1}=\frac{1}{1-f_{jj}}$$

である。最後の主張を示す。$i\ne j$ とする。$j$ への訪問は事象 $\{T_j<\infty\}$ の上でだけ起きる。$T_j$ 以後は $j$ から出発し直すので

$$E_i[N_j]=P_i(T_j<\infty)\,E_j[N_j]$$

となる。

(15.8) から同じ結論を得ることもできる。$s\uparrow1$ とすると、単調収束定理により

$$P_{jj}(s)\uparrow G(j,j),\qquad F_{jj}(s)\uparrow f_{jj}$$

なので、$G(j,j)=1/(1-f_{jj})$ である。$f_{jj}=1$ なら右辺は $\infty$ と読む。

クラスの性質

証明

$i\leftrightarrow j$ なので、ある $a,b\ge0$ で

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

となる。(15.2) の不等式を2回使うと、すべての $n$ で

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

である。$n$ について足す。右辺は正の定数 $p^{(a)}_{ji}p^{(b)}_{ij}$ と、発散する級数 $\sum_np^{(n)}_{ii}$ の積なので発散する。よって $\sum_np^{(n)}_{jj}=\infty$ となり、定理 15.3 から $j$ は再帰的である。

証明

$j=i$ なら明らかなので $j\ne i$ とする。

$i\to j$ なので、出発点から出て、途中で出発点を通らずに $j$ に達する経路が正の確率で存在する。実際、$p^{(n)}_{ij}>0$ となる経路をとり、最後に $i$ を通った時刻より後の部分を使えばよい。この経路の確率を $\alpha>0$ とする。この経路で $j$ に達し、そのあと二度と出発点に戻らなければ、$i$ への戻りは起きない。強マルコフ性から

$$1-f_{ii}=P_i(T_i=\infty)\ge\alpha\,(1-f_{ji})$$

である。$f_{ii}=1$ なので左辺は 0 である。$\alpha>0$ から $f_{ji}=1$ を得る。

すると $j\to i$ なので $i\leftrightarrow j$ である。定理 15.4 から $j$ は再帰的である。役割を入れ替えれば $f_{ij}=1$ である。

証明

(1) 再帰的なクラスの状態 $i$ から、1歩で状態 $j$ へ移れるとする。このとき $i\to j$ である。命題 15.5 から $j\to i$ となり、$j\in C$ である。

(2) 有限の閉じたクラス $C$ の状態 $i$ から出発する。連鎖は $C$ を出ないので、訪問回数の合計は

$$\sum_{j\in C}N_j=\infty$$

である。期待値をとると $\sum_{j\in C}G(i,j)=\infty$ となる。$C$ は有限なので、和のどれかの項が発散する。その項を $G(i,j)=\infty$ とする。定理 15.3 から

$$G(j,j)\ge f_{ij}G(j,j)=G(i,j)=\infty$$

なので、$j$ は再帰的である。定理 15.4 からクラス全体が再帰的である。

無限の状態空間では (2) は成り立たない。偏りのあるランダムウォークは既約だが、次の小節で見るようにすべての状態が過渡的である。

1次元のランダムウォーク

$0<p<1$ と $q=1-p$ を使い、整数の上の単純ランダムウォークを

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

で定める。既約で、周期は 2 である。原点に $2n$ ステップで戻るには、右と左を $n$ 回ずつ選べばよいので

$$p^{(2n)}_{00}=\binom{2n}{n}(pq)^n,\qquad p^{(2n+1)}_{00}=0\tag{15.10}$$

である。Stirling の公式 $n!\sim\sqrt{2\pi n}\,(n/\mathrm{e})^n$ を使うと

$$\binom{2n}{n}\sim \frac{4^n}{\sqrt{\pi n}},\qquad p^{(2n)}_{00}\sim\frac{(4pq)^n}{\sqrt{\pi n}}.$$

ここで $4pq=1-(p-q)^2\le1$ で、等号は $p=q=\frac12$ のときだけである。

• $p\ne\frac12$ なら、級数は等比級数で抑えられて収束する。
• $p=\frac12$ なら、$\sum n^{-1/2}=\infty$ で発散する。

よって次が分かる。

証明

前半は上で示した。母関数には二項級数

$$(1-x)^{-1/2}=\sum_n\binom{2n}{n}\Bigl(\frac x4\Bigr)^n\qquad(\left\vert x\right\vert <1)$$

を使う。$x=4pqs^2$ を入れれば、(15.10) から $P_{00}$ が得られる。(15.8) から $F_{00}=1-1/P_{00}$ である。$s\uparrow1$ とすると

$$f_{00}=1-\sqrt{1-4pq}=1-\sqrt{(p-q)^2}=1-\left\vert p-q\right\vert$$

となる。

次に、第7章 確認テスト 7.4-5 で前提にした「$+1$ への到達」を示す。

証明

最初の1歩で場合を分ける。

1. 1歩目が右。 $X_1=+1$ なら $T_1=1$ である。
2. 1歩目が左。 $X_1=-1$ なら、まず 0 に戻り、そこから $+1$ に達しなければならない。遷移確率は平行移動で変わらない。よって $-1$ から 0 に達するまでの時間は、$T_1$ と同じ分布をもつ。 0 に戻った時刻は停止時刻である。強マルコフ性 (15.4) により、そこから $+1$ に達するまでの時間は、それまでの時間と独立で、やはり $T_1$ と同じ分布をもつ。

したがって、1歩目が左のとき $T_1$ は $1+T'+T''$ と同じ分布に従う。ここで $T',T''$ は $T_1$ の独立な複製である。母関数で書くと

$$\Phi(s)=ps+qs\,\Phi(s)^2\tag{15.13}$$

を得る。複製のどちらかが $\infty$ なら和も $\infty$ である。これは $s^{\infty}=0$ の読み方と整合する。これは $\Phi$ の2次方程式 $qs\Phi^2-\Phi+ps=0$ で、根は

$$\Phi(s)=\frac{1\pm\sqrt{1-4pqs^2}}{2qs}$$

である。$T_1\ge1$ なので $0\le\Phi(s)\le s$ である。よって $s\downarrow0$ で $\Phi$ は 0 に近づかなければならない。

$+$ の根は $s\downarrow0$ で発散するので、マイナスの根が正しい。これで (15.12) を得る。両辺は $s$ について連続なので、根の選び方は $(0,1)$ 全体で変わらない。

$s\uparrow1$ とすると、単調収束定理により $\Phi(s)\uparrow P_0(T_1<\infty)$ で、

$$P_0(T_1<\infty)=\frac{1-\left\vert p-q\right\vert }{2q} =\begin{cases}\dfrac{2q}{2q}=1&(p\ge q),\\[8pt]\dfrac{2p}{2q}=\dfrac pq&(p<q)\end{cases}$$

となる。平均は $\Phi'(1-)$ である。

$p>q$ のときを考える。(15.13) を微分して、$s=1$ と $\Phi(1)=1$ を入れる。

$$\begin{aligned}\Phi'&=p+q\Phi^2+2qs\Phi\Phi'\\ \Phi'(1)(1-2q)&=p+q=1\end{aligned}$$

$1-2q=p-q$ なので $E_0[T_1]=1/(p-q)$ である。

$p=q=\frac12$ のときは $\Phi(s)=(1-\sqrt{1-s^2})/s$ で、商の微分から

$$\Phi'(s)=\frac{1}{s^2}\Bigl(\frac{s^2}{\sqrt{1-s^2}}-1+\sqrt{1-s^2}\Bigr)\ \longrightarrow\ \infty\qquad(s\uparrow1)$$

となる。単調収束定理から

$$E_0[T_1]=\sum_nnP_0(T_1=n)=\lim_{s\uparrow1}\Phi'(s)=\infty$$

である。

対称な場合の結論は「$+1$ には確率 1 で達するが、達するまでの平均時間は無限大」である。これは第7章 確認テスト 7.4-5 で Wald の等式から導いた $E[N]=\infty$ と一致する。

また、再帰性からも $P_0(T_1<\infty)=1$ が出る。対称なランダムウォークは既約で、原点は再帰的である。よって命題 15.5 から $f_{01}=1$ である。

多次元のランダムウォーク

$\mathbb{Z}^d$ 上の対称な単純ランダムウォークは、各ステップで $2d$ 個の隣の点のどれかへ等確率で移る。2次元と3次元を調べる。

証明

$d=2$。 位置を $(X_n,Y_n)$ とし、座標を45度回して

$$U_n=X_n+Y_n,\qquad V_n=X_n-Y_n$$

と置く。1歩の変位は $(\pm1,0),(0,\pm1)$ の4通りである。これに対応する $(U,V)$ の変位は $(+1,+1),(-1,-1),(+1,-1),(-1,+1)$ で、どれも等確率である。

したがって、新しい2つの座標の変位は、それぞれ等確率で $+1$ か $-1$ をとる。両者は互いに独立である。つまり $U_n$ と $V_n$ は独立な1次元の対称ランダムウォークである。原点に戻るのは $U_{2n}=V_{2n}=0$ のときなので

$$p^{(2n)}_{00}=\Bigl(\binom{2n}{n}2^{-2n}\Bigr)^2\sim\frac{1}{\pi n}.$$

$\sum1/n=\infty$ なので再帰的である。

$d=3$。 $2n$ ステップで原点に戻るのは、3つの軸の正の向きと負の向きを同じ回数ずつ選ぶときである。その回数を軸ごとに $i,j,k$ 回（$i+j+k=n$）とすると

$$p^{(2n)}_{00}=\sum_{i+j+k=n}\frac{(2n)!}{(i!\,j!\,k!)^2}\,6^{-2n} =\binom{2n}{n}2^{-2n}\sum_{i+j+k=n}\Bigl(\frac{n!}{i!\,j!\,k!}3^{-n}\Bigr)^2.$$

和の中の $c_{ijk}=\frac{n!}{i!j!k!}3^{-n}$ は3項分布の確率なので、合計は 1 である。よって

$$\sum c_{ijk}^2\le\max c_{ijk}\sum c_{ijk}=\max c_{ijk}$$

である。3項分布の確率が最大になるのは、3つの回数が $n/3$ に最も近いときである。Stirling の公式から、$n$ によらない定数 $C$ を使って次のように評価できる。

$$\max c_{ijk}\le \frac Cn$$

$\binom{2n}{n}2^{-2n}\le1/\sqrt{n}$ と合わせて

$$p^{(2n)}_{00}\le\frac{C}{n^{3/2}},\qquad\sum_np^{(2n)}_{00}<\infty$$

となり、過渡的である。$d\ge4$ では、最初の3成分に注目した同様の評価で過渡的であることが示せる。

3次元の Green 関数の値は、数値計算で $G(0,0)\approx1.5164$ と求まる。原点に戻る確率は

$$f_{00}=1-\frac1{G(0,0)}\approx0.340$$

である。3次元の対称なランダムウォークは、約 $66\%$ の確率で原点に二度と戻らない。

確認テスト

オリジナル

1. 15.1-1 状態空間が有限のマルコフ連鎖では、すべての状態が過渡的になることはない。その理由を述べよ。
2. 15.1-2 状態空間 $S=\{a,b,c\}$ 上の連鎖を、次の遷移確率で定める。

$$p_{aa}=\tfrac13,\quad p_{ab}=\tfrac23,\quad p_{ba}=\tfrac12,\quad p_{bc}=\tfrac12,\quad p_{cc}=1$$

戻る確率 $f_{aa}$ を求めよ。Green 関数 $G(a,a)$ と $G(a,b)$ を求めよ。また、$a$ から出発して $c$ に吸収されるまでの時間の期待値を求めよ。3. 15.1-3 整数の上の単純ランダムウォークで $p>q$ とする。(15.12) を直接 $s$ で微分して $s\uparrow1$ とせよ。これで $E_0[T_1]=1/(p-q)$ を確かめよ。4. 15.1-4 平面の格子 $\mathbb{Z}^2$ 上の対称な単純ランダムウォークについて、次の2つが等しいことを示せ。

$$p^{(2n)}_{00}=\binom{2n}{n}^24^{-2n},\qquad \sum_{i+j=n}\frac{(2n)!}{(i!\,j!)^2}4^{-2n}$$

恒等式 $\sum_i\binom ni^2=\binom{2n}{n}$ を使ってよい。5. 15.1-5 整数の上で、各ステップで確率 $\frac12$ でその場に留まり、確率 $\frac14$ ずつで左右に1動く連鎖を考える。$p^{(n)}_{00}=\binom{2n}{n}4^{-n}$ を示せ。また原点が再帰的であることを示せ。