Xích Markov

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ố trong tương lai chỉ phụ thuộc vào trạng thái của biến cố hiện tại và độc lập với quá khứ
(Đổi hướng từ Quá trình Markov)

Trong toán họclý thuyết xác suất, xích Markov, chuỗi Markov hay quá trình Markov (Tiếng Anh: Markov chain) 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ố trong tương lai chỉ phụ thuộc vào trạng thái của biến cố hiện tại và độc lập với quá khứ.[1][2]Nói cách khác, xích Markov mô tả một hệ thống không có trí nhớ (memoryless) mà ở đó tất cả các phép thử đều thoả mãn tính chất Markov. 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,[3][4][5] 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ể.[6]

Quá trình Markov 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 tintrí tuệ nhân tạo.[6][7][8]

Giới thiệu

sửa
 
Nhà toán học Nga Andrey Markov

Định nghĩa

sử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 đó.[9] 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.[10] 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ỳ),[11][12][13][14] 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ỳ).[10]

Các loại xích Markov

sửa

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),[15] 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ể.[16][17][18] 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).[19] 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.[20] 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ửa

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ử

sửa

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.[21][22][23] 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.[24][25][26] 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.[27] 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,[21][22][23] vốn thường được coi là điều kiện cần thiết để luật số lớn vẫn đúng.[23] 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 đó.[21]

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 PaulTatyana Ehrenfest năm 1907, và một quá trình rẽ nhánh, đưa ra bởi Francis GaltonHenry William Watson năm 1873, trước nghiên cứu của Markov.[21][22] 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é.[28] 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.[21][29]

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.[30][31] 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.[30][32] Ô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 đó.[30][33] Độ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.[34] Những phương trình vi phân đó nay gọi là phương trình Kolmogorov[35] hoặc phương trình Kolmogorov–Chapman.[36] 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.[31]

Ví dụ

sửa

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.[37][38] 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.[39][40] 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,[24] được coi là những quá trình quan trọng nhất trong lý thuyết quá trình ngẫu nhiên.[41][42][43] 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.[37][38]

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

sửa

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

sửa

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 X1, X2, X3, ... 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 đó:

  nếu cả hai xác suất có điều kiện này có nghĩa, tức là nếu  

Những giá trị khả dĩ của Xi 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ể

sửa
  • Xích Markov thời gian đồng nhất là những quá trình mà
 
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à
 
với mọi nk. 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 X0 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
 
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ừ (Xn) một chuỗi (Yn) 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  .

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

sửa

Một xích Markov thời gian liên tục   được định nghĩa bởi một không gian trạng thái hữu hạn hoặc đếm được  , một ma trận tốc độ chuyển đổi   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  , phần tử   không âm và diễn tả tốc độ của quá trình khi chuyển từ trạng thái   sang trạng thái  . Các phần tử   đượ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.[44]

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

sửa
 
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   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   thì   độc lập với các giá trị   trước (s < t), và khi h → 0 với mọi jt thì

 ,

trong đó   là hàm delta Kronecker, sử dụng ký hiệu o nhỏ. Các   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

sửa

Với mọi n = 0, 1, 2, 3, ... và các thời điểm có chỉ số không quá n: t0, t1, t2, ... và tất cả trạng thái ở những thời điểm này i0, i1, i2, i3, ..., ta có

 

trong đó pij là nghiệm của phương trình vi phân cấp một

 

Với điều kiện ban đầu P(0)ma trận đơn vị.

Không gian trạng thái hữu hạn

sửa

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

 

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

sửa

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

 

Đị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:

 

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  , 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

sửa

