随机速度车队行驶问题

问题描述:在公路上有N辆朝着同一方向行驶的汽车,所有汽车的速度是由独立同分布的随机变量产生的,且行驶过程中速度保持不变,如果一辆汽车追及上了其前面的车,这两辆车会形成车队以较慢车的速度继续行驶,两个车队追及上时也会继续合并成更大的车队,试问时间足够长以后公路上期望会剩下多少个不同的车队?

答案\sum_{i=1}^N\frac{1}{i}

Solution

比较关键的idea或许只有一步:由于汽车的速度是独立同分布的随机数,且追及上与否在时间足够长时只与速度间的大小关系有关,因此可以将所有汽车的速度按顺序看作1,2,\cdots,N的排列.

考虑一下为什么最终会分成不同的车队,这是因为更靠后的车队无法追及上前面的车队,那么最终靠后的车队带头的车速一定小于最终靠前的车队带头的车速,注意到每个车队中带头的车肯定是整个车队原始速度最慢的车,这意味着最终靠后的车队带头的车速小于其前面所有车的初始速度.

稍微有点绕,不过这里已经可以直接给出结论:最终每个车队带头的车,其速度一定是原始速度序列的前缀最小值(这里假设汽车是从前向后编号的).

那么原问题所求的就是1,2,\cdots,N的排列中不同的前缀最小值期望个数,第i个数成为前缀最小值的概率是\frac{1}{i},利用期望的线性性即得答案为\sum_{i=1}^N\frac{1}{i}.

Review

这个问题还算简单(我给别人讲起时都说是脑筋急转弯),做法也称不上很有新意或是趣味,可能唯一的亮点是我第一次看到这个问题(也是别人问起的我),脑海里立马闪过了\Theta(\log N)这个答案,再联想到调和级数,然后恍然大悟 🙂

“未见其人,先闻其声”,确实值得一记吧.

发表评论

您的电子邮箱地址不会被公开。