网格相遇：两人相向随机行走

Meeting on a Grid

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

题目详情

Alan 在 $(0,0)$ ，Barbara 在 $(4,4)$ 。

每分钟：

Alan 以相等概率向上或向右走 1 格（若在边界则只能走不会离开 0..4×0..4 的方向）。
Barbara 类似，但以相等概率向下或向左走 1 格（边界同理）。

问：两人在到达各自的对角点之前相遇的概率是多少？

Alan is sitting at $(0,0)$ and Barbara is sitting at $(4,4)$ . Each minute, Alan moves up or to the right one unit with equal probability, unless he is on the border of the $4 \times 4$ grid centered at $(2,2)$ , in which case he moves in the only possible direction that keeps him within range. Barbara behaves similarly, but moves down or to the left instead. What is the probability that the two meet before they reach the opposite corner?

解析

两人每分钟同时走一步。设第 $t$ 分钟后 Alan 在 $(i, t-i)$ （其中 $i$ 为前 $t$ 步向右次数），Barbara 在 $(4-L, L)$ （其中 $L$ 为前 $t$ 步向左次数）。

若两人相遇，则必须满足

(i, t-i)=(4-L, L).

由第二个坐标得 $t-i=L$ ，代入第一个坐标 $i=4-L$ 得 $t=4$ 。

因此他们只能在第 4 步结束时相遇。

第 4 步内两人都不会被边界强迫改变随机性，所以 $i\sim\mathrm{Bin}(4,1/2)$ 、 $L\sim\mathrm{Bin}(4,1/2)$ 且独立。

相遇条件为 $i+L=4$ ，概率为

\sum_{k=0}^{4}\frac{\binom{4}{k}}{16}\cdot\frac{\binom{4}{4-k}}{16} =\frac{\sum_{k=0}^{4}\binom{4}{k}^2}{256} =\frac{\binom{8}{4}}{256}=\frac{70}{256}=\frac{35}{128}.

所以答案为 $\boxed{35/128}$ 。