ค้นหาความน่าจะเป็นของรัฐในช่วงเวลาที่กำหนดในกลุ่ม Markov - ชุดที่ 1 ใน Python

สมมติว่าเรามีกราฟลูกโซ่มาร์คอฟ g; เราพบความน่าจะเป็นที่จะไปถึงสถานะ F ณ เวลา T หากเราเริ่มจากสถานะ S เมื่อเวลา t =0 ดังที่เราทราบแล้วว่าห่วงโซ่ Markov เป็นกระบวนการสุ่มที่ประกอบด้วยสถานะต่างๆ และความน่าจะเป็นที่จะย้ายสถานะหนึ่งไปยังอีกสถานะหนึ่ง สิ่งนี้สามารถแสดงเป็นกราฟกำกับ โหนดเป็นสถานะและขอบมีความเป็นไปได้ที่จะเปลี่ยนจากโหนดหนึ่งไปอีกโหนดหนึ่ง จากสถานะหนึ่งไปอีกสถานะหนึ่ง ต้องใช้เวลาในการย้ายหน่วย ผลรวมของความน่าจะเป็นของขอบขาออกคือหนึ่งสำหรับทุกโหนด

ดังนั้น หากอินพุตเป็น N =6, S =4, F =2, T =100 เอาต์พุตจะเป็น 0.28499144801478526

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• table :=เมทริกซ์ขนาด (N+1)x(T+1) และเติม 0.0

• ตาราง[S, 0] :=1.0

• สำหรับผมอยู่ในช่วง 1 ถึง T ทำ

  • สำหรับ j ในช่วง 1 ถึง N ทำ

    • สำหรับแต่ละ k ใน G[j] ทำ

      • table[j, i] :=table[j, i] + k[1] * table[k[0], i - 1]

• กลับตาราง[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