到達確率と平均到達時間

ある迷路に部屋 $\mathrm{A}$、部屋 $\mathrm{B}$ と出口があり、ネズミが $1$ 分ごとに $1$ 回、次の規則で移動する（各回の移動は、それまでの経過とは独立に、現在いる場所だけで決まる）。

• 部屋 $\mathrm{A}$ にいるとき：確率 $\frac{2}{3}$ で部屋 $\mathrm{B}$ へ移り、確率 $\frac{1}{3}$ で部屋 $\mathrm{A}$ にとどまる。
• 部屋 $\mathrm{B}$ にいるとき：確率 $\frac{1}{2}$ で出口に到達し、確率 $\frac{1}{2}$ で部屋 $\mathrm{A}$ へ戻る。

ネズミははじめ部屋 $\mathrm{A}$ にいる。出口に初めて到達するまでの移動回数の期待値を求めよ。ただし、この期待値が有限であることは用いてよい。

正方形 $\mathrm{ABCD}$ の頂点の上を点 $\mathrm{P}$ が動く。点 $\mathrm{P}$ は $1$ 回の移動で、いまいる頂点に隣り合う $2$ つの頂点のどちらかへ、それぞれ確率 $\frac{1}{2}$ で移る。各回の移動は互いに独立とする。点 $\mathrm{P}$ ははじめ頂点 $\mathrm{A}$ にある。点 $\mathrm{P}$ が初めて頂点 $\mathrm{C}$ に到達するまでの移動回数の期待値を求めよ。ただし、この期待値は有限であるとしてよい。

3 つの部屋 $\mathrm{A}$, $\mathrm{B}$, $\mathrm{C}$ と出口があり、扉は次の 4 枚だけである。

• $\mathrm{A}$ と $\mathrm{B}$ を結ぶ扉
• $\mathrm{A}$ と $\mathrm{C}$ を結ぶ扉
• $\mathrm{B}$ と $\mathrm{C}$ を結ぶ扉
• $\mathrm{C}$ と出口を結ぶ扉

1 匹のネズミが部屋 $\mathrm{A}$ にいる。ネズミは 1 回の移動ごとに、いまいる部屋にある扉のうち 1 枚を等しい確率で選び、その扉を通って隣の部屋（または出口）へ移る。選び方は過去の移動とは独立である。ネズミが出口に出た時点で移動を終える。部屋 $\mathrm{A}$ から出発して出口に出るまでの移動回数の期待値を求めよ。

状態空間 $S=\{1,2,3\}$ 上の時間一様なマルコフ連鎖 $(X_n{)}_{n\ge 0}$ の推移確率行列が
$$P=\left(\begin{array}{ccc}0& 1& 0\\ \frac{1}{3}& \frac{1}{3}& \frac{1}{3}\\ 0& \frac{1}{2}& \frac{1}{2}\end{array}\right)$$
で与えられている（$i$ 行 $j$ 列の成分が状態 $i$ から状態 $j$ への推移確率）。$X_0=1$ とし、$T=\min \{n\ge 1:X_n=1\}$ を状態 $1$ への最初の再帰時刻とする。平均再帰時間 $m_1=E[T]$ を求めよ。

状態空間 $S=\{1,2,3\}$ 上の時間的に一様なマルコフ連鎖 $(X_n{)}_{n\ge 0}$ の推移確率行列が
$$P=\left(\begin{array}{ccc}\frac{1}{2}& \frac{1}{2}& 0\\ \frac{1}{3}& 0& \frac{2}{3}\\ 1& 0& 0\end{array}\right)$$
で与えられている。第 $i$ 行第 $j$ 列の成分は、状態 $i$ から状態 $j$ へ 1 ステップで移る確率 $p_{ij}$ である。$X_0=3$ から出発したとき、初めて状態 $3$ に戻るまでのステップ数を $T_3=\min \{n\ge 1:X_n=3\}$ とする。状態 $3$ の平均再帰時間 $m_3=E[T_3\mid X_0=3]$ を求めよ。

${\xi }_1,{\xi }_2,\dots$ を独立同分布な確率変数で、
$$P({\xi }_k=1)=\frac{1}{3},P({\xi }_k=-1)=\frac{2}{3}$$
を満たすものとする。$X_0=2$、$X_n=2+{\xi }_1+\cdots +{\xi }_n$ $(n\ge 1)$ とおく。これは、所持金 $2$ 円のギャンブラーが、勝つ確率 $\frac{1}{3}$ で $1$ 円を得て、負ける確率 $\frac{2}{3}$ で $1$ 円を失う賭けを繰り返すときの、$n$ 回後の所持金を表す。

$$\tau =\min \{n\ge 0:X_n=0\text{または}{X}_n=5\}$$
とする。つまり、所持金が $0$ 円になるか $5$ 円になった時点で賭けをやめる。賭けをやめるまでの回数の期待値 $E[\tau ]$ を求めよ。

