马尔可夫链问题：两罐球转移终止的期望时间求解

嗨，我来帮你理清这个问题，首先得纠正你一个小误解——我们要的不是min(E₀,E_N)，这是因为E₀和E_N如果是从初始状态出发分别到达0或N的期望时间，那首次到达任意终止状态的期望时间可不是两者的最小值，而是要通过马尔可夫链的递推方程来求解，下面一步步来拆解：

1. 定义状态与期望函数 #

首先，我们定义E[k]为当前第一罐有k个球时，到达终止状态（第一罐空k=0或满k=N）所需的期望时间：

• 边界条件：E[0] = 0，E[N] = 0（已经处于终止状态，不需要额外时间）
• 对于0 < k < N的中间状态，每次转移有3/4的概率让第一罐多1个球（到k+1），1/4的概率少1个球（到k-1），因此递推方程为：

  E[k] = 1 + (3/4)E[k+1] + (1/4)E[k-1]
  

2. 整理递推方程 #

把上面的式子变形，消去分数后得到：

3E[k+1] - 4E[k] + E[k-1] = -4

为了简化求解，我们令d[k] = E[k] - E[k-1]（表示相邻状态间的期望时间差），代入后可以得到一个线性递推关系：

3d[k+1] - d[k] = -4

3. 求解递推关系 #

我们可以通过齐次解加特解的方式求解这个递推：

• 齐次解：对应齐次方程3d[k+1] - d[k] = 0的解为 d_h[k] = A*(1/3)^{k-1}（其中A为待求常数）
• 特解：假设常数解d*，代入递推方程可得d* = -2
• 通解：将齐次解和特解合并，得到 d[k] = A*(1/3)^{k-1} - 2

接下来利用边界条件E[N] = 0，而E[N]可以表示为所有相邻差值的和：E[N] = sum_{k=1}^N d[k] = 0。代入通解并计算等比数列求和后，可解出常数A：

A = (4N*3^{N-1})/(3^N - 1)

4. 计算初始状态的期望时间 #

我们的初始状态是第一罐有N/2个球，因此需要计算E[N/2]，它等于从k=1到k=N/2的d[k]之和。代入A的表达式并化简，最终可以得到非常简洁的结果：

E[N/2] = N * (3^{N/2} - 1)/(3^{N/2} + 1)

5. 验证结果（举个例子） #

比如当N=2时，初始状态第一罐有1个球，代入公式得：
2*(3^1 - 1)/(3^1 + 1) = 2*2/4 = 1，这符合实际：从1个球出发，一步就会到达终止状态（0或2），期望时间就是1。

再比如N=4，初始状态第一罐有2个球，代入公式得：
4*(3^2 -1)/(3^2 +1) = 4*8/10 = 3.2，手动用递推计算也能得到相同结果，验证正确。

回到你的疑问 #

为什么不能取min(E₀,E_N)？因为E₀是从初始状态出发一直到到达0的期望时间（不管中途是否先到达N），E_N是到达N的期望时间（不管中途是否先到达0），而我们要的是首次到达任意一个终止状态的时间——这两个事件是互斥的（首次到达要么是0要么是N），所以期望时间是这两个事件的期望加权和，而不是取最小值，这也是为什么需要用递推来整体计算，而不是单独算两个期望再取小。

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