$k$-th minimum in a circle

智商亟需拯救。 \(\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 反应速度大不如前。

智商亟待拯救。