随机游走004 | 等公交车问题，Do it right now or never ？

0. 引言

本科的时候我们的教学楼和宿舍不在一个园区，往返的方式大致有步行、乘坐公交车、骑自行车三类。其中骑自行车车自然是最快捷的一种方式，但遇上冬天天冷风大，或是下雨天时，往往会考虑其他两种通勤方式。乘坐公交车大概是3分钟路程，速度最快，但缺点是要等，等待时间存在一定的不确定性，甚至因为校门口排队等公交的人太多了，你必须等到第二辆公交车才能上车；而步行大概是12分钟路程，纯速度而言最慢。

于是，每次中午放学走出校门时，看着公交站一群排队等车的同学，我便陷入了一阵纠结。是排队等公交车会公寓？还是步行回公寓？如果我等了一会儿公交车没来，我是应该继续等待，还是走人？

在Ross的随机过程教材中，我找到了一个把这个问题抽象为了有关愿意等待时间/(s/)的决策问题的习题。

1. 模型

假设从公交站到公寓步行需要/(W/)时间，公交车从公交站到公寓需要/(R/)时间，按照统计学中的传统假定，到达公交站的公交车数是一个泊松过程，不妨假设其速率是/(/lambda/)，那么公交车到站的间隔时间/(/tau/)便是均值为/(1//lambda/)的指数随机变量。等车策略是，我愿意为公交车等待/(s/)时间，如果/(s/)时间内等到公交车，我就乘坐公交车会公寓；如果/(s/)时间内没等到公交车，我就步行回公寓。

记我到公交站后等公交车的时间为随机变量/(T/)，由于指数分布具有无记忆性，那么假设在我到达公交站之前，上一辆公交车已经离开公交站/(/tau_0/)时间了，有/(P(T>t)=P(T>t|/tau>/tau_0)P(/tau>/tau_0+t|/tau>/tau_0)=P(/tau>t)/)，等车时间/(T/)也是均值为/(1//lambda/)的指数随机变量。

记我总的返回公寓时间为/(H/)，则根据我的等待策略有：

/[H=/begin{cases}W+s,&T>s//R+T,&T/leq s/end{cases}
/]

如果我足够“理性”，我的最优目标应该是最小化我的期望返回时间/(E[H]/)。

2. 策略

首先计算/(E[H]/)，/(E[H]/)是一个关于意愿等待时间/(s/)的函数。

/[/begin{align*}E[H]&=E[(W+s)I_{/{T>s/}}]+E[(R+T)I_{/{T/leq s/}}]//
&=(W+s)P(T>s)+/int_0^s(R+T)f(T)dT//&=(W+s)e^{-/lambda s}+/int_0^s(R+T)(1-/lambda e^{-/lambda T})dT//&=R+1//lambda+(W-R-1//lambda)e^{-/lambda s},/quad s/geq0.
/end{align*}
/]

由于

/[/frac{/part E[H]}{/part s}=-/lambda(W-R-1//lambda)e^{-/lambda s},
/]

那么，若/(W<R+1//lambda/)，/(/part E[H]//part s>0/)，/(E[H]/)关于/(s/)单调递增，/(/arg/min_{s/geq0}E[H]=0/)；

若/(W>R+1//lambda/)，/(/part E[H]//part s<0/)，/(E[H]/)关于/(s/)单调递减，/(/arg/min_{s/geq0}E[H]=/infty/)；

若/(W=R+1//lambda/)，/(/part E[H]//part s=0/)，/(E[H]/equiv R+1//lambda/)。

于是，我们的最佳等待策略只需要考虑/(s=0/)或者/(s=/infty/)的情况即可。从期望的角度来说，步行耗时/((W)/leq/)乘车耗时/((R)/)+期望等车时间/((1//lambda)/)，我就选择步行会公寓；否则就选择一直等待，知道等到车为止。如果我对/(W,R,1//lambda/)一无所知，我要知道只有两种策略可能能达最短的返回时间——要么一直等公交，要么一秒也不在公交站停留。

3. 反思

等公交问题似乎在告诫我们一个道理，“Do it right now or never !”——要么做，要么永远不做。当我已经在公交站等待/(s_0/)时间时，由于/(T/)的无记忆性，继续等下去/(T-s_0|T/geq s_0/)的期望仍然是/(1//lambda/)，因此如果此时离开/((s=s_0)/)，则/(E[H|T/geq s_0]=W+s_0>W/)，自然不如一开始就不等公交车(/(s=0/))；而若继续等待/((s=/infty/),s.t./(s>s_0,/forall s_0/geq0)/)，则/(E[H|T/geq s_0]=s_0+1//lambda+R/)，才有可能使得/(E[H|T/geq s_0]<W/)。

然而，“理性人考虑边际收益，忽略沉没成本”，当我已经在公交站等待了一段时间/(s_0/)后，我是否一定要坚持等下去呢的理由呢？实际上，这事问题转化为求/(/arg/min_{s/geq s_0}E[H|T>s_0]/)，同样因为指数分布的无记忆性，我们只需考虑/(s=s_0/)或/(s=/infty/)的情况即可。也就是说在等待了任意长的时间后，我们的决策还是两个，要走，要么继续等，都有可能最小化此时的期望返回时间。

/[/min_{s/geq s_0} E[H|T/geq s_0]=/begin{cases}W+s_0&W<R+1//lambda//s_0+1//lambda+R&W/geq R+1//lambda/end{cases}
/]

特别是如果在等待过程中，你理清了/(W,R,/lambda/)的关系，发现/(W<R+1//lambda/)，那么根据期望最小原则，就应该不再等待公交车。当/(s_0=0/)时，有以下特例：

/[/min_{s/geq 0} E[H]=/begin{cases}W&W<R+1//lambda//1//lambda+R&W/geq R+1//lambda/end{cases}
/]

也许，下次当我遇到类似的等公交车问题时，我会提前算好/(W、R、1//lambda/)，然后根据最小化期望原则，一次性制定是否等待公交车的策略。当然，我们的模型是真实世界的抽象，还存在一些局限性：

1. 实际中我们的效用函数不一定是期望，可能更加复杂；
2. /(W/)、/(R/)可能不是常数，而是随机变量；
3. 公交车的到达可能满足一个非齐次泊松过程，或者是一个更一般的更新过程；
4. 即使假设完全正确，决策还是可能不是最优的，因为它只能达到期望最优/概率最优。

最后总结一句，这个模型主要涉及到泊松过程/指数分布的无记忆性、条件期望计算。之所以不存在一个大于0的有限最优等待时间，是因为从期望的角度出发，若此刻还没等到车时，则等到车的期望时间不会随着已等时间的延长而缩短。但是，也正因为指数分布的无记忆性，在任意一个还没等到车的时刻，你选择不再等待、步行返回，都有可能是此时的最佳选择。