確認テストの解答

確率論入門　第15章 §15.7

§15.1 再帰と過渡

1. 15.1-1 すべての状態が過渡的なら、各状態への訪問は確率 1 で有限回である（定理 15.3）。状態が有限個なら、訪問回数の合計も有限になる。しかし連鎖はすべての時刻にどこかの状態にいるので、合計は無限大でなければならず、矛盾する。

式で書けば

$$\sum_{j\in S}G(i,j)=\sum_n\sum_jp^{(n)}_{ij}=\sum_n1=\infty$$

である。状態が有限なら、ある $j$ で $G(i,j)=\infty$ となる。$G(i,j)\le G(j,j)$ から、その状態は再帰的である。2. 15.1-2 $a$ に戻る道は2通りある。1歩目でその場に留まる道と、$b$ に行ってすぐ戻る道である。よって

$$f_{aa}=\tfrac13+\tfrac23\cdot\tfrac12=\tfrac23,\qquad G(a,a)=\frac{1}{1-2/3}=3$$

である。$a$ から出れば、その場に留まり続けない限り必ず $b$ に行く。留まり続ける確率は 0 なので、$f_{ab}=1$ である。$b$ に戻るには $a$ を経由するしかないので

$$f_{bb}=p_{ba}\,f_{ab}=\tfrac12,\qquad G(b,b)=2,\qquad G(a,b)=f_{ab}\,G(b,b)=2$$

である。行列で確かめる。

$$Q=\begin{pmatrix}\frac13&\frac23\\ \frac12&0\end{pmatrix},\qquad \det(I-Q)=\frac23-\frac13=\frac13$$

なので

$$(I-Q)^{-1}=3\begin{pmatrix}1&\frac23\\[2pt]\frac12&\frac23\end{pmatrix}=\begin{pmatrix}3&2\\[2pt]\frac32&2\end{pmatrix}$$

となり一致する。吸収までの時間は、過渡的な2状態に滞在する回数の合計である。よって期待値は $G(a,a)+G(a,b)=3+2=5$ である。3. 15.1-3 根号の部分を $g$ と置く。

$$\Phi(s)=\frac{1-g(s)}{2qs},\qquad g(s)=\sqrt{1-4pqs^2},\qquad g'(s)=-\frac{4pqs}{g(s)}$$

商の微分から

$$\Phi'(s)=\frac{-g'(s)\cdot2qs-(1-g(s))\cdot2q}{4q^2s^2}=\frac{4pqs^2/g(s)-(1-g(s))}{2qs^2}.$$

$p>q$ なら $g(1)=\sqrt{(p-q)^2}=p-q$ である。$s\to1$ とすると

$$\Phi'(1)=\frac{4pq/(p-q)-(1-p+q)}{2q}=\frac{4pq/(p-q)-2q}{2q}=\frac{2p}{p-q}-1=\frac{p+q}{p-q}$$

となり、$p+q=1$ から $E_0[T_1]=1/(p-q)$ である。4. 15.1-4 $2n$ ステップで原点に戻るのは、各軸の正負の向きを同じ回数ずつ選ぶときである。横の軸の回数を $i$、縦の軸の回数を $j$ とする。和は $n$ である。よって

$$p^{(2n)}_{00}=\sum_{i+j=n}\frac{(2n)!}{i!\,i!\,j!\,j!}4^{-2n}=4^{-2n}\binom{2n}{n}\sum_{i=0}^n\Bigl(\frac{n!}{i!\,(n-i)!}\Bigr)^2=4^{-2n}\binom{2n}{n}\sum_i\binom ni^2$$

である。途中で $\frac{(2n)!}{(i!j!)^2}=\binom{2n}{n}\bigl(\frac{n!}{i!j!}\bigr)^2$ を使った。恒等式から最後の和は $\binom{2n}{n}$ なので、$p^{(2n)}_{00}=\binom{2n}{n}^24^{-2n}$ を得る。

恒等式は、$2n$ 個から $n$ 個選ぶ方法を、前半と後半から何個ずつ選ぶかで分けて数えれば従う。前半から $i$ 個選ぶ場合を足すと

$$\binom{2n}{n}=\sum_i\binom ni\binom n{n-i}=\sum_i\binom ni^2$$

となる。5. 15.1-5 1歩の変位 $\eta\in\{-1,0,1\}$ は、独立な2つの Bernoulli($\frac12$) の確率変数を使って

$$\eta=B+B'-1,\qquad P(\eta=1)=\tfrac14,\quad P(\eta=0)=\tfrac12,\quad P(\eta=-1)=\tfrac14$$

