n个随机区间中最大非重叠区间数量的期望及增长阶问题

嘿，这个问题挺有意思的！我来一步步给你拆解清楚：

我们的问题是：在[0,1]上独立生成n个随机区间（每个区间由两个均匀随机数作为端点，交换大小得到左小右大的区间），$T_n$是这些区间中最大的互不重叠子集的大小，我们要找$E[T_n]$的期望和它的增长阶。

核心结论：增长阶是Θ(√n) #

简单来说，$E[T_n]$和$\sqrt{n}$同阶增长——既不会像$n$那样线性增长，也不会慢到对数级别。下面具体解释原因：

1. 为什么不可能是O(n)？ #

这个很好理解：n个随机区间在[0,1]上的重叠程度极高。随便取[0,1]里的一个点$x$，覆盖$x$的区间数目期望是$n$乘以单个区间覆盖$x$的概率，也就是$n*(1/3)$（单个随机区间的期望长度是1/3）。当$n$很大时，每个点附近都被大量区间覆盖，根本不可能选出线性数目的互不重叠区间，所以$O(n)$肯定没戏。

2. 下界：$E[T_n]$至少是Ω(√n) #

我们可以构造一个简单的下界：把[0,1]分成$\lfloor\sqrt{n}\rfloor$个互不相交的小区域，每个区域长度约为$1/\sqrt{n}$。

对于每个小区域，落在它内部的区间（左右端点都在这个区域里）的数目期望是$n*(1/\sqrt{n})^2=1$，也就是每个小区域平均有1个区间。如果一个小区域里有至少一个区间，我们就能从中选一个——这些来自不同小区域的区间肯定互不重叠。

每个小区域有至少一个区间的概率大概是$1-e^{{-1}$（用泊松近似，期望为1的泊松变量取值≥1的概率），所以这样选出的区间数目期望约为$\sqrt{n}*(1-e}{-1})$，而$T_n$是最大非重叠子集，肯定不会比这个数目小，所以$E[T_n]≥Ω(\sqrt{n})$。

3. 上界：$E[T_n]$最多是O(√n) #

我们可以用贪心算法（按右端点从小到大排序，依次选不重叠的区间）来估计，因为贪心算法在区间图上能得到最大非重叠子集的大小。

利用线性期望的性质，$E[T_n]$等于$n$乘以单个区间被贪心算法选中的概率$p_n$。当$n$很大时，每个区间被选中的概率大概和$1/\sqrt{n}$成正比——因为同一个位置附近会有$O(\sqrt{n})$个区间竞争被选中，所以每个区间的选中概率是$O(1/\sqrt{n})$，相乘后$n*p_n=O(\sqrt{n})$。

更严谨的推导可以用柯西不等式：最大非重叠子集的大小$T_n$满足$(T_n)^2 ≤ \int_0^1 C(x)dx$，其中$C(x)$是覆盖点$x$的区间数目。而$\int_0^1 C(x)dx$的期望是$n*E[区间长度]=n/3$，所以$E[(T_n)^2] ≤ n/3$，再用柯西不等式$E[T_n]≤\sqrt{E[(T_n)^2]}≤\sqrt{n/3}$，这就得到了$O(\sqrt{n})$的上界。

关于期望的精确值 #

遗憾的是，$E[T_n]$没有特别简洁的闭合表达式，但当$n$很大时，它有渐近近似：$E[T_n] ~ c\sqrt{n}$，其中$c$是一个常数，比如通过积分计算可以得到$c≈0.9003$（精确值是$2\sqrt{2}/π$）。

备注：内容来源于stack exchange，提问作者allen i