Xác suất và Thống kê

Quá trình ngẫu nhiên, xích Markov

Dãy các trạng thái ngẫu nhiên biến đổi theo thời gian, trong đó xích Markov chỉ phụ thuộc vào trạng thái hiện tại.

Trực giácNếu ngày mai chỉ quan tâm tới hôm nay, bạn có thể dự đoán tương lai xa tới đâu?

Hãy hình dung một con ếch nhảy qua lại giữa các lá sen trên ao, hoặc một quân cờ di chuyển từng ô một, hoặc thời tiết ngày mai chuyển đổi giữa nắng và mưa. Trong mỗi trường hợp có một trạng thái (lá sen nào, ô nào, thời tiết nào) thay đổi ở mỗi nhịp đồng hồ, và sự thay đổi đó không cố định trước — nó ngẫu nhiên. Một quá trình ngẫu nhiên đơn giản là một họ các biến ngẫu nhiên $X_n \in S$ được đánh chỉ số theo thời gian $n=0,1,2,\dots$ , mỗi thời điểm một trạng thái ngẫu nhiên. Cú nhảy của con ếch, và vô số hệ thống thực tế khác — đột biến gen, khách hàng tới xếp hàng, giá chứng khoán nhảy số, người lướt web bấm liên kết — đều là quá trình ngẫu nhiên theo nghĩa này. Xích Markov là trường hợp đặc biệt, cực kỳ hữu ích, khi con ếch hay quên: xác suất cú nhảy tiếp theo chỉ phụ thuộc vào lá sen nó đang ngồi hiện tại, không bao giờ phụ thuộc vào con đường ngoằn ngoèo đã đưa nó tới đó.

Đối tượng toán họcĐặc trưng chứng minh

Sơ đồ Markov có hướng ba trạng thái: các mũi tên mã hóa xác suất chuyển

p_{ij}

, mỗi hàng thỏa

\sum_jp_{ij}=1

, và điều khiển trọng tâm làm nổi bật các chuyển tiếp đi ra từ

X_0

Đại họcTính chất Markov, ma trận chuyển và phân phối dừng

Định nghĩa: Xích Markov

Cho $S$ là một tập trạng thái đếm được và $X_n \in S$ với $n=0,1,2,\dots$ là một quá trình ngẫu nhiên nhận giá trị trong $S$ . Quá trình này là một xích Markov nếu nó có tính chất Markov: $P(X_{n+1}\mid X_n,\dots,X_0)=P(X_{n+1}\mid X_n)$ với mọi lựa chọn trạng thái và mọi $n$ . Nói cách khác, toàn bộ quá khứ $X_0,\dots,X_{n-1}$ không cho thêm thông tin nào về $X_{n+1}$ một khi đã biết $X_n$ — trạng thái hiện tại là một tóm tắt đầy đủ cho toàn bộ lịch sử.

P(X_{n+1}\mid X_n,\dots,X_0)=P(X_{n+1}\mid X_n)

Khi tập trạng thái hữu hạn (hoặc đếm được) và xích thuần nhất theo thời gian, toàn bộ tính ngẫu nhiên này được nắm bắt bởi một ma trận chuyển $P$ duy nhất với các phần tử $P_{ij}=P(X_{n+1}=j\mid X_n=i)$ — xác suất nhảy tới trạng thái $j$ biết xích đang ở $i$ . Vì từ bất kỳ trạng thái nào xích cũng phải đi đâu đó, mỗi hàng của $P$ là một phân phối xác suất: không âm và tổng bằng một, $\sum_{j\in S} P_{ij}=1$ . Một ma trận có tính chất tổng hàng bằng một này được gọi là ngẫu nhiên theo hàng. Nhân các bước chuyển $n$ -bước và $m$ -bước tổ hợp chính xác như phép nhân ma trận, phương trình Chapman–Kolmogorov $P^{(n+m)}=P^{(n)}P^{(m)}$ , nên xác suất ở mỗi trạng thái sau $n$ bước xuất phát từ phân phối $\mu_0$ đơn giản là $\mu_0 P^n$ .

P_{ij}=P(X_{n+1}=j\mid X_n=i)

