一、问题

【题目】在自然数\(\{1,2,\cdots,N\}\)中随机抽取\(n\)个样本，求最小的\(k\)个样本的平均值的期望。

【定义】为方便讨论，记样本为\(\{X_1,X_2,\cdots,X_n\}\)，大小排在第\(k\)位的样本记为\(X_{(k)}\)。

注1：需要分别讨论放回抽样和不放回抽样两种情况。

注2：本问题由瓦屋青衣提供。

二、不放回抽样解法

2.1 普通解法（不放回抽样）

【预备知识】由隔板法可知，将\(N+2\)个小球分成\(n+2\)组（每组至少有一个小球），相当于在\(N+1\)个缝隙中插入\(n+1\)个隔板，共有\(\binom{N+1}{n+1}\)种分法。

同时，也可以这样考虑本问题。首先，任选一个\(k\in\{0,1,\cdots,n\}\)，先在第\(i\)个缝隙插入一个隔板，使得隔板左边至少有\(k\)个缝隙，隔板右边至少有\(n-k\)个缝隙，所以\(i\)的取值范围是\(\{k,k+1,\cdots,N-n+k\}\)，从中选定一个\(i\)后，在第\(i\)个缝隙左侧插入\(k\)个隔板，从第\(i\)个缝隙右侧插入\(n-k\)个隔板，将所有小球分为\(n+2\)组，分法有\(\binom{i}{k}\binom{N-i}{n-k}\)，遍历所有的\(i\)，就是将\(N+2\)个小球分成\(n+2\)组的方法数，所以

\[ {\color{green}\binom{N+1}{n+1}=\sum_{i=k}^{N-n+k}\binom{i}{k}\binom{N-i}{n-k}\quad k\in\{0,1,\cdots,n\}} \]

注1：当\(k=n\)时，上等式便是朱世杰恒等式的一种特殊形式。

注2：这是自己独立推导得到的，算是个人小发现，不过前人应该早已发现。

与上面的二项式系数公式相比，其在二项式的第一个系数变化；类似的还有“二项式系数的范德蒙卷积公式”，其在二项式的第二个参数变化，参见《组合数学》Richard A. Bruald，P97：

\[ \sum\limits_{k=0}^n\binom{m_1}{k}\binom{m_2}{n-k}=\binom{m_1+m_2}{n} \]

【解题】在不放回抽样情况下，所有样本共有\(\binom{N}{n}\)种可能，大小排在第\(k\)位的样本\(X_{(k)}=i\)，等价于在\(n\)个样本中有\(k-1\)个样本小于\(i\)、有1个样本等于\(i\)、有\(n-k\)个样本大于\(i\)，所以概率\(P(X_{(k)}=i)\)等于

\[ P(X_{(k)}=i)=\begin{cases} \begin{align}\frac{\binom{i-1}{k-1}\cdot1\cdot\binom{N-i}{n-k}}{\binom{N}{n}}\end{align}, & i\in\{k,k+1,\cdots,N-n+k\}\\ 0, & \text{else} \end{cases} \]

所以\(X_{(k)}\)的期望为

\[ \begin{align} E(X_{(k)})&=\sum_{i=k}^{N-n+k}iP(X_{(k)}=i)\\ &=\sum_{i=k}^{N-n+k}i\frac{\binom{i-1}{k-1}\cdot1\cdot\binom{N-i}{n-k}}{\binom{N}{n}}\\ &=\sum_{i=k}^{N-n+k}\frac{k\binom{i}{k}\binom{N-i}{n-k}}{\binom{N}{n}}\\ &=\frac{k}{\binom{N}{n}}\sum_{i=k}^{N-n+k}\binom{i}{k}\binom{N-i}{n-k}\\ &{\color{green}\Downarrow\text{利用前面的公式}\Downarrow}\\ &=\frac{k}{\binom{N}{n}}\binom{N+1}{n+1}\\ &={\color{blue}\frac{k(N+1)}{n+1}}\\ \end{align} \]

所以，最小的\(k\)个样本的平均值的期望为

\[ E(\frac{X_{(1)}+X_{(2)}+\cdots+X_{(k)}}{k})=\frac{E(X_{(1)})+E(X_{(2)})+\cdots+E(X_{(k)})}{k}={\color{blue}\frac{(k+1)(N+1)}{2(n+1)}} \]

