Vòng lặp — chuỗi Markov

Giải hệ nᵀ(I − P) = e₀ᵀ thay vì cắt vòng.

Đây là phần lõi mà công cụ làm khác với hầu hết bảng tính: vòng lặp được giải chính xác bằng đại số tuyến tính, không phải bằng cách chạy thử vài vòng rồi dừng.

Ý tưởng

Coi quy trình là một chuỗi Markov hấp thụ: mỗi bước là một trạng thái, mỗi luồng là một xác suất chuyển, các điểm kết thúc là trạng thái hấp thụ. Câu hỏi “bước v chạy trung bình bao nhiêu lần trong một lượt hồ sơ” chính là câu hỏi kinh điển về số lần ghé thăm kỳ vọng.

Công thức

Viết gọn dưới dạng ma trận:

Đọc bằng lời: “số lần ghé thăm bước v bằng 1 nếu v là điểm bắt đầu, cộng với tổng số lần các bước khác chuyển sang v”. Đây là một hệ phương trình tuyến tính — giải một lần là ra tất cả, và nghiệm đã bao gồm vô hạn số vòng lặp.

Trường hợp một vòng rework đơn

Với vòng lặp đơn giản, hệ (5) rút gọn về công thức tổng cấp số nhân:

Ví dụ tính tay

Cách công cụ giải bài toán này

def expected_visits(node_ids, transitions, start):
    # Dựng (I - P^T), vế phải là e_0
    matrix = [[1.0 if r == c else 0.0 for c in range(size)] for r in range(size)]
    for source, targets in transitions.items():
        for target, probability in targets.items():
            matrix[index[target]][index[source]] -= probability

    vector = [0.0] * size
    vector[index[start]] = 1.0

    return solve(matrix, vector)      # khử Gauss có chọn trục