Xích Markov

Trong toán học, chuỗi Markov 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ố chỉ phụ thuộc vào trạng thái của biến cố trước đó. 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.

Sơ đồ biểu diễn một quá trình Markov với hai trạng thái E và A. Mỗi số biểu diễn xác suất của quá trình Markov chuyển từ trạng thái này sang trạng thái khác theo hướng của mũi tên. Ví dụ, nếu quá trình Markov đang trong trạng thái A, thì xác suất nó chuyển sang trạng thái E là 0,4 còn xác suất nó giữ nguyên ở trạng thái A là 0,6.

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 Markove 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à toán học Nga Andrey Markov

Đị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ỳ).

Các loại xích Markov

Không gian trạng thái và hệ số thời gian của hệ thống cần được xác định rõ ràng. Bảng sau đưa ra cái nhìn tổng quan về các loại quá trình Markov khác nhau dựa trên các mức độ không gian trạng thái và thời gian rời rạc hoặc liên tục:

	Không gian trạng thái đếm được	Không gian trạng thái liên tục hoặc tổng quát
Thời gian rời rạc	Xích Markov thời gian rời rạc trên một không gian trạng thái hữu hạn hoặc đếm được	Xích Markov trên không gian trạng thái đo được (ví dụ như xích Harris)
Thời gian liên tục	Quá trình Markov thời gian liên tục	Bất kỳ quá trình ngẫu nhiên liên tục nào với tính chất Markov (ví dụ như quá trình Wiener)

Để ý rằng không có sự thống nhất trong việc dùng các thuật ngữ để chỉ trường hợp đặc biệc của quá trình Markov. Thường cụm từ "xích Markov" dùng để chỉ xích Markov thời gian rời rạc (DTMC), 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 (tiếng Anh: transition). 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, vốn thường được coi là điều kiện cần thiết để luật số lớn vẫn đúng. Markov sau đó dùng chuỗi Markov để nghiên cứu sự phân bố nguyên âm trong Yevgeny Onegin của nhà văn Aleksandr Pushkin, và chứng minh một định lý giới hạn trung tâm cho những chuỗi đó.

Năm 1912 Henri Poincaré nghiên cứu chuỗi Markov trên nhóm hữu hạn nhằm hiểu rõ hơn việc xáo lá bài. Những ứng dụng ban đầu khác của chuỗi Markov bao gồm mô hình khuếch tán, giới thiệu bởi Paul và Tatyana Ehrenfest năm 1907, và một quá trình rẽ nhánh, đưa ra bởi Francis Galton và Henry William Watson năm 1873, trước nghiên cứu của Markov. Sau khi kết quả của Galton và Watson được công bố, người ta phát hiện rằng quá trình rẽ nhánh đã được nghiên cứu độc lập từ ba thập kỉ trước đó bởi Irénée-Jules Bienaymé. 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.

Ví dụ

Bài chi tiết: Ví dụ của xích Markov

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à những ví dụ của quá trình Markov. 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, được coi là những quá trình quan trọng nhất trong lý thuyết quá trình ngẫu nhiên. 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.

Một chuỗi Markov nổi tiếng là "bước đi của kẻ say", một bước đi ngẫu nhiên trên trục số mà ở mỗi bước, vị trí có thể thay đổi +1 hoặc −1 với xác suất ngang nhau. Từ mỗi vị trí có hai chuyển đổi khả dĩ: đến số nguyên liền trước hoặc liền sau. Xác suất chuyển đổi chỉ phụ thuộc vào vị trí hiện tại, không phụ thuộc vào cách ta đến vị trí đó. Ví dụ, xác suất chuyển đổi từ 5 về 4 và từ 5 lên 6 đều là 0,5, và tất cả những xác suất chuyển đổi khác từ 5 bằng 0. Những xác suất này độc lập với trạng thái trước đó của hệ, bất kể là 4 hay 6.

Một ví dụ xích Markov mô phỏng ví dụ nho-táo-cam.

Một ví dụ khác là thói quen ăn uống của một sinh vật chỉ ăn nho, táo, hoặc cam, và tuân theo các quy luật sau đây:

• Nó ăn một lần một ngày.
• Nếu hôm nay nó ăn táo, ngày mai có ăn nho hoặc cam với cùng khả năng.
• Nếu hôm nay nó ăn nho, ngày mai nó sẽ ăn nho với xác suất 1/10, ăn táo với xác suất 4/10, và ăn cam với xác suất 5/10.
• Nếu hôm nay nó ăn cam, thì ngày mai nó sẽ ăn nho với xác suất 4/10 hoặc ăn táo với xác suất 6/10.

Thói quen ăn của sinh vật này có thể được biểu diễn bằng một chuỗi Markov vì lựa chọn của nó vào ngày mai chỉ phụ thuộc vào thứ nó ăn hôm nay, mà không phải thứ nó ăn hôm qua hay bất kỳ thời điểm nào khác trong quá khứ. Một tính chất thống kê có thể tính được là tỉ lệ số ngày kỳ vọng, xét trên một khoảng thời gian dài, mà sinh vật đó ăn một món nhất định.

