II慶應義塾大学 2000年 数学 第II問解答・解説

(1) 1回目の出目が $v$ である確率は $1/6$。2回目に $v$ から1へ進む出目は $1-v\pmod 7$ であり、$v=3,4,5,6$ のときそれぞれ $5,4,3,2$ だから、いずれも確率は $1/6$。従って $\Pr(x_1=v,x_2=1)=1/36$。

(2) 1から $n-1$ 回までAを訪れていないとする。その時点の頂点はAの外にあり、次の一歩でAの2頂点へ進む確率は $2/6=1/3$、Aの外に留まる確率は $4/6=2/3$ である。よって $$\displaystyle p_n=\frac13\left(\frac23\right)^{n-1}.$$ その期待値は等比級数の微分から $$\displaystyle \sum\limits _{n=1}^{\infty}np_n=\frac13\sum\limits _{n=1}^{\infty}n\left(\frac23\right)^{n-1}=\frac13\cdot\frac{1}{(1-2/3)^2}=3.$$

(3) Aを初めて訪れる時刻が $n$ である確率は $p_n$。その前にBを訪れていない場合、Aを避けているため頂点2は未訪問で、頂点3も未訪問である。従って時刻 $n-1$ まで $\{1,2,3\}$ を避ける必要がある。各段階でこの集合の外に留まる確率は $3/6=1/2$、最後にAへ進む確率は $1/3$。この補集合の確率は $\displaystyle \frac13(\frac12)^{n-1}$ だから、求める確率は $$\displaystyle \frac13\left\{\left(\frac23\right)^{n-1}-\left(\frac12\right)^{n-1}\right\}.$$

(4) $U_i$ を時刻iまで $\{1,2,3\}$ を一度も訪れない確率、$V_i$ を時刻iまでに頂点1または3の一方だけを訪れ、まだ両条件がそろっていない確率とする。初期値は $U_0=1,V_0=0$。外側の状態から外側に留まる確率は $1/2$、1または3の一方へ入る確率は $1/3$。Vの状態から完了せずVに留まる確率は $2/3$ なので $$\displaystyle U_{i+1}=\frac12U_i,\qquad V_{i+1}=\frac13U_i+\frac23V_i.$$ これを解くと $U_i=(1/2)^i$、$V_i=2\{(2/3)^i-(1/2)^i\}$。時刻iでUから次に完了する確率は $1/6$（頂点2へ進む場合）、Vから完了する確率は $1/3$（頂点2または未訪問側の1/3へ進む場合）である。従って最初に両条件を満たす時刻がnである確率は $$\displaystyle \frac16U_{n-1}+\frac13V_{n-1}=\left(\frac23\right)^n-\left(\frac12\right)^n.$$

各サイコロの出目 $1,\ldots,6$ は、現在位置以外の6頂点への一様な遷移を与える。$(1)$ 指定された2段の出目の確率を掛ける。$(2)$ $A$ 外の各頂点から次の1歩で $A$ に入る確率は $2/6=1/3$ なので、$\displaystyle p_n=\frac13(\frac23)^{n-1}$、期待値は $3$。$(3)$ $T_A=n$ の確率から、前段まで $B$ を訪れない経路を引く。その経路は $A\cup B$ を避けて $C=\{0,4,5,6\}$ に残るので、確率は $\displaystyle \frac13(\frac12)^{n-1}$。$(4)$ $A,B$の両方を時刻 $n$ までに訪れた確率 $F_n$ を包除原理で求め、$F_n-F_{n-1}$ を取る。