解説

方針・初手

グラフは

$$ {A,C,D}\quad \text{と}\quad {B,E}

$$

を交互に移動する二部構造になっている。したがって、$P_1=A$ から出発すると、奇数番目には $A,C,D$ のいずれか、偶数番目には $B,E$ のいずれかにいる。

また、$C$ と $D$ は移動規則上まったく同じ役割をもつので、$C,D$ をまとめて扱う。

解法1

（1） $p_n$ の計算

奇数番目と偶数番目に分ける。$m=1,2,\dots$ に対して

$$ u_m=\Pr(P_{2m-1}=A),\qquad v_m=\Pr(P_{2m}=B)

$$

とおく。

奇数番目では $P_{2m-1}$ は $A,C,D$ のいずれかであるから、$P_{2m}$ が $B$ となる確率は

$$ v_m=u_m+\frac12(1-u_m)=\frac{1+u_m}{2}

$$

である。ここで、$A$ からは必ず $B$ へ移り、$C,D$ からは確率 $\frac12$ で $B$ へ移ることを用いた。

また、$P_{2m+1}=A$ となるには、$P_{2m}=B$ から線分 $BA$ を選ぶ必要がある。$B$ から出る線分は $BA,BC,BD$ の3本なので、

$$ u_{m+1}=\frac13v_m=\frac{1+u_m}{6}

$$

である。初期値は $u_1=1$ である。

この漸化式を解くために定数解を求めると、

$$ u=\frac{1+u}{6}

$$

より

$$ u=\frac15

$$

である。したがって

$$ u_{m+1}-\frac15=\frac16\left(u_m-\frac15\right)

$$

となるから、

$$ u_m=\frac15+\frac45\left(\frac16\right)^{m-1}

$$

である。

よって

$$ v_m=\frac{1+u_m}{2} =\frac35+\frac25\left(\frac16\right)^{m-1}

$$

である。

奇数番目では $P_n$ が $A$ または $B$ であることは $P_n=A$ であることと同値であり、偶数番目では $P_n=B$ であることと同値である。したがって

$$ p_{2m-1}=\frac15+\frac45\left(\frac16\right)^{m-1}

$$

$$ p_{2m}=\frac35+\frac25\left(\frac16\right)^{m-1}

$$

である。

（2） $q_n$ の計算

$H_n$ を

$$ H_n={k=1,2,\dots,n\text{ のいずれに対しても }P_k\ne E}

$$

とおく。求める条件付き確率は

$$ q_n=\Pr(H_n\mid P_n=A\text{ または }B)

$$

である。

奇数番目と偶数番目に分けて、$m=1,2,\dots$ に対して

$$ \alpha_m=\Pr(H_{2m-1}\cap{P_{2m-1}=A})

$$

$$ \beta_m=\Pr(H_{2m}\cap{P_{2m}=B})

$$

$$ \gamma_m=\Pr(H_{2m-1}\cap{P_{2m-1}=C\text{ または }D})

$$

とおく。

初期値は

$$ \alpha_1=1,\qquad \gamma_1=0

$$

である。

$P_{2m-1}=A$ なら次は必ず $B$ に移る。また、$P_{2m-1}=C$ または $D$ なら、$B$ に移る確率は $\frac12$、$E$ に移る確率は $\frac12$ である。$E$ に移った場合は $H_{2m}$ を満たさないので、

$$ \beta_m=\alpha_m+\frac12\gamma_m

$$

である。

また、$P_{2m}=B$ からは $A,C,D$ の3方向へ等確率に移るから、

$$ \alpha_{m+1}=\frac13\beta_m,\qquad \gamma_{m+1}=\frac23\beta_m

$$

である。

$m\geqq 2$ では

$$ \alpha_m=\frac13\beta_{m-1},\qquad \gamma_m=\frac23\beta_{m-1}

$$

より

$$ \gamma_m=2\alpha_m

$$

である。したがって、$m\geqq 2$ では

$$ \beta_m=\alpha_m+\frac12\gamma_m=2\alpha_m

$$

となる。さらに

$$ \alpha_{m+1}=\frac13\beta_m=\frac23\alpha_m

$$

である。

また、

$$ \alpha_2=\frac13\beta_1=\frac13

$$

だから、$m\geqq 2$ に対して

$$ \alpha_m=\frac13\left(\frac23\right)^{m-2}

$$

である。したがって

$$ \beta_m=2\alpha_m=\left(\frac23\right)^{m-1}\qquad (m\geqq 2)

$$

である。なお、$\beta_1=1$ なので、この式は $m=1$ に対しても成り立つ。

よって、偶数番目については

$$ \begin{aligned} q_{2m} &= \frac{\beta_m}{p_{2m}} \\ \frac{\left(\frac23\right)^{m-1}} {\frac35+\frac25\left(\frac16\right)^{m-1}} \qquad (m=1,2,\dots) \end{aligned} $$

である。

奇数番目については、$q_1=1$ であり、$m\geqq 2$ に対して

$$ \begin{aligned} q_{2m-1} &= \frac{\alpha_m}{p_{2m-1}} \\ \frac{\frac13\left(\frac23\right)^{m-2}} {\frac15+\frac45\left(\frac16\right)^{m-1}} \end{aligned} $$

である。

解説

この問題では、$A$ または $B$ にいる確率だけを直接追うと、$C,D,E$ の区別が残るため漸化式が閉じにくい。まず、グラフが二部構造をもつことに注目し、奇数番目と偶数番目を分けるのが重要である。

また、$C$ と $D$ は完全に対称なので、まとめて「$C$ または $D$」として扱える。ただし、$E$ は $C,D$ と違って $A,B$ に戻るまでの構造が異なるため、(1) では単純に $A,B$ とそれ以外の2状態にまとめるだけでは不十分である。

(2) では、「$E$ を通らない」という条件を付けた確率を、正規化された条件付きの移動として扱ってはいけない。あくまで元の確率のまま、$E$ に行く経路を除いて数える必要がある。

答え

**(1)**

$m=1,2,\dots$ とすると、

$$ \begin{aligned} p_{2m-1} &= \frac15+\frac45\left(\frac16\right)^{m-1} \end{aligned} $$

$$ \begin{aligned} p_{2m} &= \frac35+\frac25\left(\frac16\right)^{m-1} \end{aligned} $$

である。

**(2)**

$$ q_1=1

$$

であり、$m\geqq 2$ に対して

$$ \begin{aligned} q_{2m-1} &= \frac{\frac13\left(\frac23\right)^{m-2}} {\frac15+\frac45\left(\frac16\right)^{m-1}} \end{aligned} $$

である。また、$m=1,2,\dots$ に対して

$$ \begin{aligned} q_{2m} &= \frac{\left(\frac23\right)^{m-1}} {\frac35+\frac25\left(\frac16\right)^{m-1}} \end{aligned} $$

である。