Random Max 题解

· · 题解

\text{Statement}

设随机变量 X_1, X_2, \dots, X_n 分别在区间 [L_1, R_1], [L_2, R_2], \dots, [L_n, R_n] 上均匀分布，求 \max(X_1, X_2, \dots, X_n) 的期望值。

\text{Solution}

令 \max X 为代表 \max(X_1, X_2, \dots, X_n) 的随机变量。同时设 F(x) = \Pr[\max X \le x] 为 \max X 的累积分布函数（CDF）。令 \max X 的概率密度函数（PDF）为 P(x)。由变量的取值非负，且 PDF 的积分为 CDF，我们可以导出使用 CDF 表示 E[\max X] 的方式：

& E[\max X] \\ = \ & \int_{0}^{\infty} yP(y) \text d y \\ = \ & \int_{0}^{\infty} \int_{0}^{y}P(y) \text dx \text d y \\ = \ & \int_{0}^{\infty} \int_{x}^{\infty}P(y) \text d y\text d x \\ = \ & \int_{0}^{\infty}\left( 1 - \int_{0}^{x}P(y) \text d y \right) \text d x \\ = \ & \int_{0}^{\infty}1 - F(x) \text d x \end{aligned}

我们记 \max X 的取值上界为 R = \max\left\{R_i\right\}。重写答案为

R - \int_{0}^{R} F(x) \text d x

这样只需要在 [0,R] 的范围内考察 F。

我们发现，\max X \le x，当且仅当 \forall X_i \le x。因此 \max X 的 CDF 应当是各个 X_i 的 CDF f_i 的乘积：

F(x) = \Pr [\max X \le x] = \prod_{i=1}^n \Pr [X_i \le x] = \prod_{i=1}^n f_i(x)

而 f_i(x) 是易表出的：

\begin{aligned} & 0 && x\le L_i \\ & \frac{x - L_i}{R_i - L_i} && L_i \le x \le R_i \\ & 1 && x \ge R_i \\ \end{aligned} \right . 注意到我们可以通过将 $[0, R]$ 以 $L_i, R_i$ 为间隔分为 $O(n)$ 个段，从大到小进行处理。如果扫到一个 $L_i$，则无需接着进行，因为这其中定有一个元素为 $0$，之后的 $F(x)$ 定为 $0$。 注意到加入一段等于是给当前的 $F(x)$ 乘入了一个度数为 $1$ 的多项式，且 $F(x)$ 初始时 $=1$，因此 $F$ 在任何时刻也是多项式。我们在移动段时只需要乘入 $\frac{x - L_i}{R_i - L_i}$ 即可。 需要注意的是，我们对每段 $[l, r]$ 考虑的积分是 $$ \int_{l}^{r}1 - F(x) \text d x = (r - l) - \int_{l}^{r}F(x) \text d x $$ 由于 $F$ 为多项式，直接做即可。 计算结果乘入 $(n+1)! \times \prod_{i=1}^n (R_i - L_i)$ 即为最终答案。 总时间复杂度为 $O(n^2)$。 [Submission](https://atcoder.jp/contests/hhkb2020/submissions/37455737).