一、问题

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

【定义】为方便讨论，记样本为 ${X_{1}, X_{2}, \dots, X_{n}}$ ，大小排在第 $k$ 位的样本记为 $X_{(k)}$ 。

image-20220417183105477

注1：需要分别讨论放回抽样和不放回抽样两种情况。
注2：本问题由瓦屋青衣提供。

二、不放回抽样解法

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

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

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

$(\binom{N + 1}{n + 1}) = \sum_{i = k}^{N - n + k} (\binom{i}{k}) (\binom{N - i}{n - k}) k \in {0, 1, \dots, n}$

注1：当 $k = n$ 时，上等式便是朱世杰恒等式的一种特殊形式。
注2：这是自己独立推导得到的，算是个人小发现，不过前人应该早已发现。

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

$\sum_{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{aligned} \frac{(\binom{i - 1}{k - 1}) \cdot 1 \cdot (\binom{N - i}{n - k})}{(\binom{N}{n})} \end{aligned}, & i \in {k, k + 1, \dots, N - n + k} \\ 0, & else \end{cases}$

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

$\begin{aligned} E (X_{(k)}) & = \sum_{i = k}^{N - n + k} i P (X_{(k)} = i) \\ = \sum_{i = k}^{N - n + k} i \frac{(\binom{i - 1}{k - 1}) \cdot 1 \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}) \\ ⇓ 利用前面的公式 ⇓ \\ = \frac{k}{(\binom{N}{n})} (\binom{N + 1}{n + 1}) \\ = \frac{k (N + 1)}{n + 1} \end{aligned}$

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

$E (\frac{X_{(1)} + X_{(2)} + \dots + X_{(k)}}{k}) = \frac{E (X_{(1)}) + E (X_{(2)}) + \dots + E (X_{(k)})}{k} = \frac{(k + 1) (N + 1)}{2 (n + 1)}$

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

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

$\begin{aligned} y_{1} & = X_{(1)} - 0 \\ y_{2} & = X_{(2)} - X_{(1)} \\ y_{3} & = X_{(3)} - X_{(2)} \\ \dots \\ y_{n} & = X_{(n)} - X_{(n - 1)} \\ y_{n + 1} & = N + 1 - X_{(n)} \\ ⇓ \\ \sum_{i = 1}^{n + 1} y_{i} & = N + 1 \end{aligned}$

由于是不放回抽样，所以任意两个相邻样本之间的距离都有同样多种可能（1至N-n+1），而每种可能性是均等的，按相同的取值范围补上端点后即为上述统计量 $y_{1}, y_{2}, \dots, 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} + \dots + y_{k}) = k E (Y) = \frac{k (N + 1)}{n + 1}$

所以前 $k$ 个样本的均值的期望为：

$E (\frac{X_{(1)} + X_{(2)} + \dots + X_{(k)}}{k}) = \frac{E (X_{(1)}) + E (X_{(2)}) + \dots + E (X_{(k)})}{k} = \frac{(k + 1) (N + 1)}{2 (n + 1)}$

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

三、放回抽样解法

3.1 普通解法（放回抽样）

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

$P (X = i) = \frac{1}{N}, i \in {1, 2, \dots, N}$

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

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

$P (X_{(k)} \leq i; N, n) = \sum_{j = k}^{n} (\binom{n}{j}) {(\frac{i}{N})}^{j} {(\frac{N - i}{N})}^{n - j}, 1 ⩽ k ⩽ n ⩽ N, 1 ⩽ i ⩽ N$

所以

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

所以

$\begin{aligned} 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}) {(\frac{1}{N})}^{j} {(\frac{N - 1}{N})}^{n - j} + \sum_{i = 2}^{n} \sum_{j = k}^{n} (\binom{n}{j}) i [{(\frac{i}{N})}^{j} {(\frac{N - i}{N})}^{n - j} - {(\frac{i - 1}{N})}^{j} {(\frac{N - i + 1}{N})}^{n - j}] \end{aligned}$

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

统计趣题-前k个次序统计量的平均值的期望

李宣 • 2021 年 12 月 23 日

统计趣题-前k个次序统计量的平均值的期望

一、问题

二、不放回抽样解法

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

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

三、放回抽样解法

3.1 普通解法（放回抽样）

蒙提霍尔问题

[笔记]概率论与数理统计-第一章

特征函数与母函数

概率统计杂记

周期函数

辛普森悖论

一维随机游走第n步时距原点的平均距离

小偷的平均得手次数（风险与收益）

周期函数

平均要取多少个区间(0,1)中的随机数才能让它们的和超过1

统计趣题-前k个次序统计量的平均值的期望