前言
两年前一位姚班大神学长回到高中母校并出了这样一道题:抢红包。
个人抢价值 元的红包,手气最佳同学抢到的红包的期望是多少?
注意这里是最大值,而最大值问题其实要比最小值问题难。当时我硬用积分和一些奇技淫巧给出了最小值的解答——
。而后大神给出了一个非常漂亮的解答,在这个解答中给出了任意排名的红包期望值。
为了尽量严谨化题意,他给出了一个等价的问题:
一段长为
的环形绳子,随机地切 刀,最长的一段长度的期望是多少?
“红包”的题面有一定歧义,因为我们没法很好定义怎么让
个人均匀地抢;而这个问题是良定义的,因为我可以良定义每一刀的均匀性——只要这一刀的概率密度在整根绳上均匀分布就可以了。
题主的问题相较于绳子版本的问题,相当于已经切好了第一刀——无论第一刀怎么切,环状绳子都会变成一段线状绳子,而这就和“玻璃棒”是等价的了。我们只需要一个额外假设——玻璃棒每一处断裂的可能性(在某种测度意义下)都是均等的——就可以说,题主的问题和绳子问题是等价的了。
题外话:我猜这个问题是受毕导一篇关于抢红包的文章的启发而来的。都是清华的大佬,想必在学术问题上也一定有很多交流吧(?
形式化题意
我们令
概率密度函数在概率空间
给出的
至于为什么是均匀分布的,这里加以不太严谨地简单说明:
我们令
开始顺时针排列下每一段的绳长的计算函数。那么不难验证,这个函数是分
的大小顺序关系(也就是每一段绳子的起点和终点到底对应第几刀),且每一段几乎都是一个双射。而线性函数总是将均匀分布映射到均匀分布。
漂亮的构造
令
这是
种情况都是对称的,所以我们只要考虑在
$\textbf {E}{x \in S} [\min \lbrace x_i \rbrace] = \textbf {E}{x \in S} [x_n]$ 的值是多少。
最关键的一步:构造线性双射:
$$
f : \Delta \rightarrow S,
t \mapsto \left(
\displaystyle\sum_{k=i}^n \frac{t_k}{k} \right)i = \left( t_1 + \dfrac{1}{2} t_2 + \dots + \dfrac{1}{n} t_n,
\dfrac{1}{2} t_2 + \dots + \dfrac{1}{n} t_n,
\dots,
\dfrac{1}{n-1} t{n-1} + \dfrac{1}{n} t_n, \dfrac{1}{n} t_n
\right)
$$
用矩阵来表达,就是
容易验证
我们发现,随机变量
那么,对于题主最小值的问题,有
$$
\textbf {E}{x \in S} [x_n]
= \textbf {E}{t \in \Delta} \left[ \dfrac{1}{n} t_n \right]
= \dfrac{1}{n} \textbf {E}_{t \in \Delta} [t_n]
= \dfrac{1}{n} \cdot \dfrac{1}{n} = \dfrac{1}{n^2}
$$
而对于原题最大值的问题,有
$$
\textbf {E}{x \in S} [x_1]
= \textbf {E}{t \in \Delta} \left[ \displaystyle\sum_{i=1}^{n}\dfrac{t_i}{i} \right]
= \displaystyle\sum_{i=1}^{n} \dfrac{1}{i} \textbf {E}{t \in \Delta} [t_i]
= \displaystyle\sum{i=1}^{n} \dfrac{1}{i} \cdot \dfrac{1}{n}
= \dfrac{1}{n} \displaystyle\sum_{i=1}^{n} \dfrac{1}{i}
$$
但是要注意原题红包总额是
更进一步
这个构造十分精妙。但是,读者也许会不禁疑惑:这个构造看起来很随意,它是唯一的吗?
维的单形,也就是这样的双射,只需给定每个顶点是怎样被映射的,就可唯一确定。也就是说,
我们从代数角度说明为什么它是几乎唯一的。
令
必须满足三个性质:
非负且单调不增(需要每一个变元都单调不增)
第一条性质保证了
的部分;第三条性质保证了
的体积是一样的,那么只能恰好为
由性质二,不妨设
从而三条性质等价地变化为
(指每个矩阵元非负)
则
$$
\begin{align*}
|\det M| &\le \prod_{i=1}^n |M_i|2 \
&= \frac{1}{n!} \prod{i=1}^n |i M_i|2 \
&\le \frac{1}{n!} \left( \frac{\sum{i=1}^n |i M_i|2}{n} \right)^n \
&\le \frac{1}{n!} \left( \frac{\sum{i=1}^n \sum_{j=1}^n i M_{ij}}{n} \right)^n \
&= \frac{1}{n!} \left( \frac{\sum_{j=1}^n 1}{n} \right)^n \
&= \frac{1}{n!} \left( \frac{n}{n} \right)^n \
&= \frac{1}{n!}
\end{align*}
$$
第一个不等号对应Hadamard不等式,第二个不等号对应均值不等式。取等条件由三个不等号的取等条件共同给出:第三个不等号告诉我们每一行只有一个非零元,第一个不等号告诉我们每一行都是正交的向量,即每行的非零元对应的列都不一样,第二个不等号告诉我们第
(因为现在行列式的绝对值等于每个非零元的乘积)。也就是
的差分矩阵只交换列得到的。从而每一个满足要求的