Một phân phối xác suất $\pi$ trên $S$ là dừng nếu nó là một điểm bất động của động lực này: $\pi P=\pi$ cùng với $\sum_{i\in S}\pi_i=1$ và $\pi_i\ge0$ . Một khi phân phối của xích bằng $\pi$ ở một bước thời gian, nó bằng $\pi$ ở mọi bước thời gian sau đó — số lượng ếch trên mỗi lá sen ngừng thay đổi ở mức tổng thể, dù mỗi con ếch riêng lẻ vẫn tiếp tục nhảy ngẫu nhiên. Tìm $\pi$ quy về giải một hệ tuyến tính, và đó chính xác là điều định lý cơ bản dưới đây biến thành một đảm bảo về sự tồn tại, tính duy nhất và sự hội tụ.

\pi P=\pi

Các tính chất chính phân loại một xích Markov
Tính chất	Định nghĩa	Hệ quả
Bất khả quy	Mọi trạng thái đều tới được mọi trạng thái khác với xác suất dương	Xích có (nhiều nhất) một phân phối dừng
Không tuần hoàn	Ước chung lớn nhất của các thời gian quay lại có thể của một trạng thái là 1	Các lũy thừa $P^n$ hội tụ theo từng phần tử, không chỉ trung bình
Hồi quy	Xuất phát từ trạng thái $i$ , xích quay lại $i$ với xác suất 1	Trên một xích hữu hạn bất khả quy, điều này luôn tự động đúng

Định lý: Định lý cơ bản của xích Markov hữu hạn

Nếu một xích Markov trên tập trạng thái hữu hạn $S$ là bất khả quy và không tuần hoàn, thì tồn tại duy nhất một phân phối dừng $\pi$ với $\pi P=\pi$ , $\pi_i>0$ với mọi trạng thái, và $\lim_{n\to\infty}P^n=\mathbf 1\,\pi$ — mọi hàng của $P^n$ hội tụ về $\pi$ khi $n\to\infty$ , bất kể phân phối xuất phát.

Vì sao đúng?

Đây là lý do khiến xích Markov hữu ích: nó nói rằng hành vi dài hạn của một hệ tiến hóa ngẫu nhiên ổn định về một mẫu hình duy nhất, có thể dự đoán được, quên đi điểm xuất phát của nó, và cho ta biết chính xác mẫu hình đó là gì (điểm bất động duy nhất của động lực chuyển tiếp).

Chứng minh

Tồn tại và duy nhất. Vì $P$ ngẫu nhiên theo hàng, vectơ toàn số 1 là một vectơ riêng phải với trị riêng 1, nên 1 cũng là trị riêng của $P$ (một ma trận và ma trận chuyển vị của nó có chung trị riêng), và có một vectơ riêng trái tương ứng $\pi$ với $\pi P=\pi$ . Tính bất khả quy có nghĩa $P$ là ma trận chuyển của một đồ thị liên thông mạnh, nên định lý Perron–Frobenius áp dụng được: trị riêng 1 là đơn (bội một) và vectơ riêng của nó có thể chọn dương ngặt, cho tính duy nhất sau khi chuẩn hóa để các phần tử có tổng bằng 1.

Hội tụ. Không tuần hoàn cộng với bất khả quy có nghĩa mọi trị riêng khác $\lambda$ của $P$ thỏa $|\lambda|<1$ (đây là phần mà tính tuần hoàn sẽ phá vỡ: một xích tuần hoàn có thêm các trị riêng nằm đúng trên đường tròn đơn vị, chẳng hạn $-1$ , không bao giờ tắt dần). Viết một phân phối xuất phát tùy ý $\mu_0$ trong cơ sở riêng của $P$ , thành phần dọc theo $\pi$ (trị riêng 1) tồn tại không đổi mãi mãi, trong khi mọi thành phần khác bị nhân với $\lambda^n$ ở bước $n$ và co lại theo cấp số nhân về không.

Kết hợp hai bước, $\mu_0 P^n$ hội tụ về riêng thành phần trị riêng 1, chính là $\pi$ , và vì điều này đúng với mọi phân phối xuất phát $\mu_0$ (bao gồm mỗi khối điểm, tức mỗi hàng của ma trận đơn vị), mọi hàng của $P^n$ hội tụ về $\pi$ như đã khẳng định.

Định lý: PageRank là phân phối dừng của người lướt web ngẫu nhiên

