Chuỗi Markov thời gian rời rạc

Một chuỗi Markov thời gian rời rạc di chuyển giữa một tập hợp các trạng thái đếm được tại các thời điểm nguyên, chọn trạng thái tiếp theo từ các xác suất chỉ phụ thuộc vào trạng thái hiện tại, được mã hóa gọn gàng trong một ma trận chuyển đổi.

Definition

Một chuỗi Markov thời gian rời rạc là một chuỗi các trạng thái ngẫu nhiên trong một tập hợp đếm được sao cho xác suất của trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại, với các xác suất một bước này được tập hợp trong một ma trận chuyển đổi.

Scope

Chủ đề này bao gồm các ma trận chuyển đổi và phương trình Chapman-Kolmogorov, tính chất Markov mạnh, phân loại các trạng thái thành các lớp giao tiếp và thành các trạng thái tạm thời, tái phát rỗng và tái phát dương, tính chu kỳ, xác suất đạt và thời gian đạt dự kiến được tính bằng phân tích bước đầu tiên, và sự phân đôi tái phát cho các bước ngẫu nhiên trên lưới số nguyên.

Core questions

• Làm thế nào một ma trận chuyển đổi mã hóa động lực học của một chuỗi qua nhiều bước?
• Các trạng thái được phân loại như thế nào theo cấu trúc giao tiếp và sự tái phát của chúng?
• Xác suất đạt và thời gian đạt dự kiến được tính như thế nào?
• Những bước ngẫu nhiên nào trở về điểm xuất phát của chúng một cách chắc chắn và những bước nào thoát ra vô cùng?

Key concepts

• ma trận chuyển đổi
• phương trình Chapman-Kolmogorov
• các lớp giao tiếp
• tái phát và tạm thời
• thời gian đạt

Key theories

Tính chất Markov mạnh

Tính chất Markov tiếp tục đúng tại các thời điểm ngẫu nhiên thích hợp được gọi là thời điểm dừng, do đó một chuỗi khởi động lại từ trạng thái của nó tại thời điểm đó, đây là công cụ chính để phân tích các lần trở lại, các chuyến đi và thời gian đạt.

Sự phân đôi tái phát

Mỗi trạng thái hoặc là tái phát, được ghé thăm vô số lần với xác suất một, hoặc là tạm thời, chỉ được ghé thăm hữu hạn lần; đối với bước ngẫu nhiên đối xứng đơn giản, điều này phụ thuộc vào chiều, với tái phát trong một và hai chiều và tạm thời trong ba chiều trở lên.

Clinical relevance

Các chuỗi Markov thời gian rời rạc mô hình hóa các trò chơi cờ bàn, hệ thống tồn kho và xếp hàng, điều hướng web thông qua chuỗi PageRank, và sự kế thừa di truyền và sinh thái; lý thuyết về thời gian đạt và tái phát của chúng trả lời các câu hỏi thực tế về việc mất bao lâu để một hệ thống đạt đến trạng thái mục tiêu hoặc trở về điều kiện tham chiếu.

History

Markov đã giới thiệu các chuỗi này vào năm 1906, áp dụng chúng vào chuỗi các nguyên âm và phụ âm trong một bài thơ của Pushkin để chứng minh định luật số lớn đúng cho các biến phụ thuộc. Phân tích các bước ngẫu nhiên của Polya năm 1921 đã thiết lập sự phân đôi tái phát phụ thuộc vào chiều mà mang ảnh hưởng của ông.

Key figures

• Andrey Markov
• George Polya
• Joseph L. Doob

Seminal works

• norris1997

Frequently asked questions

Sự khác biệt giữa trạng thái tái phát và trạng thái tạm thời là gì?

Một trạng thái tái phát là trạng thái mà chuỗi chắc chắn sẽ quay lại, và do đó ghé thăm vô số lần, trong khi một trạng thái tạm thời chỉ được ghé thăm hữu hạn lần trước khi chuỗi đi lạc vĩnh viễn.

Tại sao bước ngẫu nhiên đơn giản lại tái phát ở các chiều thấp nhưng không ở các chiều cao?

Trong một và hai chiều, bước đi trở về gốc với xác suất một, nhưng từ ba chiều trở lên có đủ không gian để thoát ra, do đó bước đi chỉ trở về hữu hạn lần và là tạm thời; đây là kết quả kinh điển của Polya.