Xích Markov

Trong toán học và lý thuyết xác suất, xích Markov, chuỗi Markov hay quá trình Markov (Tiếng Anh: Markov chain) là một quá trình ngẫu nhiên mô tả một dãy các biến cố khả dĩ trong đó xác suất của mỗi biến cố trong tương lai chỉ phụ thuộc vào trạng thái của biến cố hiện tại và độc lập với quá khứ. Nói cách khác, xích Markov mô tả một hệ thống không có trí nhớ (memoryless) mà ở đó tất cả các phép thử đều thoả mãn tính chất Markov. Một dãy vô hạn đếm được, trong đó xích thay đổi trạng thái theo từng khoảng thời gian rời rạc, cho ta một xích Markov thời gian rời rạc (DTMC). Một quá trình diễn ra trong thời gian liên tục được gọi là xích Markov thời gian liên tục (CTMC). Chúng được đặt tên theo nhà toán học người Nga Andrey Markov.

Xích Markov có được ứng dụng rộng rãi làm mô hình thống kê của nhiều quá trình đời thực, như là nghiên cứu hệ thống điều khiển hành trình trong các xe motor, hàng đợi hay hàng người đến sân bay, tỉ giá hối đoái tiền tệ và sự biến đổi của dân số quần thể.

Quá trình Markov là cơ sở cho phương pháp mô phỏng ngẫu nhiên xích Markov Monte Carlo, được dùng để mô phỏng việc lấy mẫu từ một phân bố xác suất phức tạp, và có ứng dụng trong thống kê Bayes, nhiệt động lực học, cơ học thống kê, vật lý, hóa học, kinh tế, tài chính, xử lý tín hiệu, lý thuyết thông tin và trí tuệ nhân tạo.

Giới thiệu
]]

Định nghĩa
Một quá trình Markov là một quá trình ngẫu nhiên thỏa mãn tính chất Markov (đôi khi được gọi là "tính không ghi nhớ"). Nói đơn giản, nó là một quá trình mà các kết quả ở tương lai có thể được dự đoán chỉ dựa trên trạng thái hiện tại và—quan trọng hơn—dự đoán ấy tốt bằng dự đoán dựa trên toàn bộ lịch sử của quá trình đó. Nói cách khác, dựa trên trạng thái hiện tại của hệ thống, những trạng thái quá khứ và tương lai là độc lập.

Một xích Markov là một loại quá trình Markov có không gian trạng thái rời rạc hoặc tập chỉ số rời rạc (thường biểu diễn thời gian), tuy nhiên không có định nghĩa chính xác thống nhất. Thông thường, một xích Markov còn được định nghĩa là một quá trình Markov trong thời gian liên tục hoặc rời rạc với không gian trạng thái đếm được (tức thời gian bất kỳ), nhưng cũng có định nghĩa khác coi xích Markov có thời gian rời rạc trong không gian trạng thái đếm được hoặc liên tục (tức không gian trạng thái bất kỳ). nhưng một số tác giả dùng "quá trình Markov" để chỉ một xích Markov thời gian liên tục (CTMC) mà không nói cụ thể. Ngoài ra, có một số mở rộng của quá trình Markov nằm ngoài bốn loại trên nhưng không có tên gọi đặc biệt nào (xem mô hình Markov). Hơn nữa, chỉ số thời gian không nhất thiết phải là số thực; giống như không gian trạng thái, có những quá trình di chuyển qua tập chỉ số của những cấu trúc toán học khác.

Trong khi tham số thời gian thường là rời rạc, không gian trạng thái của một chuỗi Markov không có quy tắc thống nhất chung nào. Tuy nhiên, nhiều ứng dụng của chuỗi Markov thường dùng không gian trạng thái hữu hạn hoặc vô hạn đếm được, cho phép phân tích thống kê đơn giản hơn. Ngoài số chỉ thời gian và không gian trạng thái, còn có nhiều biến thể, mở rộng và tổng quát khác. Để đơn giản, phần lớn bài viết tập trung vào trường hợp thời gian rời rạc, không gian trạng thái rời rạc, trừ khi được nói rõ.

