智商亟需拯救。 $\newcommand{\D}[0]{\mathrm{d}}$

Problem

@fotile 问的一个题，我将题目改了下描述：

$n$ 个变量 $x_1, x_2, \dots, x_n$ ，满足 $0 \leq x_i$ 且 $\sum x_i = 1$ 。求 $x_i$ 中第 $k$ 小值的期望。

Solution

积分吧。

我们先考虑最小值。枚举最小值，求最小值的 pdf(概率密度函数) 就好了。

令最小值的 pdf 为 $f(n, x)$ ，由于时间关系（我还想睡觉）我就不说怎么求了（感觉比较好求）。

总之 balabala 可以得到

$$f(n, x) = n (n - 1) (1- n x)^{n-2}$$

然后考虑最小值。暴力积分可得

$$\begin{array}{rl} & \int*{0}^{\frac{1}{n}} x f(n, x) \D x \\ = & \int*{0}^{\frac{1}{n}} x n (n-1) (1-nx)^{n-2} \D x \\ = & \frac{n-1}{n} \int*{0}^{1} nx (1-nx)^{n-2} \D nx \\ = & \frac{n-1}{n} \int*{0}^{1} (1-x) x^{n-2} \D x \\ = & \frac{n-1}{n} (\frac{1}{n-1} - \frac{1}{n}) \\ = & \frac{1}{n^2} \end{array}$$

接下来就是求 $k$ 小值了。令 $g(n, k)$ 表示 $n$ 个变量， $k$ 小值的期望。还是暴力积分。枚举最小值 $x$ ，再把剩下所有数全部减去 $x$ 后，可以得到剩下若干个变量的和是 $1 - nx$ ，且这 $n - 1$ 个变量仍然是均匀分布的，第 $k - 1$ 小的期望是 $(1 - nx) g(n - 1, k - 1)$ ，再加上 $x$ ，就是减去 $x$ 前这 $n$ 个数中第 $k$ 小的期望，也就是：

$$\begin{array}{rl} & g(n, k) \\ = & \int*{0}^{\frac{1}{n}} (x + (1-nx) g(n - 1, k - 1)) f(n, x) \D x \\ = & \int*{0}^{\frac{1}{n}} x f(n, x) \D x + \int*0^{\frac{1}{n}} (1-nx) g(n - 1, k - 1) f(n, x) \D x \\ = & \frac{1}{n^2} + g(n - 1, k - 1) \int*{0}^{\frac{1}{n}} (n-1) (1-nx)^{n-1} \D x \\ = & \frac{1}{n^2} + \frac{(n - 1) g(n - 1, k - 1)}{n} \\ \end{array}$$

这样子是不好看的，于是还可以再化简一下：

$$n g(n, k) = \frac{1}{n} + (n-1) g(n - 1, k - 1)$$

聪明的同学把最小值的公式代入后发现 $g(n, k)$ 有一个 closed-form:

$$g(n, k) = \frac{1}{n} \sum*{i = n - k}^n \frac{1}{i} = \frac{H_n - H*{n - k}}{n}$$

不知道是否有问题……@fotile @wzy @dyh

nonsense

感觉这个方法不难，为啥我就想了好久呢 T_T 反应速度大不如前。

智商亟待拯救。