题目

题目大意

随机变量 $x_1, \dots, x_n$，$x_i$ 在区间 $[L_i, R_i]$ 上均匀分布。试求 $\max x_i$ 的期望。

数据范围

• $n \le 1000$
• $0 \le L_i < R_i \le 10^9$
• $L_i, R_i$ 都是整数

分析

首先，$\max x_i$ 的取值范围是 $[\max L_i, \max R_i]$。
其次，$\Pr(\max x_i \le x) = \prod_{i:x \le R_i} \frac{x - L_i}{R - L_i}$。
令 $L = \max L_i$，$R = \max R_i$，有
\begin{aligned}
E(\max x_i) &= \int_L^R x \dif \Pr(\max x_i \le x) \\
&= x\Pr(\max x_i \le x)|_L^R - \int_L^R \Pr(\max x_i \le x) \dif x \\
&= R - \int_L^R \Pr(\max x_i \le x) \dif x
\end{aligned}
于是问题归为计算定积分 $\int_L^R \Pr(\max x_i \le x) \dif x$。
比较方便的办法是从 $R$ 到 $L$ 分段计算 $\Pr(\max x_i \le x)$ 的表达式，再进行积分。时间复杂度 $O(n^2)$。

总结

上述计算过程可以推广。若随机变量 $X$ 在区间 $[L, R]$ 上取值，其累积分布函数是 $F(x):= \Pr(X\le x)$，$g(X)$ 随机变量 $X$ 的一个函数，则 $E(g(X)) := \int_L^R g(x)\dif F(x) = g(R) - \int_L^R F(x) \dif g(x)$。