一次ステップ解析

方程式を満たすこと。 出発点で分ける。

• $i\in A$ なら $\tau_A=0$ である。よって $h_i=1$ である。
• $i\notin A$ なら $\tau_A\ge1$ である。到達が起きるのは、時刻 1 以降に $A$ に入るときである。

時刻 1 でのマルコフ性から

$$P_i(\tau_A<\infty\mid X_1=j)=P_j(\tau_A<\infty)=h_j$$

なので、全確率の公式から

$$h_i=\sum_jP_i(X_1=j)\,P_i(\tau_A<\infty\mid X_1=j)=\sum_jp_{ij}h_j$$

となる。

最小であること。 $x$ を (15.15) の非負解とする。すべての $n\ge0$ と状態について

$$x_i\ge P_i(\tau_A\le n)\tag{15.16}$$

を $n$ についての帰納法で示す。

1. $n=0$ のとき。 右辺は、目標の中では $1=x_i$、外では $0\le x_i$ である。
2. $n$ から $n+1$ へ。 $A$ の中では右辺は $1=x_i$ である。$A$ の外では、1歩目で分けて

$$x_i=\sum_jp_{ij}x_j\ge\sum_jp_{ij}P_j(\tau_A\le n)=P_i(\tau_A\le n+1)$$

となる（最後の等号は時刻 1 でのマルコフ性）。よって $n+1$ でも成り立つ。$n\to\infty$ とすると、確率の下からの連続性から

$$P_i(\tau_A\le n)\uparrow P_i(\tau_A<\infty)=h_i$$

なので、$x_i\ge h_i$ である。

方程式を満たすこと。 $i\notin A$ なら $\tau_A\ge1$ である。到達時間は、$X_1$ から出発し直した到達時間に 1 を足したものである。マルコフ性から

$$E_i[\tau_A\mid X_1=j]=1+k_j\qquad(j\in A \text{ なら } k_j=0)$$

なので

$$k_i=\sum_jp_{ij}(1+k_j)=1+\sum_{j\notin A}p_{ij}k_j$$

である。

最小であること。 $y$ を (15.17) の非負解とする。$A$ の外の $i$ について、方程式を繰り返し代入すると

$$\begin{aligned}y_i&=1+\sum_{j_1\notin A}p_{ij_1}y_{j_1} =1+\sum_{j_1\notin A}p_{ij_1}+\sum_{j_1,j_2\notin A}p_{ij_1}p_{j_1j_2}y_{j_2}\\ &=P_i(\tau_A\ge1)+P_i(\tau_A\ge2)+\sum_{j_1,j_2\notin A}p_{ij_1}p_{j_1j_2}y_{j_2}\end{aligned}$$

となる。$P_i(\tau_A\ge m+1)$ は、時刻 1 から $m$ までずっと目標の外にいる確率である。よって

$$P_i(\tau_A\ge m+1)=\sum_{j_1,\dots,j_m\notin A}p_{ij_1}\cdots p_{j_{m-1}j_m}$$

である。$n$ 回代入して、非負の最後の項を捨てると

$$y_i\ge\sum_{m=1}^nP_i(\tau_A\ge m)$$

である。$n\to\infty$ とすると、右辺は

$$\sum_{m\ge1}P_i(\tau_A\ge m)=E_i[\tau_A]=k_i$$

に収束する。

$S\setminus A$ の状態はすべて、§15.1 の意味で過渡的である。実際、目標の外の各状態 $i$ には、$A$ に到達する経路がある。その確率を $\alpha_i>0$、長さを $m_i$ とする。そして

$$\alpha=\min_{i\notin A}\alpha_i,\qquad m=\max_{i\notin A}m_i$$

と置く。目標の外のどこから出発しても、$m$ ステップ以内に目標に入る確率は $\alpha$ 以上である。マルコフ性を $m$ ステップごとに使うと、次の評価を得る。

