Tìm xác suất trạng thái tại thời điểm T trong chuỗi Markov - Phần 1 trong Python

Cho đồ thị chuỗi Markov g, ta cần tìm xác suất đến trạng thái F tại thời điểm T nếu bắt đầu từ trạng thái S lúc t = 0. Chuỗi Markov là quá trình ngẫu nhiên với các trạng thái và xác suất chuyển đổi. Được biểu diễn bằng đồ thị có hướng: nút là trạng thái, cạnh có trọng số là xác suất chuyển. Từ trạng thái này sang trạng thái khác mất 1 đơn vị thời gian. Tổng xác suất các cạnh ra của mỗi nút bằng 1.

Ví dụ, với N = 6, S = 4, F = 2, T = 100, kết quả là 0.28499144801478526.

Thuật toán giải quyết (Dynamic Programming)

• Tạo bảng table kích thước (N+1) x (T+1) khởi tạo 0.0.
• table[S][0] := 1.0.
• Với i từ 1 đến T:
  • Với j từ 1 đến N:
    • Với mỗi cạnh k trong G[j] (k[0] là đỉnh đích, k[1] là xác suất):
      • table[j][i] += k[1] * table[k[0]][i-1].
• Trả về table[F][T].

Ví dụ minh họa

def get_probability(G, N, F, S, T):
    table = [[0.0 for _ in range(T+1)] for _ 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))  # 0.28499144801478526

Đầu vào

6, 4, 2, 100

Đầu ra

0.28499144801478526