確率論の問題

マス $x$ から出発したときの $(3,3)$ への平均到達時間を $h(x)$ とする。有限で既約な連鎖なので $h(x)<\infty$ であり、$h((3,3))=0$ である。$h$ は 1 歩目で条件付けると
$$h(x)=1+\sum _{y}P(x,y)h(y)(x\ne (3,3))$$
を満たす（マルコフ性による first-step analysis）。

対称性による状態の整理. 主対角線に関する鏡映 $(i,j)\mapsto (j,i)$ は $(1,1)$ と $(3,3)$ を固定し、推移確率を保つので $h(i,j)=h(j,i)$ である。そこで
$$a=h(1,1),b=h(1,2)=h(2,1),c=h(1,3)=h(3,1),d=h(2,2),e=h(2,3)=h(3,2)$$
とおく。

各マスの隣接マス.
- $(1,1)$：$(1,2),(2,1),(2,2)$ の 3 つ。
- $(1,2)$：$(1,1),(1,3),(2,1),(2,2),(2,3)$ の 5 つ。
- $(1,3)$：$(1,2),(2,2),(2,3)$ の 3 つ。
- $(2,2)$：他の 8 マスすべて。
- $(2,3)$：$(1,2),(1,3),(2,2),(3,2),(3,3)$ の 5 つ。

したがって
$$\begin{array}{rl}(1)a& =1+\frac{2}{3}b+\frac{1}{3}d,\\ (2)b& =1+\frac{1}{5}(a+b+c+d+e),\\ (3)c& =1+\frac{1}{3}(b+d+e),\\ (4)d& =1+\frac{1}{8}(a+2b+2c+2e+0),\\ (5)e& =1+\frac{1}{5}(b+c+d+e+0).\end{array}$$

連立方程式を解く. $(2)$ より $4b=5+a+c+d+e$、$(5)$ より $4e=5+b+c+d$。辺々引くと $4b-4e=a+e-b$、すなわち
$$e=b-\frac{a}{5}.$$
$(1)$ より $d=3a-3-2b$。これらを $(3)$ の $3c=3+b+d+e$ に代入すると
$$3c=3+b+(3a-3-2b)+\left(b-\frac{a}{5}\right)=\frac{14}{5}a⟹c=\frac{14}{15}a.$$
$(2)$ の $4b=5+a+c+d+e$ に代入すると
$$4b=5+a+\frac{14}{15}a+3a-3-2b+b-\frac{a}{5}=2+\frac{71}{15}a-b,$$
よって $5b=2+\frac{71}{15}a$、すなわち $20b=8+\frac{284}{15}a$。
$(4)$ の $8d=8+a+2b+2c+2e$ に代入すると、左辺は $24a-24-16b$、右辺は
$$8+a+2b+\frac{28}{15}a+2b-\frac{2}{5}a=8+\frac{37}{15}a+4b.$$
よって $24a-\frac{37}{15}a-32=20b$、すなわち $\frac{323}{15}a-32=20b$。これに $20b=8+\frac{284}{15}a$ を代入して
$$\frac{323}{15}a-32=8+\frac{284}{15}a⟹\frac{39}{15}a=40⟹a=\frac{200}{13}.$$
（このとき $b=\frac{2918}{195},c=\frac{560}{39},d=\frac{2579}{195},e=\frac{2318}{195}$ となり、$(1)$〜$(5)$ をすべて満たすことが確かめられる。）

別の確認. この連鎖はキングの隣接グラフ上の単純ランダムウォークで、辺の数は次数の和 $4\cdot 3+4\cdot 5+8=40$ の半分の $20$ である。$180^{\circ }$ 回転は $(1,1)$ と $(3,3)$ を入れかえるグラフの自己同型なので、$E[T]$ は通勤時間 $2|E|R_{\mathrm{eff}}$ の半分 $20R_{\mathrm{eff}}$ に等しい（$R_{\mathrm{eff}}$ は各辺を抵抗 $1$ とした $(1,1)$–$(3,3)$ 間の有効抵抗で、$R_{\mathrm{eff}}=\frac{10}{13}$）。これも上の結果と一致する。

以上より
$$E[T]=\frac{200}{13}.$$

対称性（$i\leftrightarrow j$ の入れ替え）で状態を同一視する。$h(x)$ を $x$ から $(3,3)$ に到達するまでの期待時間とし、$a=h(1,1)$、$b=h(1,2)=h(2,1)$、$c=h(1,3)=h(3,1)$、$d=h(2,2)$、$e=h(2,3)=h(3,2)$ とおく。$h(3,3)=0$。

各マスの隣接マスから次の連立方程式を得る。
$a=1+\frac{2b+d}{3}$
$b=1+\frac{a+b+c+d+e}{5}$
$c=1+\frac{b+d+e}{3}$
$d=1+\frac{a+2b+2c+2e}{8}$
$e=1+\frac{b+c+d+e}{5}$

$c$ と $e$ の式から $e=\frac{18+4b+4d}{11}$、$c=\frac{17+5b+5d}{11}$ を得る。
これと $a$ の式を $b$ の式に代入すると $83b=303+71d$。
$d$ の式に代入すると $199d=507+142b$。
2 式から $6435d=85107$、すなわち $d=\frac{2579}{195}$、$b=\frac{2918}{195}$。
よって $a=1+\frac{2b+d}{3}=1+\frac{187}{13}=\frac{200}{13}$。

検算：$c\approx 14.359$、$e\approx 11.887$ として $d$ の式の右辺は $(8+15.385+29.928+28.718+23.774)/8\approx 13.226=d$ となり一致する。

ゆえに $E[T]=\frac{200}{13}$。