5大阪大学 2010年 数学 第5問解答・解説

以下の確率計算は、PとQの移動先の選択が互いに独立である通常の解釈に基づく。 より明確には、各時刻 $n$ において $P_n\ne Q_n$ の場合、時刻 $n$ までの全履歴と現在位置対 $(P_n,Q_n)$ を条件として、次の移動先 $P_{n+1},Q_{n+1}$ をそれぞれ現在位置の3つの隣接頂点から一様に選び、2つの選択はその条件の下で互いに独立とする。この選択則を各時刻で同じに適用する。$P_n=Q_n$ となった後は、問題文の規則どおり同じ頂点にとどまる。 立方体の頂点を3ビットで表すと、辺で結ばれた頂点同士では偶奇が反転する。初期位置A,Cは同じ偶奇である。P,Qが異なる限り、両者は同時に隣接頂点へ移るため、時刻ごとに両者の偶奇は一致したままである。立方体で同じ偶奇をもつ異なる頂点間の距離は2であり、2頂点には共通の隣接頂点が2つある。 (1) $P=A$ の隣接頂点は $B,D,E$、$Q=C$ の隣接頂点は $B,D,G$ である。独立選択なら9通りの順序対は等確率で、衝突する $(B,B),(D,D)$ を除くと $$\boxed{(B,D),(B,G),(D,B),(D,G),(E,B),(E,D),(E,G)}$$ の7通りである。 (2) 異なる位置からの次の一歩で衝突するのは、共通する2頂点のどちらかを両者が選ぶ場合なので、その確率は $2/9$。衝突後は2点が同じ頂点にとどまる。従って $$\displaystyle r_0=1,\qquad r_{n+1}=\frac79r_n,\qquad \boxed{r_n=\left(\frac79\right)^n}.$$ (3) $p_n$ のとき、2点は同じ面の対角頂点にある。代表例 $P=A,Q=C$ では $N(A)=\{B,D,E\},N(C)=\{B,D,G\}$。両方が上面内へ動く4通りのうち衝突2通りを除いた $(B,D),(D,B)$ の2通りと、両方が垂直に動く $(E,G)$ の1通りが $p_{n+1}$ に入るので、寄与は $3/9=1/3$。 $q_n$ のときの代表例 $P=A,Q=F$ では $N(A)=\{B,D,E\},N(F)=\{B,E,G\}$。次に同じ面の異なる頂点になるのは、上面の $(D,B)$ と下面の $(E,G)$ の2通りである。立方体の対称性により、各 $q_n$ 状態からの寄与は $2/9$。同じ頂点にいる状態からは移動せず、その状態は $p_{n+1}$ に数えられない。よって $$\displaystyle \boxed{p_{n+1}=\frac13p_n+\frac29q_n}.$$

また $r_n=p_n+q_n$ であり、(2)より $\displaystyle r_{n+1}=\frac79(p_n+q_n)$。従って $$\displaystyle q_{n+1}=\frac49p_n+\frac59q_n.$$ (4) $p_0=1,\ q_0=0$ なので $p_n>0$。$z_n=q_n/p_n$ とおくと $$\displaystyle z_{n+1}=\frac{4+5z_n}{3+2z_n},\qquad 2-z_{n+1}=\frac{2-z_n}{3+2z_n}.$$ $z_0=0$ から $0\le z_n<2$ であり、$0\le2-z_{n+1}\le(2-z_n)/3$。従って $2-z_n\to0$ となり、 $$\displaystyle \boxed{\lim\limits _{n\to\infty}\frac{q_n}{p_n}=2}.$$ ただし、原文はP,Qの選択間の独立性を明記していない。独立性なしには全問の確率的な答えは一意でない。例えば初回に共通の一様な添字 $1,2,3$ を使い、Pの行先を $(B,D,E)$、Qの行先を $(B,D,G)$ と同じ添字で対応させると、各行先は個別には一様でも衝突確率は $2/3$、したがって $r_1=1/3$ となる。上記の $r_1=7/9$ は独立選択の場合である。