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

假设我们有一个马尔可夫链图 g；我们需要找到从状态 S 开始，当时间 t = 0 时，在时间 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

  • 对于 i 从 1 到 T，执行

    • 对于 j 从 1 到 N，执行

      • 对于 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))

输入

6, 4, 2, 100

输出

0.28499144801478526

更新于: 2020年8月27日

287 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告