2.2 巧妙解法（不放回抽样）

设排序后的样本为\(X_{(1)},X_{(2)},\cdots,X_{(n)}\)，构造新的统计量：

\[ \begin{align} y_1&=X_{(1)}-0\\ y_2&=X_{(2)}-X_{(1)}\\ y_3&=X_{(3)}-X_{(2)}\\ &\cdots\\ y_n&=X_{(n)}-X_{(n-1)}\\ y_{n+1}&=N+1-X_{(n)}\\ &\Downarrow\\ \sum_{i=1}^{n+1}y_i&=N+1 \end{align} \]

由于是不放回抽样，所以任意两个相邻样本之间的距离都有同样多种可能（1至N-n+1），而每种可能性是均等的，按相同的取值范围补上端点后即为上述统计量\(y_1,y_2,\cdots,y_{n+1}\)，因此这些统计量是同分布的\(y_i\sim Y\)，所以：

\[ E(Y)=\frac{1}{n+1}\sum_{i=1}^{n+1}y_i=\frac{N+1}{n+1} \]

所以第\(k\)个样本的期望为：

\[ E(X_{(k)})=E(y_1+y_2+\cdots+y_k)=kE(Y)={\color{blue}\frac{k(N+1)}{n+1}} \]

所以前\(k\)个样本的均值的期望为：

\[ E(\frac{X_{(1)}+X_{(2)}+\cdots+X_{(k)}}{k})=\frac{E(X_{(1)})+E(X_{(2)})+\cdots+E(X_{(k)})}{k}={\color{blue}\frac{(k+1)(N+1)}{2(n+1)}} \]

注：这一巧妙方法由于llc提供。

三、放回抽样解法

3.1 普通解法（放回抽样）

对于放回抽样，由于任意想个相邻样本的距离的分布不再相同，所以不能使用上面的方法求解。不过，抽出的\(n\)个样本\(X\)的分布都是相同的：

\[ P(X=i)=\frac{1}{N},\quad i\in\{1,2,\cdots,N\} \]

注意：这里不能直接使用次序统计量的公式，这是由于在公式推导过程中，要求只有一个观察值落入区间\([y_k,y_k+dy)\)之中。

第\(k\)个样本\(X_{(k)}\)值小于等于\(i\)的概率，等价于在\(n\)次伯努力实验中至少有\(i\)个样本小于等于\(x\)，即（定义\(0^0=1\)，下同）

\[ P(X_{(k)}\le i; N, n)=\sum_{j=k}^n \binom{n}{j}\left(\frac{i}{N}\right)^j\left(\frac{N-i}{N}\right)^{n-j},\qquad 1\leqslant k\leqslant n\leqslant N,\;1\leqslant i\leqslant N \]

所以

\[ P(X_{(k)}=i;N,n)=\begin{cases} \sum_\limits{j=k}^n \binom{n}{j}\left(\frac{i}{N}\right)^j\left(\frac{N-i}{N}\right)^{n-j}, & i=1\\ \sum_\limits{j=k}^n \binom{n}{j}\left[\left(\frac{i}{N}\right)^j\left(\frac{N-i}{N}\right)^{n-j}-\left(\frac{i-1}{N}\right)^j\left(\frac{N-i+1}{N}\right)^{n-j}\right], & i\in\{2,3,\cdots,N\} \end{cases} \]

所以

\[ \begin{align} E(X_{(k)})&=\sum_{i=1}^n i P(X_{(k)}=i;N,n)\\ &=P(X_{(k)}=1;N,n)+\sum_{i=2}^n i P(X_{(k)}=i;N,n)\\ &=\sum_{j=k}^n \binom{n}{j}\left(\frac{1}{N}\right)^j\left(\frac{N-1}{N}\right)^{n-j}+ \sum_{i=2}^n \sum_{j=k}^n \binom{n}{j}i\left[\left(\frac{i}{N}\right)^j\left(\frac{N-i}{N}\right)^{n-j}-\left(\frac{i-1}{N}\right)^j\left(\frac{N-i+1}{N}\right)^{n-j}\right] \end{align} \]

尚未完成化简工作，未完待续……