मार्कोव श्रृंखला में एक निश्चित समय पर एक राज्य की संभावना का पता लगाएं - पायथन में 1 सेट करें

मान लीजिए कि हमारे पास मार्कोव चेन ग्राफ g है; यदि हम समय t =0 होने पर राज्य S से शुरू करते हैं तो हमें समय T पर राज्य F तक पहुंचने की संभावना मिलती है। जैसा कि हम जानते हैं कि एक मार्कोव श्रृंखला एक यादृच्छिक प्रक्रिया है जिसमें विभिन्न राज्यों और एक राज्य को दूसरे में स्थानांतरित करने की संभावनाएं शामिल हैं। इसे एक निर्देशित ग्राफ के रूप में दर्शाया जा सकता है; नोड्स राज्य हैं और किनारों के एक नोड से दूसरे में जाने की संभावना है। एक राज्य से दूसरे राज्य में जाने में इकाई समय लगता है। जावक किनारों की प्रायिकताओं का योग प्रत्येक नोड के लिए एक होता है।

इसलिए, यदि इनपुट N =6, S =4, F =2, T =100 जैसा है, तो आउटपुट 0.28499144801478526

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• तालिका:=आकार का एक मैट्रिक्स (N+1)x(T+1) और 0.0 से भरें

• तालिका [एस, 0] :=1.0

• मैं के लिए 1 से टी की सीमा में, करो

  • 1 से N की श्रेणी में j के लिए, करें

    • G[j] में प्रत्येक k के लिए, करें

      • टेबल [जे, आई]:=टेबल [जे, आई] + के [1] * टेबल [के [0], आई -1]

• वापसी तालिका [एफ, टी]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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