1,2,...,nからm個をランダムに取ってきたときの最小値の平均値

事の発端

事の発端は、塾で教えている生徒から来た、ある問題に関する質問でした。

　 $100$ 個の数字 $1,2,\cdots\cdots,100$ から $3$ 個の数を任意に選んだとき、最小の数の平均値はいくつか。

僕がすぐに考えた解法は、期待値の定義どおり、ある数 $k$ が最小の数となる確率を求めて $k$ との積を取り、和を取る方法です。ただ、これをやってみると…

いま、1から100のうち、最小の数となりうるのは1から98である。この範囲のある整数を $k$ とおき、最小の数が $k$ となる確率を求めると、最小でない残り2枚を $k+1$ 以上 $100$ 以下の数から選ぶ確率なので $\displaystyle \frac{{}_{100-k}C_2}{{}_{100}C_3}$ である。よって求める期待値は
　 $\displaystyle E[k]=\frac1{{}_{100}C_3} \displaystyle \sum_{k=1}^{98}k\ {}_{100-k}C_2$
となる。

$\sum$ の中は $k$ の3次式なので手計算は一応可能で、実際に計算すると $\displaystyle \frac{101}4$ となります。ただ、この問題がもともと穴埋め式の問題だったことと、最後の答えが綺麗に $\displaystyle \frac{100+1}{3+1}$ になっていたので、何かもっと綺麗な解法があるのではないかとTwitterに助けを求めました。すると、非常に様々な解法が寄せられました。 togetter.com

最終的にこれだ、というものがあったので、その解法と地道に計算する方法、2通りの解法を紹介します。

せっかくなので一般化

先ほどの問題だと具体的すぎるので、ここから先は一般化して次の問題を考えます。

　 $n$ 個の数字 $1,2,\cdots\cdots,n$ から $m$ 個の数を任意に選んだとき、最小の数の平均値はいくつか（ただし、 $n\geq m$ とする）。

コンビネーションをガリ ガリ計算する方法

まずは先ほどと同様に定義どおり計算します。最小の数となりうる整数 $k$ について、最小の数が $k$ となる確率は、最小でない残り $m-1$ 枚を $k+1$ 以上 $n$ 以下の $n-k$ 枚から選ぶ確率なので $\displaystyle \frac{{}_{n-k}C_{m-1}}{{}_{n}C_{m}}$ となります。これを用いて期待値は
　 ${ \begin{align} E[k]&=\frac1{{}_nC_m}\sum_{k=1}^{n-m+1}k\ {}_{n-k}C_{m-1}\\ &=\frac1{{}_nC_m}\sum_{k=1}^{n-m+1}\{(n+1)-(n-k+1)\}{}_{n-k}C_{m-1}\\ \end{align} }$
と立式できます。ここで、
　 ${ \begin{align} (n-k+1){}_{n-k}C_{m-1}&=(n-k+1)\ \frac{(n-k)!}{(m-1)!(n-k-m+1)!}\\ &=m\ \frac{(n-k+1)!}{m!(n-k-m+1)!}\\ &=m\ {}_{n-k+1}C_{m} \end{align} }$
を用いることで、上の期待値は
　 $\displaystyle E[k]=\frac1{{}_nC_m} \sum_{k=1}^{n-m+1}\{ (n+1)\ {}_{n-k}C_{m-1}-m\ {}_{n-k+1}C_m \}$
と書き直すことができます。さてここでいったん、 $\displaystyle \sum_{i=k}^l{}_iC_k$ を考えます。二項係数の性質
　 ${}_iC_k+{}_iC_{k+1}={}_{i+1}C_{k+1},\ {}_kC_k={}_{k+1}C_{k+1}=1$
を繰り返し用いれば、
　 $\displaystyle{ \begin{align} \sum_{i=k}^l{}_iC_k &= {}_kC_k+{}_{k+1}C_k+{}_{k+2}C_k+{}_{k+3}C_k+\cdots+{}_lC_k\\ &= {}_{k+1}C_{k+1}+{}_{k+1}C_k+{}_{k+2}C_k+{}_{k+3}C_k+\cdots+{}_lC_k\\ &= {}_{k+2}C_{k+1}+{}_{k+2}C_k+{}_{k+3}C_k+\cdots+{}_lC_k\\ &= {}_{k+3}C_{k+1}+{}_{k+3}C_k+\cdots+{}_lC_k\\ &= {}_lC_{k+1}+{}_lC_k\\ &= {}_{l+1}C_{k+1} \end{align} }$
となることがわかります。これを $E[k]$ の $\sum$ の第1項には $k=m-1,\,l=n-1$ として、第2項には $k=m,\,l=n$ として代入することで、
　 $\displaystyle { \begin{align} E[k]&=\frac1{{}_nC_m}\{(n+1)\,{}_nC_m-m\,{}_{n+1}C_{m+1}\}\\ &=n+1-m\,\frac{{}_{n+1}C_{m+1}}{{}_nC_m}\\ &=(n+1)\left(1-\frac{m}{m+1}\right)\\ &=\frac{n+1}{m+1} \end{align}}$
が導出できました（ふう……）。

もっとエレガントに解く方法

さすがに二項係数の計算は疲れます。もっと直感的な解法はないのでしょうか。もう一度問題を見てみましょう。

　 $n$ 個の数字 $1,2,\cdots\cdots,n$ から $m$ 個の数を任意に選んだとき、最小の数の平均値はいくつか（ただし、 $n\geq m$ とする）。

いま、適当に選ばれた $m$ 個の数字を小さい順に $x_1,x_2,\cdots\cdots,x_m$ とします（ただし、 $x_1\geq 1,\,x_{i+1}\geq x_i+1,\, x_m\leq n$ ）。
いま、これらの差に着目して $m+1$ 個の数字 $y$ を、
　 $y_1= x_1,\ y_i=x_i-x_{i-1}\,(2\leq i\leq m),\ y_{m+1}=n+1-x_m$
によって定めます。このとき、 $(x_1,x_2,\cdots\cdots,x_m)$ と $(y_1,y_2\cdots\cdots,y_{m+1})$ は1対1に対応します。
　 $y_1+y_2+\cdots\cdots+y_{m+1}=n+1$
が常に成立すること、および最小値 $x_1=y_1$ に注意すると、以下のように問題が言い換えられることがわかります。