无限延伸圣诞树格点上随机游走返回顶部顶点的概率求解

问题定义 #

想象一个由等边三角形构成的圣诞树格点（示意图如下），这个格点是向下无限延伸的。

我们从顶部的顶点开始做随机游走：每一步随机选一个相邻顶点移动，每个相邻顶点的选中概率相等，允许重复访问同一个顶点。

我想知道，最终能回到顶部顶点的概率是多少？

背景由来 #

最近我在研究Polya随机游走常数相关的内容，刚好赶上圣诞季，到处都是圣诞树的元素，这个问题就自然而然冒出来了。

我的推导思路 #

我先定义了两个变量：

• $p(k)$：第 $k$ 步首次回到顶部顶点的概率
• $P(n)=\sum\limits_{k=2}^n p(k)$：前 $n$ 步内首次返回的概率总和

我们要找的就是当 $n$ 趋向无穷时的 $P(\infty)$。

通过手动计数路径的方式，我算出了前几步的结果：

• $p(2)=\frac14$
• $p(3)=\frac{1}{4^2}=\frac{1}{16}$
• $p(4)=\frac{2}{4^{3}+\frac{1}{4}2\cdot3}=\frac{5}{96}$
• $p(5)=\frac{3}{4^{4}+\frac{4}{4}3\cdot 3}=\frac{25}{768}$
• $p(6)=\frac{6}{4^{5}+\frac{21}{4}4 6}+\frac{12}{4^3 6^{2}+\frac{4}{4}2 6^3}=\frac{179}{6912}$

越往后计算越麻烦，目前算到前6步的累积概率：
$P(6)=\frac14+\frac{1}{16}+\frac{5}{96}+\frac{25}{768}+\frac{179}{6912}\approx 0.423032$

我个人猜测 $P(\infty)<1$，原因是：每当走到树的边界位置时，向下走的概率是向上走的两倍，路径很容易就往更深处飘走，再也回不来。而如果是完整的无限三角格点（不是这种半无限的圣诞树结构），返回原点的概率应该是1。

补充更新 #

评论区里有位@user分享了更多 $n$ 值对应的 $P(n)$ 结果，包括n=5、6、50、100、150、200、250、300（我自己算的n=5、6的结果和他完全一致）。这里附上 $P(n)$ 随步数 $n$ 变化的折线图，涵盖的n值是2、6、50、100、150、200、250、300。

备注：内容来源于stack exchange，提问作者Dan