Wiki › Thuật toán › Toán học › Chuỗi Markov và kỳ vọng qua hệ phương trình

Chuỗi Markov và kỳ vọng qua hệ phương trình

Tính kỳ vọng số bước và xác suất hấp thụ của quá trình ngẫu nhiên có chu trình bằng phương trình bước đầu tiên và khử Gauss. Kèm cách dựng trạng thái KMP cho bài tung đồng xu tới khi gặp một xâu.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 13 phút 3 lượt xem

Chuỗi Markov (Markov chain) là mô hình một quá trình ngẫu nhiên đi qua các trạng thái, trong đó bước tiếp theo chỉ phụ thuộc vào trạng thái hiện tại, không phụ thuộc vào lịch sử: từ trạng thái i sang trạng thái j với xác suất cố định Pij. Rất nhiều bài "tung đồng xu cho tới khi...", "đi ngẫu nhiên trên đồ thị cho tới khi gặp đỉnh n", "trò chơi kết thúc khi..." chính là một chuỗi Markov có các trạng thái hấp thụ (vào rồi không ra).

Câu hỏi điển hình là kỳ vọng số bước tới khi bị hấp thụ, hoặc xác suất kết thúc ở một trạng thái hấp thụ cụ thể. Khi đồ thị chuyển trạng thái không có chu trình, DP xác suất & kỳ vọng theo thứ tự topo là đủ. Khi có chu trình (đi lùi, thử lại, quay về trạng thái cũ), các ẩn phụ thuộc vòng tròn vào nhau và ta phải giải hệ phương trình tuyến tính bằng khử Gauss trong O(n3), dùng được với vài trăm trạng thái.

Ý tưởng / Trực giác

Phương trình bước đầu tiên (first-step analysis). Gọi Ei là kỳ vọng số bước còn lại khi đang ở trạng thái i. Nếu i hấp thụ thì Ei=0. Ngược lại, quá trình đi thêm đúng một bước, sang j với xác suất Pij, và từ đó (nhờ tính Markov: tương lai chỉ phụ thuộc trạng thái hiện tại) kỳ vọng phần còn lại là Ej. Theo luật kỳ vọng toàn phần:

Ei=1+∑jPijEj.

Cũng lập luận đó cho xác suất xi bị hấp thụ tại một trạng thái đích t: xt=1, xs=0 với các trạng thái hấp thụ khác, còn với trạng thái tạm thời xi=∑jPijxj (bước đầu không tốn chi phí, nên không có số hạng 1).

Chuyển vế, ta được hệ n phương trình n ẩn: (I−Q)E=1, với Q là ma trận chuyển giữa các trạng thái tạm thời.

Khi nào hệ có nghiệm duy nhất? Bổ đề: nếu từ mọi trạng thái tạm thời đều có đường đi (xác suất dương) tới một trạng thái hấp thụ, thì I−Q khả nghịch và E hữu hạn. Phác thảo chứng minh: khi đó có L và δ>0 sao cho từ bất kỳ đâu, trong L bước bị hấp thụ với xác suất ít nhất δ; vậy QL có tổng mỗi hàng ≤1−δ, nên Qk→0 và chuỗi I+Q+Q2+… hội tụ về (I−Q)−1. Phần tử (I−Q)ij−1 chính là số lần kỳ vọng ghé thăm j khi xuất phát từ i (ma trận cơ bản). Nếu có một nhóm trạng thái tạm thời "kẹt" không bao giờ thoát ra, kỳ vọng là vô hạn và hệ suy biến: kiểm tra bằng BFS trên đồ thị ngược trước khi giải.

Số lần ghé thăm. Đôi khi bài hỏi tổng chi phí phụ thuộc vào cạnh hoặc đỉnh đi qua. Gọi fj là số lần kỳ vọng đứng ở j khi xuất phát từ s. Lập luận theo bước cuối (lần ghé j đến từ đâu): fj=[j=s]+∑ifiPij, tức hệ với ma trận chuyển vị (I−Q)Tf=es. Kỳ vọng số lần đi qua cạnh i→j là fiPij, và nhờ tuyến tính của kỳ vọng, tổng chi phí kỳ vọng là ∑fiPij·chi phí(i→j).