と書ける。$n$ 歩後の位置は $\sum(B_k+B'_k)-n$ である。和 $\sum(B_k+B'_k)$ は二項分布 $\mathrm{Bin}(2n,\frac12)$ に従うので

$$p^{(n)}_{00}=P\bigl(\mathrm{Bin}(2n,\tfrac12)=n\bigr)=\binom{2n}{n}4^{-n}\sim\frac{1}{\sqrt{\pi n}}$$

である。$\sum_nn^{-1/2}=\infty$ なので、定理 15.3 から原点は再帰的である。

§15.2 一次ステップ解析

1. 15.2-1 $i\ge1$ で $p\cdot1+q\cdot1=1$ なので、定数 1 は (15.15) を満たす。しかし §15.2 の計算から、最小の非負解は $h_i=(q/p)^i<1$ である。定理 15.10 から、到達確率は最小解の方である。定数 1 は方程式を満たすが、帰納法の評価 (15.16) は $x\ge h$ を与えるだけで、等号を保証しない。状態空間が無限なので、命題 15.12 の一意性も使えない。
2. 15.2-2 公正な場合は、$u_2=2/6=\frac13$ と $D_2=2\cdot4=8$ である。$p=\frac23$ では $r=\frac12$ で

$$u_2=\frac{1-(1/2)^2}{1-(1/2)^6}=\frac{3/4}{63/64}=\frac{48}{63}=\frac{16}{21}\approx0.762$$

である。3. 15.2-3 方程式は次のとおりである。

$$k_N=0,\qquad k_0=1+k_1,\qquad k_i=1+\tfrac12(k_{i-1}+k_{i+1})\quad(1\le i\le N-1)$$

命題 15.12 から、解はただ1つである。$k_i=N^2-i^2$ を入れると

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

で、境界の式 $k_0=1+(N^2-1)=N^2$ と $k_N=0$ も満たす。$N=3$ のときは、方程式を直接解いて確かめる。

$$\begin{aligned}k_0&=1+k_1,\qquad k_1=1+\tfrac12(k_0+k_2),\qquad k_2=1+\tfrac12k_1&&\text{（方程式）}\\ k_1&=1+\tfrac12(1+k_1+k_2)\ \Longrightarrow\ k_1=3+k_2&&\text{（第1式を第2式に代入）}\\ k_2&=1+\tfrac12(3+k_2)\ \Longrightarrow\ k_2=5,\quad k_1=8,\quad k_0=9&&\text{（第3式に代入）}\end{aligned}$$

公式の値 $9-4=5$、$9-1=8$、9 と一致する。4. 15.2-4 過渡的な状態は「進みなし（$s_0$）」「直前が H（$s_1$）」と、もう1つある。それは「直前が HT（$s_2$）」である。吸収状態は「HTH 完成」である。

• 進みなしからは、H で $s_1$ に、T で同じ状態に移る。
• $s_1$ からは、H で同じ状態に留まり（新しい H が先頭になる）、T で $s_2$ に移る。
• $s_2$ からは、H で完成し、T で $s_0$ に戻る（HTT の末尾は HTH の先頭と重ならない）。

各状態からの平均時間を $k_0,k_1,k_2$ とすると

$$k_0=1+\tfrac12(k_1+k_0),\qquad k_1=1+\tfrac12(k_1+k_2),\qquad k_2=1+\tfrac12k_0.$$

順に解く。

$$\begin{aligned}k_0&=2+k_1&&\text{（第1式）}\\ k_1&=2+k_2&&\text{（第2式）}\\ k_0&=4+k_2=5+\tfrac12k_0&&\text{（第3式を代入）}\end{aligned}$$

よって $k_0=10$ である。

§15.3 定常分布と極限定理

1. 15.3-1 $P=I$ の連鎖は状態を動かないので、$1\not\to2$ である。よって既約でない（クラスが2つある）。定理 15.19 は既約な連鎖についての主張なので、矛盾しない。
2. 15.3-2 定常分布と平均再帰時間は

$$\pi=\Bigl(\frac{0.1}{0.4},\frac{0.3}{0.4}\Bigr)=\Bigl(\frac14,\frac34\Bigr),\qquad m_1=\frac1{\pi_1}=4$$

である。ずれは

$$p^{(n)}_{11}-\pi_1=\frac{a}{a+b}(1-a-b)^n=0.75\times0.6^n$$

なので、条件 $0.75\times0.6^n<0.01$ は

$$n>\frac{\log(0.01/0.75)}{\log0.6}\approx8.45$$