$$\begin{aligned}P_i(\tau_A>\ell m)&\le(1-\alpha)^\ell\\ (Q^n)_{ij}&\le P_i(\tau_A>n)\ \to\ 0\end{aligned}$$

よって $Q^n\to0$ で、$\sum_nQ^n$ は収束する。さらに

$$(I-Q)\sum_{n=0}^NQ^n=I-Q^{N+1}\to I$$

から、$I-Q$ は正則で $(I-Q)^{-1}=\sum_nQ^n$ である。

• $k$ の一意性。 (15.17) の $A$ の外の部分は $(I-Q)k=\mathbf 1$ と書ける。よって解は $k=(I-Q)^{-1}\mathbf 1$ ただ1つである。
• $h$ の一意性。 (15.15) の2つの有界な解の差を $u$ とする。目標の外で $u=Qu$ を満たすので、$u=Q^nu\to0$ となる。よって解はただ1つである。

平均到達時間が有限であることも、上の評価から出る。

$$E_i[\tau_A]=\sum_mP_i(\tau_A\ge m)\le\sum_\ell m(1-\alpha)^\ell<\infty$$

(1) 吸収状態 $a$ に吸収されるのは、ある時刻に過渡的な状態 $j$ にいて、次の1歩でそこへ移るときである。この事象は時刻と $j$ について排反なので、確率は

$$\sum_n\sum_{j\in T}(Q^n)_{ij}R_{ja}=(NR)_{ia}$$

である。

(2) 吸収までの時間は、過渡的な状態に滞在する回数の合計 $\sum_{j\in T}N_j$ である。よって期待値は

$$\sum_{j\in T}N_{ij}=(N\mathbf 1)_i$$

である。

状態は有限で、内部のどの状態からも 0 に到達できるので、命題 15.12 から、方程式の有界な解がただ1つあり、それが求める量である。

$u_i$。 方程式は次のとおりである。

$$u_0=0,\qquad u_N=1,\qquad u_i=pu_{i+1}+qu_{i-1}\quad(1\le i\le N-1)$$

$p+q=1$ を使って $u_i=(p+q)u_i$ と書き直すと

$$p(u_{i+1}-u_i)=q(u_i-u_{i-1}),\qquad\text{すなわち}\qquad u_{i+1}-u_i=r\,(u_i-u_{i-1})$$

となる。$c=u_1-u_0=u_1$ と置くと、差は $u_{i+1}-u_i=r^ic$ である。足し合わせて

$$u_i=c\,(1+r+\cdots+r^{i-1})=\begin{cases}c\,\dfrac{1-r^i}{1-r}&(r\ne1),\\[6pt] c\,i&(r=1)\end{cases}$$

である。$u_N=1$ から $c$ を決めると (15.20) を得る。

$D_i$。 方程式は次のとおりである。

$$D_0=D_N=0,\qquad D_i=1+pD_{i+1}+qD_{i-1}$$

$p=q=\frac12$ のとき、$D_i=i(N-i)$ を入れると

$$1+\tfrac12\bigl[(i+1)(N-i-1)+(i-1)(N-i+1)\bigr]=1+\tfrac12\bigl[2i(N-i)-2\bigr]=i(N-i)$$

で方程式を満たし、境界条件も満たす。$p\ne q$ のときは、特殊解として $D_i=i/(q-p)$ を試す。

$$1+\frac{p(i+1)+q(i-1)}{q-p}=1+\frac{i-(q-p)}{q-p}=\frac{i}{q-p}$$

で方程式を満たす。斉次方程式 $D_i=pD_{i+1}+qD_{i-1}$ の解は、$u_i$ の計算と同じ形をしている。よって一般解は

$$D_i=\frac{i}{q-p}+\alpha+\beta r^i$$

である。境界条件から定数を決める。

$$\begin{aligned}D_0=0&\ \Longrightarrow\ \beta=-\alpha\\ D_N=0&\ \Longrightarrow\ \alpha(1-r^N)=-\frac{N}{q-p}\end{aligned}$$

これで (15.22) を得る。