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

Arnab Chakraborty

更新於: 2020年8月27日

287 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習