Dựng trạng thái là phần khó nhất. Với bài tung đồng xu tới khi xuất hiện xâu S, trạng thái không phải "toàn bộ dãy đã tung" mà là độ dài tiền tố dài nhất của S khớp với phần cuối dãy đã tung, chuyển trạng thái bằng hàm tiền tố KMP (|S|+1 trạng thái). Với nhiều xâu, dùng Aho-Corasick.

Ví dụ chạy tay

Tung đồng xu cân đối cho tới khi xuất hiện xâu S=010. Trạng thái k∈{0,1,2,3} là độ dài phần khớp, k=3 hấp thụ.

          '0'          '1'          '0'
   (0) --------> (1) --------> (2) --------> [3]  hấp thụ
   ^ |           ^ |            |
   | | '1'       | | '0'        | '1'
   +-+           +-+            +-----> (0)

 (0) gặp '1': vẫn chưa khớp gì      -> 0
 (1) = "0" gặp '0': "00" khớp "0"    -> 1
 (2) = "01" gặp '1': "011" không khớp -> 0

Hệ phương trình bước đầu tiên (mỗi chiều xác suất 12):

E0&=1+12E1+12E0E1&=1+12E2+12E1E2&=1+12E3+12E0E3&=0

Rút gọn: E0=2+E1, E1=2+E2, E2=1+12E0. Thế lần lượt: E0=4+E2=5+12E0, nên E0=10.

Trạng thái k Phần đã khớp Ek
0 (rỗng) 10
1 0 8
2 01 6
3 010 0

Kiểm chứng bằng công thức đóng cho đồng xu cân đối: E=∑2k trên các k mà tiền tố độ dài k của S bằng hậu tố độ dài k. Với 010: k=1 (0) và k=3, nên E=2+8=10, khớp.

Cài đặt

solve là khử Gauss chọn trụ lớn nhất (giả sử nghiệm duy nhất, như bổ đề ở trên đảm bảo). Trạng thái hấp thụ được đưa vào hệ bằng phương trình Ei=0 (hoặc xi=[i=t]), để mọi chỉ số giữ nguyên.

C++
// Giải hệ n ẩn a * x = b (a là n x (n+1)), giả sử nghiệm duy nhất; khử Gauss chọn trụ lớn nhất.
vector<double> solve(vector<vector<double>> a) {
    int n = a.size();
    for (int col = 0; col < n; col++) {
        int sel = col;
        for (int i = col; i < n; i++)
            if (fabs(a[i][col]) > fabs(a[sel][col])) sel = i;
        swap(a[sel], a[col]);
        for (int i = 0; i < n; i++)
            if (i != col) {
                double c = a[i][col] / a[col][col];
                for (int j = col; j <= n; j++) a[i][j] -= c * a[col][j];
            }
    }
    vector<double> x(n);
    for (int i = 0; i < n; i++) x[i] = a[i][n] / a[i][i];
    return x;
}

// P[i][j] = xác suất đi từ i sang j; absorbing[i] = true nếu i là trạng thái hấp thụ.
// Kỳ vọng số bước tới khi bị hấp thụ: E[i] = 0 nếu i hấp thụ, ngược lại E[i] = 1 + sum P[i][j] E[j].
vector<double> expected_steps(const vector<vector<double>>& P, const vector<bool>& absorbing) {
    int n = P.size();
    vector<vector<double>> a(n, vector<double>(n + 1, 0));
    for (int i = 0; i < n; i++) {
        a[i][i] = 1;
        if (absorbing[i]) continue;  // hàng E[i] = 0
        for (int j = 0; j < n; j++) a[i][j] -= P[i][j];
        a[i][n] = 1;  // chi phí của một bước
    }
    return solve(a);
}

