Symmetry and Relative motion

一维醉鬼走路问题：现在有两个人同时从原点出发，每一次每个人往左走和往右走的概率是相等的。求这个概率，当走$N$步后，他俩再次相遇。

从醉鬼$A$的视角来看，$B$每一次行动可以分为：距离$A$不动，距离$A$往左走2步，或者距离$A$往右走2步。 两人最终相遇，相当于往左走的总部数$N_l$等于往右走的总步数$N_r$.故

$$P=\sum_{a=0}^{\big [\cfrac N 2\big ]}\cfrac {A_N^N}{(A_a^a)^2}(\cfrac {1}{4})^a(\cfrac {1}{4})^a(\cfrac {1}{2})^{N-2a}$$

换一个思路，任何一个醉鬼往左走和往右走的概率关于原点对称的，所以经过$N$步后它最终在不同位置的概率分布也是关于原点对称的：$P(N_A)=P(-N_A)$($N_A$是走了$N$步后醉鬼$A$所处的最终位置).所以$P(N_A=N_B)=P(N_A=-N_B)=P(N_A+N_B=0)$.又因为，每次走路两两独立，往左和往右的概率一样（无论是对$A$还是对$B$）， 故可以虚拟一个醉鬼$C$,来替代两人走$2N$步：$P(N_A+N_B=0)=P(N_C=0)$，而

$$P(N_c=0)=C_{2N}^N(\cfrac {1}{2})^{2N}$$