状態空間 $\{0,1,2,3\}$ 上の時間的に一様なマルコフ連鎖 $(X_n{)}_{n\ge 0}$ があり、推移確率 $p_{ij}=P(X_{n+1}=j\mid X_n=i)$ は次のとおりである。
- 状態 $0$ と状態 $3$ は吸収状態である（$p_{00}=p_{33}=1$）。
- 状態 $1$ からは $p_{12}=\frac{1}{2}$, $p_{11}=\frac{1}{4}$, $p_{10}=\frac{1}{4}$。
- 状態 $2$ からは $p_{23}=\frac{1}{3}$, $p_{21}=\frac{1}{3}$, $p_{20}=\frac{1}{3}$。

$X_0=1$ から出発したとき、この連鎖が状態 $0$ に到達する前に状態 $3$ に到達する確率を求めよ。

状態空間 $\{1,2,3,4\}$ 上の時間的に一様なマルコフ連鎖 $(X_n{)}_{n\ge 0}$ の推移確率行列が
$$P=\left(\begin{array}{cccc}0& \frac{1}{2}& \frac{1}{2}& 0\\ \frac{1}{3}& 0& \frac{1}{3}& \frac{1}{3}\\ \frac{1}{2}& \frac{1}{4}& 0& \frac{1}{4}\\ 1& 0& 0& 0\end{array}\right)$$
で与えられているとする（第 $i$ 行第 $j$ 列の成分が $P(X_{n+1}=j\mid X_n=i)$ である）。$X_0=1$ とし、
$$T=\min \{n\ge 0:X_n=4\}$$
とおく。期待値 $E[T]$ を求めよ。

頂点集合 $\{h,v_0,v_1,v_2,v_3\}$ をもち、辺が
$$v_0{v}_1,v_1{v}_2,v_2{v}_3,v_3{v}_0,h{v}_0,h{v}_1,h{v}_2,h{v}_3$$
の $8$ 本であるグラフ $G$（正方形の 4 頂点と、そのすべてに隣接する中心 $h$ からなるグラフ）を考える。$G$ 上の単純ランダムウォーク $(X_n{)}_{n\ge 0}$、すなわち各時刻に現在の頂点に隣接する頂点の中から等確率で 1 つを選んで移動する時間的に一様なマルコフ連鎖を考え、$X_0=h$ とする。
$$T=\min \{n\ge 0:X_n=v_0\}$$
とおくとき、期待値 $E[T]$ を求めよ。

$3\times 3$ の盤のマスを座標 $(i,j)$ $(i,j\in \{1,2,3\})$ で表す。マス $(i,j)$ と $(i^{\prime },j^{\prime })$ は、$(i,j)\ne (i^{\prime },j^{\prime })$ かつ $\max (|i-i^{\prime }|,|j-j^{\prime }|)=1$ のとき隣接するという（チェスのキングが 1 手で動ける関係）。

この盤上のマルコフ連鎖 $(X_n{)}_{n\ge 0}$ を、各時刻に現在のマスに隣接するマスの中から等確率で 1 つ選んでそこへ移る、として定める。$X_0=(1,1)$ とし、
$$T=\min \{n\ge 0:X_n=(3,3)\}$$
とおく。$E[T]$ を求めよ。

状態空間 $\{1,2,3,4\}$ 上の斉次マルコフ連鎖 $X_0,X_1,X_2,\dots$ の推移確率行列が
$$P=\left(\begin{array}{cccc}1& 0& 0& 0\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{2}& 0\\ \frac{1}{6}& \frac{1}{3}& 0& \frac{1}{2}\\ 0& 0& 0& 1\end{array}\right)$$
で与えられている。ここで $P$ の $(i,j)$ 成分は $P(X_{n+1}=j\mid X_n=i)$ を表す。状態 $1$ と状態 $4$ は吸収状態である。$X_0=2$ のとき、この連鎖が状態 $1$ より先に状態 $4$ に到達する（すなわち最終的に状態 $4$ に吸収される）確率を求めよ。

2 つの箱 A, B と、番号 $1,2,3,4$ の付いた $4$ 個の玉がある。はじめ ($n=0$) に $4$ 個の玉はすべて箱 A に入っている。各時刻 $n=1,2,3,\dots$ に、$4$ 個の玉の中から $1$ 個を等確率 $\frac{1}{4}$ で選ぶ（選択は時刻ごとに独立）。選んだ玉を、それが入っている箱からもう一方の箱へ移す。

$4$ 個の玉がはじめてすべて箱 B に入っている時刻を
$$T=\min \{n\ge 1:\text{時刻 }n\text{ の操作後にすべての玉が箱 B にある}\}$$
とする。期待値 $E[T]$ を求めよ。

