自回避随机访问达到n次所需步数的期望值

KeyTo9_Fans

玩家一开始位于格点(0,0)处，该点的访问次数为1，其余格点的访问次数为0

接下来的每一步，玩家都会往上下左右的其中一个方向走一个单位长度

具体往哪个方向走，则取决于要前往的那个格点的访问次数

玩家总是前往访问次数最少的那个相邻格点

如果有多个相邻格点的访问次数是并列最少的，那么玩家会从这些访问次数并列最少的相邻格点中，随机选择一个前往

如果某个格点的访问次数达到2次，玩家就会停下来，那么平均需要走71.759步才会停下来：



我们模拟1.2亿次的结果和这个德国人（https://www.randomwalk.de/stw2d.html）模拟120亿次的结果是吻合的（相差1是因为他们的最后一步不算）：



而我们模拟128亿次得到的95%置信区间是71.7587±0.0009，减去1之后比他略小一些，但也在合理误差范围内

本贴要求解的问题是：

(1)

如果某个格点的访问次数达到3次，玩家才会停下来，那么平均需要走多少步才会停下来？

如果某个格点的访问次数达到4次，玩家才会停下来，那么平均需要走多少步才会停下来？

如果某个格点的访问次数达到5次，玩家才会停下来，那么平均需要走多少步才会停下来？

……

(2)

如果玩家永不停止，那么：

【恰好被玩家访问过1次的格子数】除以【玩家访问过的格子总数】的商是否有极限？

【恰好被玩家访问过2次的格子数】除以【玩家访问过的格子总数】的商是否有极限？

【恰好被玩家访问过3次的格子数】除以【玩家访问过的格子总数】的商是否有极限？

……

如有，这些极限值分别是多少？

KeyTo9_Fans

为了解答1楼提出的一系列问题，我目前开启了3个进程

第1个进程开启了2个线程，目前运行了15天19小时，结果如下：

如果某个格点的访问次数达到2次，玩家才会停下来，那么停下来之前平均要走70.759151(45)步

第2个进程开启了4个线程，目前运行了13天5小时，结果如下：

如果某个格点的访问次数达到3次，玩家才会停下来，那么停下来之前平均要走2911.552(11)步

第3个进程开启了26个线程，目前运行了9天9小时，结果如下：

如果玩家在三维空间里走，直到某个格点的访问次数达到2次才会停下来，那么停下来之前平均要走3953.795(13)步

这个结果在2个月前被1楼提到的那个德国人 Hugo Pfoertner 抢先提交到oeis里了

数列编号是A378903：https://oeis.org/A378903

我们比他晚了2个月才开始运行程序，可能需要再继续运行几个月到1年不等的时间，才能赶超他，在oeis上贡献我们的研究成果（将这个数列延长2项）