Chuỗi Markov — Ma trận chuyển trạng thái và ứng dụng

Chuỗi Markov là một mô hình cho hệ thống chuyển giữa các trạng thái theo từng bước, chẳng hạn như Nắng và Mưa. Quy tắc quan trọng là bước tiếp theo chỉ phụ thuộc vào trạng thái hiện tại, nếu đó là một giả thiết hợp lý cho hệ thống bạn đang mô hình hóa.

Các xác suất một bước đó được gom lại trong một ma trận chuyển trạng thái. Nếu quá trình hiện đang ở trạng thái $i$ và chuyển sang trạng thái $j$ ở bước tiếp theo với xác suất $P_{ij}$, thì

$$P = (P_{ij})$$

Với một chuỗi Markov hữu hạn, mỗi hàng của $P$ có tổng bằng $1$ vì quá trình phải chuyển đến một trong các trạng thái tiếp theo được phép.

Tính chất Markov có nghĩa là gì

Ý tưởng hình thức là

$$P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i)$$

Điều này nói rằng một khi bạn đã biết trạng thái hiện tại $X_n = i$, thì lịch sử trước đó không làm thay đổi xác suất của bước tiếp theo trong mô hình.

Điều kiện này rất quan trọng. Một số hệ thống thực có trí nhớ, xu hướng hoặc hiệu ứng trễ, nên chuỗi Markov chỉ phù hợp khi giả thiết “biết trạng thái hiện tại là đủ” là một xấp xỉ hợp lý.

Cách đọc ma trận chuyển trạng thái

Giả sử một mô hình thời tiết đơn giản có hai trạng thái:

• Nắng
• Mưa

Dùng ma trận chuyển trạng thái sau:

$$P = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix}$$

Hãy đọc mỗi hàng là trạng thái hiện tại và mỗi cột là trạng thái tiếp theo.

Vậy nếu hôm nay là Nắng, mô hình cho biết ngày mai là Nắng với xác suất $0.8$ và Mưa với xác suất $0.2$. Nếu hôm nay là Mưa, ngày mai là Nắng với xác suất $0.4$ và Mưa với xác suất $0.6$.

Ví dụ có lời giải: Thời tiết trong hai ngày

Giả sử phân phối hôm nay là

$$\mathbf{v}_0 = \begin{bmatrix} 1 & 0 \end{bmatrix}$$

Điều này có nghĩa là mô hình bắt đầu ở trạng thái Nắng với xác suất $1$.

Phân phối vào ngày mai là

$$\mathbf{v}_1 = \mathbf{v}_0 P = \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix}$$

Vì vậy sau một bước, mô hình cho xác suất Nắng là $80\%$ và xác suất Mưa là $20\%$.

Sau thêm một bước nữa,

$$\mathbf{v}_2 = \mathbf{v}_1 P = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.72 & 0.28 \end{bmatrix}$$

Bây giờ xác suất Nắng là $0.72$ và xác suất Mưa là $0.28$.

Điểm quan trọng không chỉ là phép tính. Ma trận cập nhật toàn bộ phân phối xác suất theo từng bước, và đó là lý do chuỗi Markov hữu ích cho các quá trình lặp lại.

Chuỗi Markov được dùng ở đâu

Chuỗi Markov hữu ích khi một hệ thống thay đổi theo từng giai đoạn và bạn muốn biết xác suất của điều xảy ra tiếp theo.

Các ví dụ phổ biến gồm mô hình thời tiết, di chuyển trong trò chơi bàn cờ, mô hình hàng đợi và điều hướng web đơn giản hóa. Trong mỗi trường hợp, mô hình chỉ hữu ích nếu các trạng thái được chọn hợp lý và các xác suất chuyển trạng thái là thực tế.

Những lỗi thường gặp với chuỗi Markov

Coi mọi quá trình ngẫu nhiên đều là Markov

Một quá trình không tự động là chuỗi Markov chỉ vì nó ngẫu nhiên. Mô hình đòi hỏi hành vi ở bước tiếp theo phải được quyết định bởi trạng thái hiện tại theo cách bạn đã định nghĩa các trạng thái.

Quên ý nghĩa của các hàng

Mọi người thường nhầm lẫn giữa hàng và cột. Bạn cần dùng một quy ước nhất quán. Trên trang này, hàng là trạng thái hiện tại và cột là trạng thái tiếp theo.

Dùng các xác suất không hợp lệ

Mỗi phần tử phải nằm giữa $0$ và $1$, và mỗi hàng phải có tổng bằng $1$ đối với ma trận chuyển trạng thái chuẩn của một chuỗi Markov hữu hạn.

Cho rằng mô hình dự đoán một tương lai chắc chắn

Chuỗi Markov thường cho xác suất, không phải sự chắc chắn. Ngay cả khi một trạng thái có khả năng cao hơn, vẫn có thể có nhiều trạng thái tiếp theo khác xảy ra.

Hành vi dài hạn phụ thuộc vào chính chuỗi

Một số chuỗi Markov tiến dần đến một phân phối ổn định dài hạn, thường được gọi là phân phối dừng. Nhưng điều đó không xảy ra với mọi chuỗi, và chi tiết còn phụ thuộc vào các tính chất của chuỗi, chẳng hạn như cách các trạng thái liên thông với nhau và liệu kiểu chuyển động có tính chu kỳ hay không.

Vì vậy, bạn hoàn toàn có thể xem việc nhân lặp lại với $P$ là một cách để nghiên cứu hành vi dài hạn, nhưng không nên mặc định rằng nó sẽ hội tụ nếu chưa kiểm tra các điều kiện.

Khi nào chuỗi Markov là một mô hình tốt

Hãy dùng chuỗi Markov khi tất cả các điều sau đây đều đúng ở mức hợp lý:

• Quá trình có thể được mô tả bằng một tập trạng thái đủ gọn.
• Thời gian tiến theo các bước rời rạc, hoặc bạn đã chọn mô hình hóa nó theo cách đó.
• Các xác suất ở bước tiếp theo được xác định một cách có ý nghĩa bởi trạng thái hiện tại.

Nếu các điều kiện đó không thỏa mãn, mô hình vẫn có thể là một xấp xỉ thô, nhưng bạn nên nói rõ điều đó.

Hãy thử phiên bản của riêng bạn

Hãy xây dựng một mô hình ba trạng thái như Nhu cầu thấp, Nhu cầu trung bình và Nhu cầu cao. Chọn các xác suất theo hàng sao cho mỗi hàng có tổng bằng $1$, chọn một phân phối ban đầu, rồi tính bước tiếp theo bằng $\mathbf{v}_{n+1} = \mathbf{v}_n P$. Nếu muốn đi xa hơn, hãy thử cập nhật thêm một lần nữa và xem phân phối có bắt đầu ổn định theo một quy luật nào đó hay không.