问题描述

一个长度为 $1$ 的线段上随机撒 $n-1$ 个点，形成了 $n$ 条线段，那么这 $n$ 条线段中第 $k$ 短（ $k\leq n$ ）的线段期望长度是多少呢？答案是：

$\frac 1n \sum_{i=0}^{k-1} \frac 1{n-i}$
例如，

$n$ 条线段中最短的线段期望长度是

$\frac 1 {n^2}$ ，第二短的期望是

$\frac 1n (\frac 1n + \frac 1{n-1})$ ，依此类推。

事实上，这 $n$ 条线段期望的长度分布是指数分布，可以类比玻尔兹曼分布，少数较长的线段占据了大部分长度。而如果按照从左往右的顺序的话，每条线段长度都服从相同的概率分布，概率密度函数都是 $\displaystyle f(x) = (n-1) \cdot (1-x)^{n-2}$ 。

这里只证明第 $k$ 短的期望。推导过程很大一部分借鉴了这篇博客。当然北航也写过类似的题解：

[2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest](http://clatisus.com/2015-2016 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest)

cz_xuyixuan的题解

ccosi的题解

证明

我们采用数学归纳法的思路。

当 $k=1$ 时，我们先证明 $n$ 条线段中最短的线段期望长度是 $\frac 1 {n^2}$ 。

不妨考虑最短长度不小于 $x$ 时的概率如何求解。实际上相当于把每条线段都预留上 $x$ 的长度，剩下的就是一个随机分配的问题了，每条线段都有 $(1-nx)$ 的概率，即：

$P(L_{1} \geq x) = P(L_1\geq x,L_2\geq x,\cdots,L_n\geq x,L_1+L_2+\cdots+L_n=1) = (1-nx)^{n-1}$
求最短线段的期望长度就是这样一个积分：

$\begin{align} E(L_{1}) & = \int_0^{\frac 1n} xP(L_{1} = x) \textrm{d}x\ & = \int_0^{\frac 1n} P(L_{1} \geq x) \textrm{d}x \ & = \int_0^{\frac 1n} (1-nx)^{n-1} \textrm{d}x\ & = \frac 1{n^2} \end{align}$
由此，

$k=1$ 的情况得到了证明。

假设 $k=d$ 的情况，上述结论成立，我们考虑 $k=d+1$ 的情况。

求第 $d+1$ 短的期望长度，我们只需要先把最短的一段截走，之后就是对于 $n-1$ 条线段的第 $d$ 短的问题了。

$\begin{align} E(L_{d+1}) & = E(L_1)+(1-n\cdot E(L_1)) \cdot \frac{1}{n-1}\sum_{i=1}^d\frac 1{n-i} \ & = \frac{1}{n^2} + \frac{1}{n}\sum_{i=1}^d \frac 1{n-i} \ & = \frac 1n \sum_{i=0}^{d}\frac 1{n-i} \end{align}$
由此，命题得证。

例题 AGC 032F

你有一个大小为 $1$ 的圆形比萨，你首先将会切 $n$ 刀，每一刀都是随机一个 $[0,2\pi)$ 的角度 $\theta$ ，然后从圆心沿着水平方向逆时针 $\theta$ 的角度切下去。 $n$ 刀过后，比萨被切成了 $n$ 份。

之后，你可以选取面积之和最接近 $\frac 13$ 的连续的若干份比萨作为你的食物。问你吃到的比萨大小与 $\frac 13$ 的距离的期望是多少，即 $|x-\frac 13|$ 的期望。

题目链接

解答：

$ans = \sum_{i=1}^m \frac{1}{3^i \cdot n(n-i+1)}$

AC代码

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1, i##_end_ = (n); i <= i##_end_; ++i)
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

const int MOD = 1000000007, maxn = 1020000;
int muln(int x, int y) { return 1LL * x  * y % MOD; }
int qpow(int x, int y) {
    int ret = 1;
    for(; y; y >>= 1, x = muln(x, x))
        if(y & 1) ret = muln(ret, x);
    return ret;
}
int inv(int x) { return qpow(x, MOD - 2); }
int n, ans, i3 = inv(3), in, p3 = 1;

int main() {
    scanf("%d", &n);
    in = inv(n);
    for(int i = 1; i <= n; ++i) {
        p3 = muln(p3, i3);
        ans += muln(p3, muln(in, inv(n - i + 1)));
        if(ans >= MOD) ans -= MOD; 
    }
    printf("%d\n", ans);
    
    return 0;
}