车队合并：最终簇数期望

Car Crash

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

题目详情

有 $N$ 名员工各自开车上班，车辆初始间距足够大，且每辆车速度互不相同并随机分配。更快的车追上更慢的车后会降速并以慢车速度行驶。经过很久， $N$ 辆车会形成 $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}=\frac{7381}{2520}\approx 2.928968.