Chuyển đổi
Sự biến đổi trạng thái của hệ thống được gọi là sự chuyển trạng thái hay chuyển đổi (). Xác suất của các khả năng chuyển trạng thái khác nhau được gọi là xác suất chuyển đổi. Một quá trình được xác định bởi một không gian trạng thái, một ma trận xác suất chuyển đổi mô tả xác suất của các chuyển đổi, và một trạng thái ban đầu (hay phân bố ban đầu) trên không gian trạng thái. Theo thông lệ, ta coi tất cả trạng thái và chuyển đổi khả dĩ được tính trong quá trình, nên luôn có một trạng thái tiếp theo, và quá trình không dừng lại.

Một quá trình ngẫu nhiên thời gian rời rạc gồm một hệ thống ở một trạng thái nhất định vào một bước nào đó, và trạng thái của hệ thay đổi giữa các bước. Các bước này thường được coi là khoảnh khắc trong thời gian, nhưng cũng có thể là khoảng cách vật lý hay những đại lượng khác. Về mặt toán học, các bước này được biểu diễn bằng số nguyên hoặc số tự nhiên. Tính chất Markov nói rằng phân bố xác suất có điều kiện của hệ ở bước tiếp theo (và tất cả các bước trong tương lai) chỉ phụ thuộc vào trạng thái hiện tại của hệ, chứ không phụ thuộc vào trạng thái của hệ ở những bước trước.

Do hệ thay đổi ngẫu nhiên, không thể đoán chính xác được trạng thái của xích Markov ở một thời điểm trong tương lai. Tuy nhiên, các tính chất thống kê của hệ có thể được dự đoán.

Lịch sử
Nhà toán học Nga Andrey Markov nghiên cứu quá trình Markov từ đầu thế kỷ 20, đăng tải bài báo đầu tiên về vấn đề này năm 1906. Quá trình Markov trong thời gian liên tục được phát hiện trước đó từ lâu dưới dạng quá trình Poisson. Markov bắt đầu quan tâm đến việc nghiên cứu một mở rộng của dãy ngẫu nhiên độc lập sau một bất đồng với Pavel Nekrasov, người khẳng định tính độc lập là cần thiết để luật số lớn yếu đúng. Trong bài báo đầu tiên về xích Markov xuất bản năm 1906, Markov chỉ ra rằng trong một số điều kiện nhất định, kết quả trung bình của một xích Markov sẽ hội tụ về một vectơ các giá trị cố định, chứng minh quy luật số lớn yếu mà không cần điều kiện độc lập, Từ năm 1928, Maurice Fréchet bắt đầu quan tâm đến chuỗi Markov, và đến năm 1938 ông xuất bản một bài báo nghiên cứu chi tiết về quá trình ngẫu nhiên này.

Andrei Kolmogorov viết một bài báo năm 1931 phát triển phần lớn lý thuyết về quá trình Markov thời gian liên tục. Kolmogorov một phần được truyền cảm hứng bởi nghiên cứu năm 1900 của Louis Bachelier về sự thay đổi của thị trường chứng khoán cũng như những kết quả của Norbert Wiener về mô hình chuyển động Brown của Einstein. Ông đưa ra và nghiên cứu một nhóm các quá trình Markov cụ thể được biết với tên gọi quá trình khuếch tán, và suy ra các phương trình vi phân mô tả những quá trình đó. Độc lập với những nghiên cứu của Kolmogorov, trong một bài viết năm 1928, nhà toán học Sydney Chapman đưa ra một phương trình, nay gọi là phương trình Chapman–Kolmogorov, trong lúc nghiên cứu chuyển động Brown. Những phương trình vi phân đó nay gọi là phương trình Kolmogorov hoặc phương trình Kolmogorov–Chapman. Những nhà toán học khác có đóng góp quan trọng cho cơ sở của quá trình Markov bao gồm William Feller từ những năm 1930, và Eugene Dynkin từ những năm 1950. Một số biến thể của những quá trình này đã được nghiên cứu từ hàng trăm năm trước trong ngữ cảnh biến số độc lập. Hai ví dụ quan trọng của quá trình Markov là quá trình Wiener, còn gọi là quá trình chuyển động Brown, và quá trình Poisson, Hai quá trình này là quá trình Markov trong thời gian liên tục, còn bước đi ngẫu nhiên trên số nguyên và bài toán sai lầm của con bạc là quá trình Markov trong thời gian rời rạc.

Định nghĩa vô cùng bé