Đặ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 (hay phân phối dừng - stationary distribution) 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 (hay không thể tối giản - 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ả.

Hồi quy 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 hữu hạn cho mọi trạng thái.

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

Nếu chuỗi Markov thoả mãn cả ba tính chất bao gồm hồi quy dương, bất khả quy và phi tuần hoàn thì chuỗi Markov có tính ergodic. Khi đó phân phối giới hạn cũng chính là phân phối ổn định.

Xích Markov trong không gian trạng thái rời rạc

sửa

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 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ì 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

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 đợithố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 iki 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 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

sửa

Tham khảo

sửa
  1. ^ “Markov chain | Definition of Markov chain in US English by Oxford Dictionaries”. Oxford Dictionaries | English. Bản gốc lưu trữ ngày 15 tháng 12 năm 2017. Truy cập ngày 14 tháng 12 năm 2017.
  2. ^ Definition at Brilliant.org "Brilliant Math and Science Wiki". Truy cập ngày 12 tháng 5 năm 2019
  3. ^ Samuel Karlin; Howard E. Taylor (ngày 2 tháng 12 năm 2012). A First Course in Stochastic Processes. Academic Press. tr. 47. ISBN 978-0-08-057041-9. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  4. ^ Bruce Hajek (ngày 12 tháng 3 năm 2015). Random Processes for Engineers. Cambridge University Press. ISBN 978-1-316-24124-0. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  5. ^ G. Latouche; V. Ramaswami (ngày 1 tháng 1 năm 1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM. tr. 4–. ISBN 978-0-89871-425-8. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  6. ^ a b Sean Meyn; Richard L. Tweedie (ngày 2 tháng 4 năm 2009). Markov Chains and Stochastic Stability. Cambridge University Press. tr. 3. ISBN 978-0-521-73182-9. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  7. ^ Reuven Y. Rubinstein; Dirk P. Kroese (ngày 20 tháng 9 năm 2011). Simulation and the Monte Carlo Method. John Wiley & Sons. tr. 225. ISBN 978-1-118-21052-9. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  8. ^ Dani Gamerman; Hedibert F. Lopes (ngày 10 tháng 5 năm 2006). Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference, Second Edition. CRC Press. ISBN 978-1-58488-587-0. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  9. ^ Øksendal, B. K. (Bernt Karsten) (2003). Stochastic differential equations: an introduction with applications (ấn bản thứ 6). Berlin: Springer. ISBN 3540047581. OCLC 52203046.
  10. ^ a b Søren Asmussen (ngày 15 tháng 5 năm 2003). Applied Probability and Queues. Springer Science & Business Media. tr. 7. ISBN 978-0-387-00211-8. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  11. ^ Emanuel Parzen (ngày 17 tháng 6 năm 2015). Stochastic Processes. Courier Dover Publications. tr. 188. ISBN 978-0-486-79688-8. Lưu trữ bản gốc ngày 20 tháng 11 năm 2017.
  12. ^ Samuel Karlin; Howard E. Taylor (ngày 2 tháng 12 năm 2012). A First Course in Stochastic Processes. Academic Press. tr. 29 and 30. ISBN 978-0-08-057041-9. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  13. ^ John Lamperti (1977). Stochastic processes: a survey of the mathematical theory. Springer-Verlag. tr. 106–121. ISBN 978-3-540-90275-1. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  14. ^ Sheldon M. Ross (1996). Stochastic processes. Wiley. tr. 174 and 231. ISBN 978-0-471-12062-9. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  15. ^ Everitt, B.S. (2002) The Cambridge Dictionary of Statistics. CUP. ISBN 0-521-81099-X
  16. ^ Parzen, E. (1962) Stochastic Processes, Holden-Day. ISBN 0-8162-6664-6 (Table 6.1)
  17. ^ Dodge, Y. (2003) The Oxford Dictionary of Statistical Terms, OUP. ISBN 0-19-920613-9 (entry for "Markov chain")
  18. ^ Dodge, Y. The Oxford Dictionary of Statistical Terms, OUP. ISBN 0-19-920613-9
  19. ^ Van Huu, Nguyen; Hoang, Vuong Quan; Ngoc, Tran Minh (2005). “Central Limit Theorem for Functional of Jump Markov Processes”. Vietnam Journal of Mathematics. 33 (4): 443–461.
  20. ^ Meyn, S. Sean P., and Richard L. Tweedie. (2009) Markov chains and stochastic stability. Cambridge University Press. (Preface, p. iii)
  21. ^ a b c d e Charles Miller Grinstead; James Laurie Snell (1997). Introduction to Probability. American Mathematical Soc. tr. 464–466. ISBN 978-0-8218-0749-1.
  22. ^ a b c Pierre Bremaud (ngày 9 tháng 3 năm 2013). Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer Science & Business Media. tr. ix. ISBN 978-1-4757-3124-8. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  23. ^ a b c Hayes, Brian (2013). “First links in the Markov chain”. American Scientist. 101 (2): 92–96. doi:10.1511/2013.101.92.
  24. ^ a b Sheldon M. Ross (1996). Stochastic processes. Wiley. tr. 235 and 358. ISBN 978-0-471-12062-9. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  25. ^ Jarrow, Robert; Protter, Philip (2004). “A short history of stochastic integration and mathematical finance: The early years, 1880–1970”. A Festschrift for Herman Rubin. Institute of Mathematical Statistics Lecture Notes – Monograph Series. tr. 75–91. CiteSeerX 10.1.1.114.632. doi:10.1214/lnms/1196285381. ISBN 978-0-940600-61-4. ISSN 0749-2170.
  26. ^ Guttorp, Peter; Thorarinsdottir, Thordis L. (2012). “What Happened to Discrete Chaos, the Quenouille Process, and the Sharp Markov Property? Some History of Stochastic Point Processes”. International Statistical Review. 80 (2): 253–268. doi:10.1111/j.1751-5823.2012.00181.x. ISSN 0306-7734.
  27. ^ Seneta, E. (1996). “Markov and the Birth of Chain Dependence Theory”. International Statistical Review / Revue Internationale de Statistique. 64 (3): 255–257. doi:10.2307/1403785. ISSN 0306-7734. JSTOR 1403785.
  28. ^ Seneta, E. (1998). “I.J. Bienaymé [1796–1878]: Criticality, Inequality, and Internationalization”. International Statistical Review / Revue Internationale de Statistique. 66 (3): 291–292. doi:10.2307/1403518. ISSN 0306-7734. JSTOR 1403518.
  29. ^ Bru B, Hertz S (2001). “Maurice Fréchet”. Trong Heyde CC, Seneta E, Crépel P, Fienberg SE, Gani J (biên tập). Statisticians of the Centuries. New York, NY: Springer. tr. 331–334. doi:10.1007/978-1-4613-0179-0_71. ISBN 978-0-387-95283-3.
  30. ^ a b c Kendall, D. G.; Batchelor, G. K.; Bingham, N. H.; Hayman, W. K.; Hyland, J. M. E.; Lorentz, G. G.; Moffatt, H. K.; Parry, W.; Razborov, A. A.; Robinson, C. A.; Whittle, P. (1990). “Andrei Nikolaevich Kolmogorov (1903–1987)”. Bulletin of the London Mathematical Society. 22 (1): 33. doi:10.1112/blms/22.1.31. ISSN 0024-6093.
  31. ^ a b Cramer, Harald (1976). “Half a Century with Probability Theory: Some Personal Recollections”. The Annals of Probability. 4 (4): 509–546. doi:10.1214/aop/1176996025. ISSN 0091-1798.
  32. ^ Marc Barbut; Bernard Locker; Laurent Mazliak (ngày 23 tháng 8 năm 2016). Paul Lévy and Maurice Fréchet: 50 Years of Correspondence in 107 Letters. Springer London. tr. 5. ISBN 978-1-4471-7262-8. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  33. ^ Valeriy Skorokhod (ngày 5 tháng 12 năm 2005). Basic Principles and Applications of Probability Theory. Springer Science & Business Media. tr. 146. ISBN 978-3-540-26312-8. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  34. ^ Bernstein, Jeremy (2005). “Bachelier”. American Journal of Physics. 73 (5): 395–398. Bibcode:2005AmJPh..73..395B. doi:10.1119/1.1848117. ISSN 0002-9505.
  35. ^ William J. Anderson (ngày 6 tháng 12 năm 2012). Continuous-Time Markov Chains: An Applications-Oriented Approach. Springer Science & Business Media. tr. vii. ISBN 978-1-4612-3038-0. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  36. ^ Kendall, D. G.; Batchelor, G. K.; Bingham, N. H.; Hayman, W. K.; Hyland, J. M. E.; Lorentz, G. G.; Moffatt, H. K.; Parry, W.; Razborov, A. A.; Robinson, C. A.; Whittle, P. (1990). “Andrei Nikolaevich Kolmogorov (1903–1987)”. Bulletin of the London Mathematical Society. 22 (1): 57. doi:10.1112/blms/22.1.31. ISSN 0024-6093.
  37. ^ a b Ionut Florescu (ngày 7 tháng 11 năm 2014). Probability and Stochastic Processes. John Wiley & Sons. tr. 373 and 374. ISBN 978-1-118-59320-2. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  38. ^ a b Samuel Karlin; Howard E. Taylor (ngày 2 tháng 12 năm 2012). A First Course in Stochastic Processes. Academic Press. tr. 49. ISBN 978-0-08-057041-9. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  39. ^ Weiss, George H. (2006). “Random Walks”. Encyclopedia of Statistical Sciences. tr. 1. doi:10.1002/0471667196.ess2180.pub2. ISBN 978-0471667193.
  40. ^ Michael F. Shlesinger (1985). The Wonderful world of stochastics: a tribute to Elliott W. Montroll. North-Holland. tr. 8–10. ISBN 978-0-444-86937-1. Lưu trữ bản gốc ngày 23 tháng 3 năm 2017.
  41. ^ Emanuel Parzen (ngày 17 tháng 6 năm 2015). Stochastic Processes. Courier Dover Publications. tr. 7 and 8. ISBN 978-0-486-79688-8. Lưu trữ bản gốc ngày 20 tháng 11 năm 2017.
  42. ^ Joseph L. Doob (1990). Stochastipoic processes. Wiley. tr. 46 and 47. Lưu trữ bản gốc ngày 20 tháng 11 năm 2017.
  43. ^ Donald L. Snyder; Michael I. Miller (ngày 6 tháng 12 năm 2012). Random Point Processes in Time and Space. Springer Science & Business Media. tr. 32. ISBN 978-1-4612-3166-0. Lưu trữ bản gốc ngày 20 tháng 11 năm 2017.
  44. ^ Norris, J. R. (1997). “Continuous-time Markov chains I”. Markov Chains. tr. 60–107. doi:10.1017/CBO9780511810633.004. ISBN 9780511810633.
  • 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