XÍCH MARKOV

 .  XÍCH MARKOV

 

                                                                                        Я вас люблю (к чему лукавить?)

25B

Ứng dụng đầu tiên của xích Markov là nghiên cứu phân tích ngôn ngữ trong trường thiên Eugene Onegin của đại thi hào Nga Alexander Pushkin.Trên hình bên trái là trích đoạn trường thiên (tiếng Nga và tiếng Anh của bản dịch) còn bên phải là bức phác họa chân dung  nhân vật chính Onegin trong trường thiên do Pushkin vẽ .

  

100 năm xích Markov, một công cụ toán học cho nhiều lĩnh vực 

                                                                             

Xích Markov (Markov chain) là một công cụ  toán học được ứng dụng rộng rãi trong nhiều lĩnh vực:ngôn ngữ, dự báo thời tiết, dự báo thị trường , kinh tế,  thông tin, âm nhạc... hóa học, sinh học,vật lý (cơ lượng tử, lò phản ứng hạt nhân, dự án Manhattan).

      

                                                          Hình 1.  Andrei Andreevich Markov

100 năm về trước nhà toán học người Nga A.A. Markov (hình 1) đã có một đóng góp quan trọng vào lý thuyết xác suất. Ngày 23/1/1913 ông công bố kết quả tìm được khi nghiên cứu các quy luật xuất hiện nguyên âm và phụ âm trong trường thiên nổi tiếng  Eugene Onegin của đại thi hào Nga Pushkin tại Hàn lâm viện Hoàng gia Khoa học St.Peterburg. Kỹ thuật ông sử dụng – hiện nay được biết là xích Markov- một hướng mới quan trọng của lý thuyết xác suất [1],[2]. Xích Markov xuất hiện mọi nơi trong khoa học hiện đại. 

Xích Markov là gì và hoạt động như thế nào?

Một xích Markov là một dãy các biến số ngẫu nhiên X1, X2, X3,...có tính chất gọi là tính chất Markov: xác suất của hệ trong tương lai chỉ phụ thuộc vào hiện tại (nghĩa là phụ thuộc vào trạng thái ngay trước đó mà không phụ thuộc vào quá khứ xa hơn). 

Trong lý thuyết xác suất và thống kê 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 nói ở trên.

Một quá trình Markov có thể hình dung như một quá trình “không ký ức-memoryless”: nói một cách cụ thể hơn, một quá trình thỏa mãn tính chất Markov nếu chúng ta có thể đưa ra những tiên liệu cho hệ trong tương lai mà chỉ căn cứ trên hiện trạng ( trạng thái hiện tại) của hệ mà không cần đến toàn bộ lịch sử của hệ trong quá khứ, như vậy là xem hệ không phụ thuộc vào quá khứ xa. 

Thường thường danh từ xích Markov được sử dụng cho một quá trình Markov với một không gian trạng thái rời rạc (hữu hạn và đếm được) định nghĩa trên một tập thời gian rời rạc ( đó là xích Markov với thời gian rời rạc). Nhiều tác giả còn mở rộng xích Markov với thời gian liên tục. 

Lý thuyết xác suất bắt nguồn từ các trò chơi may rủi (súc sắc,...) trong đó kết quả mỗi lần ném (ví dụ con súc sắc) là độc lập với các lần khác. Tính độc lập này làm cho việc tính các xác suất kết hợp (compound probabilities) trở nên dễ dàng.Ví dụ xác suất có được mặt trước của một đồng xu sau hai lần ném là 1/2x1/2 = ¼.

Nói chung xác suất của hai sự kiện sẽ là p.q, nếu ta có nguyên lý độc lập

đối với các trạng thái. Song không phải nhiều trường hợp của cuộc sống tuân theo điều kiện nói trên (tức xảy ra độc lập với nhau). 

Nếu tương lai chỉ phụ thuộc vào thực trạng của hệ hiện nay thì các trạng thái  kết nối với nhau và ta có xích Markov.

Trong xích Markov một hệ phải có một tập các trạng thái khác nhau và những ma trận mô tả sự chuyển biến giữa những trạng thái đó.

Sau đây ta sẽ minh họa  ứng dụng xích Markov vào dự báo thời tiết, dự báo thị trường, sáng tác âm nhạc,  hóa học,vật lý đặc biệt vật lý lượng tử và hạt nhân.

