text:
Xích Markov
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 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 (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 Xn+1 khi cho biết 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 (x thuộc không gian trạng thái ). Đó là thuộc tính Markov.
Một cách đơn giản để hình dung một kiểu chuỗi Markov 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 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
Các tính chất của xích Markov[sửa | sửa mã nguồn]
Đặ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ị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:
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.
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[sửa | sửa mã nguồn]
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
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
- .
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ì 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 , với
- ,
độ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).
Các ứng dụng khoa học[sửa | sửa mã nguồn]
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ố ổ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ó 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.
Xem thêm[sửa | sửa mã nguồn]
- 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[sửa | sửa mã nguồn]
- 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[sửa | sửa mã nguồn]
- (pdf) Markov Chains chapter in American Mathematical Society's introductory probability book
- Google Pagerank
- 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

markdown:
# Xích Markov
|Bài viết này cần thêm
|
Trong
[toán học](/wiki/To%C3%A1n_h%E1%BB%8Dc), 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](/w/index.php?title=Andrei_Andreyevich_Markov&action=edit&redlink=1), là một [quá trình ngẫu nhiên](/wiki/Qu%C3%A1_tr%C3%ACnh_ng%E1%BA%ABu_nhi%C3%AAn) thời gian rời rạc với [tính chất Markov](/wiki/Thu%E1%BB%99c_t%C3%ADnh_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](/wiki/D%C3%A3y_(to%C3%A1n_h%E1%BB%8Dc)) *X* 1, *X* 2, *X* 3,... gồm các [biến ngẫu nhiên](/wiki/Bi%E1%BA%BFn_ng%E1%BA%ABu_nhi%C3%AAn). 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
*X* là trạng thái của quá trình (hệ) tại thời điểm n `n`.
Nếu việc xác định (dự đoán) phân bố
[xác suất có điều kiện](/wiki/X%C3%A1c_su%E1%BA%A5t_c%C3%B3_%C4%91i%E1%BB%81u_ki%E1%BB%87n) của *X* khi cho biết các trạng thái quá khứ là một hàm chỉ phụ thuộc n+1 *X* thì: *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*
). Đó là
[thuộc tính Markov](/wiki/Thu%E1%BB%99c_t%C3%ADnh_Markov).
Một cách đơn giản để hình dung một kiểu chuỗi Markov cụ thể là qua một
[ôtômat hữu hạn](/w/index.php?title=%C3%94t%C3%B4mat_h%E1%BB%AFu_h%E1%BA%A1n&action=edit&redlink=1) ( *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
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](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_(l%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B)#.C4.91.E1.BB.93_th.E1.BB.8B_c.C3.B3_h.C6.B0.E1.BB.9Bng), 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](/wiki/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](/wiki/Chuy%E1%BB%83n_%C4%91%E1%BB%99ng_Brown) ( *Brownian motion*) và [Tổng hợp ergodic](/w/index.php?title=T%E1%BB%95ng_h%E1%BB%A3p_ergodic&action=edit&redlink=1), hai chủ đề quan trọng của vật lý trong những năm đầu của [thế kỷ 20](/wiki/Th%E1%BA%BF_k%E1%BB%B7_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](/wiki/Lu%E1%BA%ADt_s%E1%BB%91_l%E1%BB%9Bn) cho các sự kiện độc lập.
## Mục lục
## Các tính chất của xích Markov[
[sửa](/w/index.php?title=X%C3%ADch_Markov&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=X%C3%ADch_Markov&action=edit§ion=1)]
Đặ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](/w/index.php?title=X%C3%A1c_su%E1%BA%A5t_chuy%E1%BB%83n_d%E1%BB%8Bch&action=edit&redlink=1) 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:
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](/w/index.php?title=X%C3%A1c_su%E1%BA%A5t_bi%C3%AAn&action=edit&redlink=1) ( *marginal distribution*) *P*( *X* ) là phân bố trên các trạng thái tại thời điểm n *n*. Phân bố ban đầu là *P*( *X* 0). 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](/w/index.php?title=Ph%C6%B0%C6%A1ng_tr%C3%ACnh_Frobenius-Perron&action=edit&redlink=1).
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](/w/index.php?title=H%C3%A0m_ri%C3%AAng&action=edit&redlink=1) ( *eigenfunction*) của hàm phân bố điều kiện, gắn với [giá trị riêng](/wiki/Gi%C3%A1_tr%E1%BB%8B_ri%C3%AAng) ( *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[
[sửa](/w/index.php?title=X%C3%ADch_Markov&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=X%C3%ADch_Markov&action=edit§ion=2)]
Nếu không gian trạng thái là
[hữu hạn](/w/index.php?title=H%E1%BB%AFu_h%E1%BA%A1n&action=edit&redlink=1), 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](/wiki/Ma_tr%E1%BA%ADn_(to%C3%A1n_h%E1%BB%8Dc)), gọi là *ma trận chuyển đổi* ( *transition matrix*), với thành phần thứ ( *i*, *j*) bằng vớ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** là ma trận chuyển đổi k *k*-bước.
Phân bố ổn định là một vector thỏa mãn phương trình
.
Như vậy, phân bố ổn định
là một
[eigenvector](/w/index.php?title=Eigenvector&action=edit&redlink=1) của ma trận chuyển đổi, được gắn với [giá trị riêng](/wiki/Gi%C3%A1_tr%E1%BB%8B_ri%C3%AAng) 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** 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 k ![ \pi^*](http://upload.wikimedia.org/math/7/1/b/71b8fc2358b015a138a1e9d2cd008a34.png)
,
độc lập với phân bố ban đầu
. Điều này được phát biểu trong
[Định lý Perron-Frobenius](/w/index.php?title=%C4%90%E1%BB%8Bnh_l%C3%BD_Perron-Frobenius&action=edit&redlink=1).
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ê](/w/index.php?title=Ma_tr%E1%BA%ADn_ng%E1%BA%ABu_nhi%C3%AAn_th%E1%BB%91ng_k%C3%AA&action=edit&redlink=1) ( *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](/w/index.php?title=S%E1%BA%AFp_x%E1%BA%BFp_Bernoulli&action=edit&redlink=1) ( *Bernoulli scheme*). Một Bernoulli scheme chỉ với 2 trạng thái thì gọi là một [quá trình Bernoulli](/w/index.php?title=Qu%C3%A1_tr%C3%ACnh_Bernoulli&action=edit&redlink=1) ( *Bernoulli process*).
## Các ứng dụng khoa học[
[sửa](/w/index.php?title=X%C3%ADch_Markov&veaction=edit&vesection=3) | [sửa mã nguồn](/w/index.php?title=X%C3%ADch_Markov&action=edit§ion=3)]
Các hệ thống Markovian xuất hiện nhiều trong
[vật lí](/wiki/V%E1%BA%ADt_l%C3%BD_h%E1%BB%8Dc), đặc biệt là [cơ học thống kê](/wiki/C%C6%A1_h%E1%BB%8Dc_th%E1%BB%91ng_k%C3%AA) ( *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](/w/index.php?title=L%C3%AD_thuy%E1%BA%BFt_h%C3%A0ng_%C4%91%E1%BB%A3i&action=edit&redlink=1) và [thống kê](/wiki/Khoa_h%E1%BB%8Dc_Th%E1%BB%91ng_k%C3%AA). Bài báo nổi tiếng của [Claude Shannon](/wiki/Claude_Shannon) năm [1948](/wiki/1948) *, là một bước trong việc tạo ra lãnh vực A mathematical theory of communication* [lí thuyết thông tin](/wiki/L%C3%AD_thuy%E1%BA%BFt_th%C3%B4ng_tin), mở ra bằng cách giới thiệu khái niệm của [entropy](/wiki/Entropy_th%C3%B4ng_tin)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](/w/index.php?title=Gi%E1%BA%A3i_thu%E1%BA%ADt_Viterbi&action=edit&redlink=1)để sửa lỗi (error-correction), trong khi các [mô hình Markov ẩn](/wiki/M%C3%B4_h%C3%ACnh_Markov_%E1%BA%A9n)(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](/wiki/Nh%E1%BA%ADn_d%E1%BA%A1ng_ti%E1%BA%BFng_n%C3%B3i)và trong [tin sinh học](/wiki/Tin_sinh_h%E1%BB%8Dc), chẳng hạn để mã hóa vùng/dự đoán gene. [PageRank](/wiki/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* liên kết thì nó có xác suất chuyển tới là (1- i *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.
## Xem thêm[
[sửa](/w/index.php?title=X%C3%ADch_Markov&veaction=edit&vesection=4) | [sửa mã nguồn](/w/index.php?title=X%C3%ADch_Markov&action=edit§ion=4)] [Mô hình Markov ẩn](/wiki/M%C3%B4_h%C3%ACnh_Markov_%E1%BA%A9n) [Ví dụ về Xích Markov](/w/index.php?title=V%C3%AD_d%E1%BB%A5_v%E1%BB%81_X%C3%ADch_Markov&action=edit&redlink=1) [Quá trình Markov](/wiki/Qu%C3%A1_tr%C3%ACnh_Markov) [Quá trình quyết định Markov](/w/index.php?title=Qu%C3%A1_tr%C3%ACnh_quy%E1%BA%BFt_%C4%91%E1%BB%8Bnh_Markov&action=edit&redlink=1) [Shift of finite type](/w/index.php?title=D%E1%BB%8Bch_chuy%E1%BB%83n_h%E1%BB%AFu_h%E1%BA%A1n_ki%E1%BB%83u&action=edit&redlink=1) [Mark V Shaney](/w/index.php?title=Mark_V_Shaney&action=edit&redlink=1) [Markoff Chaney](/w/index.php?title=Markoff_Chaney&action=edit&redlink=1) [xích Markov thời gian liên tục](/w/index.php?title=X%C3%ADch_Markov_th%E1%BB%9Di_gian_li%C3%AAn_t%E1%BB%A5c&action=edit&redlink=1)
## Tham khảo[
[sửa](/w/index.php?title=X%C3%ADch_Markov&veaction=edit&vesection=5) | [sửa mã nguồn](/w/index.php?title=X%C3%ADch_Markov&action=edit§ion=5)]
- 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](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0898712963). *(See Chapter 7.)*
- J.L. Doob.
*Stochastic Processes*. New York: John Wiley and Sons, 1953. [ISBN 0-471-52369-0](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0471523690).
## Liên kết ngoài[
[sửa](/w/index.php?title=X%C3%ADch_Markov&veaction=edit&vesection=6) | [sửa mã nguồn](/w/index.php?title=X%C3%ADch_Markov&action=edit§ion=6)] [(pdf) Markov Chains chapter in American Mathematical Society's introductory probability book](http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf) [Google Pagerank](http://www.lamseo.com/google-pagerank-1) [Markov Chains](http://crypto.mat.sbg.ac.at/~ste/diss/node6.html) [Class structure](http://planetmath.org/?op=getobj&from=objects&id=5765)trên [PlanetMath](/wiki/PlanetMath). [Generating Text](http://www.cs.bell-labs.com/cm/cs/pearls/sec153.html) *(About generating random text using a Markov chain.)* [The World's Largest Matrix Computation](http://www.mathworks.com/company/newsletters/news_notes/clevescorner/oct02_cleve.html) *(Google's PageRank as the stationary distribution of a random walk through the Web.)* [Disassociated Press](http://www.gnu.org/software/emacs/manual/html_node/Dissociated-Press.html)in [Emacs](/wiki/Emacs)approximates a Markov process [[1]](http://rapt.us/toys/chain.pl)Markov chains used to produce semi-coherent English. [List of Markov chains-related resources](http://www.compression-links.info/Markov)


text:
triệt
Từ điển mở Wiktionary
Mục lục
Tiếng Việt[sửa]
Cách phát âm[sửa]
Phiên âm Hán–Việt[sửa]
Các chữ Hán có phiên âm thành “triệt”
Chữ Nôm[sửa]
(trợ giúp hiển thị và nhập chữ Nôm)
Cách viết từ này trong chữ Nôm
Từ tương tự[sửa]
Các từ có cách viết hoặc gốc từ tương tự
Động từ[sửa]
triệt
- Từ dùng trong cuộc đánh kiệu chỉ việc ăn cả bốn quân bài cùng một thứ.
- Triệt ngũ vạn.
- Diệt cho hết.
- Triệt bọn phản động.
Tham khảo[sửa]
- Hồ Ngọc Đức, Dự án Từ điển tiếng Việt miễn phí (chi tiết)
- Thông tin chữ Hán và chữ Nôm dựa theo cơ sở dữ liệu của phần mềm WinVNKey, đóng góp bởi học giả Lê Sơn Thanh; đã được các tác giả đồng ý đưa vào đây. (chi tiết)

markdown:
# triệt
Từ điển mở Wiktionary
## Mục lục
## Tiếng Việt[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-vie-&action=edit§ion=T-1)]
### Cách phát âm[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-pron-&action=edit§ion=T-1)]
|
|[Huế](/wiki/Hu%E1%BA%BF) [Sài Gòn](/wiki/S%C3%A0i_G%C3%B2n) [Vinh](/wiki/Vinh) [Thanh Chương](/wiki/Thanh_Ch%C6%B0%C6%A1ng) [Hà Tĩnh](/wiki/H%C3%A0_T%C4%A9nh)
[Phiên âm Hán–Việt](//vi.wikipedia.org/wiki/Phi%C3%AAn_%C3%A2m_H%C3%A1n-Vi%E1%BB%87t)[ [sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-hanviet-&action=edit§ion=T-1)]
Các chữ Hán có phiên âm thành “triệt”
### Chữ Nôm[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-n%C3%B4m-&action=edit§ion=T-1)]
(
[trợ giúp hiển thị và nhập chữ Nôm](/wiki/Tr%E1%BB%A3_gi%C3%BAp:Ch%E1%BB%AF_N%C3%B4m))
Cách viết từ này trong chữ Nôm
### Từ tương tự[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-paro-&action=edit§ion=T-1)]
Các từ có cách viết hoặc gốc từ tương tự
### Động từ[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-verb-&action=edit§ion=T-1)] **triệt** [Từ](/wiki/t%E1%BB%AB)dùng trong cuộc [đánh](/wiki/%C4%91%C3%A1nh) [kiệu](/wiki/ki%E1%BB%87u)chỉ [việc](/wiki/vi%E1%BB%87c) [ăn](/wiki/%C4%83n)cả [bốn](/wiki/b%E1%BB%91n) [quân bài](/wiki/qu%C3%A2n_b%C3%A0i)cùng một [thứ](/wiki/th%E1%BB%A9). **Triệt**ngũ vạn.
-
[Diệt](/wiki/di%E1%BB%87t)cho [hết](/wiki/h%E1%BA%BFt). **Triệt**bọn phản động.
-
### Tham khảo[
[sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-ref-&action=edit§ion=T-1)]
- Hồ Ngọc Đức,
[Dự án Từ điển tiếng Việt miễn phí](http://www.informatik.uni-leipzig.de/~duc/Dict/)( [chi tiết](/wiki/Wiktionary:Ngu%E1%BB%93n_g%E1%BB%91c/FVDP))
- Thông tin chữ Hán và chữ Nôm dựa theo cơ sở dữ liệu của phần mềm
[WinVNKey](http://winvnkey.sf.net), đóng góp bởi học giả Lê Sơn Thanh; đã được các tác giả đồng ý đưa vào đây. ( [chi tiết](/wiki/Wiktionary:Ngu%E1%BB%93n_g%E1%BB%91c/WinVNKey/L%C3%AA_S%C6%A1n_Thanh))

WARC-Type: response

Content-Type: application/http; msgtype=response

Content-Type: text/html; charset=UTF-8

Connection: close

X-Content-Type-Options: nosniff

Content-language: vi

X-UA-Compatible: IE=Edge

Vary: Accept-Encoding,Cookie

Content-Encoding: gzip

Via: 1.1 varnish, 1.1 varnish

Accept-Ranges: bytes

X-Cache: cp1066 hit (1), cp1065 frontend miss (0)

Cache-Control: private, s-maxage=0, max-age=0, must-revalidate

Set-Cookie: WMF-Last-Access=05-Oct-2015;Path=/;HttpOnly;Expires=Fri, 06 Nov 2015 00:00:00 GMT