Cho $J$ là ma trận toàn số 1 kích thước $N\times N$ ( $N$ = số trang web) và $P$ là ma trận liên kết ngẫu nhiên theo hàng (trang $i$ liên kết đều tới mỗi trang nó trỏ tới; trang không có liên kết ra được gửi đều tới mọi trang). Với mọi hệ số giảm chấn $d\in(0,1)$ , ma trận Google $G=dP+(1-d)\tfrac1N J$ là ma trận chuyển của một xích Markov bất khả quy, không tuần hoàn, nên theo định lý cơ bản ở trên nó có duy nhất một phân phối dừng $\pi$ với $\pi=\pi\Big(dP+(1-d)\tfrac1N J\Big)$ — $\pi$ này chính là vectơ PageRank, và thuật toán lặp lũy thừa $\pi_{k+1}=\pi_k G$ hội tụ về nó từ bất kỳ phỏng đoán xuất phát nào.

Vì sao đúng?

Điều này biến ý tưởng mơ hồ "trang quan trọng được liên kết bởi các trang quan trọng khác" thành một bài toán điểm bất động rõ ràng với nghiệm duy nhất được đảm bảo, và giải thích tại sao việc đơn giản lặp lại "lan tỏa thứ hạng dọc theo liên kết" (lặp lũy thừa) được đảm bảo hoạt động thay vì dao động hay phân kỳ.

Chứng minh

Bất khả quy. Vì $1-d>0$ , mọi phần tử của $G$ đều dương ngặt ( $G_{ij}\ge(1-d)/N>0$ ), nên từ bất kỳ trang nào cũng có một bước nhảy trực tiếp với xác suất dương tới bất kỳ trang khác — đồ thị nền tảng liên thông mạnh một cách tầm thường, do đó $G$ bất khả quy.

Không tuần hoàn. Một xích mà mọi trạng thái đều có thể đi trực tiếp tới mọi trạng thái (kể cả chính nó, vì $G_{ii}>0$ cũng vậy) có sẵn thời gian quay lại ở mọi độ dài $1,2,3,\dots$ , mà ước chung lớn nhất của chúng là 1; nên $G$ không tuần hoàn.

Tồn tại, duy nhất, hội tụ. $G$ ngẫu nhiên theo hàng theo cách xây dựng (tổ hợp lồi $dP+(1-d)\tfrac1N J$ của hai ma trận ngẫu nhiên theo hàng $P$ và $J/N$ là ngẫu nhiên theo hàng), và nó bất khả quy, không tuần hoàn như vừa chỉ ra, nên định lý cơ bản của xích Markov hữu hạn áp dụng trực tiếp: tồn tại duy nhất $\pi$ dừng với $\pi=\pi\Big(dP+(1-d)\tfrac1N J\Big)$ , và $G^n$ hội tụ theo từng phần tử về một ma trận có mọi hàng bằng $\pi$ .

Lặp lũy thừa. Vì $\pi_k=\pi_0G^k$ với mọi phân phối xuất phát $\pi_0$ , và mọi hàng của $G^k$ hội tụ về $\pi$ khi $k\to\infty$ , trung bình có trọng số $\pi_0G^k$ cũng hội tụ về $\pi$ — đây chính xác là lý do việc lặp lại $\pi_{k+1}=\pi_k G$ từ một thứ hạng xuất phát tùy ý (thường là phân phối đều) hội tụ về vectơ PageRank thật.

Đại họcỨng dụng thực tiễn và Ví dụ minh họa

Xích Markov mô hình hóa vô số hệ thống nơi việc "quên quá khứ khi biết hiện tại" là một xấp xỉ hợp lý. Thuật toán PageRank gốc của Google xếp hạng trang web theo phân phối dừng của một người lướt web ngẫu nhiên bấm liên kết (đã chứng minh ở trên). Trong sinh học, trình tự DNA và con đường gấp cuộn protein được mô hình hóa như xích Markov trên các nucleotide hay cấu hình. Trong tài chính và nghiên cứu vận trù, hệ thống xếp hàng (khách chờ ở quầy thu ngân) và mức tồn kho được theo dõi như xích Markov để tính thời gian chờ dài hạn và xác suất hết hàng. Trong nhận dạng giọng nói và xử lý ngôn ngữ tự nhiên, mô hình Markov ẩn nối chuỗi các âm vị hay nhãn từ loại. Và trong khoa học máy tính, thuật toán MCMC (Markov chain Monte Carlo) xây dựng một xích Markov có phân phối dừng là một phân phối mục tiêu khó lấy mẫu, rồi mô phỏng nó để rút ra các mẫu xấp xỉ.