// Xác suất bị hấp thụ tại trạng thái target: x[i] = [i == target] nếu i hấp thụ,
// ngược lại x[i] = sum P[i][j] x[j].
vector<double> absorb_prob(const vector<vector<double>>& P, const vector<bool>& absorbing, int target) {
    int n = P.size();
    vector<vector<double>> a(n, vector<double>(n + 1, 0));
    for (int i = 0; i < n; i++) {
        a[i][i] = 1;
        if (absorbing[i]) {
            a[i][n] = (i == target);
            continue;
        }
        for (int j = 0; j < n; j++) a[i][j] -= P[i][j];
    }
    return solve(a);
}
Python
# Giải hệ n ẩn a * x = b (a là n x (n+1)), giả sử nghiệm duy nhất; khử Gauss chọn trụ lớn nhất.
def solve(a):
    a = [row[:] for row in a]
    n = len(a)
    for col in range(n):
        sel = max(range(col, n), key=lambda i: abs(a[i][col]))
        a[sel], a[col] = a[col], a[sel]
        for i in range(n):
            if i != col:
                c = a[i][col] / a[col][col]
                if c:
                    a[i] = [x - c * y for x, y in zip(a[i], a[col])]
    return [a[i][n] / a[i][i] for i in range(n)]


# P[i][j] = xác suất đi từ i sang j; absorbing[i] = True nếu i là trạng thái hấp thụ.
# Kỳ vọng số bước tới khi bị hấp thụ: E[i] = 0 nếu i hấp thụ, ngược lại E[i] = 1 + sum P[i][j] E[j].
def expected_steps(P, absorbing):
    n = len(P)
    a = [[0.0] * (n + 1) for _ in range(n)]
    for i in range(n):
        a[i][i] = 1.0
        if absorbing[i]:
            continue  # hàng E[i] = 0
        for j in range(n):
            a[i][j] -= P[i][j]
        a[i][n] = 1.0  # chi phí của một bước
    return solve(a)


# Xác suất bị hấp thụ tại trạng thái target: x[i] = [i == target] nếu i hấp thụ,
# ngược lại x[i] = sum P[i][j] x[j].
def absorb_prob(P, absorbing, target):
    n = len(P)
    a = [[0.0] * (n + 1) for _ in range(n)]
    for i in range(n):
        a[i][i] = 1.0
        if absorbing[i]:
            a[i][n] = 1.0 if i == target else 0.0
            continue
        for j in range(n):
            a[i][j] -= P[i][j]
    return solve(a)
