一车道追尾成团的期望数

N 转车

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

题目详情

Initially, there are $N$ cars on a one- lane highway, spaced far apart. They all start driving at the same time in the same direction. Each car drives at a constant speed, with their speeds being random and independent from each other. In the beginning, all the cars have different speeds; however, when a faster car approaches a slower one, it gets stuck behind it and starts driving at the speed of the slower car. After a certain time, all the cars get separated into several clusters, with all the cars within the same cluster driving at the same speed. What is the expected number of clusters?

解析

车辆速度独立且连续分布。最终每个簇的头车是该簇最慢车。

设簇数为 $C_N$ ，令 $\alpha_N=\mathbb{E}[C_N]$ 。最慢车出现在第 $k$ 辆的概率为 $1/N$ 。

在“第 $k$ 辆最慢”条件下，其后方 $k-1$ 辆最终并入该簇，前方 $N-k$ 辆的结构与规模 $N-k$ 的问题同分布，因此

\mathbb{E}[C_N\mid \text{最慢在 }k]=1+\alpha_{N-k}.

取期望得递推并解出

\boxed{\mathbb{E}[C_N]=\sum_{k=1}^N\frac{1}{k}}.