Xích Markov với Dự báo thời tiết 

Một giản đồ mô tả cấu trúc xích Markov sẽ gồm những vòng tròn và những mũi tên. Vòng tròn biểu diễn trạng thái còn mũi tên chỉ quá trình chuyển tiếp. Mỗi mũi tên có đính một con số biểu diễn xác suất của chuyển tiếp.

Dự báo thời tiết hôm nay phụ thuộc vào thời tiết hôm qua. Sau đây là ví dụ của một mô hình đơn giản về thời tiết gồm 3 trạng thái:nắng, mây và mưa và có 9 chuyển tiếp (xem hình 1).

Xích Markov có thể trả lời câu hỏi “Nếu hôm nay trời là mây thì xác suất là mưa trong 2  ngày tiếp theo bằng bao nhiêu? “.Câu trả lời có thể được tìm ra bằng cách lấy tổng của các đóng góp dẫn từ trạng thái mây đến trạng thái mưa trong 2 bước.

 

                   Hình1 .Trên hình ta có 9 xác suất chuyển tiếp giữa 3 trạng thái nắng, mây và mưa.

Xác suất chuyển tiếp cho một xích Markov có 3 trạng thái có thể xếp đặt thành một ma trận 3x3, tức một hình vuông với 9 con số .

Thời tiết của ngày sau ngày mai (tức 2 ngày sau) là thế nào? Có một cách tính dựa trên số học ma trận. Theo dõi tất cả lộ trình 2 bước qua sơ đồ vòng tròn-mũi tên sẽ cho ta thời tiết 2 ngày sau. Điều này tương ứng với phép nhân ma trận  (nhân P với chính nó).  

Quá trình tính các chuyển tiếp nhiều bậc (multistage) tương đương với phép nhân ma trận nhiều lần.Bản thân ma trận  P tiên đoán thời tiết ngày mai, còn

tích P.P=P2 cho thời tiết của ngày sau ngày mai, P.P.P= P3 cho thời tiết sau 3 ngày.

Nếu xét một dự báo dài hạn thì xích Markov hội tụ:  trong ma trận P tất cả hàng đều như nhau và tất cả các cột có cùng một trị số (xem hình 2).Ý nghĩa của điều này là: xét thời tiết dài hạn thì xác suất của một trạng thái không còn phụ thuộc vào trạng thái ban đầu nữa, ví dụ không còn ý nghĩa dự báo thời tiết của 3 tuần sau nếu biết thời tiết của hôm nay.

Xích Markov có một hạn chế.Các xác suất phụ thuộc vào tình trạng hiện tại mà không phụ thuộc vào các tình trạng của lịch sử trước kia.Điều hạn chế này là nghiêm trọng. Cuộc sống là dãy dài của nhiều sự kiện. Và dãy nhân quả này kéo dài vào quá khứ sẽ không phải là xích Markov.

Tuy nhiên quá khứ kéo dài đó có thể thu lại được và mã hóa vào trạng thái hiện tại. Ví dụ thời tiết của ngày mai có thể làm cho phụ thuộc vào thời tiết cả ngày hôm qua  và ngày nay bằng cách tạo ra một mô hình 9 trạng thái mà mỗi trạng thái là dãy 2 ngày (xin xem xích Markov bậc m ở phần trên ). 

     

       

           Hình 2 (lấy từ tài liệu [2] ). Một xích Markov mô tả một tập các trạng thái và các chuyển tiếp giữa các trạng thái đó.Trên sơ đồ phía trái trên dựa trên một mô hình đơn giản về thời tiết được biểu diễn các điểm s=nắng(1) ,c=mây (2)và r= mưa(3);các chuyển tiếp được biểu diễn bằng những mũi tên kèm theo xác suất.Các xác suất cũng có thể xếp thành một ma trận (xem giữa hình), mỗi hàng cho ta một trạng thái khả dĩ của thời tiết của ngày hôm nay còn mỗi cột cho ta trạng thái tương ứng của ngày mai. 

 Nếu lấy lũy thừa ma trận nhiều lần (xem phần dưới hình) ta có dự báo thời tiết cho nhiều ngày sau và ta nhận thấy ma trận tiến đến một cấu hình ổn định trong đó các hàng của ma trận đều giống nhau. 