Gọi X_t là biến ngẫu nhiên mô tả trạng thái của quá trình tại thời gian , và giả sử quá trình ở trạng thái ở thời điểm . Khi ấy, với điều kiện X_t=i thì X_{t+h}=j độc lập với các giá trị X_s trước , và khi với mọi và thì
:\Pr(X(t+h) = j \mid X(t) = i) = \delta_{ij} + q_{ij}h + o(h),
trong đó \delta_{ij} là hàm delta Kronecker, sử dụng ký hiệu o nhỏ. Các q_{ij} có thể được coi là biểu diễn tốc độ chuyển đổi từ trạng thái sang trạng thái .

Định nghĩa xác suất chuyển đổi
Với mọi và các thời điểm có chỉ số không quá : và tất cả trạng thái ở những thời điểm này , ta có
:\Pr(X_{t_{n+1}} = i_{n+1} \mid X_{t_0} = i_0 , X_{t_1} = i_1 , \ldots, X_{t_n} = i_n) = p_{i_n i_{n+1}}(t_{n+1} - t_n)
trong đó là nghiệm của phương trình vi phân cấp một
:P'(t) = P(t) Q

Với điều kiện ban đầu là ma trận đơn vị.

Không gian trạng thái hữu hạn
Nếu không gian trạng thái là hữu hạn, phân bố xác suất chuyển đổi có thể được biểu diễn bằng một ma trận, gọi là ma trận chuyển đổi , sao cho các phần tử của bằng
:p_{ij} = \Pr(X_{n+1}=j\mid X_n=i).

Khi ấy mỗi hàng của có tổng bằng 1 và tất cả phần tử đều không âm, tức là một ma trận ngẫu nhiên phải.

Phân phối dừng
Một phân phối dừng là một vectơ hàng, có các phần tử không âm có tổng bằng 1, không bị thay đổi khi thực hiện phép toán ma trận chuyển đổi lên nó. Nói cách khác, nó thỏa mãn
: \pi\mathbf{P} = \pi.

Định nghĩa này có liên quan đến vectơ riêng, và thực chất là vectơ riêng bên trái của với giá trị riêng bằng 1 được chuẩn hóa:
:\pi=\frac{e}{\sum_i{e_i}}
Với một xích Markov ta thường quan tâm đến một trạng thái dừng là giới hạn của dãy phân bố xác suất đối với một phân bố ban đầu nhất định.

Các giá trị của vectơ phân phối dừng thỏa mãn \textstyle \sum_i 1 \cdot \pi_i=1, tức tích vô hướng của với vectơ đơn vị là một, do đó nằm trên một đơn hình.

Các tính chất của xích Markov
Đặc điểm của một xích Markov được biểu diễn bởi phân bố điều kiện

: P(X_{n+1}| X_n)\,

đó là xác suất chuyển dịch của quy trình.

Nó đôi khi còn được gọi là xác suất chuyển dịch "một-bước".

Xác suất của một chuyển dịch trong hai, ba, hoặc nhiều bước hơn được rút ra từ xác suất chuyển dịch một bước và thuộc tính Markov:

: P(X_{n+2}|X_n) = \int P(X_{n+2},X_{n+1}|X_n)\,dX_{n+1}
= \int P(X_{n+2}|X_{n+1}) \, P(X_{n+1}|X_n) \, dX_{n+1}

Tương tự,

: P(X_{n+3}|X_n) = \int P(X_{n+3}|X_{n+2}) \int P(X_{n+2}|X_{n+1}) \, P(X_{n+1}|X_n) \, dX_{n+1} \, dX_{n+2}

Các công thức này tổng quát hóa tới các thời điểm n&nbsp;+&nbsp;k tùy ý trong tương lai bằng cách nhân các xác suất chuyển dịch và lấy tích phân k&nbsp;−&nbsp;1 lần.

