Xích Markov

Bách khoa toàn thư mở Wikipedia

Trong toán học, một xích Markov hay chuỗi Markov (thời gian rời rạc), đặt theo tên nhà toán học người Nga Andrei Andreyevich Markov, là một quá trình ngẫu nhiên thời gian rời rạc với tính chất Markov. Trong một quá trình như vậy, quá khứ không liên quan đến việc tiên đoán tương lai mà việc đó chỉ phụ thuộc theo kiến thức về hiện tại.

Xích Markov là một dãy X₁, X₂, X₃, ... gồm các biến ngẫu nhiên. Tập tất cả các giá trị có thể có của các biến này được gọi là không gian trạng thái $S$ , giá trị của X_n là trạng thái của quá trình (hệ) tại thời điểm n.

Nếu việc xác định (dự đoán) phân bố xác suất có điều kiện của X_n+1 khi cho biết các trạng thái quá khứ là một hàm chỉ phụ thuộc X_n thì:

$P(X_{n+1}=x|X_0, X_1, X_2, \ldots, X_n) = P(X_{n+1}=x|X_n), \,$

trong đó x là một trạng thái nào đó của quá trình (x thuộc không gian trạng thái $S$ ) . Đó là thuộc tính Markov.

Một cách đơn giản để hình dung một kiểu chuỗi Markop cụ thể là qua một ôtômat hữu hạn (finite state machine). Nếu hệ ở trạng thái y tại thời điểm n thì xác suất mà hệ sẽ chuyển tới trạng thái x tại thời điểm n+1 không phụ thuộc vào giá trị của thời điểm n mà chỉ phụ thuộc vào trạng thái hiện tại y. Do đó, tại thời điểm n bất kỳ, một xích Markov hữu hạn có thể được biểu diễn bằng một ma trận xác suất, trong đó phần tử x, y có giá trị bằng $P(X_{n+1}=x|X_n=y) \,$ và độc lập với chỉ số thời gian n (nghĩa là để xác định trạng thái kế tiếp, ta không cần biết đang ở thời điểm nào mà chỉ cần biết trạng thái ở thời điểm đó là gì). Các loại xích Markov hữu hạn rời rạc này còn có thể được biểu diễn bằng đồ thị có hướng, trong đó các cung được gắn nhãn bằng xác suất chuyển từ trạng thái tại đỉnh (vertex) đầu sang trạng thái tại đỉnh cuối của cung đó.

Markov đã đưa ra các kết quả đầu tiên (1906) về các quá trình này. Andrey Nikolaevich Kolmogorov (1936) đã đưa ra một suy rộng tới các không gian trạng thái vô hạn đếm được.

Các xích Markov có liên quan tới chuyển động Brown (Brownian motion) và Tổng hợp ergodic, hai chủ đề quan trọng của vật lý trong những năm đầu của thế kỷ 20, nhưng Markov có vẻ phải tham gia vào quá trình phát triển của toán học, còn gọi là sự mở rộng của luật số lớn cho các sự kiện độc lập.

Mục lục

1 Các tính chất của xích Markov
2 Xích Markov trong không gian trạng thái rời rạc
3 Các ứng dụng khoa học
4 Xem thêm
5 Tham khảo
6 Liên kết ngoài

[sửa] 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ịnh 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.

[sửa] 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 $π *$ là một eigenvector 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 $π *$ , với

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

độc lập với phân bố ban đầu $π$ . Đ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).

[sửa] 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ê điề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ố chuẩn (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 1 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.

[sửa] 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

[sửa] 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.

[sửa] Liên kết ngoài

(pdf) Markov Chains chapter in American Mathematical Society's introductory probability book
Markov Chains
Class structure trên PlanetMath.
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
[1] Markov chains used to produce semi-coherent English.
List of Markov chains-related resources

Thể loại: Lí thuyết xác suất | Quá trình ngẫu nhiên

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Xích Markov

Bách khoa toàn thư mở Wikipedia

Mục lục

[sửa] Các tính chất của xích Markov

[sửa] Xích Markov trong không gian trạng thái rời rạc

[sửa] Các ứng dụng khoa học

[sửa] Xem thêm

[sửa] Tham khảo

[sửa] Liên kết ngoài

Views

Chuyển hướng

Tìm kiếm

Ngôn ngữ khác