Xích Markov và dự báo thị trường 

                                                    Hình 3 . Một mô hình thị trường (chứng khoán). Mũi tên đính kèm trị số mô tả xác suất chuyển tiếp ví dụ từ thị trường suy thoái sang thị trường có lãi ta có xác suất 0,25.

Thêm một ví dụ minh họa ở hình số 4 lấy từ tài liệu [3].Các trạng thái kinh tế là: thị trường có lãi (bull market), thị trường thua lỗ (bear market), thời gian suy thoái kinh tế (recession) xét trong một tuần cho mỗi trạng thái.

Theo  kết quả trên  đây thì ta có thể thấy được xác suất chuyển từ thị trường thua lỗ ở thời điểm n sang thị trường có lãi ở thời điểm n+3 là 0,3575, sang thị trường thua lỗ ở thời điểm n+3 là 0,56825 và sang thị trường suy thoái ở thời điểm n+3 là 0,07425.

Xích Markov và sáng tác trong âm nhạc

Xích Markov có thể ứng dụng trong  thuật sáng tác âm nhạc, đặc biệt trong các chương trình CSound, Max hay SuperCollider. Ở đây các trạng thái sẽ là các nốt nhạc: do, re, mi, fa, sol, la, si cùng với các nốt thăng (dièse- #) và giáng (bémol-b). Ký hiệu la tinh của những nốt này là C, D, E, F, G, A, và B.Trên hình 4 ta có ví dụ về những ma trận chuyển tiếp bậc 1 và 2.Trong xích bậc 1 các trạng thái của hệ là những nốt hiện tại. Một xích bậc 2  gồm 2 nốt có thể đưa vào để mô tả chi tiết hơn trạng thái của âm điệu hiện tại .

                           Hình 4. Sử dụng xích Markov trong sáng tác âm nhạc

Cần áp dụng ma trận chuyển tiếp xác suất (transition probability matrix) để chọn các nốt tiếp theo .Ma trận chuyển tiếp phụ thuộc vào các luật hòa âm, giai điệu sử dụng.Đây chính là quá trình sáng tác có sử dụng xích Markov.

Xích Markov trong Hóa học 

  Mỗi phản ứng hóa học là một chuyển biến  trạng thái trong xích Markov. Hóa học là lĩnh vực mà các xích Markov và quá trình Markov với thời gian liên tục được ứng dụng nhiều bởi vì đấy là những hệ thỏa mãn tốt tính chất Markov nói ở phần trên.

Một ví dụ: mô hình cổ điển hoạt động của enzyme theo động học Michaelis-Menten (Michaelis-Menten kinetics). Quá trình này có thể mô tả như một xích Markov (hình 5). 

 

 

Hình 5.  Động học  Michaelis-Menten (Michaelis-Menten kinetics). Chất enzym E kết nối chất nền S (substrate) và tạo nên sản phẩm P. Mỗi phản ứng là một chuyển biến trạng thái trong xích Markov.

Mô hình Michaelis-Menten tương đối rõ ràng cho việc ứng dụng xích Markov song những quá trình phức tạp khác cũng có thể mô hình hóa nhờ xích Markov.

Xích Markov trong vật lý 

Xích Markov được sử dụng rộng rãi trong nhiệt động học và vật lý thống kê. Phương pháp Markov trở nên rất quan trọng trong việc tạo nên (generate) những chuỗi số ngẫu nhiên . Một hướng quan trọng là kết hợp Xích Markov với phương pháp Monte Carlo thành MCMC ( Markov chain Monte Carlo), đây là một phương pháp có tầm quan trọng lớn đối với vật lý hạt nhân ( cơ học lượng tử, khuếch tán neutron, tính toán lò phản ứng,...).

Phương pháp Monte Carlo (MC) như chúng ta biết là một thuật toán (algorithm) thực hiện trên nhiều mẫu ngẫu nhiên (random sample) để cuối cùng lấy trị số trung bình và có được kết quả mong muốn. MC được sử dụng trong vật lý và toán học khi chúng ta gặp khó khăn trong việc thu một kết quả giải tích và  trong việc sử dụng thuật toán tất định (deterministic algorithm).

Một phương pháp quan trọng để gầy ra những điểm mẫu (sampling points) trong một thể tích của không gian nhiều chiều là sử dụng xích Markov.

Tính tích phân

Cơ học lượng tử 

                          Hình 6 . Richard P.Feynman

                          Hình 7. Nicholas C.Metropolis'

Nicholas C.Metropolis (hình 7) là một nhà vật lý và toán học lớn song được ít người biết đến, ông nghiên cứu lò phản ứng hạt nhân cùng với Enrico Ferni và Edward Teller sau đó hợp tác với J.Robert Oppenheimer trong dự án Manhattan-dự án chế tạo bom nguyên tử đầu tiên của Mỹ trong thế chiến II.

Tính toán lò phản ứng hạt nhân  

Phương pháp Monte Carlo đặc biệt hữu hiệu trong việc mô hình các hệ với nhiều bậc tự do như lò phản ứng hạt nhân, các chất lỏng,các hệ sinh học.

Phương pháp Monte Carlo có thể nói đó là tiếp cận những bài toán tất định bằng cách tiếp cận xác suất để giải những bài toán liên quan đến các hệ phức tạp như lò phản ứng hạt nhân.

 

                                                                 Hình 8. Enrico Fermi

Enrico Fermi (hình 8) là nhà vật lý Mỹ gốc Ý giải Nobel năm 1938. Năm 1930 Enrico Fermi sử dụng Monte Carlo trong tính toán khuếch tán neutron. Sau đó, ông cùng nhiều nhà khoa học khác là những người đầu tiên sử dụng MC và MCMC trong việc chế tạo Lò phản ứng hạt nhân đầu tiên năm 1942 và trong dự án Manhattan. 

Như chúng ta biết phương pháp Monte Carlo rất hữu dụng trong việc tính toán lò phản ứng. Trong việc sử dụng MC để tính toán lò phản ứng một khâu quan trọng là tạo nên những quỹ đạo ngẫu nhiên, một trong những cách giải quyết là sử dụng các xích Markov (đó chính là lý thuyết MCMC). 

Kết luận 

Trong thực tế xích Markov được sử dụng rộng rãi trong nhiều lĩnh vực : vật lý, hóa học,sinh học, kinh tế, khoa học thông tin, dự báo thời tiết, ngôn ngữ học, âm nhạc,...

Đặc biệt xích Markov được sử dụng rộng rãi trong vật lý hạt nhân khi kết hợp với phương pháp Monte Carlo thành MCMC: tính toán khuếch tán neutron, tính toán lò phản ứng,... 

Trong trường hợp đơn giản (xem các ví dụ trình bày trên đây xích Markov được minh họa vào những trường hợp  hệ gồm 3 trạng thái với xác suất chuyển biến là P) xích Markov rất dễ sử dụng: chỉ cần thiết lập một mô hình (dựa trên một bộ dữ liệu thống kê), sau đó thiết lập ma trận xác suất chuyển tiếp giữa các trạng thái của hệ P và tiếp theo dùng công thức x (n+1) = x (n) P là có thể tính được xác suất của trạng thái của hệ tại các thời điểm tiếp theo.

Xích Markov là một công cụ toán học rất quan trọng, nhất là khi kết hợp với phương pháp Monte Carlo trong MCMC sẽ trở thành một công cụ toán học đặc biệt cần thiết đối với việc tính toán các hệ phức tạp như lò phản ứng hạt nhân.                                                                     

                                               

Tài liệu tham khảo

[1] Seneta, E.1996. Markov and the birth of chain dependence theory, Internatioal Statistical Review 64:255-263.

[2] Brian Hayes (senior writer for American Scientist), First links in the Markov chain,American Scientist số tháng 3/2013.

[3] The Oxford Dictionary of Statistical Terms, OUP. ISBN 0-19-920613-9 (entry for "Markov chain")

[4] Bước ngẫu nhiên Gauss  Metropolis ( Gaussian Random Walk Metropolis): sử dụng những bước đi theo công thức Y= Xt+sW, trong đó W là biến số ngẫu nhiên Gaussian còn s là độ dài bước đi.

Bước ngẫu nhiên đồng nhất Metropolis (Uniform Random Walk Metropolis): sử dụng những bước đi Y=Xt+sU, trong đó U là biến số phân bố đều (uniformly distributed) trên đoạn [-1,+1].