京都大学 2009年度 前期日程 第2次学力試験（数学理系乙）理系（乙）数学 第3問

番号 $n$ のカードより上にあるカードの枚数を $k$ とする。$k>0$ のとき、一番上のカードを取り除いた直後は上のカードが $k-1$ 枚になる。取り出したカードを番号 $n$ のカードより上へ戻す方法は $k$ 通り、下へ入れる方法は $n-k$ 通りである。したがって$$P(k\to k)={\displaystyle \frac{k}{n}},P(k\to k-1)={\displaystyle \frac{n-k}{n}}\mathrm{.}$$初めは $k=n-1$ であり、1回の試行で $k$ は高々1しか減らない。

まず、最初の $n-1$ 回で毎回 $k$ が1ずつ減る確率を $p$ とすると$$p={\displaystyle \frac{1}{n}}\cdot {\displaystyle \frac{2}{n}}\cdots {\displaystyle \frac{n-1}{n}}={\displaystyle \frac{(n-1)!}{n^{n-1}}}\mathrm{.}$$この後は番号 $n$ のカード自身が一番上にある。第 $n$ 回でこのカードを再び一番上へ戻す確率は $1\mathrm{/}n$ だから、この場合の確率は $p\mathrm{/}n$ である。

次に、第 $n$ 回で初めて $k=0$ となる場合を考える。この場合、$n$ 回のうち $n-1$ 回は $k$ が1減り、残る1回だけ正の状態 $k$ にとどまる。この停滞が状態 $k$ で起こる確率は、全て減る経路の確率 $p$ に $k\mathrm{/}n$ を掛けたものである。$k=1,2,\dots ,n-1$ を合計すると$$p\sum _{k=1}^{n-1}{\displaystyle \frac{k}{n}}=p{\displaystyle \frac{n-1}{2}}\mathrm{.}$$以上の2つの場合は互いに排反であり、これら以外には $n$ 回で $k=0$ になれない。したがって求める確率は$$\begin{array}{rl}{\displaystyle {\displaystyle \frac{(n-1)!}{n^{n-1}}}({\displaystyle \frac{1}{n}}+{\displaystyle \frac{n-1}{2}})}& {\displaystyle ={\displaystyle \frac{(n-1)!\{n(n-1)+2\}}{2n^n}}\mathrm{.}}\end{array}$$状態の移り方

状態は「番号 $n$ のカードより上にある枚数」。正の状態では，1回に0または1だけ減る。