解説

方針・初手

2つの粒子の位置そのものをすべて追うより、「同じ点にいるか、異なる点にいるか」だけに注目する。

時刻 $n$ 秒後に2つの粒子が同じ点にいる確率を $p(n)$ とおくと、次の1秒で同じ点にいる確率がどう変化するかを調べれば、漸化式が立つ。

解法1

時刻 $n$ 秒後に、2つの粒子が同じ点にいる場合と、異なる点にいる場合に分ける。

（i） 時刻 $n$ 秒後に同じ点にいる場合

例えば2つの粒子がともに点 $A$ にいるとする。次の1秒で、それぞれの粒子は点 $B$ または点 $C$ に確率 $\dfrac{1}{2}$ ずつで移動する。

次の時刻でも同じ点にいるのは、2つとも $B$ に移動する場合、または2つとも $C$ に移動する場合である。したがってその確率は

$$ \left(\frac{1}{2}\right)^2+\left(\frac{1}{2}\right)^2=\frac{1}{2}

$$

である。

（ii） 時刻 $n$ 秒後に異なる点にいる場合

例えば一方が点 $A$、もう一方が点 $B$ にいるとする。

点 $A$ にいる粒子は次に $B$ または $C$ に移動し、点 $B$ にいる粒子は次に $A$ または $C$ に移動する。

次の時刻に同じ点にいるためには、2つの粒子がともに点 $C$ に移動するしかない。したがってその確率は

$$ \frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}

$$

である。

以上より、時刻 $n+1$ 秒後に同じ点にいる確率は

$$ p(n+1)=\frac{1}{2}p(n)+\frac{1}{4}{1-p(n)}

$$

である。整理すると

$$ p(n+1)=\frac{1}{4}p(n)+\frac{1}{4}

$$

となる。

また、時刻 $0$ では2つの粒子はともに点 $A$ にいるので、

$$ p(0)=1

$$

である。

漸化式

$$ p(n+1)=\frac{1}{4}p(n)+\frac{1}{4}

$$

の定数解を $p(n)=\alpha$ とおくと、

$$ \alpha=\frac{1}{4}\alpha+\frac{1}{4}

$$

より、

$$ \alpha=\frac{1}{3}

$$

である。

そこで

$$ q(n)=p(n)-\frac{1}{3}

$$

とおくと、

$$ q(n+1)=\frac{1}{4}q(n)

$$

となる。よって

$$ q(n)=q(0)\left(\frac{1}{4}\right)^n

$$

である。

ここで

$$ q(0)=p(0)-\frac{1}{3}=1-\frac{1}{3}=\frac{2}{3}

$$

だから、

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

$$

である。

したがって

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

$$

を得る。

解法2

1つの粒子が時刻 $n$ 秒後に各頂点にいる確率を求め、それを2つの粒子について掛け合わせる。

1つの粒子について、時刻 $n$ 秒後に点 $A$ にいる確率を $a_n$ とする。対称性より、点 $B$、点 $C$ にいる確率は等しく、それぞれ

$$ \frac{1-a_n}{2}

$$

である。

点 $A$ にいるためには、1秒前に点 $B$ または点 $C$ にいて、そこから点 $A$ に移動すればよい。したがって

$$ \begin{aligned} a_{n+1} &= \frac{1}{2}\cdot\frac{1-a_n}{2} + \frac{1}{2}\cdot\frac{1-a_n}{2} &= \frac{1-a_n}{2} \end{aligned} $$

である。

つまり

$$ a_{n+1}=-\frac{1}{2}a_n+\frac{1}{2}

$$

であり、初期条件は

$$ a_0=1

$$

である。

定数解を求めると

$$ \alpha=-\frac{1}{2}\alpha+\frac{1}{2}

$$

より、

$$ \alpha=\frac{1}{3}

$$

である。したがって

$$ \begin{aligned} a_n-\frac{1}{3} &= \left(-\frac{1}{2}\right)^n \left(a_0-\frac{1}{3}\right) \end{aligned} $$

となるから、

$$ \begin{aligned} a_n &= \frac{1}{3}+\frac{2}{3}\left(-\frac{1}{2}\right)^n \end{aligned} $$

である。

よって、点 $B$、点 $C$ にいる確率はそれぞれ

$$ \begin{aligned} \frac{1-a_n}{2} &= \frac{1}{3}-\frac{1}{3}\left(-\frac{1}{2}\right)^n \end{aligned} $$

である。

2つの粒子は独立に運動するので、同じ点にいる確率は

$$ \begin{aligned} p(n) &= a_n^2 + 2\left\{ \frac{1}{3}-\frac{1}{3}\left(-\frac{1}{2}\right)^n \right\}^2 \end{aligned} $$

である。ここで $x=\left(-\dfrac{1}{2}\right)^n$ とおくと、

$$ \begin{aligned} p(n) &= \left(\frac{1+2x}{3}\right)^2 + 2\left(\frac{1-x}{3}\right)^2\\ &= \frac{(1+2x)^2+2(1-x)^2}{9}\\ &= \frac{1+4x+4x^2+2-4x+2x^2}{9}\\ &= \frac{3+6x^2}{9}\\ &= \frac{1}{3}+\frac{2}{3}x^2. \end{aligned}

$$

また、

$$ \begin{aligned} x^2= \left\{\left(-\frac{1}{2}\right)^n\right\}^2 &= \left(\frac{1}{4}\right)^n \end{aligned} $$

であるから、

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

$$

となる。

解説

この問題では、各粒子の具体的な経路を数え上げると複雑になる。重要なのは、2つの粒子が「同じ点にいるかどうか」という状態だけを追えば十分である点である。

同じ点にいる状態から次も同じ点にいる確率は $\dfrac{1}{2}$、異なる点にいる状態から次に同じ点にいる確率は $\dfrac{1}{4}$ である。この2つを正しく区別できれば、一次漸化式に帰着できる。

また、極限として

$$ \lim_{n\to\infty}p(n)=\frac{1}{3}

$$

となる。これは、十分時間が経つと各粒子が3つの頂点にほぼ等確率で分布し、2つの粒子が同じ点にいる確率が $\dfrac{1}{3}$ に近づくことと対応している。

答え

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

$$