Tìm xác suất của một trạng thái tại một thời điểm nhất định trong chuỗi Markov - Đặt 1 trong Python

Giả sử chúng ta có đồ thị chuỗi Markov g; chúng ta có xác suất tìm được xác suất để đạt đến trạng thái F tại thời điểm T nếu chúng ta bắt đầu từ trạng thái S khi thời điểm t =0. Như chúng ta biết chuỗi Markov là một quá trình ngẫu nhiên bao gồm các trạng thái khác nhau và các xác suất để chuyển trạng thái này sang trạng thái khác. Điều này có thể được biểu diễn dưới dạng đồ thị có hướng; các nút là các trạng thái và các cạnh có xác suất đi từ nút này sang nút khác. Từ trạng thái này sang trạng thái khác, phải mất một đơn vị thời gian để di chuyển. Tổng xác suất của các cạnh đi ra là một đối với mọi nút.

Vì vậy, nếu đầu vào là N =6, S =4, F =2, T =100, thì đầu ra sẽ là 0,28499144801478526

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• table:=ma trận có kích thước (N + 1) x (T + 1) và điền bằng 0,0

• bảng [S, 0]:=1.0

• đối với tôi trong phạm vi từ 1 đến T, hãy làm

  • đối với j trong phạm vi từ 1 đến N, thực hiện

    • đối với mỗi k trong G [j], thực hiện

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

• bảng trả về [F, T]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

6, 4, 2, 100

Đầu ra

0.28499144801478526