Ví dụ: Phân phối dừng của thời tiết

Một mô hình thời tiết đơn giản có hai trạng thái, Nắng và Mưa, với ma trận chuyển $P=\begin{pmatrix}0.9&0.1\\0.5&0.5\end{pmatrix}$ (hàng 1 = từ Nắng, hàng 2 = từ Mưa; nên từ Nắng nó vẫn Nắng với xác suất $0.9$ và thành Mưa với xác suất $0.1$ ). Tìm phân phối dừng $\pi=(\pi_1,\pi_2)$ .

Lời giải

Các phương trình dừng là $\pi P=\pi$ , tức $0.9\pi_1+0.5\pi_2=\pi_1$ và $0.1\pi_1+0.5\pi_2=\pi_2$ , cùng với $\pi_1+\pi_2=1$ .

Phương trình đầu đơn giản thành $0.5\pi_2=0.1\pi_1$ , tức $\pi_2=0.2\pi_1$ (phương trình thứ hai cho cùng quan hệ, vì các hàng của $\pi P-\pi$ phụ thuộc lẫn nhau).

Thay vào chuẩn hóa: $\pi_1+0.2\pi_1=1$ , nên $1.2\pi_1=1$ và $\pi_1=5/6$ , $\pi_2=1/6$ .

Vậy $\pi=(5/6,\,1/6)$ — về dài hạn xích thời tiết này Nắng $5/6$ thời gian. Điều này khớp trực giác: trạng thái 1 (Nắng) "dính" hơn nhiều (xác suất $0.9$ ở lại) so với trạng thái 2 (Mưa, xác suất $0.5$ ở lại), nên xích dành phần lớn thời gian ở trạng thái dính.

Ví dụ: PageRank của một mạng ba trang web

Một mạng web nhỏ có ba trang $A,B,C$ : trang $A$ liên kết đều tới $B$ và $C$ , trang $B$ chỉ liên kết tới $C$ , và trang $C$ chỉ liên kết ngược lại $A$ : $P(A\to B)=P(A\to C)=\tfrac12,\quad P(B\to C)=1,\quad P(C\to A)=1$ . Mô hình hóa các cú bấm của người lướt web ngẫu nhiên như một xích Markov trên $\{A,B,C\}$ và tìm vectơ PageRank $\pi$ .

Lời giải

Trước tiên kiểm tra xích bất khả quy và không tuần hoàn: mọi trang đều tới được mọi trang khác (qua $A\to B\to C\to A$ ), và có chu trình độ dài 2 ( $A\to C\to A$ ) và độ dài 3 ( $A\to B\to C\to A$ ), ước chung lớn nhất là 1, nên định lý cơ bản đảm bảo tồn tại duy nhất $\pi$ dừng.

Viết các phương trình cân bằng theo từng cột: $\pi_A$ chỉ nhận dòng từ $C$ , $\pi_B$ chỉ từ $A$ , và $\pi_C$ từ cả $A$ và $B$ : $\pi_A=\pi_C,\quad \pi_B=\tfrac12\pi_A,\quad \pi_C=\tfrac12\pi_A+\pi_B$ .

Hai phương trình đầu cho $\pi_A=\pi_C$ và $\pi_B=\tfrac12\pi_A$ trực tiếp; thay vào chuẩn hóa $\pi_A+\pi_B+\pi_C=1$ cho $\pi_A+\tfrac12\pi_A+\pi_A=1$ , tức $\tfrac52\pi_A=1$ .

Giải ra, $\pi_A=2/5$ , nên $\pi=(\pi_A,\pi_B,\pi_C)=(2/5,\,1/5,\,2/5)$ . Trang $A$ và trang $C$ đồng hạng cao nhất vì mỗi trang nhận liên kết từ một trang mà bản thân chỉ có một liên kết ra để gửi toàn bộ trọng số qua đó — đúng kiểu "tập trung phiếu bầu" mà PageRank được thiết kế để thưởng.

