UOJ Logo liuzhaozhou的博客

博客

标签
暂无

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

2022-07-14 23:10:22 By liuzhaozhou

利益相关:提问者,我太蠢了。

我把此问题转发到超理论坛上,感谢 @Gee Law 提供的解答。 把平面按照它的所有的点按照奇数、偶数步染色,只考虑偶数步。(染色见 Random Walks on a Hexagonal Lattice 的图。)注意偶数步的格点就是 ${\mathbb{Z}+\omega\mathbb{Z}}$,其中 $\omega$ 是一个本原三次单位根,可以同构到 $\mathbb{Z}^2$。列出它两步位移 $X_2$ 的分布:

  • $X_2=(0,0)^{\mathsf{T}}$ w.p. $\frac13$;
  • $X_2=z$ w.p. $\frac19$ 对任意 ${z\in\{(1,0)^{\mathsf{T}},(-1,0)^{\mathsf{T}},(0,1)^{\mathsf{T}},(0,-1)^{\mathsf{T}},(1,-1)^{\mathsf{T}},(-1,1)^{\mathsf{T}}\}}$。

横坐标的分布:$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}$ 有

$$\begin{aligned} 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}. $$

共 1 篇博客