步行过红绿灯的最佳策略

KeyTo9_Fans

我要去的终点需要过$n$条打横的马路和$m$条打竖的马路，如下图所示：



下图是$n=1$、$m=1$的简单例子：



由于马路中间有围栏无法穿过，所以我只能在十字路口走斑马线过马路。

每个十字路口的信号灯都是交替地  允许/禁止  东西方向/南北方向  通行（不允许走对角线），

并且信号灯上有倒计时，明确指示还有多少时间改变通行方向。

为了将问题简化，我们假设：

1. 所有的十字路口的东西方向和南北方向的通行时长是相等的，

2. 两个方向的通行可以无缝切换，也就是两边都不允许通行的时长忽略不计，

3. 马路不宽，而且我过马路很快，所需时长忽略不计。

每在十字路口过完一条马路，我可以根据另一条马路的倒计时，决定等待这个倒计时然后通过，还是直接前行到下一个十字路口。

假设我是无法提前预测下一个十字路口的信号灯状态的，只能走到下一个十字路口，才能看清楚两边的信号灯状态和倒计时。

也就是信号灯的状态处于一个周期里的任一时刻的概率是均匀分布的，并且每个十字路口的信号灯状态相互独立。

我希望采取最佳策略过马路，使得停下来等待的总时长的期望值最小，并且过马路的次数必须为$(n+m)$。

问：

当$n$和$m$都很大的时候（例如：$n=m=5*10^7$），最佳策略下停下来等待的总时长的期望值是多少？

#####

我目前只知道贪心的策略，也就是哪条斑马线可以通行，就过那条斑马线，

于是$(10^8-10^4)$条马路都无需等待，直接通过了，

但是最后的$10^4$条马路就只剩一个方向可以走了，于是就只能干等信号灯了，

所以等待时间的期望值是$10^4/4$次变灯的时间。

不知道最佳策略下，这个期望值能优化到什么级别。

希望坛友们能和我一起来解决这个有趣的问题。

mathe

为简化模型起见，假设每个路口每经过单位时间会均匀变换一下，而每个路口余下的时间显示为单位时间的百分比，如果到达一个路口，总是一个方向是绿灯，另外一个方向显示余下时间为(0,1)中均匀分布的的一个数字。
需要横穿m个路口，竖穿n个路口的等待平均等待时间为E(m,n). 于是显然E(0,n)=n/2,E(m,0)=m/2.
而对于m>n>0,那么如果横向是绿灯，纵向是红灯，显示时间为p,那么他横穿期望时间为E(m-1,n), 纵穿期望时间为E(m,n-1)+p,
于是我们可以得知，在p>E(m,n-1)-E(m-1,n)时，需要选择横穿，不然选择纵穿。同样如果纵向是绿灯，横向是红灯，有类似结论。
由此可以得出:
如果$1+E(m-1,n)>E(m,n-1)>E(m-1,n)$
那么$E(m,n)=1/2 E(m-1,n)+1/2((1-(E(m,n-1)-E(m-1,n)))E(m-1,n)+\int_0^{E(m,n-1)-E(m-1,n)} (p+E(m,n-1))dp )=(2-E(m,n-1)+E(m-1,n))/2 E(m-1,n)+(E(m,n-1)-E(m-1,n))^2/2+(E(m,n-1)-E(m-1,n)) E(m,n-1)$
交换两者关系有类似结论，而余下部分选择时间短的方向，同样可以计算出结果。
于是后面就是一个递归计算的过程了。

KeyTo9_Fans

我手算出来的结果好像有点差异，边界好像是$n/4$、$m/4$次变灯时间。

然后好像每个方格的四个角都需要标上时间，需要用$E_0(m,n)$、$E_1(m,n)$、$E_2(m,n)$、$E_3(m,n)$来表示，

不能简单地用$E(m,n)$表示，具体情况如下图所示：



还有没有别的问题，我暂时不确定。

KeyTo9_Fans

我把每个方格的四个角都算了一个期望时间，

然后用递推的方法，编程求出了当$n=m=7200$时，

最佳策略下停下来等待的总时长的期望值是$2.527189$次变灯的时间。

据此可以拟合出$n=m$时，最佳策略下停下来等待的总时长的期望值是${ln(n+1)+1.226}/4$次变灯的时间。

而“哪边能走就走哪边”的策略，则需要等待${\sqrt(2n)}/4$次变灯的时间，比最佳策略差了很多。

至于最佳策略为啥如此之优秀，我目前是完全想不通的。

我之前一直以为，最佳策略大概只比“哪边能走就走哪边”的策略少等一半的时间，

但没想到程序求出来的等待时间竟如此之小，比${\sqrt(2n)}/4$小了无穷多倍。

如果程序没错的话，就需要一个直观的解释，为啥$n$和$m$都增加$1$之后，等待时间只增加$1/{4n}$，而不是增加$1/{4\sqrt(2n)}$。

不知道谁可以解释清楚这个增量呢？