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

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

इसलिए, यदि इनपुट 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