と同値である。最小の $n$ は 9 である。実際 $0.75\times0.6^8\approx0.0126$ で、$0.75\times0.6^9\approx0.0076$ である。3. 15.3-3 $\pi P=\pi$ の第0成分は $\pi_0=q\pi_0+q\pi_1$ である。ここから $\pi_1=\frac pq\pi_0$ を得る。$j\ge1$ の成分は $\pi_j=p\pi_{j-1}+q\pi_{j+1}$ である。$r=p/q$ と置き、$\pi_j=r^j\pi_0$ と仮定して次の項を計算する。

$$\begin{aligned}q\pi_{j+1}&=\pi_j-p\pi_{j-1}=(r^j-pr^{j-1})\pi_0=r^{j-1}(r-p)\pi_0\\ r-p&=\frac pq-p=\frac{p(1-q)}{q}=\frac{p^2}{q}\\ \pi_{j+1}&=r^{j-1}\frac{p^2}{q^2}\pi_0=r^{j+1}\pi_0\end{aligned}$$

帰納法から $\pi_j=r^j\pi_0$ である。$r<1$ なので規格化でき、$\pi_j=(1-r)r^j$ である。$p=\frac13$ では $r=\frac12$ である。よって $\pi_0=\frac12$ で、$m_0=1/\pi_0=2$ である。4. 15.3-4 一様分布 $\pi_i=1/\left\vert S\right\vert$ を考える。列の和が 1 なので

$$\sum_i\pi_ip_{ij}=\frac1{\left\vert S\right\vert }\sum_ip_{ij}=\frac1{\left\vert S\right\vert }=\pi_j$$

となり、定常分布である。系 15.20 から定常分布はこれだけである。定理 15.19 から $m_i=1/\pi_i=\left\vert S\right\vert$ である。5. 15.3-5 $n$ ステップ後の位置は、二項分布を平行移動したものである。よって

$$p^{(n)}_{ij}=p^{(n)}_{0,j-i}\le\max_kp^{(n)}_{0k}\le\binom{n}{\lfloor n/2\rfloor}2^{-n}\to0$$

である。定常分布 $\pi$ があるとすると、任意の $n$ で

$$\pi_j=\sum_i\pi_ip^{(n)}_{ij}\le\max_kp^{(n)}_{0k}\sum_i\pi_i=\max_kp^{(n)}_{0k}$$

が成り立つ。$n\to\infty$ とすると $\pi_j=0$ となる。すべての成分が 0 なのは、総和が 1 であることと矛盾する。

§15.4 エルゴード定理と再生報酬

1. 15.4-1 連鎖は既約で有限なので、正再帰的である。エルゴード定理から

$$\frac{V_3(n)}n\to\frac1{m_3}=\pi_3=\frac38\quad\text{a.s.}$$

である。2. 15.4-2 到着間隔を $\xi$ とする。周期の中の時刻 $s\in[0,\xi)$ に来た客の待ち時間は $\xi-s$ である。その積分が1周期の報酬で

$$\int_0^\xi(\xi-s)\,\mathrm{d} s=\frac{\xi^2}2$$

となる。間隔の平均と2乗の平均は

$$E[\xi]=1,\qquad E[\xi^2]=V[\xi]+E[\xi]^2=\frac13+1=\frac43$$

なので、定理 15.24 から長時間平均は

$$\frac{E[\xi^2/2]}{E[\xi]}=\frac{2/3}{1}=\frac23$$

（約 6.7 分）である。平均の到着間隔の半分（5 分）より長い。長い間隔ほどその中に来る客が多いので、客が経験する間隔は平均より長くなる。3. 15.4-3 2状態の公式で $a=0.1$、$b=0.3$ である。よって定常分布は

$$\pi=\Bigl(\frac{0.3}{0.4},\frac{0.1}{0.4}\Bigr)=(0.75,0.25)$$

である。エルゴード定理から、平均利益は $3\times0.75+(-1)\times0.25=2$ である。4. 15.4-4 行列の累乗 $P^n$ は、偶数乗なら単位行列で、奇数乗なら $P$ 自身である。よって $p^{(n)}_{11}$ は $1,0,1,0,\dots$ と振動して収束しない。一方、$\sum_{k<n}p^{(k)}_{11}=\lceil n/2\rceil$ なので

$$\frac1n\Bigl\lceil \frac n2\Bigr\rceil\to\frac12$$

である。これは毎回2歩で戻ること、つまり $m_1=2$ と合う。

一般の場合は、$0\le V_j(n)/n\le1$ なので (15.30) に有界収束定理（第5章 §5.2 の優収束定理）を使えて

