解説

方針・初手

時刻 $0$ で点 $P$ はすでに頂点 $A$ にいる。したがって、求める確率は、時刻 $1,2,\ldots,n$ の間に $B,C,D$ のすべてに少なくとも一度到達する確率である。

「すべてに到達する」を直接数えるよりも、「少なくとも1つの頂点に到達しない」確率を包除原理で引く。

解法1

頂点 $B,C,D$ のうち、特定の1つ、例えば $B$ に時刻 $1$ から時刻 $n$ まで一度も到達しない確率を考える。

$B$ を避けるなら、点 $P$ は $A,C,D$ の3頂点の間だけを動く。ただし、どの頂点にいても、移動先として選べる3頂点のうち、$B$ を除いた2頂点が許される。

したがって、各時刻で $B$ を避ける確率は $\dfrac{2}{3}$ であり、$n$ 秒間ずっと $B$ を避ける確率は

$$ \left(\frac{2}{3}\right)^n

$$

である。

同様に、$C$ を避ける確率、$D$ を避ける確率もそれぞれ

$$ \left(\frac{2}{3}\right)^n

$$

である。

次に、例えば $B$ と $C$ の両方を一度も訪れない確率を考える。このとき点 $P$ は $A,D$ の2頂点の間だけを動く必要がある。

$A$ にいるときは $D$ を選ぶしかなく、$D$ にいるときは $A$ を選ぶしかない。どちらの場合も、許される移動先は3頂点中1頂点だけである。

よって、$B,C$ の両方を避ける確率は

$$ \left(\frac{1}{3}\right)^n

$$

である。

同様に、$B,D$ を避ける場合、$C,D$ を避ける場合もそれぞれ

$$ \left(\frac{1}{3}\right)^n

$$

である。

最後に、$B,C,D$ のすべてを一度も訪れないことは、時刻 $1$ 以降もずっと $A$ にいることを意味する。しかし点 $P$ は毎秒、現在いる頂点とは異なる頂点へ必ず移動するので、これは $n \geqq 1$ では不可能である。

したがって、その確率は $0$ である。

包除原理より、$B,C,D$ のすべてに少なくとも一度到達する確率は

$$ 1-3\left(\frac{2}{3}\right)^n+3\left(\frac{1}{3}\right)^n

$$

である。

解法2

時刻 $k$ までに現れた頂点の個数に注目する。

時刻 $k$ までに現れた頂点が $r$ 個であるとする。ただし現在いる頂点は、その $r$ 個の中に含まれる。次の移動でまだ現れていない頂点へ行く確率は、未訪問の頂点が $4-r$ 個あるので

$$ \frac{4-r}{3}

$$

である。

逆に、すでに現れた頂点へ行く確率は、現在いる頂点には移動できないため、候補は $r-1$ 個であり、

$$ \frac{r-1}{3}

$$

である。

ここで、時刻 $k$ までに現れた頂点が $r$ 個である確率を $p_r(k)$ とする。求める確率は $p_4(n)$ である。

時刻 $0$ では $A$ のみ現れているから

$$ p_1(0)=1,\qquad p_2(0)=p_3(0)=p_4(0)=0

$$

である。

時刻 $1$ には必ず $A$ 以外の頂点へ移動するので、

$$ p_2(1)=1

$$

である。

以後、$B,C,D$ のうち何個を訪れたかを考えると、時刻 $1$ から時刻 $n$ までの $n$ 回の移動で、$B,C,D$ の3頂点すべてを少なくとも1回訪れる確率を求めればよい。

この条件は、3種類の頂点 $B,C,D$ がすべて出ることと同じである。特定の1頂点を一度も訪れない確率は、解法1と同様に

$$ \left(\frac{2}{3}\right)^n

$$

である。

また、特定の2頂点を一度も訪れない確率は

$$ \left(\frac{1}{3}\right)^n

$$

である。

よって包除原理により、

$$ p_4(n)=1-3\left(\frac{2}{3}\right)^n+3\left(\frac{1}{3}\right)^n

$$

となる。

解説

この問題では、点 $P$ の位置そのものをすべて追うよりも、「まだ訪れていない頂点」に注目する方が自然である。

特に、時刻 $0$ ですでに $A$ を訪れているため、実質的には $B,C,D$ の3頂点をすべて訪れる確率を求める問題になる。

直接「3頂点すべてを訪れる経路」を数えると場合分けが煩雑になる。一方、「特定の頂点を訪れない」「特定の2頂点を訪れない」という余事象は、各時刻で許される移動先の個数が一定になるため、簡単に計算できる。

答え

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

$$