在马尔可夫链中找到给定时间的状态概率-在Python中设置1

假设我们有一个马尔可夫链图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的矩阵

• 表[S，0]：= 1.0

• 对于1到T范围内的i

• 对于G [j]中的每个k，

• table [j，i]：= table [j，i] + k [1] * table [k [0]，i-1]

• 对于1到N范围内的j，执行

• 返回表[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))

输入项

6, 4, 2, 100

输出结果

0.28499144801478526