无限正六边形网格随机游走,求回到原点期望步数？

· · 个人记录

利益相关：提问者，我太蠢了。

我把此问题转发到超理论坛上，感谢 @Gee Law 提供的解答思路。下面是我码的正文。

把平面按照它的所有的点按照奇数、偶数步染色，只考虑偶数步。（染色见 Random Walks on a Hexagonal Lattice 的图。）注意偶数步的格点就是 {\mathbb{Z}+\omega\mathbb{Z}}，其中 \omega 是一个本原三次单位根，可以同构到 \mathbb{Z}^2。列出它两步位移 X_2 的分布：

横坐标的分布：0 w.p. \frac59，+1 w.p. \frac29，-1 w.p. \frac29。

返回原点的必要条件是横坐标返回 0，可以证明横坐标返回 0 的期望时间是 +\infty。设 T_n 是横坐标为 n 的时候横坐标首次返回 0 所需要的期望时间，并记 {T_0=0}，由对称性 {T_n=T_{-n}}，且对 n>0 有

T_n=2+\left(\frac59 T_n+\frac29 T_{n-1}+\frac29 T_{n+1}\right).

显然有 {T_n\geq 2n=2(n+0)}，归纳可知对任意 {n\geq k\geq 0} 有

T_n &{}=2+\left(\frac59 T_n+\frac29 T_{n-1}+\frac29 T_{n+1}\right)\\ &{}\geq 2+\left(\frac59 2(n+k-1)+\frac29 2(n-1+k-1)+\frac29 2(n+1+k-1)\right)\\ &{}=2(n+k), \end{aligned}

特别地，{T_n\geq 4n}。注意上面整个过程从 {T_n\geq 2(1+0)n} 推出了 {T_n\geq 2(1+1)n}，如此归纳可知对任意 {m\in\mathbb{N}} 有 {T_n\geq 2(1+m)n}，于是 {T_1={+\infty}}，而横坐标为 0 时横坐标再次返回原点的期望时间是

\frac59\cdot 2+\frac49 T_1={+\infty}.