在马尔可夫链中查找给定时间的状态概率 - Python 中的集合 1

pythonserver side programmingprogramming更新于 2025/10/15 23:40:17

假设我们有一个马尔可夫链图 g；如果我们在时间 t = 0 时从状态 S 开始，则我们必须找到在时间 T 达到状态 F 的概率。众所周知，马尔可夫链是一个由各种状态和从一个状态移动到另一个状态的概率组成的随机过程。这可以表示为有向图；节点是状态，边具有从一个节点移动到另一个节点的概率。从一个状态移动到另一个状态需要单位时间。每个节点的传出边的概率总和为 1。

因此，如果输入为 N = 6、S = 4、F = 2、T = 100，则输出将为 0.28499144801478526

为了解决这个问题，我们将遵循以下步骤 −

table := 大小为 (N+1)x(T+1) 的矩阵并填充 0.0
table[S, 0] := 1.0
对于范围为 1 到 T 的 i，执行
- 对于范围为 1 到 N 的 j，执行
  - 对于 G[j] 中的每个 k，执行
    - table[j, i] := table[j, i] + k[1] * table[k[0], i - 1]
返回 table[F, T]

示例

让我们看看下面的实现以便更好地理解 −

def get_probability(G, N, F, S, T):
   table = [[0.0 for j in range(T+1)] for i in range(N+1)]
   table[S][0] = 1.0
   for i in range(1, T+1):
      for j in range(1, N +1):
         for k in G[j]:
            table[j][i] += k[1] * table[k[0]][i - 1]
   return table[F][T];
graph = []
graph.append([])
graph.append([(2, 0.09)])
graph.append([(1, 0.23),(6, 0.62)])
graph.append([(2, 0.06)])
graph.append([(1, 0.77),(3, 0.63)])
graph.append([(4, 0.65),(6, 0.38)])
graph.append([(2, 0.85),(3, 0.37), (4, 0.35), (5, 1.0)])
N = 6
S, F, T = 4, 2, 100
print(get_probability(graph, N, F, S, T))