0%

抢红包问题

原知乎回答

前言

两年前一位姚班大神学长回到高中母校并出了这样一道题:抢红包。

个人抢价值 元的红包,手气最佳同学抢到的红包的期望是多少?

注意这里是最大值,而最大值问题其实要比最小值问题难。当时我硬用积分和一些奇技淫巧给出了最小值的解答——
。而后大神给出了一个非常漂亮的解答,在这个解答中给出了任意排名的红包期望值。

为了尽量严谨化题意,他给出了一个等价的问题:

一段长为 的环形绳子,随机地切 刀,最长的一段长度的期望是多少?

“红包”的题面有一定歧义,因为我们没法很好定义怎么让
个人均匀地抢;而这个问题是良定义的,因为我可以良定义每一刀的均匀性——只要这一刀的概率密度在整根绳上均匀分布就可以了。

题主的问题相较于绳子版本的问题,相当于已经切好了第一刀——无论第一刀怎么切,环状绳子都会变成一段线状绳子,而这就和“玻璃棒”是等价的了。我们只需要一个额外假设——玻璃棒每一处断裂的可能性(在某种测度意义下)都是均等的——就可以说,题主的问题和绳子问题是等价的了。

题外话:我猜这个问题是受毕导一篇关于抢红包的文章的启发而来的。都是清华的大佬,想必在学术问题上也一定有很多交流吧(?


形式化题意

我们令 代表玻璃棒碎片的第 段的长度是多少。

概率密度函数在概率空间

给出的 维多面体(如果读者熟悉的话,也就是单纯形)中是均匀分布的。从而,我们要研究的就变成了
的值是多少。

至于为什么是均匀分布的,这里加以不太严谨地简单说明:

我们令 代表在环状绳子上切的第 刀的位置,那么, 就是均匀分布的。我们令
代表从
开始顺时针排列下每一段的绳长的计算函数。那么不难验证,这个函数是分 段线性的,而每一段恰好对应一种
的大小顺序关系(也就是每一段绳子的起点和终点到底对应第几刀),且每一段几乎都是一个双射。而线性函数总是将均匀分布映射到均匀分布。


漂亮的构造

这是 中保证 大小顺序的一个子多面体。显然,对于 之间大小顺序的
种情况都是对称的,所以我们只要考虑在
$\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不等式,第二个不等号对应均值不等式。取等条件由三个不等号的取等条件共同给出:第三个不等号告诉我们每一行只有一个非零元,第一个不等号告诉我们每一行都是正交的向量,即每行的非零元对应的列都不一样,第二个不等号告诉我们第
行的非零元满足 是一个常量,从而易知
(因为现在行列式的绝对值等于每个非零元的乘积)。也就是 必须是我们给出的例子
的差分矩阵只交换列得到的。从而每一个满足要求的 都可以通过我们给出的例子交换一些列来得到。这刚好对应了几何直观:
维单纯形的 个顶点的排列。