车祸

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$ ?

解析

按初始位置从前到后扫描，形成新车队当且仅当遇到“目前最慢”的新速度（记录最小值）。

随机互异速度下，这等价于随机排列中记录最小值个数，其期望为调和数

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

故

\mathbb{E}[K]=H_{10}=\frac{7381}{2520}\approx 2.928968.