Một chuỗi các biến cố độc lập (ví dụ như một chuỗi tung đồng xu) thỏa mãn định nghĩa của một chuỗi Markov. Tuy nhiên, mô hình xích Markov thường chỉ được áp dụng khi phân bố xác suất của bước tiếp theo phụ thuộc vào trạng thái hiện tại.

Định nghĩa chính xác

Xích Markov thời gian rời rạc

Bài chi tiết: Xích Markov thời gian rời rạc

Một xích Markov thời gian rời rạc là một dãy các biến ngẫu nhiên X₁, X₂, X₃, ... với tính chất Markov, tức xác suất chuyển sang trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại chứ không phụ thuộc vào những trạng thái trước đó:

$\Pr(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x\mid X_{n}=x_{n}),$ nếu cả hai xác suất có điều kiện này có nghĩa, tức là nếu $\Pr(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.$

Những giá trị khả dĩ của X_i tạo thành một tập đếm được S gọi là không gian trạng thái của xích.

Biến thể

• Xích Markov thời gian đồng nhất là những quá trình mà

$\Pr(X_{n+1}=x\mid X_{n}=y)=\Pr(X_{n}=x\mid X_{n-1}=y)$

với mọi n. Nói cách khác, xác suất chuyển trạng thái độc lập với n.

• Xích Markov dừng là những quá trình mà

$\Pr(X_{0}=x_{0},\ldots ,X_{k}=x_{k})=\Pr(X_{n}=x_{0},\ldots ,X_{n+k}=x_{k})$

với mọi n và k. Mọi chuỗi Markov dừng đều là chuỗi Markov thời gian đồng nhất theo định lý Bayes.

Điều kiện cần và đủ để một chuỗi Markov thời gian đồng nhất là chuỗi dừng là phân bố của X₀ là một phân bố dừng của chuỗi Markov đó.

• Một chuỗi Markove có trí nhớ (hoặc chuỗi Markov cấp m)

trong đó m là số nguyên dương, là một quá trình thỏa mãn

${\begin{aligned}{}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},\dots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},\dots ,X_{n-m}=x_{n-m})\qquad n>m\end{aligned}}$

Nói cách khác, trạng thái tương lai phụ thuộc vào m trạng thái quá khứ. Có thể thiết lập từ (X_n) một chuỗi (Y_n) mang tính chất Markov bằng cách xét không gian trạng thái là các bộ sắp thứ tự gồm m giá trị X, tức $Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)$.

Xích Markov thời gian liên tục

Bài chi tiết: Xích Markov thời gian liên tục

Một xích Markov thời gian liên tục $(X_{t})_{t\geq 0}$ được định nghĩa bởi một không gian trạng thái hữu hạn hoặc đếm được $S$, một ma trận tốc độ chuyển đổi $Q$ với các chiều bằng với chiều của không gian trạng thái, và một phân bố xác suất ban đầu trên không gian trạng thái đó. Với $i\neq j$, phần tử $q_{ij}$ không âm và diễn tả tốc độ của quá trình khi chuyển từ trạng thái $i$ sang trạng thái $j$. Các phần tử $q_{ii}$ được chọn sao cho mỗi hàng của ma trận tốc độ chuyển đổi có tổng bằng 0.

Có ba định nghĩa tương đương nhau của quá trình này.

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

Xích Markov thời gian liên tục được đặc trưng bởi tốc độ chuyển đổi, đạo hàm theo thời gian của xác suất chuyển đổi giữa trạng thái i và j.

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 t, và giả sử quá trình ở trạng thái i ở thời điểm t. 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 (s < t), và khi h → 0 với mọi j và t 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 i sang trạng thái j.

Định nghĩa xác suất chuyển đổi

Với mọi n = 0, 1, 2, 3, ... và các thời điểm có chỉ số không quá n: t₀, t₁, t₂, ... và tất cả trạng thái ở những thời điểm này i₀, i₁, i₂, i₃, ..., 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 đó p_ij 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 P(0) 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 P, sao cho các phần tử (i, j) của P bằng

$p_{ij}=\Pr(X_{n+1}=j\mid X_{n}=i).$

Khi ấy mỗi hàng của P có tổng bằng 1 và tất cả phần tử đều không âm, tức P 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 P 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 e của P 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 + 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 − 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(X₀). 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 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 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 qui 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 cho mọi trạng thái.

Nếu chuỗi Markov là hồi qui dương, thì tồn tại một phân bố ổn định. Nếu chuỗi Markov là hồi qui 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.

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ì P^k 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ì P^k 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 Lưu trữ 2008-05-22 tại Wayback Machine
• Google Pagerank
• Markov Chains Lưu trữ 2007-06-30 tại Wayback Machine
• “Class structure”. PlanetMath.

• Generating Text Lưu trữ 2008-05-12 tại Wayback Machine (About generating random text using a Markov chain.)
• The World's Largest Matrix Computation Lưu trữ 2008-05-09 tại Wayback Machine (Google's PageRank as the stationary distribution of a random walk through the Web.)
• Disassociated Press Lưu trữ 2005-12-04 tại Wayback Machine in Emacs approximates a Markov process
• [1] Lưu trữ 2005-08-30 tại Wayback Machine Markov chains used to produce semi-coherent English.
• List of Markov chains-related resources Lưu trữ 2006-01-11 tại Wayback Machine