Lỗi hay gặp. Hai sai lầm liên tục xảy ra. Thứ nhất, nhầm lẫn tính chất Markov với độc lập hoàn toàn: tương lai của một xích Markov không độc lập với quá khứ nói chung — nó độc lập với quá khứ với điều kiện biết trạng thái hiện tại, một phát biểu yếu hơn nhiều (và hữu ích hơn nhiều). Thứ hai, quên rằng một phân phối dừng có thể tồn tại mà xích không bao giờ hội tụ về nó: một xích tuần hoàn (ví dụ một xích hai trạng thái luân phiên tất định

A\to B\to A\to B

) vẫn có một phân phối dừng giải

\pi P=\pi

, nhưng

P^n

không bao giờ hội tụ — nó cứ dao động mãi giữa hai ma trận. Sự hội tụ cần tính không tuần hoàn thêm vào tính bất khả quy; riêng phương trình

\pi P=\pi

là chưa đủ.

Ghi chú lịch sử

Andrey Markov giới thiệu các xích mang tên ông vào năm 1906, trong một bài báo phân tích sự luân phiên nguyên âm và phụ âm trong bài thơ Eugene Onegin của Pushkin — một phần để phản bác một tuyên bố đương thời rằng tính độc lập là cần thiết để luật số lớn đúng, cho thấy các dãy phụ thuộc nhưng hay quên vẫn tuân theo các luật giới hạn tương tự. Lý thuyết vẫn chủ yếu mang tính tổ hợp cho tới khi bài báo năm 1931 của Andrey Kolmogorov về các phương pháp giải tích trong lý thuyết xác suất đặt các quá trình Markov tổng quát, gồm cả phiên bản thời gian liên tục và trạng thái liên tục, trên nền tảng lý thuyết độ đo chặt chẽ, liên hệ chúng với phương trình vi phân (phương trình tiến và lùi Kolmogorov) và mở đường cho lý thuyết tổng quát về quá trình ngẫu nhiên dùng ngày nay.

Andrey Kolmogorov

Hiện trạng nghiên cứu tính đến năm 2026

Xích Markov vẫn là một lĩnh vực nghiên cứu sôi động vượt xa cách dùng cổ điển của nó. Markov chain Monte Carlo (MCMC) là trụ cột tính toán của thống kê Bayes và vật lý thống kê, và một bài toán mở trung tâm là chặn thời gian trộn — cần bao nhiêu bước để một xích gần với phân phối dừng của nó — cho các xích phát sinh từ các mô hình chiều cao thực tế; các kỹ thuật khoảng cách phổ và ghép cặp cho câu trả lời sắc nét với một số xích (xáo bài, đi bộ ngẫu nhiên trên nhóm) nhưng vẫn khó cho nhiều xích dùng trong thực tế, chẳng hạn xích lấy mẫu từ hậu nghiệm Bayes phức tạp hay các phân phối kiểu mô hình Ising gần điểm chuyển pha. Quá trình quyết định Markov, thêm các hành động điều khiển được vào một xích Markov, là nền tảng của học tăng cường hiện đại; hiểu độ phức tạp mẫu và các đảm bảo hội tụ của thuật toán RL hoạt động trên không gian trạng thái khổng lồ hoặc liên tục là một lĩnh vực hoạt động tích cực kết nối lý thuyết xác suất, tối ưu hóa và học máy. Về mặt ứng dụng, các mô hình người lướt web ngẫu nhiên và khuếch tán tinh vi hơn tiếp tục được phát triển cho hệ thống xếp hạng và gợi ý, vượt xa công thức PageRank ban đầu.

Tính chất Markov nói rằng, biết trạng thái hiện tại $X_n$ , trạng thái tiếp theo $X_{n+1}$ là:

Một xích 3 trạng thái có các hàng ma trận chuyển mà mỗi hàng phải:

Với ma trận chuyển $P=\begin{pmatrix}0.9&0.1\\0.5&0.5\end{pmatrix}$ , vectơ $\pi$ nào thỏa $\pi P=\pi$ và $\sum_{i\in S}\pi_i=1$ ?

Trong PageRank gốc của Google, hệ số giảm chấn $d<1$ (trộn thêm một bước nhảy đều $1/N$ tới mọi trang) chủ yếu cần thiết vì nó đảm bảo ma trận Google là:

Tài liệu tham khảo

David A. Levin, Yuval Peres, Elizabeth L. Wilmer (2017). Markov Chains and Mixing Times
Sergey Brin, Lawrence Page (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine
James R. Norris (1997). Markov Chains