棋盘随机骑士简单随机游走：角落返回时长及转移矩阵构建问询

1. 转移矩阵构建 #

首先把8x8棋盘的每个格子标记为一个状态（比如用(x,y)表示，其中x,y ∈ {1,2,...,8}），转移矩阵P是一个64×64的矩阵，规则如下：

• 对任意状态(x,y)，先找出所有合法的骑士移动：即满足1 ≤ x+dx ≤8且1 ≤ y+dy ≤8的(dx,dy)组合，也就是{(±1,±2), (±2,±1)}中的有效项。
• 设k为该状态的合法移动数量，那么对每个合法移动到达的状态(x',y')，P[(x,y)][(x',y')] = 1/k；其余状态的转移概率为0。

举几个具体例子：

• 角落状态(1,1)：只有2个合法移动(2,3)和(3,2)，所以P[(1,1)][(2,3)] = 1/2，P[(1,1)][(3,2)] = 1/2，其余均为0。
• 边非角落状态(1,2)：有3个合法移动(2,4)、(3,1)、(3,3)，所以这三个状态的转移概率都是1/3，其余为0。
• 内部核心状态(3,3)：有8个合法移动，每个目标状态的转移概率都是1/8。

2. 计算返回角落的平均时间 #

我们可以利用马尔可夫链平均返回时间定理：对于不可约、非周期的马尔可夫链，状态i的平均返回时间等于该状态在平稳分布中概率的倒数，即 ( m_i = \frac{1}{\pi_i} )。

步骤1：确定平稳分布

棋盘上的骑士游走属于图上的随机游走，这类游走的平稳分布与每个状态的「度数」（合法移动数量d_i）成正比，公式为：
[ \pi_i = \frac{d_i}{\sum_{j=1}^{64} d_j} ]

先计算所有状态的度数总和：

• 4个角落状态：每个度数为2 → 4×2=8
• 8个邻角落的边状态（比如(1,2)、(2,1)）：每个度数为3 → 8×3=24
• 16个边中间状态（比如(1,3)、(3,1)）：每个度数为4 → 16×4=64
• 16个内部边缘状态（比如(2,3)、(3,2)）：每个度数为6 → 16×6=96
• 16个内部核心状态（比如(3,3)）：每个度数为8 → 16×8=128

总度数和为 ( 8+24+64+96+128=320 )。

步骤2：计算角落状态的平稳概率

单个角落状态的度数d_i=2，所以：
[ \pi_i = \frac{2}{320} = \frac{1}{160} ]

步骤3：计算平均返回时间

根据定理，平均返回时间为：
[ m_i = \frac{1}{\pi_i} = 160 ]

简单来说，从角落出发的骑士，平均需要160步才能返回该角落。

补充：线性方程组方法（需细致状态分组） #

如果不用平稳分布，需要将状态按与起始角落的关系、对称性分成更多组（比如起始角落、与角落相邻的内部状态、与这些内部状态相邻的边状态等），建立对应的线性方程组求解，最终结果也会是160，但过程会繁琐很多。

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