math - 为什么这个解决吸收马尔可夫链的想法行不通？

Question

编辑：似乎我的方法有效。

我遇到了一个编程问题，需要我计算到达终端状态的概率。

经过几个小时的艰苦尝试以传统方式解决后，我搜索了一下，发现它被称为吸收马尔可夫链。并且有一个公式。

但是，我试图弄清楚我的解决方案中缺少什么，因为它似乎是正确的。

请原谅粗制滥造的图画。该图中基本上有4个节点，黑线显示原始转换和概率，而彩色线显示终止路径。

步骤是这样的：

1. 跟踪所有可能的路径到终止点，总结每条路径到终止节点的概率。那就是到达节点的概率。

2. 忽略循环路径。这意味着从4到1的“1/3”转换基本上被忽略了。

(2) 的原因：因为我们可以假设返回会增加每条可能路径的概率，使得它们彼此之间仍然保持相同的相对概率！例如，如果我要从4回到1，那么回到2、3和4的机会将分别增加1/27 (1/3 * 1/3 * 1/3)，使得相对概率还是互相平等的！

我希望以上是有道理的。

3. 将每个节点的概率计算为“每个节点的概率”/“终止概率”，因为通过消除循环图，到达每个节点的概率将不再是 1。

因此，鉴于上述算法，以下是找到的值：

红色路径：1/3
绿色路径：1/3
蓝色路径：1/3 * 2/3 = 2/9

达到3的概率：1/3
达到2的概率：2/9 + 1/3 = 5/9
终止的总概率：1/3 + 5/9 = 8/9

因此，最终达到3的概率： (1/3) / (8/9) = 3/8

最终达到2的概率：(5/9) / (8/9) = 5/8

如果您不确定步骤（2），我们可以再试一次！

假设我们从1到4再回到1，这有 1/9 的概率。

从这里，我们可以再次遵循每条彩色路径 * 1/9 概率。

结合之前计算的概率，这给了我们：

10/27 概率达到3。
达到2的概率为 50/81 。
总终止概率为 80/81。

终止于3的新概率现在是 (10/27) / (80/81) = 3/8 (SAME)
终止于2的新概率现在是 (50/81) / (80/81) = 5/8 (相同的）

但是，使用我在网上找到的算法， 3和2的实际概率分别为 (2/5) 和 (3/5) （虽然它是错误的可能性很小）。 原来我错误地使用了在线解决方案

我意识到我的答案实际上非常接近，但我不确定为什么它是错误的？

标签： mathgraphmarkov-chains

Answer 1

我们可以用矩阵来表示马尔可夫链的转移M。在 Python 表示法中，这看起来像：

M = [[  0, 1/3, 1/3, 1/3],
     [  0,   1,   0,   0],
     [  0,   0,   1,   0],
     [1/3, 2/3,   0,   0]])

以及带有向量 的概率S，初始状态 1 为 100%。

S = [1, 0, 0, 0]

将 S 乘以 M 得到新的概率：

S*M = [0, 1/3, 1/3, 1/3]
S*M**2 = [1/9, 5/9, 1/3, 0]
S*M**3 = [0, 16/27, 10/27, 1/27]
S*M**4 = [1/81, 50/81, 10/27, 0]
S*M**n = [3**(-n)*((-1)**n + 1)/2,
          3**(-n)*((-1)**n + 5*3**n - 6)/8,
          3**(-n)*(-(-1)**n + 3*3**n - 2)/8,
          3**(-n)*(1 - (-1)**n)/2]

在n趋于无穷的极限中，对于偶数n，这将给出

[0, 5/8, 3/8, 0]

同样以等概率从 1、2、3 和 4 开始：

S = [1/4, 1/4, 1/4, 1/4]
S*M = [1/12, 1/2, 1/3, 1/12]
S*M**2 = [1/36, 7/12, 13/36, 1/36]
S*M**n = [3**(-n)/4, 5/8 - 3*3**(-n)/8, 3/8 - 3**(-n)/8, 3**(-n)/4]

导致同样的极限[0, 5/8, 3/8, 0]。

从 1 和 4 开始，概率相等：

S = [1/2, 0, 0, 1/2]
S*M = [1/6, 1/2, 1/6, 1/6]
S*M**2 = [1/18, 2/3, 2/9, 1/18]
S*M**n = [3**(-n)/2, 3/4 - 3*3**(-n)/4, 1/4 - 3**(-n)/4, 3**(-n)/2]

给出n走向无穷大的另一个极限：

[0, 3/4, 1/4, 0]