解説

方針・初手

部屋 $A_1$ にいる確率だけを追えばよい。

次に $A_1$ に移動できるのは、直前に $A_1$ 以外の部屋にいた場合だけである。どの部屋にいても、現在いる部屋以外の $k$ 個の部屋を等確率で選ぶので、$A_1$ へ移動する確率は $\dfrac{1}{k}$ である。

解法1

$n$ 回移動した後に部屋 $A_1$ にいる確率を $p_n$ とおく。

最初は部屋 $A_0$ にいるので、

$$ p_0=0

$$

である。

$n+1$ 回移動した後に $A_1$ にいるためには、$n$ 回移動した後に $A_1$ 以外の部屋にいて、そこから $A_1$ を選べばよい。

$n$ 回移動した後に $A_1$ 以外の部屋にいる確率は $1-p_n$ であり、その状態から $A_1$ へ移動する確率は $\dfrac{1}{k}$ であるから、

$$ p_{n+1}=\frac{1-p_n}{k}

$$

すなわち、

$$ p_{n+1}=-\frac{1}{k}p_n+\frac{1}{k}

$$

である。

この漸化式の定数解を求める。$p_{n+1}=p_n=c$ とすると、

$$ c=\frac{1-c}{k}

$$

より、

$$ (k+1)c=1

$$

したがって、

$$ c=\frac{1}{k+1}

$$

である。

よって漸化式を

$$ \begin{aligned} p_{n+1}-\frac{1}{k+1} &= -\frac{1}{k}\left(p_n-\frac{1}{k+1}\right) \end{aligned} $$

と変形できる。

したがって、

$$ \begin{aligned} p_n-\frac{1}{k+1} &= \left(-\frac{1}{k}\right)^n \left(p_0-\frac{1}{k+1}\right) \end{aligned} $$

である。$p_0=0$ を代入すると、

$$ \begin{aligned} p_n-\frac{1}{k+1} &= -\frac{1}{k+1}\left(-\frac{1}{k}\right)^n \end{aligned} $$

よって、

$$ \begin{aligned} p_n &= \frac{1}{k+1} \left\{1-\left(-\frac{1}{k}\right)^n\right\} \end{aligned} $$

となる。

解説

この問題では、すべての部屋を個別に追う必要はない。求めたいのは $A_1$ にいる確率だけであり、次に $A_1$ に入れるかどうかは「現在 $A_1$ にいるか、いないか」だけで決まる。

特に、直前に $A_1$ にいる場合は次の移動で $A_1$ にとどまることはできない。一方、直前に $A_1$ 以外にいれば、どの部屋からでも $A_1$ へ移動する確率は同じく $\dfrac{1}{k}$ である。この性質から、一次漸化式に落とし込める。

また、$k=1$ の場合も公式は成り立つ。このとき部屋は $A_0,A_1$ の2つだけなので、奇数回後は必ず $A_1$、偶数回後は必ず $A_0$ にいる。公式

$$ \frac{1}{2}{1-(-1)^n}

$$

はこの動きと一致する。

答え

$n$ 回移動した後に部屋 $A_1$ にいる確率は

$$ \boxed{\frac{1}{k+1}\left\{1-\left(-\frac{1}{k}\right)^n\right\}}

$$

である。