京都大学 1998年度 後期日程 第2次学力試験理系（後期）数学 第5問

経路が存在するためには、ある$i$ $(1\leqq i\leqq n)$について$$A_1\to A_2\to \cdots \to A_i,A_i\to B_i,B_i\to B_{i+1}\to \cdots \to B_n$$のすべての横辺が通れればよい。

上段の横辺を左から見て、最初に×印が現れる位置を$t$とする。すなわち$1\leqq t\leqq n-1$のとき、上段の第1辺から第$t-1$辺までは矢印、第$t$辺は×印である。この確率は$$p^{t-1}(1-p)$$である。この場合、縦辺を上がる列は$i\leqq t$でなければならない。経路が存在するための必要十分条件は、下段の第$t$辺から第$n-1$辺までがすべて矢印であることであり、その確率は$p^{n-t}$である。$t$より左の下段の状態は問わない。

上段に×印が1つもない場合は確率$p^{n-1}$であり、列$n$で縦辺を上がれば必ず到達できる。従って$$\begin{array}{rl}{\displaystyle Q_n}& {\displaystyle =\sum _{t=1}^{n-1}{p}^{t-1}(1-p)p^{n-t}+p^{n-1}}\\ {\displaystyle }& {\displaystyle =(n-1)(1-p)p^{n-1}+p^{n-1}}\\ {\displaystyle }& {\displaystyle =p^{n-1}\{1+(n-1)(1-p)\}\mathrm{.}}\end{array}$$(1) 特に$$Q_2=p(2-p),Q_3=p^2(3-2p)\mathrm{.}$$(2)$$Q_n=p^{n-1}\{1+(n-1)(1-p)\}\mathrm{.}$$

下段で出発点から連続して進める長さと、上段で終点まで連続して進める開始位置を確率変数として比較する。最初の失敗位置で排反分解し、経路の和を数えずに求める。

(1)
$n=2$ のとき、下段または上段の横辺の少なくとも一方が矢印なら到達できるから$$Q_2=1-(1-p{)}^2=p(2-p)\mathrm{.}$$$n=3$ では、下段の最初の×が第1辺、第2辺、または下段に×がない場合へ分けると$$Q_3=(1-p)p^2+p(1-p)p+p^2=p^2(3-2p)\mathrm{.}$$(2)
下段 $A_1,A_2,\dots$ で最初に通れない横辺の番号を $T$ とする。$T=t$（$1\leqq t\leqq n-1$）とは、第1辺から第 $t-1$ 辺までが矢印、第 $t$ 辺が×であることであり、$$\mathrm{Pr}(T=t)=p^{t-1}(1-p)\mathrm{.}$$このとき下段から上段へ移れる最も右の列は $t$ である。従って経路が存在する必要十分条件は、上段の第 $t$ 辺から第 $n-1$ 辺までがすべて矢印であることである。その条件付き確率は$$p^{n-t}\mathrm{.}$$上下の横辺は独立なので、この場合の寄与は$$p^{t-1}(1-p)p^{n-t}=(1-p)p^{n-1}\mathrm{.}$$これは $t=1,\dots ,n-1$ の各場合で同じである。

下段に×がない場合は確率 $p^{n-1}$ で、列 $n$ で上がれば必ず到達できる。従って$$\begin{array}{rl}{\displaystyle Q_n}& {\displaystyle =(n-1)(1-p)p^{n-1}+p^{n-1}}\\ {\displaystyle }& {\displaystyle =p^{n-1}\{1+(n-1)(1-p)\}\mathrm{.}}\end{array}$$