Xác suất biên (marginal distribution) P(X'n) là phân bố trên các trạng thái tại thời điểm n. Phân bố ban đầu là P(X0). Sự tiến hóa của quy trình qua một bước được mô tả bằng công thức

: P(X_{n+1}) = \int P(X_{n+1}|X_n)\,P(X_n)\,dX_n

Đây là một phiên bản của phương trình Frobenius-Perron.

Có thể tồn tại một hoặc nhiều phân bố trạng thái π sao cho

: \pi(X) = \int P(X|Y)\,\pi(Y)\,dY

trong đó Y chỉ là một cái tên thuận tiện cho biến tích phân (variable of integration).

Phân bố π như vậy được gọi là một phân bố ổn định (stationary distribution) hoặc phân bố trạng thái ổn định.

Một phân bố ổn định (hay phân phối dừng - stationary distribution) là một hàm riêng (eigenfunction) của hàm phân bố điều kiện, gắn với giá trị riêng (eigenvalue) là 1.

Việc có phân bố ổn định hay không, và nó có là duy nhất hay không (nếu tồn tại), là phụ thuộc vào từng thuộc tính cụ thể của quá trình.

Bất khả quy (hay không thể tối giản - irreducible) nghĩa là mọi trạng thái đều có thể truy xuất từ mỗi trạng thái khác. Một quá trình là tuần hoàn nếu tồn tại ít nhất một trạng thái mà quá trình sẽ trả về trạng thái đó sau một khoảng thời gian cố định (lớn hơn một). Phi tuần hoàn (aperiodic) nghĩa là không tồn tại trạng thái nào như vậy cả.

Hồi quy dương (positive recurrent) nghĩa là thời gian được kì vọng trở lại trạng thái ban đầu là một giá trị dương hữu hạn cho mọi trạng thái.

Nếu chuỗi Markov là hồi quy dương, thì tồn tại một phân bố ổn định. Nếu chuỗi Markov là hồi quy dương và không thể tối giản được nữa, thì tồn tại một phân bố ổn định duy nhất.

Nếu chuỗi Markov thoả mãn cả ba tính chất bao gồm hồi quy dương, bất khả quy và phi tuần hoàn thì chuỗi Markov có tính ergodic. Khi đó phân phối giới hạn cũng chính là phân phối ổn định.

Xích Markov trong không gian trạng thái rời rạc
Nếu không gian trạng thái là hữu hạn, phân bố xác suất chuyển trạng thái có thể được biểu diễn dưới dạng một ma trận, gọi là ma trận chuyển đổi (transition matrix), với thành phần thứ (i, j) bằng với

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

Với không gian trạng thái rời rạc, tích phân của xác suất chuyển đổi ở bước thứ k là phép tổng, và có thể được tính bằng lũy thừa bậc k của ma trận chuyển đổi. Nghĩa là, nếu P là ma trận chuyển đổi 1-bước, thì Pk là ma trận chuyển đổi k-bước.

Phân bố ổn định là một vector thỏa mãn phương trình

: \mathbf{P}\pi^ = \pi^.

Như vậy, phân bố ổn định \pi^ là một vectơ riêng của ma trận chuyển đổi, được gắn với giá trị riêng 1.

Nếu ma trận chuyển đổi P là không thể tối giản được, và phi tuần hoàn, thì Pk hội tụ từng giá trị thành phần về một ma trận trong đó mỗi cột là phân bố ổn định duy nhất \pi^, với

:\lim_{k\rightarrow\infty}\mathbf{P}^k\pi=\pi^,

độc lập với phân bố ban đầu \pi. Điều này được phát biểu trong Định lý Perron-Frobenius.

Ma trận chuyển đổi mà dương (nghĩa là mọi thành phần của ma trận là dương) thì ma trận là không thể tối giản và phi tuần hoàn. Một ma trận là một ma trận ngẫu nhiên thống kê (stochastic matrix) khi và chỉ khi nó là ma trận của các xác suất chuyển đổi của một chuỗi Markov nào đó.

Trường hợp đặc biệt, nếu xác suất chuyển đổi là độc lập với quá khứ thì được gọi là một sắp xếp Bernoulli (Bernoulli scheme). Một Bernoulli scheme chỉ với 2 trạng thái thì gọi là một quá trình Bernoulli (Bernoulli process).

Các ứng dụng khoa học
Các hệ thống Markovian xuất hiện nhiều trong vật lý, đặc biệt là cơ học thống kê (statistical mechanics), bất cứ khi nào xác suất được dùng để biểu diễn các chi tiết chưa được biết hay chưa được mô hình hóa của một hệ thống, nếu nó có thể giả định rằng thời gian là bất biến và không có mối liên hệ trong quá khứ cần nghĩ đến mà không bao gồm sự miêu tả trạng thái. Xích Markov có thể dùng để mô hình hóa nhiều quá trình trong lý thuyết hàng đợi và thống kê. Bài báo nổi tiếng của Claude Shannon năm 1948 A mathematical theory of communication, là một bước trong việc tạo ra lãnh vực lý thuyết thông tin, mở ra bằng cách giới thiệu khái niệm của entropy thông qua mô hình hóa Markov của ngôn ngữ tiếng Anh. Mỗi mô hình đã lý tưởng hóa có thể nắm bắt được nhiều hệ thống được thống kê đều đặn. Thậm chí không cần miêu tả đầy đủ cấu trúc, giống như là những mô hình tín hiệu, hiệu quả trong việc giải mã dữ liệu thông qua kỹ thuật viết code entropy. Nó cũng hiệu quả trong việc ước lượng trạng thái và xác định mẫu. Hệ thống điện thoại di động trên thế giới dùng giải thuật Viterbi để sửa lỗi (error-correction), trong khi các mô hình Markov ẩn (với xác suất chuyển đổi Markov ban đầu là không được biết và phải được ước lượng từ dữ liệu) được dùng rất nhiều trong nhận dạng tiếng nói và trong tin sinh học, chẳng hạn để mã hóa vùng/dự đoán gene.

PageRank của một trang web dùng bởi Google được định nghĩa bằng một xích Markov. Nó là xác suất để đến được trang i trong phân bố ổn định (stationary distribution) dựa vào xích Markov của mọi trạng (đã biết). Nếu N là số lượng trang web đã biết, và một trang i có k'i liên kết thì nó có xác suất chuyển tới là (1-q)/k'i + q/N cho mọi trang mà có liên kết tới và q/N cho mọi trang mà không có liên kết tới. Tham số q thường được chọn là khoảng 0.15.

Phương pháp chuỗi Markov cũng trở nên rất quan trọng trong việc sinh ra những chuỗi số từ những số ngẫu nhiên để phản ánh một cách chính xác những phân bố xác suất phức tạp - tiến trình MCMC là 1 ví dụ. Trong những năm gần đây, phương pháp này đã cách mạng hóa tính khả thi của phương pháp Bayes.

Chuỗi markov cũng có nhiều ứng dụng trong mô hình sinh học, đặc biệt là trong tiến trình dân số- một tiến trình tương tự như tiến trình sinh học.

Một ứng dụng của chuỗi Markov gần đây là ở thống kê địa chất. Đó là: chuỗi Markov được sử dụng trong mô phỏng 3 chiều của giá trị có điều kiện riêng phần. Ứng dụng này được gọi là "chuỗi markov thống kê địa chất", cũng giống như ngành thống kê địa chất. Hiện nay phương pháp này vẫn còn đang phát triển.

Chuỗi Markov cũng có thể ứng dụng trong nhiều trò chơi game. Nhiều loại game của trẻ em (Chutes and Ladders, Candy Land), là kết quả chính xác điển hình của chuỗi Markov. Ở mỗi vòng chơi, người chơi bắt đầu chơi từ trạng thái định sẵn, sau đó phải có lợi thế gì đó mới có thể vượt qua được bàn kế.

Trong ngành quản lý đất đai: người ta còn ứng dụng GIS, RS và chuỗi Markov vào phân tích sự thay đổi sử dụng đất (land use change), từ đó dự báo được tình hình sử dụng đất trong giai đoạn kế tiếp.

Xem thêm
Mô hình Markov ẩn
Ví dụ về xích Markov
Quá trình Markov
Quá trình quyết định Markov
Shift of finite type
Mark V Shaney
Markoff Chaney
Xích Markov thời gian liên tục

Tham khảo

A.A. Markov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp 135–156, 1906.
A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.
Leo Breiman. Probability. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-296-3. (See Chapter 7.)
J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0.

Liên kết ngoài
(pdf) Markov Chains chapter in American Mathematical Society's introductory probability book
Google Pagerank
Markov Chains

Generating Text (About generating random text using a Markov chain.)
The World's Largest Matrix Computation (Google's PageRank as the stationary distribution of a random walk through the Web.)
Disassociated Press in Emacs approximates a Markov process
Markov chains used to produce semi-coherent English.
List of Markov chains-related resources