一、问题

【题目】在自然数$\{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} $$

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