$$\frac1n\sum_{k=0}^{n-1}p^{(k)}_{ij}=E_i\Bigl[\frac{V_j(n)}{n}\Bigr]\to\frac1{m_j}$$

である。

§15.5 応用

1. 15.5-1 列の和もすべて 1 なので、確認テスト 15.3-4 から一様分布 $\pi=(\frac13,\frac13,\frac13)$ が定常分布である。しかし $\pi_1p_{12}=\frac13\ne0=\pi_2p_{21}$ なので、詳細つり合いは成り立たない。この連鎖は1つの向きにしか回らず、時間を逆にすると向きが変わるので可逆でない。
2. 15.5-2 重みは $w_k=2^{-k}$ である。上へ移る提案は確率 $w_{k+1}/w_k=\frac12$ で受け入れ、下へ移る提案は必ず受け入れる。よって

$$p_{k,k+1}=\tfrac12\cdot\tfrac12=\tfrac14\ (k=0,1,2),\qquad p_{k,k-1}=\tfrac12\ (k=1,2,3),\qquad p_{00}=\tfrac34,\ p_{11}=p_{22}=\tfrac14,\ p_{33}=\tfrac12$$

である。目標の分布 $\pi=(8,4,2,1)/15$ について

$$\pi_kp_{k,k+1}=\frac{\pi_k}4,\qquad \pi_{k+1}p_{k+1,k}=\frac{\pi_{k+1}}2=\frac{\pi_k}4$$

なので、詳細つり合いが成り立つ。時間平均の極限は

$$\sum_kk\pi_k=\frac{0\cdot8+1\cdot4+2\cdot2+3\cdot1}{15}=\frac{11}{15}$$

である。3. 15.5-3 定理 15.19 から

$$\pi_3=\frac{\binom63}{64}=\frac{20}{64}=\frac5{16},\qquad m_3=\frac{16}{5}=3.2,\qquad m_0=2^6=64$$

である。4. 15.5-4 2つの粒子の1歩をそれぞれ $\eta,\eta'$ とする（独立に $\pm1$）。法5で $D_{n+1}-D_n=\eta-\eta'$ である。この差は $+2,0,-2$ を確率 $\frac14,\frac12,\frac14$ でとり、過去と独立である。よって $D$ は次の遷移確率のマルコフ連鎖である。

$$p_{d,d\pm2}=\tfrac14,\qquad p_{dd}=\tfrac12$$

これは 25 状態の組 $(X,Y)$ の連鎖から集約したものである。

$3\cdot2=6\equiv1\pmod5$ なので、$E_n=3D_n\bmod5$ と置く。差の $\pm2$ の動きは、新しい変数の $\pm1$ の動きになる。

よって新しい変数は円周上で、左右に確率 $\frac14$ ずつ動き、確率 $\frac12$ で留まる連鎖である。出発の $D_0=1$ は $E_0=3$ に対応する。2つの粒子が出会うことは $E=0$ に対応する。0 に達するまでの平均時間を $k_e$ とする（$k_0=k_5=0$）。$e=1,\dots,4$ について

$$k_e=1+\tfrac12k_e+\tfrac14(k_{e-1}+k_{e+1}),\qquad\text{すなわち}\qquad k_e=2+\tfrac12(k_{e-1}+k_{e+1})$$

である。$k_e=2e(5-e)$ を入れると

$$2+\tfrac12\cdot2\bigl[(e-1)(6-e)+(e+1)(4-e)\bigr]=2+(2e(5-e)-2)=2e(5-e)$$

で満たす。命題 15.12 から解はこれだけである。求める期待値は $k_3=2\cdot3\cdot2=12$ である。5. 15.5-5 $i\ne j$ で $q_{ij},q_{ji}>0$ とし、比を

$$\rho=\frac{w_jq_{ji}}{w_iq_{ij}}\le1$$

と仮定する（$\rho>1$ なら2つの状態を入れ替える）。このとき

$$p_{ij}=q_{ij}\rho=\frac{w_jq_{ji}}{w_i},\qquad p_{ji}=q_{ji}\min(1,1/\rho)=q_{ji}$$

なので

$$w_ip_{ij}=w_jq_{ji}=w_jp_{ji}$$

で、$Z$ で割れば詳細つり合いである。提案の確率が 0 の場合は別に見る。$q_{ij}=0$ のときは $p_{ij}=0$ と定める。$q_{ji}=0$ のときも受け入れ確率が 0 となって $p_{ij}=0$ なので、両辺とも 0 である。