无模拟近似下能否用算法求解二维随机游走的期望击中时间？

精确解算法实现方案 #

你之前递归缺少的基例很明确：所有被边界吸收的点（即is_absorbed(x,y)返回真的坐标），期望击中时间直接取0，这就是递归终止条件。

对于所有未被吸收的内部格点，期望击中时间满足如下差分关系：
E(x,y) = 1 + 0.25 * E(x+1,y) + 0.25 * E(x-1,y) + 0.25 * E(x,y+1) + 0.25 * E(x,y-1)
这个公式的逻辑是：当前步消耗1单位时间，之后以均等概率进入四个相邻格点的期望状态。

两种可落地的精确解算法 #

1. 有限线性方程组求解（适用于边界范围较小的场景）

因为吸收边界是包围原点的有限闭合边界，所有可达的内部格点总数是有限的，按如下步骤操作即可得到精确有理数解：

• 首先枚举所有内部格点：从原点出发做BFS遍历，只要相邻格点未被吸收就标记为内部点，直到所有内部点都被记录，给每个内部点分配唯一编号，假设总共有N个内部点，最终需要求解N元一次线性方程组。
• 组装系数矩阵A和常数项向量b：对每个编号为i的内部点(x,y)，设置A[i][i] = 1，常数项b[i] = 1；如果四个相邻格点是编号为j的内部点，设置A[i][j] -= 0.25；如果相邻点是吸收点则无需额外处理（对应期望为0，不影响方程）。
• 用高斯消元求解线性方程组Ax = b，结果向量中对应原点编号的数值就是原点出发的精确期望击中时间。

2. 迭代动态规划（适用于边界范围较大的场景）

如果内部点数量过多，高斯消元O(N³)的复杂度过高，可以用迭代法收敛到精确解：

• 初始化所有内部点的E值为0，吸收点的E值始终固定为0。
• 循环迭代更新所有内部点的E值：E_new(x,y) = 1 + 0.25 * (E(x+1,y) + E(x-1,y) + E(x,y+1) + E(x,y-1))。
• 重复迭代直到两次迭代的所有点数值差小于你需要的精度阈值；如果需要严格精确的有理数解，可以采用分数运算迭代到数值完全不再变化即可。

内容的提问来源于stack exchange，提问作者addawaddawoo