マルコフ連鎖と推移確率

ある町の天気は毎日「晴れ」か「雨」のどちらかであり、翌日の天気はその日の天気だけで次のように決まるものとする。

• ある日が晴れならば、翌日が晴れである確率は $\frac{3}{4}$、雨である確率は $\frac{1}{4}$ である。
• ある日が雨ならば、翌日が晴れである確率は $\frac{1}{2}$、雨である確率は $\frac{1}{2}$ である。

すなわち、状態を $1$（晴れ）、$2$（雨）とすると、天気は推移確率行列
$$P=\left(\begin{array}{cc}\frac{3}{4}& \frac{1}{4}\\ \frac{1}{2}& \frac{1}{2}\end{array}\right)$$
をもつ斉次マルコフ連鎖 $X_0,X_1,X_2,\dots$ に従う（$(i,j)$ 成分は状態 $i$ から状態 $j$ へ移る確率）。今日（$0$ 日目）は晴れである。$n$ を $0$ 以上の整数とするとき、$n$ 日後が晴れである確率 $p_n=P(X_n=1)$ を $n$ の式で求めよ。

ある町の天気は「晴れ」か「雨」のどちらかであり、翌日の天気はその日の天気だけで次の確率で決まるとする。

つまり、状態を 晴れ $=1$、雨 $=2$ とするとき、天気の列 $X_0,X_1,X_2,\dots$ は推移確率行列
$$P=\left(\begin{array}{cc}\frac{3}{4}& \frac{1}{4}\\ \frac{1}{2}& \frac{1}{2}\end{array}\right)$$
の斉次マルコフ連鎖である。$0$ 日目は晴れ（$X_0=1$）であった。正の整数 $n$ に対して、$n$ 日目が晴れである確率 $p_n=P(X_n=1)$ を $n$ の式で求めよ。

ある工場の機械は、毎朝「稼働」か「故障」のどちらかの状態にある。翌朝の状態は、その日の朝の状態だけで次のように確率的に決まるものとする。

• その日の朝に稼働していれば、翌朝も稼働している確率は $\frac{3}{4}$、故障している確率は $\frac{1}{4}$ である。
• その日の朝に故障していれば、その日のうちに修理が行われ、翌朝に稼働している確率は $\frac{1}{2}$、故障したままである確率は $\frac{1}{2}$ である。

すなわち、状態を（稼働, 故障）の順に並べた推移確率行列は
$$P=\left(\begin{array}{cc}\frac{3}{4}& \frac{1}{4}\\ \frac{1}{2}& \frac{1}{2}\end{array}\right)$$
である（第 $i$ 行第 $j$ 列が、状態 $i$ から状態 $j$ へ移る確率）。

$0$ 日目の朝、機械は故障していた。$n$ を $0$ 以上の整数とするとき、$n$ 日目の朝に機械が稼働している確率 $p_n$ を $n$ の式で求めよ。

ある町の天気は、毎日「晴れ」か「雨」のどちらかであるとする。天気の変わり方は次の規則に従う。

• ある日が晴れのとき、翌日が雨になる確率は $\frac{1}{4}$、晴れになる確率は $\frac{3}{4}$
• ある日が雨のとき、翌日が晴れになる確率は $\frac{1}{3}$、雨になる確率は $\frac{2}{3}$

翌日の天気は当日の天気だけで決まり、それより前の天気には関係しないものとする。$n$ を正の整数とし、今日から $n$ 日後が雨である確率を $r_n$ とする。今日の天気にかかわらず、極限 $\underset{n\to \infty }{\lim }{r}_n$ を求めよ。

$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$ の $3$ つであるマルコフ決定過程を考える。各時刻 $t=0,1,2,\dots$ に現在の状態を見て行動を $1$ つ選ぶと、その時刻の報酬を受け取り、次の時刻の状態が次の確率で決まる（$p_{ij}$ は状態 $i$ から状態 $j$ へ遷移する確率）。

• 状態 $1$ で行動 $a$：報酬 $2$、$(p_{11},p_{12},p_{13})=\left(\frac{1}{2},\frac{1}{2},0\right)$
• 状態 $1$ で行動 $b$：報酬 $0$、$(p_{11},p_{12},p_{13})=(0,0,1)$
• 状態 $2$ で行動 $a$：報酬 $4$、$(p_{21},p_{22},p_{23})=\left(\frac{1}{3},\frac{2}{3},0\right)$
• 状態 $2$ で行動 $b$：報酬 $1$、$(p_{21},p_{22},p_{23})=\left(0,\frac{1}{2},\frac{1}{2}\right)$
• 状態 $3$ で行動 $c$（選べる行動はこれのみ）：報酬 $6$、$(p_{31},p_{32},p_{33})=\left(\frac{1}{2},\frac{1}{4},\frac{1}{4}\right)$

方策 $\pi$ のもとで時刻 $t$ に得る報酬を $R_t$ とし、初期状態 $i$ からの長期平均報酬を
$$g^{\pi }(i)=\underset{N\to \infty }{\lim }\frac{1}{N}{E}^{\pi }\left[\sum _{t=0}^{N-1}{R}_t|X_0=i\right]$$
で定める。この長期平均報酬のすべての方策にわたる最大値（最適平均報酬）を求めよ。なお、状態と行動が有限のこのマルコフ決定過程では、最適な方策が定常な決定的方策（各状態で常に同じ行動を選ぶ方策）の中に存在し、その最適平均報酬は初期状態によらないことを用いてよい。

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]$ を求めよ。

状態空間 $\{1,2,3\}$ 上の斉次マルコフ連鎖 $X_0,X_1,X_2,\dots$ の推移確率行列が
$$P=\left(\begin{array}{ccc}\frac{1}{2}& \frac{1}{2}& 0\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{2}\\ \frac{1}{3}& 0& \frac{2}{3}\end{array}\right)$$
で与えられている（$(i,j)$ 成分が状態 $i$ から状態 $j$ へ 1 回で移る確率）。$X_0=1$ とするとき、極限
$$\underset{n\to \infty }{\lim }P(X_{n+1}=X_n)$$
の値を求めよ。

表が出る確率が $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$ の式で求めよ。