Dựng chuỗi cho bài "tung tới khi gặp xâu S"
C++
// Xích Markov của bài "tung đồng xu tới khi gặp xâu s" (p1 = xác suất ra '1').
// Trạng thái k = độ dài tiền tố dài nhất của s khớp với phần cuối dãy đã tung (KMP).
vector<vector<double>> pattern_chain(const string& s, double p1) {
    int n = s.size();
    vector<int> pi(n, 0);  // hàm tiền tố
    for (int i = 1; i < n; i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    vector<vector<double>> P(n + 1, vector<double>(n + 1, 0));
    for (int k = 0; k < n; k++)  // trạng thái n hấp thụ: hàng toàn 0
        for (char c : {'0', '1'}) {
            int t = k;
            while (t > 0 && s[t] != c) t = pi[t - 1];
            if (s[t] == c) t++;
            P[k][t] += (c == '1' ? p1 : 1 - p1);
        }
    return P;
}
Python
# Xích Markov của bài "tung đồng xu tới khi gặp xâu s" (p1 = xác suất ra '1').
# Trạng thái k = độ dài tiền tố dài nhất của s khớp với phần cuối dãy đã tung (KMP).
def pattern_chain(s, p1):
    n = len(s)
    pi = [0] * n  # hàm tiền tố
    for i in range(1, n):
        k = pi[i - 1]
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    P = [[0.0] * (n + 1) for _ in range(n + 1)]
    for k in range(n):  # trạng thái n hấp thụ: hàng toàn 0
        for c in "01":
            t = k
            while t > 0 and s[t] != c:
                t = pi[t - 1]
            if s[t] == c:
                t += 1
            P[k][t] += p1 if c == "1" else 1 - p1
    return P

Dùng: P = pattern_chain(S, 0.5), đánh dấu trạng thái |S| là hấp thụ, rồi expected_steps(P, absorbing)[0] là kỳ vọng số lần tung.

Độ phức tạp

Bước Thời gian Bộ nhớ
Lập hệ từ ma trận chuyển n trạng thái O(n2) O(n2)
Giải hệ bằng khử Gauss O(n3) O(n2)
Dựng chuỗi KMP cho xâu độ dài L O(L2) O(L2)
Chuỗi có cấu trúc đường thẳng hoặc cây (khử theo thứ tự) O(n) O(n)

Chi phí bị chi phối bởi khử Gauss: n=500 trạng thái là khoảng 1,25·108 phép tính, vừa trong một giây với C++. Nếu chuỗi chỉ đi giữa các trạng thái kề nhau (ví dụ i→i±1), hệ là ba đường chéo và giải được trong O(n) bằng cách biểu diễn Ei=aiEi+1+bi rồi thế ngược. Lặp giá trị E←1+QE cũng hội tụ nhưng có thể cần cực nhiều vòng khi kỳ vọng lớn (ví dụ 1020 bước), nên không thay được việc giải hệ.

⚠️ Lỗi thường gặp

  • Quên phương trình cho trạng thái hấp thụ: nếu để hàng của trạng thái hấp thụ toàn 0 trong ma trận hệ, ma trận suy biến. Phải ghi rõ Ei=0 (hệ số 1 trên đường chéo).
  • Có trạng thái không bao giờ bị hấp thụ: kỳ vọng vô hạn, khử Gauss chia cho trụ gần 0 và in số rác. Kiểm tra bằng BFS ngược từ các trạng thái hấp thụ; trạng thái không tới được phải xử lý riêng.
  • Hấp thụ ngay khi chạm, không đi tiếp: trong bước đi ngẫu nhiên "dừng khi tới đỉnh n", đỉnh n không có cạnh đi ra trong ma trận, và số lần ghé thăm của nó không được nhân với các cạnh kề.
  • Nhầm chiều hệ: kỳ vọng từ i dùng hệ (I−Q)E=1 (theo hàng), còn số lần ghé thăm khi xuất phát từ s dùng (I−Q)Tf=es (theo cột). Đảo nhầm cho kết quả sai nhưng trông hợp lý.
  • Mất độ chính xác khi kỳ vọng khổng lồ: khi xác suất chuyển rất lệch (ví dụ cần 20 lần ra mặt có xác suất 0,1 liên tiếp), hệ kém điều kiện và khử Gauss với phép trừ mất hết chữ số. Dùng khử trạng thái kiểu GTH (tính 1−Pxx bằng tổng xác suất rời x, không dùng phép trừ).
  • In số nguyên lớn bằng số thực: kỳ vọng như 220 cộng dồn có thể in sai chữ số cuối với độ chính xác mặc định; nếu đáp án là số nguyên, làm tròn và in số nguyên.

Biến thể / Mở rộng

  • Kỳ vọng theo modulo p: khi đáp án là phân số ab in dạng a·b−1modp, giải cùng hệ bằng gauss_mod ở trang Khử Gauss.
  • Chuỗi không chu trình: DP xác suất & kỳ vọng theo thứ tự topo, O(V+E).
  • Trạng thái vô cùng lớn: tìm một đại lượng (hàm thế) thay đổi đúng một hằng số theo kỳ vọng sau mỗi bước; khi đó kỳ vọng số bước bằng hiệu giá trị đầu và cuối chia cho hằng số (định lý dừng tùy chọn), không cần lập hệ.
  • Nhiều xâu đích: trạng thái là nút của automaton Aho-Corasick; xác suất mỗi xâu xuất hiện trước là xác suất hấp thụ.
  • Phân phối dừng: với chuỗi không có trạng thái hấp thụ, phân phối dừng π=πP, ∑πi=1 cũng là một hệ tuyến tính (thay một phương trình bằng điều kiện tổng). Xác suất sau k bước với k lớn: nhân ma trận.

Bài tập luyện

  • Tung đồng xu (icpc21mbc): (Hard) Kỳ vọng số lần tung cho tới khi xuất hiện xâu S (|S|≤20); chuỗi Markov trên trạng thái KMP như ví dụ ở trên, hoặc công thức đóng suy ra từ nó.
  • Đồ thị (icpc25mbe): (Very Hard) Bước đi ngẫu nhiên từ đỉnh 1 tới đỉnh n; giải hệ số lần ghé thăm mỗi đỉnh để có số lần kỳ vọng đi qua mỗi cạnh, rồi đánh số cạnh tham lam.
  • Xác suất dễ (icpc19nate): (Very Hard) Xác suất mỗi người thắng trong trò tung đồng xu với hai xâu đích; chuỗi hấp thụ trên automaton Aho-Corasick, cần khử trạng thái ổn định số vì kỳ vọng có thể tới 1020.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0