4愛媛大学 2014年 数学 第4問解答・解説

(1)(i) $P=C$ のとき、$Q$ の行先候補は $A,C,D$。このうち $C$ から距離1の頂点は $A,D$ なので2通り。(ii) $P=B$ のとき、$Q$ の行先候補 $A,C,D$ は全て $B$ から距離1だから3通り。

(2) 以下では、各ステップで $P,Q$ がそれぞれの候補から独立に行先を選び、その選択が過去の履歴にも依存しないと仮定する。$t=1$ で $P=B,C,D$ は各確率 $1/3$。$P=B$ なら $Q$ は確率1で別頂点、$P=C,D$ なら確率 $2/3$ で別頂点だから $$\displaystyle p_1=\frac13\cdot1+\frac23\cdot\frac23=\frac79.$$ この独立性を原文は明記していない。たとえば $(P,Q)$ の行先を $B\mapsto A,C\mapsto C,D\mapsto D$ と対応させる結合なら各点の周辺分布は一様だが $p_1=1/3$。対応を $B\mapsto C,C\mapsto D,D\mapsto A$ とすれば同じ周辺分布のまま $p_1=1$。そのため以下は独立性を補った場合の答えである。

(3) 同じ頂点から出発すると、独立な行先が一致する確率は $3/9=1/3$ なので $P(d_{n+1}=1\mid d_n=0)=2/3$。異なる頂点を $A,B$ とすれば、行先候補はそれぞれ $\{B,C,D\},\{A,C,D\}$。一致する組は $(C,C),(D,D)$ の2組だから $P(d_{n+1}=1\mid d_n=1)=7/9$。従って $$\displaystyle P(d_1+d_2=1)=\frac29\cdot\frac23+\frac79\cdot\frac29=\frac{26}{81}.$$

(4) 遷移確率から $$\displaystyle p_{n+1}=\frac23(1-p_n)+\frac79p_n=\frac23+\frac19p_n.$$ $p_0=1$ であり、定常値は $3/4$。よって $$\displaystyle p_n-\frac34=\frac19\left(p_{n-1}-\frac34\right),\qquad p_n=\frac34+\frac{1}{4\cdot9^n}\quad(n\ge0).$$

設問(1)でPが1つの頂点にいる場合、Qはt=0にBから出発し、t=1にはA,C,Dのいずれかにいる。(i) P=CならA,Dが距離1なので2通り。(ii) P=BならA,C,Dの3か所すべてが距離1なので3通り。

ただし(2)以降の確率は、本文の各点ごとの周辺確率だけでは一意に定まらない。以下では、各時刻にP,Qが行き先を互いに独立に選び、次時刻の選択は現在までの履歴に依存しないと仮定する。(1)の初期1ステップで、Pの行先B,C,DとQの行先A,C,Dをそれぞれ1/3で対応させる結合を考えると、対応B→A,C→C,D→Dでは$p_1=1/3$、対応B→C,C→D,D→Aでは$p_1=1$となり、いずれも各点の行先は一様である。従って独立性の仮定が必要である。

独立選択の下では、Pの行先がB,C,Dのいずれも確率1/3。P=BのときQの3候補はいずれも距離1、P=C,DのときはQの候補のうち2か所が距離1である。よって p_1=(1/3)·1+(2/3)·(2/3)=7/9。

距離が0の状態では両点は同じ頂点から出発し、それぞれ残る3頂点を一様に選ぶので、次に同じ頂点となる確率は1/3、従って距離1となる確率は2/3。距離1の状態をP=A,Q=Bとして一般性を失わずに考えると、行先候補はそれぞれ{B,C,D},{A,C,D}である。2点が同じ頂点に着くのは(C,C),(D,D)の2通り、全9通りが同確率なので、次も距離1である確率は7/9。したがって $\displaystyle p_{n+1}=(1-p_n)\cdot\frac23+p_n\cdot\frac79=\frac23+\frac19p_n$。

初期状態はAとBで距離1だから $p_0=1$。定常値は3/4であり、漸化式から $\displaystyle p_n-\frac34=(p_0-\frac34)\cdot9^{-n}$。従って $\displaystyle p_n=\frac34+\frac{1}{4\cdot9^n}$。また、p_1=7/9、$\displaystyle \Pr(d_2=1\mid d_1=0)=\frac23$、$\displaystyle \Pr(d_2=1\mid d_1=1)=\frac79$より、$\displaystyle \Pr(d_1+d_2=1)=\frac29\cdot\frac23+\frac79\cdot\frac29=\frac{26}{81}$。