马尔可夫链吸收时间求解：线性细胞填充过程问题

一、状态定义与转移关系 #

首先咱们先明确所有可能的状态——因为初始只有第一个细胞是1，且只有与1相邻的0细胞才能被激活，所以所有激活的细胞一定是从左到右连续的（不可能出现中间有0、右边有1的情况，因为右边的1无法被激活）。因此我们可以用S_k表示状态：前k个细胞为1，剩余N−k个为0（k=1,2,...,N），其中S_N是所有细胞全为1的吸收态。

转移概率/速率 #

对于每个非吸收态S_k（k < N）：

• 当前共有N−k个0细胞，其中只有第k+1个细胞与1相邻（左边是第k个细胞，值为1），选到它时会转移到S_{k+1}，转移概率为1/(N−k)；
• 剩下的N−k−1个0细胞（第k+2到N个），选到它们时状态不会改变，因此S_k的自环概率为(N−k−1)/(N−k)。

如果用转移速率（连续时间视角）理解，可以认为每单位时间内每个0细胞被选中的速率是1/(N−k)，那么从S_k到S_{k+1}的速率是1（只有1个有效细胞），自环速率是N−k−1。

状态转移关系可以直观表示为：

S_1 ←(自环概率 (N-2)/(N-1))→ S_1 →(1/(N-1)) S_2 ←(自环概率 (N-3)/(N-2))→ S_2 →(1/(N-2)) ... → S_{N-1} →(1/1) S_N（吸收态）

二、期望吸收时间的推导 #

设E_k为从状态S_k到吸收态S_N的期望步数，显然E_N = 0（已经是终态）。

对于k < N，我们可以根据状态转移列写期望方程：

从S_k出发，走1步后，要么以(N−k−1)/(N−k)的概率留在S_k，要么以1/(N−k)的概率走到S_{k+1}，因此：
E_k = 1 + [(N−k−1)/(N−k)]·E_k + [1/(N−k)]·E_{k+1}

接下来化简这个方程：

1. 把含E_k的项移到左边：
   E_k - [(N−k−1)/(N−k)]·E_k = 1 + [1/(N−k)]·E_{k+1}
2. 左边合并同类项：
   [ (N−k) - (N−k−1) ]/(N−k) · E_k = 1 + [1/(N−k)]·E_{k+1}
   也就是1/(N−k) · E_k = 1 + [1/(N−k)]·E_{k+1}
3. 两边乘以N−k，得到递推式：
   E_k = (N−k) + E_{k+1}

现在我们从k=N-1开始往回递推：

• E_{N-1} = (N - (N-1)) + E_N = 1 + 0 = 1
• E_{N-2} = (N - (N-2)) + E_{N-1} = 2 + 1 = 3
• E_{N-3} = 3 + E_{N-2} = 3 + 3 = 6
• ...
• 最终，初始状态S_1的期望吸收时间为：
  E_1 = (N−1) + (N−2) + ... + 1 = N(N−1)/2

本质上这个递推式是把每一步的“等待时间”累加起来——在状态S_k时，期望需要N−k步才能转移到S_{k+1}（因为每次转移成功的概率是1/(N−k)，几何分布的期望是1/p = N−k），所以总期望就是1到N-1的自然数求和。

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