$3\times 3$ のマス目の盤を考え、第 $i$ 行第 $j$ 列のマスを $(i,j)$ $(1\le i,j\le 3)$ と表す。盤上のキングは、縦・横・斜めに隣り合うマス（すなわち $\max (|i-i^{\prime }|,|j-j^{\prime }|)=1$ を満たすマス $(i^{\prime },j^{\prime })$）へ 1 回に 1 マス動く。

盤上のマスを値にとるマルコフ連鎖 $(X_n{)}_{n\ge 0}$ を次のように定める。$X_0=(1,1)$ とし、各時刻 $n=0,1,2,\dots$ において、$X_{n+1}$ は $X_n$ からキングが動ける盤上のマスのうちの 1 つを、それまでの経過と独立に等確率で選んだものとする。
$$T=\min \{n\ge 0:X_n=(3,3)\}$$
とおくとき、期待値 $E[T]$ を求めよ。

状態空間 $\{0,1,2,3\}$ 上の斉次マルコフ連鎖 $X_0,X_1,X_2,\dots$ の 1 ステップの推移確率が次で与えられている。
- 状態 $0$ と状態 $3$ は吸収状態である（一度入ると出ない）。
- 状態 $1$ からは、確率 $\frac{1}{3}$ で $0$ へ、確率 $\frac{1}{2}$ で $2$ へ移り、確率 $\frac{1}{6}$ で $1$ にとどまる。
- 状態 $2$ からは、確率 $\frac{1}{2}$ で $0$ へ、確率 $\frac{1}{4}$ で $1$ へ、確率 $\frac{1}{4}$ で $3$ へ移る。

$X_0=1$ のとき、この連鎖が状態 $0$ より先に状態 $3$ に到達する確率を求めよ。

三角柱の頂点と辺からなるグラフ $G$ を考える。すなわち、頂点集合は $\{a_1,a_2,a_3,b_1,b_2,b_3\}$ で、辺は
$$a_1{a}_2,a_2{a}_3,a_3{a}_1,b_1{b}_2,b_2{b}_3,b_3{b}_1,a_1{b}_1,a_2{b}_2,a_3{b}_3$$
の $9$ 本である。$G$ 上の単純ランダムウォーク $(X_n{)}_{n\ge 0}$（各時刻に、現在の頂点に隣接する $3$ 頂点のいずれかへ等確率 $\frac{1}{3}$ で、それまでの経過とは独立に移る斉次マルコフ連鎖）を $X_0=a_1$ から出発させる。
$$\tau =\min \{n\ge 0:X_n=b_2\}$$
とおくとき、期待値 $E[\tau ]$ を求めよ。

$a,b$ を正の整数とする。${\xi }_1,{\xi }_2,\dots$ を独立同分布な確率変数で $P({\xi }_k=1)=P({\xi }_k=-1)=\frac{1}{2}$ を満たすものとし、$S_0=0$, $S_n={\xi }_1+\cdots +{\xi }_n$ $(n\ge 1)$ とおく。
$$T=\min \{n\ge 0:S_n=-a\text{または}{S}_n=b\}$$
とする。$S_T=b$ という条件のもとでの $T$ の条件付き期待値 $E[T\mid S_T=b]$ を $a,b$ の式で求めよ。

表が出る確率が $p$ $(0<p<1)$ の硬貨を、毎回独立に繰り返し投げる。「表が $3$ 回連続して出る」または「裏が $2$ 回連続して出る」のどちらかが初めて起きた時点で投げるのをやめる。表が $3$ 回連続して出たことで終わる確率を $p$ の式で表せ。

$n\ge 2$ を整数とし、$\{0,1{\}}^n$ に値をとるマルコフ連鎖 $(X_t{)}_{t\ge 0}$ を次のように定める。$X_0=(0,0,\dots ,0)$ とし、各時刻 $t=0,1,2,\dots$ において、添字 $i\in \{1,2,\dots ,n\}$ を一様に選び、それとは独立にビット $b\in \{0,1\}$ を等確率で選んで、$X_t$ の第 $i$ 成分だけを $b$ に置き換えたものを $X_{t+1}$ とする（他の成分は変えない）。各時刻の選択は互いに独立とする。

$$T=\min \{t\ge 0:X_t=(1,1,0,0,\dots ,0)\}$$

とおく（第 $1$ 成分と第 $2$ 成分が $1$、残りが $0$ の状態に初めて到達する時刻）。期待値 $E[T]$ を $n$ の式で求めよ。

${\xi }_1,{\xi }_2,\dots$ を独立同分布な確率変数で $$P({\xi }_k=1)=P({\xi }_k=-1)=\frac{1}{4},P({\xi }_k=0)=\frac{1}{2}$$ を満たすものとし、$S_0=0$, $S_n={\xi }_1+\cdots +{\xi }_n$ $(n\ge 1)$ とおく。停止時刻 $$\tau =\min \{n\ge 0:S_n=-2\text{または}{S}_n=3\}$$ を考える（$\tau <\infty$ が確率 $1$ で成り立つ）。$\tau$ の分散 $V(\tau )$ を求めよ。