11千葉大学 2018年 数学 第11問解答・解説

問題のカードの位置だけに注目し、位置を上から数えた番号で表す。対象カードが位置 $r>1$ にあるとき、先頭の別のカードを取り除くと対象カードは位置 $r-1$ になる。そのカードを対象カードより上に入れる $r-1$ 通りでは対象カードは位置 $r$ に戻り、下に入れる $n-r+1$ 通りでは位置 $r-1$ にとどまる。対象カードが位置1にあるときは、そのカード自身を移すので、移動後の位置は1から (n) まで等確率である。

$C_1$ は初め位置1にあるため、1回後の位置は各々確率 $1/n$ である。この一様分布が次の試行後にも保たれることを確かめる。位置1に来る確率は、直前に位置1または位置2にある場合を合わせて $$\displaystyle \frac1n\cdot\frac1n+\frac1n\cdot\frac{n-1}{n}=\frac1n.$$ 位置 $\ell$（$2\le\ell\le n$）に来る確率は、直前に位置1、位置 $\ell$、位置 $\ell+1$ にある場合を合わせて $$\displaystyle \frac1n\left(\frac1n+\frac{\ell-1}{n}+\frac{n-\ell}{n}\right)=\frac1n,$$ ただし $\ell=n$ では最後の項は0である。したがって一様分布は各試行で保たれる。よって $$\displaystyle P(2,\ell)=\frac1n,\qquad P(k,\ell)=\frac1n\quad(k\ge1).$$

次に $C_2$ を考える。初め位置2にあり、位置2にいる間は、次の試行で確率 $1/n$ で位置2にとどまり、確率 $(n-1)/n$ で位置1に移る。位置1に移った次の試行で $C_2$ 自身が移され、その後の位置は一様となり、以後もその分布が保たれる。

$k$ 回後にまだ位置2にとどまる確率は $n^{-k}$、ちょうど $k$ 回目に初めて位置1へ移る確率は $(n-1)n^{-k}$ である。また、$k-1$ 回目以前に位置1へ移り、その次の試行で一様分布になった確率は $$\displaystyle \sum\limits _{s=1}^{k-1}\frac{n-1}{n^s}=1-n^{-(k-1)}.$$ したがって $$\displaystyle Q(k,\ell)=\frac{1-n^{-(k-1)}}n+n^{-k}\mathbf 1_{\{\ell=2\}}+(n-1)n^{-k}\mathbf 1_{\{\ell=1\}}\quad(k\ge1).$$ これを $\ell$ ごとに整理すると $$\displaystyle Q(k,\ell)=\begin{cases} \dfrac1n+\dfrac{n-2}{n^k}&(\ell=1),\\[2pt] \dfrac1n&(\ell=2),\\[2pt] \dfrac1n-\dfrac1{n^k}&(3\le\ell\le n). \end{cases} \quad(k\ge1).$$