等车问题

转自view-source:http://www.cnblogs.com/jmp0xf/p/2014AlibabaWaiting_Bus.html

20. 有 A 和 B 两路公交车，平均发车间隔分别为 5 分钟和 10 分钟。某乘客在站点 S 可以 任意选择两者之一乘坐，假定 A 和 B 到达 S 的时刻无法确定，那么该乘客的平均等待时间约为____。

A、1 分钟 20 秒     B、3 分钟 20 秒     C、2 分钟 30 秒     D、1 分钟 40 秒

首先，平均等待时间即为等待时间的期望，形式上我们有式子

$$ E[t]=\int \intD min(tA, tB) p(tA,tB)  d tA  d tB$$

 $tA, tB$ 均为随机变量，对应相应公车到达的剩余时间；$min(tA, tB)$ 对应着理性乘客假设，即该乘客一定会上先来的那辆车，那么等车时间就是等待先来的那辆车花去的时间；$p(tA,tB)$ 为 $tA, tB$ 的联合概率密度；$D$ 为积分区域，也即 $p(tA,tB)$ 不为 $0$ 的区域。

     倘若发车间隔为固定时间，而“A 和 B 到达 S 的时刻无法确定”，那么在没有其他信息的情况下，可认为 $tA$ 在区间 $[0,5)$ 上均匀分布，而 $tB$ 在区间$[0,10)$ 上均匀分布，又不妨假设$tA, tB$相互独立，因此在如左图矩形积分区域( $tA\in [0, 5)$$, tB\in [0, 10)$ )中，$p(tA,tB)=p(tA)p(tB)=1/50$。图中虚线可以看作是等高线，区域内的高就是需要积分的值 $min(tA, tB)$。红色虚线为纵向，表示其所在区域( $tA<tB$ )的值为 $tA$；蓝色虚线为横向，表示其所在区域( $tB<tA$ )的值为 $tB$。

    分析到这里，想象力好的同学应该可以直接从左图看出结果来。这个地方由于积分区域概率密度处处相等为常数，原二重积分可以转化为求空间体积，然后除以积分区域面积。图中点虚线将积分区域分成上下两部，且具有相等的累积概率。若将积分区域的值看作高，那么上半部分是一个三角柱，其体积等于一半棱长为5的正立方体，即125/2。下半部分是一个四棱椎，其体积相当于三分之一棱长为5的正立方体（为什么是三分之一？一个立方体可以切出三个四棱椎，然后根据<a href="http://zh.wikipedia.org/zh-cn/%E7%A5%96%E6%9A%85%E5%8E%9F%E7%90%86" target="blank">祖暅原理可以知道这三个椎体体积相等），即125/3。于是

　　　　　　平均等待时间 $E[t]=(125/2+125/3)/50=25/12=2\frac{1}{12}$

如果老老实实积分就是这样算

$$E[t]=\frac{1}{50}\left( \int0^5 \int{tB}^5 tB  d tA  d tB+\int0^5 \int{tA}^5 tA  d tB  d tA+\int0^5 \int5^{10} tA  d tB  d tA\right)=\left( \dfrac{125}{6}+\dfrac{125}{6}+\dfrac{125}{2}\right)\dfrac{1}{50}=\dfrac{25}{12}=2\dfrac{1}{12}$$

    发车间隔不固定，那么 $tA, tB$ 的值域变为$[0, +\infty)$，随之而来的是另一个问题，概率密度分布是什么样的？此时值域不再有限，无法使用均等分布。注意这里问题的关键字是等待，说起等待，首先就应该想到<a href="http://zh.wikipedia.org/zh-cn/%E6%B3%8A%E6%9D%BE%E5%88%86%E4%BD%88" target="blank">泊松分布（Poisson Distribution）和泊松过程（Poisson process）。这里，等车的过程就可以看作两个相互独立的泊松过程。泊松过程的平稳独立增量假设十分重要，这意味着从任意时刻开始分布都是一样的，也就是说并不存在等待越久公车更可能即将到来这件事情。由此，泊松过程中，两次事件中的间隔时间服从指数分布，即

$$t \sim \lambda e^{-\lambda t}, t\geqslant 0$$

平均间隔时间即期望间隔时间$E[t]=\int0^{+\infty} t\lambda e^{-\lambda t}  d t=\dfrac{1}{\lambda}        (1)$

由这个结论加上已知可得$tA \sim \frac{1}{5} e^{-\frac{1}{5} tA}, tA\geqslant 0;  tB \sim\frac{1}{10} e^{-\frac{1}{10} tB}, tB\geqslant 0$

那么仍然根据独立假设，可得$p(tA, tB)=\frac{1}{5}e^{-\frac{1}{5}tA} \frac{1}{10}e^{-\frac{1}{10}tB},  tA\geqslant 0, tB\geqslant 0$

$\displaystyle{E[t]=\int0^{+\infty} \int{tB}^{+\infty} tB \frac{1}{5}e^{-\frac{1}{5}tA} \frac{1}{10}e^{-\frac{1}{10}tB}  d tA  d tB+\int0^{+\infty} \int{tA}^{+\infty} tA \frac{1}{5}e^{-\frac{1}{5}tA} \frac{1}{10}e^{-\frac{1}{10}tB}  d tB  d tA}$

$\displaystyle{=\int0^{+\infty} tB \frac{1}{10}e^{-\frac{1}{10}tB}e^{-\frac{1}{5}tB}  d tB+\int0^{+\infty} tA \frac{1}{5}e^{-\frac{1}{5}tA}e^{-\frac{1}{10}tA}  d tA}$

$\displaystyle{=\int0^{+\infty}x\left ( \frac{1}{5}+\frac{1}{10} \right ) e^{-\left (\frac{1}{5}+\frac{1}{10}\right ) x}  dx}$

$\displaystyle{=\frac{1}{\frac{1}{5}+\frac{1}{10}}}$    根据式$(1)$

$=3\dfrac{1}{3}$

也即3分钟20秒，选B。

另外上述积分推出了一个比较妙的结果，就是两个相互独立的泊松过程一起作用后可以看作一个新的泊松过程，并且其率参数（rate parameter）为相应两子过程率参数的和。有了这个结论，我们可以快速得到不同数值条件同类问题的答案。

在笔试中，比较直觉和取巧一点儿的方法是：如果只有A路，则平均等待时间就是5分钟。容易想到增加一路平均发车间隔也为5分钟的公车将使平均等待时间减半即2分钟30秒。则增加一路平均发车间隔为10分钟的公车将使平均等待时间落在两分半和五分钟之间，所以选择B。

还有一小撮别有用心的人使用一个神奇的方法，即每5分钟来辆A车，每10分钟来辆B车，平均下来每10分钟可来3辆车，于是平均等待时间为10/3=3分20秒。对于此种解法，我只能。。。

呵呵。。