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 mà chỉ phụ thuộc theo kiến thức về hiện tại.
Còn có xích Markov thời gian liên tục.
Xích Markov là một dãy X1, X2, X3, ... 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, giá trị của Xn là trạng thái của quá trình tại (hệ) thời điểm n.
Nếu phân bố xác suất có điều kiện của Xn+1 trên các trạng thái quá khứ là một hàm chỉ phụ thuộc Xn thì:
trong đó x là một trạng thái nào đó của quá trình. Đó 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 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 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 đầ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 |
[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
đó 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:
Tương tự,
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(Xn) 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
Đâ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
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.
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ả.
Positive recurrent means that the expected return time is finite for every state. Sometimes the terms indecomposable, acyclic, and persistent are used as synonyms for "irreducible", "aperiodic", and "recurrent", respectively. When the state space of a Markov chain is not irreducible, it may be partitioned into a set of (irreducible) communicating classes, each of which may be classified as above. The problem of classification is an important one in the mathematical study of Markov chains and related stochastic processes.
If the Markov chain is positive recurrent, there exists a stationary distribution. If it is positive recurrent and irreducible, there exists a unique stationary distribution, and furthermore the process constructed by taking the stationary distribution as the initial distribution is ergodic. Then the average of a function f over samples of the Markov chain is equal to the average with respect to the stationary distribution,
In particular, this holds for f equal to the identity function. Thus the average of sample values over time is equal to the expected value of the stationary distribution.
Furthermore, the equivalence of averages also holds if f is the indicator function on some subset A of the state space.
where μπ is the measure induced by π.
This makes it possible to approximate the stationary distribution by a histogram or other density estimate of a sequence of samples.
[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, với thành phần thứ (i, j) bằng với
For a discrete state space, the integrations in the k-step transition probability are summations, and can be computed as the k'th power of the transition matrix. That is, if P is the one-step transition matrix, then Pk is the transition matrix for the k-step transition.
The stationary distribution is a vector which satisfies the equation
.
In this case, the stationary distribution π * is an eigenvector of the transition matrix, associated with the eigenvalue 1.
If the transition matrix P is irreducible, and aperiodic, then Pk converges elementwise to a matrix in which each column is the unique stationary distribution π * , with
,
independent of the initial distribution π. This is stated by the Perron-Frobenius theorem.
A transition matrix which is positive (that is, every element of the matrix is positive) is irreducible and aperiodic. A matrix is a stochastic matrix if and only if it is the matrix of transition probabilities of some Markov chain.
Note: In this formulation, element (i, j) is the probability of a transition from j to i. An equivalent formulation is sometimes given with element (i, j) equal to the probability of a transition from i to j. In that case the transition matrix is just the transpose of the one given here. Also, the stationary distribution of the system is then given by the left eigenvector of the transition matrix, instead of the right eigenvector.
The special case of the transition probability being independent of the past is known as the Bernoulli scheme. A Bernoulli scheme with only two possible states is known as a 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ó ki liên kết thì nó có xác suất chuyển tới là (1-q)/ki + 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] Bộ khởi tạo mô phỏng Markov Văn bản liên kết
Markov processes can also be used to generate superficially "real-looking" text given a sample document: they are used in various pieces of recreational "parody generator" software (see Jeff Harrison, Mark V Shaney or [[1]]). Markov chains have also been used in music composition.
[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
[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
- [2] Markov chains used to produce semi-coherent English.
- List of Markov chains-related resources