马尔可夫链:查找终端状态计算

Question

我正在试着解决这个问题。希望有人能告诉我如何完成这项工作。我查阅了以下页面，但我无法用java/python编写生成正确输出并通过所有测试用例的代码。我将非常感谢任何人的帮助。

Markov chain probability calculation - Python

Calculating Markov chain probabilities with values too large to exponentiate

编写一个函数answer(m)，它接受一个非负整数数组，该数组表示状态已经进入下一个状态多少次，并为每个终端状态返回一个整数数组，给出每个终端状态的确切概率，表示为每个状态的分子，然后以最简单的形式在末尾返回所有这些状态的分母。该矩阵最多为10乘以10。可以保证，无论矿石处于哪种状态，都存在从该状态到终端状态的路径。也就是说，处理最终将始终以稳定状态结束。ore开始于状态0。只要有规律地简化分数，在计算过程中，分母将适合有符号的32位整数。例如，考虑矩阵m：

[
[0,1,0,0,0,1],  # s0, the initial state, goes to s1 and s5 with equal    probability
[4,0,0,3,2,0],  # s1 can become s0, s3, or s4, but with different probabilities
[0,0,0,0,0,0],  # s2 is terminal, and unreachable (never observed in practice)
[0,0,0,0,0,0],  # s3 is terminal
[0,0,0,0,0,0],  # s4 is terminal
[0,0,0,0,0,0],  # s5 is terminal
]

    So, we can consider different paths to terminal states, such as:

    s0 -> s1 -> s3

    s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> s4

    s0 -> s1 -> s0 -> s5

    Tracing the probabilities of each, we find that

    s2 has probability 0

    s3 has probability 3/14

    s4 has probability 1/7

    s5 has probability 9/14

Answer 1

我不确定边缘情况的结果应该是什么，但我对这个问题所做的是：

1. 创建了第二个矩阵，该矩阵通过将每行中的所有分子相加来包含每个概率的所有分母。
2. 从相同大小的单位矩阵中找到矩阵中的第一个终端状态，以用作非终端的边界，该矩阵以第一个终端为界。
3. 找到了差值的倒数。有几种方法可以做到这一点，我决定用差来扩充匹配单位矩阵。
4. 将逆矩阵乘以从第一个终端到矩阵末尾的有界矩阵。
5. 然后，找到结果分母，并返回从第一个终端到矩阵末尾的第一行分子。

附注：

• 你需要写一个简化小数的函数(你可能还需要写gcf和lcm函数来帮助你简化)。

，

• ，你可能还需要对矩阵进行排序，这样终端就在矩阵的末尾，所以它的形式是正确的。
• 边缘情况: 1x1矩阵，只有1个非终端状态的矩阵，10x10矩阵，只有1个终端状态的矩阵

Answer 2

我知道这是一个有点老的话题，但也许有人会感兴趣。

在我的例子中，这个PDF对我帮助很大：https://math.dartmouth.edu/archive/m20x06/public_html/Lecture14.pdf

该算法易于实现。

正如Ana所说，你需要对矩阵进行排序，记住同时对行和列进行排序，以获得适当的结果。

关于边缘情况：

如果从唯一一个状态开始，则

• 1x1始终为100%，并且它必须终止，因为没有其他状态。
• 如果只有一个非终止状态，则结果将与此行相同。不需要计算。

Ana的答案中的最后两个边缘案例(在我看来应该被接受)不是边缘案例，坦率地说，它们是常规案例，所以你需要正常地计算答案。

Answer 3

作为另一种方法，可以考虑使用Engel's algorithm for absorbing Markov chains来计算吸收概率。这不需要矩阵求逆/线性系统解，因此不需要有理数算术。