车祸

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.