東京工業大学 1989年 理系 第5問 解説

方針・初手

(1)は、確率の漸化式を立てる典型問題である。$k$回目の試行後に「相異なる数字が$r$個」となる状態が、$k-1$回目の試行後のどのような状態から遷移するかを場合分けして考える。 (2)は、期待値の定義式と(1)で求めた確率の漸化式を組み合わせることで、$E_k$に関する漸化式を導出する方針が基本となる。両辺に$r$を掛けてシグマをとり、うまく変形して$E_{k-1}$を作り出す。また、期待値の線形性を利用する見通しの良い別解も考えられる。

解法1

(1) $k$回目の試行を終えた時点で相異なる数字が$r$個記録されている事象は、次の2つの排反な事象のいずれかが起こる場合である。

(i)

$k-1$回目の試行までに相異なる数字が$r$個記録されており、$k$回目にその$r$個の数字のいずれかを取り出す場合。 その確率は $\frac{r}{n} P(S_{k-1}=r)$ である。

(ii)

$k-1$回目の試行までに相異なる数字が$r-1$個記録されており、$k$回目にそれらと異なる数字を取り出す場合。 箱の中にはまだ記録されていないカードが $n-(r-1) = n-r+1$ 枚あるので、その確率は $\frac{n-r+1}{n} P(S_{k-1}=r-1)$ である。

これらは互いに排反であるから、求める確率はこれらの和となる。

$$ P(S_k=r) = \frac{r}{n} P(S_{k-1}=r) + \frac{n-r+1}{n} P(S_{k-1}=r-1) $$

(2) (1)で求めた等式の両辺に $r$ を掛け、$r=1$ から $k$ まで和をとると、

$$ \sum_{r=1}^k r P(S_k=r) = \sum_{r=1}^k \frac{r^2}{n} P(S_{k-1}=r) + \sum_{r=1}^k \frac{r(n-r+1)}{n} P(S_{k-1}=r-1) $$

左辺は $E_k$ の定義そのものである。右辺を変形して $E_{k-1}$ をくくり出す。 右辺第1項は、$P(S_{k-1}=k) = 0$ であることに注意すると、和の上端を $k-1$ にしても値は変わらない。

$$ \sum_{r=1}^k \frac{r^2}{n} P(S_{k-1}=r) = \frac{1}{n} \sum_{r=1}^{k-1} r^2 P(S_{k-1}=r) $$

右辺第2項について、$r-1=j$ とおくと $r=j+1$ であり、$r=1$ のとき $P(S_{k-1}=0)=0$ となるため和は $j=1$ から $k-1$ まで考えればよい。

$$ \sum_{r=1}^k \frac{r(n-r+1)}{n} P(S_{k-1}=r-1) = \frac{1}{n} \sum_{j=1}^{k-1} (j+1)(n-j) P(S_{k-1}=j) $$

文字を $r$ に揃えてまとめると、

$$ \begin{aligned} E_k &= \frac{1}{n} \sum_{r=1}^{k-1} r^2 P(S_{k-1}=r) + \frac{1}{n} \sum_{r=1}^{k-1} (r+1)(n-r) P(S_{k-1}=r) \\ &= \frac{1}{n} \sum_{r=1}^{k-1} \{ r^2 + (r+1)(n-r) \} P(S_{k-1}=r) \\ &= \frac{1}{n} \sum_{r=1}^{k-1} (rn-r+n) P(S_{k-1}=r) \\ &= \frac{n-1}{n} \sum_{r=1}^{k-1} r P(S_{k-1}=r) + \sum_{r=1}^{k-1} P(S_{k-1}=r) \end{aligned} $$

ここで、期待値の定義より $\sum_{r=1}^{k-1} r P(S_{k-1}=r) = E_{k-1}$ であり、全確率の総和は $\sum_{r=1}^{k-1} P(S_{k-1}=r) = 1$ であるから、

$$ E_k = \frac{n-1}{n} E_{k-1} + 1 $$

となる。この漸化式を変形すると、

$$ E_k - n = \frac{n-1}{n} (E_{k-1} - n) $$

$1$回目の試行では必ず$1$種類の数字が出るので $E_1 = 1$ である。 よって、数列 $\{E_k - n\}$ は初項 $E_1 - n = 1 - n$、公比 $\frac{n-1}{n}$ の等比数列となる。

$$ \begin{aligned} E_k - n &= (1-n) \left( \frac{n-1}{n} \right)^{k-1} \\ &= -n \cdot \frac{n-1}{n} \left( \frac{n-1}{n} \right)^{k-1} \\ &= -n \left( \frac{n-1}{n} \right)^k \end{aligned} $$

したがって、求める期待値は

$$ E_k = n \left\{ 1 - \left( 1 - \frac{1}{n} \right)^k \right\} $$

解法2

(2)の別解として、和の期待値は期待値の和になる性質（期待値の線形性）を利用する。

$i=1, 2, \dots, n$ について、確率変数 $X_i$ を次のように定める。 $k$回の試行の中に数字 $i$ が1回でも出れば $X_i=1$、1回も出なければ $X_i=0$ とする。 記録された相異なる数字の個数 $S_k$ は、これら $X_i$ の総和として表される。

$$ S_k = \sum_{i=1}^n X_i $$

両辺の期待値をとると、

$$ E_k = E(S_k) = \sum_{i=1}^n E(X_i) $$

数字 $i$ が1回も出ない確率は、毎回の試行で $i$ 以外の $n-1$ 枚のいずれかを取り出す確率なので $\left( \frac{n-1}{n} \right)^k$ である。 よって、数字 $i$ が少なくとも1回出る確率は $1 - \left( \frac{n-1}{n} \right)^k$ である。 したがって、$X_i$ の期待値は

$$ E(X_i) = 1 \cdot \left\{ 1 - \left( \frac{n-1}{n} \right)^k \right\} + 0 \cdot \left( \frac{n-1}{n} \right)^k = 1 - \left( 1 - \frac{1}{n} \right)^k $$

これはすべての $i$ について等しい値をとるから、

$$ \begin{aligned} E_k &= \sum_{i=1}^n \left\{ 1 - \left( 1 - \frac{1}{n} \right)^k \right\} \\ &= n \left\{ 1 - \left( 1 - \frac{1}{n} \right)^k \right\} \end{aligned} $$

解説

(1)はマルコフ連鎖的な状態遷移を立式する基本操作である。手前の状態と確率を掛け合わせることで、漸化式を構成できる。 (2)の解法1は、(1)の誘導に忠実に乗った「確率の漸化式から期待値の漸化式を作る」定石手法である。シグマ計算において、添字のずれに注意して式を整理する処理能力が問われる。 解法2で用いた「指示関数（指標変数）」を利用した期待値の計算は、入試数学における強力な武器である。各事象が互いに独立であるかどうかにかかわらず「和の期待値は期待値の和」となる性質を利用することで、複雑なシグマ計算を大幅にショートカットできる。難関大で期待値が出題された際には、解法2のような視点を持っておくと検算も含めて非常に有利になる。

答え

(1)

$$ P(S_k=r) = \frac{r}{n} P(S_{k-1}=r) + \frac{n-r+1}{n} P(S_{k-1}=r-1) $$

(2)

$$ E_k = n \left\{ 1 - \left( 1 - \frac{1}{n} \right)^k \right\} $$