车队合并（Car Fleet）：最终簇数期望

Car Crash

专题: Probability / 概率
难度: L6
来源: QuantQuestion

题目详情

有 $N$ 名员工各自开车上班，车辆初始间距足够大，且每辆车速度互不相同并随机分配。

当一辆更快的车追上更慢的车时，它会降速并以慢车速度行驶，从而形成车队（cluster）。经过足够长时间，所有车辆会形成 $K$ 个速度不同的车队。

当 $N=10$ 时，求 $\mathbb{E}[K]$ 。

$N$ employees are driving their individual cars on their way to work at QuantEssential. All cars are reasonably spaced apart, and they all travel at distinct speeds which are randomly assigned. When a faster car catches up to a slower car, it assumes the slower car's speed. After a very long period of time has passed, all $N$ cars have settled into $K$ clusters traveling at distinct speeds. What is the expected value of $K$ when $N = 10$ ?

解析

把车辆按初始位置从前到后排序。最终每个车队对应于“从前往后扫描时遇到的新最慢速度”（记录最小值）。

在随机互异速度的假设下，这等价于随机排列中“记录最小值（record lows）”的个数，其期望为调和数

\mathbb{E}[K]=H_N=\sum_{i=1}^{N}\frac{1}{i}.

因此

\mathbb{E}[K]=H_{10}=1+\frac12+\cdots+\frac{1}{10}\approx 2.928968.