Bạn sẽ học được gì
- Mô hình hóa một hệ ngẫu nhiên bằng xích Markov thời gian rời rạc, lập ma trận chuyển và tính xác suất chuyển nhiều bước
- Phân loại trạng thái (tối giản, tuần hoàn, hồi quy, không hồi quy) và tìm phân phối dừng; vận dụng định lý hội tụ và định lý ergodic
- Tính xác suất hấp thụ và thời gian chạm kỳ vọng bằng phương pháp phân tích bước đầu
- Sử dụng quá trình Poisson, quá trình đổi mới và xích Markov thời gian liên tục để phân tích hệ hàng đợi
- Nhận biết martingale, áp dụng định lý dừng tùy ý để tính xác suất phá sản và thời gian chờ
- Giải thích nguyên lý của MCMC (thuật toán Metropolis) và định giá quyền chọn trong mô hình nhị thức
Nên học trước
Giới thiệu
Quá trình ngẫu nhiên là họ các biến ngẫu nhiên được đánh chỉ số theo thời gian: số khách trong hàng đợi, giá một cổ phiếu, vị trí của một phân tử, trạng thái của một trang web mà người dùng đang xem. Nếu lý thuyết xác suất mô tả một phép thử, thì quá trình ngẫu nhiên mô tả cả một diễn biến ngẫu nhiên và trả lời những câu hỏi như: về lâu dài hệ ở trạng thái nào bao nhiêu phần trăm thời gian? Trung bình phải chờ bao lâu để một sự kiện xảy ra? Một chiến lược cá cược có thể thắng được một trò chơi công bằng không?
Xích Markov: tương lai chỉ phụ thuộc hiện tại
Phần lớn lộ trình xoay quanh xích Markov (còn gọi là chuỗi Markov): quá trình có tính Markov — biết trạng thái hiện tại thì quá khứ không cho thêm thông tin về tương lai. Với không gian trạng thái hữu hạn, toàn bộ động lực nằm trong một ma trận chuyển P, và xác suất chuyển sau n bước chính là Pⁿ. Đây là lúc đại số tuyến tính phát huy tác dụng: phân phối dừng là vectơ riêng trái ứng với trị riêng 1, còn tốc độ hội tụ về phân phối dừng liên quan tới các trị riêng còn lại. Các khái niệm phân loại trạng thái — tối giản, tuần hoàn, hồi quy, không hồi quy (chuyển tiếp) — quyết định xích có hội tụ hay không.
Từ thời gian rời rạc sang thời gian liên tục
Quá trình Poisson mô hình hóa các sự kiện đến ngẫu nhiên theo thời gian (cuộc gọi, khách hàng, gói tin): số sự kiện trong một khoảng có phân phối Poisson và thời gian giữa hai sự kiện có phân phối mũ. Tổng quát hơn, quá trình đổi mới cho phép thời gian chờ có phân phối bất kỳ, và xích Markov thời gian liên tục được mô tả bằng ma trận cường độ (toán tử sinh) cùng các phương trình Kolmogorov. Lý thuyết hàng đợi — M/M/1, M/M/c — là ứng dụng trực tiếp và rất thực tế của phần này.
Martingale: trò chơi công bằng
Một martingale là quá trình mà kỳ vọng giá trị tương lai, biết toàn bộ quá khứ, đúng bằng giá trị hiện tại — mô hình toán học của một trò chơi công bằng. Định lý dừng tùy ý (optional stopping) cho thấy không có chiến lược dừng hợp lý nào biến trò chơi công bằng thành có lợi, và là công cụ gọn gàng để tính xác suất phá sản hay thời gian chờ kỳ vọng. Martingale là ngôn ngữ nền của tài chính toán học: định giá quyền chọn trong mô hình nhị thức và mô hình Black–Scholes đều dựa trên nó.
Cách học
- Vững lý thuyết xác suất (kỳ vọng có điều kiện, phân phối mũ và Poisson) và thoải mái với ma trận, trị riêng trước khi bắt đầu.
- Với mỗi mô hình, hãy viết chương trình mô phỏng quỹ đạo và so sánh tần suất thực nghiệm với kết quả lý thuyết (phân phối dừng, thời gian chạm kỳ vọng).
- Luôn phân biệt câu hỏi về hành vi dài hạn (phân phối dừng, định lý ergodic) và câu hỏi về thời điểm dừng (xác suất hấp thụ, thời gian thoát) — hai nhóm này dùng hai bộ công cụ khác nhau.
Lộ trình bám theo giáo trình gọn và nhiều ví dụ của Durrett; môn MIT OpenCourseWare 6.262 (Discrete Stochastic Processes) có video bài giảng đầy đủ nếu bạn muốn học theo lớp. Tổng cộng khoảng 45 giờ. Đây là thời lượng tối thiểu cho lượt học đầu; một học phần tương đương ở đại học thường cần 120–150 giờ.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Essentials of Stochastic Processes
Richard Durrett · 2016 · Bản thứ 3
Vì sao chọn: Giáo trình chính (sách trả phí): gọn, rất nhiều ví dụ và bài tập, chỉ cần xác suất bậc đại học. Sáu chương khớp đúng sáu bước của lộ trình: xích Markov, quá trình Poisson, quá trình đổi mới, xích thời gian liên tục, martingale và tài chính toán học.
Nên đọc: Chương 1–6
Markov Chains
J. R. Norris · 1998
Giáo trình xích Markov chặt chẽ của Cambridge (sách trả phí). Đọc khi muốn chứng minh đầy đủ cho các định lý về hồi quy, phân phối dừng và xích thời gian liên tục; chương ứng dụng có thêm mô hình hàng đợi, sinh học và MCMC.
Nên đọc: Chương 1–3; Chương 5 Applications
Markov Chains and Mixing Times
David A. Levin, Yuval Peres · 2017 · Bản thứ 2
Chuyên khảo về thời gian trộn của xích Markov; tác giả cho tải miễn phí bản PDF lần xuất bản thứ hai. Dành cho người học muốn biết xích hội tụ về phân phối dừng nhanh đến mức nào — câu hỏi cốt lõi của MCMC và thuật toán ngẫu nhiên.
Nên đọc: Chương 1–5
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Xích Markov thời gian rời rạc
khoảng 9 giờTính Markov, ma trận chuyển, phương trình Chapman–Kolmogorov, xác suất chuyển nhiều bước; phân loại trạng thái: liên thông, tối giản, hồi quy và không hồi quy, chu kỳ. Luyện tập: lập ma trận chuyển cho mô hình thời tiết ba trạng thái và bài toán con bạc, tính Pⁿ bằng NumPy và quan sát các hàng dần giống nhau.
- Đọc: Chương 1 Markov Chains (phần đầu: định nghĩa, xác suất nhiều bước, phân loại trạng thái) — Essentials of Stochastic Processes
- Đọc: Chương 1 Discrete-time Markov chains — Markov Chains
Bước 2: Phân phối dừng, hội tụ và thời gian chạm
khoảng 8 giờPhân phối dừng, điều kiện cân bằng chi tiết, định lý hội tụ và định lý ergodic; xác suất hấp thụ và thời gian thoát kỳ vọng bằng phân tích bước đầu; ý niệm về thời gian trộn. Luyện tập: tính xác suất phá sản và số ván chơi kỳ vọng trong bài toán con bạc bằng hệ phương trình tuyến tính, rồi kiểm tra bằng mô phỏng.
- Đọc: Chương 1 Markov Chains (phần sau: phân phối dừng, hành vi giới hạn, thời gian thoát) — Essentials of Stochastic Processes
- Đọc: Chương 1 Introduction to finite Markov chains; Chương 4 Introduction to Markov chain mixing — Markov Chains and Mixing Times
Bước 3: Quá trình Poisson và quá trình đổi mới
khoảng 8 giờPhân phối mũ và tính không nhớ, quá trình Poisson thuần nhất, phép gộp và phép tách, quá trình Poisson phức hợp; quá trình đổi mới, định lý đổi mới cơ bản và nghịch lý thời gian chờ. Luyện tập: mô phỏng khách đến một quầy theo quá trình Poisson và kiểm tra nghịch lý thời gian chờ xe buýt bằng thực nghiệm.
- Đọc: Chương 2 Poisson Processes; Chương 3 Renewal Processes — Essentials of Stochastic Processes
Bước 4: Xích Markov thời gian liên tục và hàng đợi
khoảng 8 giờMa trận cường độ, phương trình Kolmogorov tiến và lùi, phân phối dừng của xích liên tục, quá trình sinh – tử; các mô hình hàng đợi M/M/1, M/M/c và công thức Little. Luyện tập: tính độ dài hàng đợi trung bình và thời gian chờ trung bình của hàng đợi M/M/1 theo cường độ tải ρ, rồi mô phỏng để đối chiếu khi ρ tiến gần 1.
- Đọc: Chương 4 Continuous Time Markov Chains — Essentials of Stochastic Processes
- Đọc: Chương 2 Continuous-time Markov chains I; Chương 3 Continuous-time Markov chains II — Markov Chains
Bước 5: Martingale và thời điểm dừng
khoảng 7 giờKỳ vọng có điều kiện theo quá khứ, martingale, martingale trên và dưới, thời điểm dừng, định lý dừng tùy ý và các định lý hội tụ martingale. Luyện tập: dùng martingale Sₙ và Sₙ² − n của bước ngẫu nhiên đối xứng để tìm lại xác suất phá sản và thời gian chơi kỳ vọng đã tính ở bước 2.
- Đọc: Chương 5 Martingales — Essentials of Stochastic Processes
Bước 6: Ứng dụng: MCMC và tài chính toán học
khoảng 5 giờThuật toán Metropolis và lấy mẫu Gibbs như những xích Markov được thiết kế có phân phối dừng cho trước; định giá quyền chọn trong mô hình nhị thức, độ đo trung hòa rủi ro và ý tưởng của công thức Black–Scholes. Luyện tập: cài đặt thuật toán Metropolis lấy mẫu từ một phân phối chỉ biết tới hằng số chuẩn hóa. Muốn đi sâu hơn có thể xem các bài giảng của môn MIT OCW 6.262.
- Đọc: Chương 6 Mathematical Finance — Essentials of Stochastic Processes
- Đọc: Chương 3 Markov chain Monte Carlo: Metropolis and Glauber chains — Markov Chains and Mixing Times
Khái niệm chính
- Quá trình ngẫu nhiên
- Họ các biến ngẫu nhiên {Xₜ} đánh chỉ số theo thời gian t (rời rạc hoặc liên tục) trên cùng một không gian xác suất.
- Tính Markov
- Phân phối có điều kiện của tương lai, biết hiện tại và toàn bộ quá khứ, chỉ phụ thuộc vào hiện tại.
- Ma trận chuyển
- Ma trận xác suất chuyển P với P(i, j) là xác suất đi từ trạng thái i sang j trong một bước; xác suất chuyển n bước là Pⁿ (phương trình Chapman–Kolmogorov).
- Phân loại trạng thái
- Xích tối giản khi mọi trạng thái liên thông với nhau; trạng thái hồi quy nếu chắc chắn quay lại, không hồi quy (chuyển tiếp) nếu có xác suất dương không bao giờ quay lại; chu kỳ là ước chung lớn nhất của các độ dài vòng quay về.
- Phân phối dừng
- Phân phối π thỏa πP = π; với xích tối giản, không tuần hoàn trên tập hữu hạn trạng thái, phân phối tại thời điểm n hội tụ về π từ mọi điểm xuất phát.
- Định lý ergodic
- Với xích tối giản, hồi quy dương, tỉ lệ thời gian xích ở trạng thái j về lâu dài bằng π(j), và bằng nghịch đảo của thời gian quay lại kỳ vọng.
- Phân tích bước đầu
- Kỹ thuật lập hệ phương trình tuyến tính cho xác suất hấp thụ hoặc thời gian chạm kỳ vọng bằng cách điều kiện theo bước chuyển đầu tiên.
- Quá trình Poisson
- Quá trình đếm có số gia độc lập, số sự kiện trong khoảng độ dài t có phân phối Poisson(λt) và thời gian giữa các sự kiện là các biến mũ độc lập tham số λ.
- Quá trình đổi mới
- Tổng quát hóa quá trình Poisson: thời gian giữa các lần đổi mới độc lập cùng phân phối bất kỳ; định lý đổi mới cho tốc độ dài hạn 1/μ.
- Xích Markov thời gian liên tục
- Quá trình Markov với thời gian lưu tại mỗi trạng thái có phân phối mũ, được mô tả bằng ma trận cường độ Q và phương trình Kolmogorov P′(t) = QP(t).
- Hàng đợi M/M/1
- Mô hình hàng đợi với khách đến theo quá trình Poisson, thời gian phục vụ mũ và một máy phục vụ; ổn định khi cường độ tải ρ = λ/μ < 1.
- Martingale
- Quá trình Mₙ thỏa E[Mₙ₊₁ | quá khứ tới n] = Mₙ; mô hình toán học của trò chơi công bằng.
- Thời điểm dừng và định lý dừng tùy ý
- Thời điểm dừng là thời điểm ngẫu nhiên quyết định được chỉ từ thông tin tới hiện tại; dưới điều kiện thích hợp, E[M_T] = E[M₀].
- Markov chain Monte Carlo
- Lấy mẫu từ một phân phối phức tạp bằng cách xây dựng xích Markov (Metropolis, Gibbs) nhận phân phối đó làm phân phối dừng.
Học xong để làm gì
- Lý thuyết hàng đợi: thiết kế tổng đài, máy chủ web, quầy giao dịch và mạng máy tính
- Thuật toán PageRank và các mô hình bước ngẫu nhiên trên đồ thị, mạng xã hội
- Tài chính toán học: định giá quyền chọn, mô hình lãi suất và rủi ro tín dụng
- Thống kê Bayes và học máy: MCMC để lấy mẫu từ phân phối hậu nghiệm, mô hình Markov ẩn trong nhận dạng tiếng nói
- Sinh học và vật lý: động học quần thể, di truyền (mô hình Wright–Fisher), khuếch tán phân tử
- Độ tin cậy và bảo trì: mô hình hỏng hóc – sửa chữa của hệ thống kỹ thuật
Câu hỏi thường gặp
Xích Markov và chuỗi Markov có khác nhau không?
Không, đó là hai cách dịch của Markov chain. Nhiều giáo trình ở Việt Nam dùng "xích Markov", trong khi tài liệu phổ thông thường viết "chuỗi Markov".
Có cần lý thuyết độ đo không?
Không cho lộ trình này: giáo trình của Durrett chỉ dùng xác suất bậc đại học. Lý thuyết độ đo trở nên cần thiết khi học chuyển động Brown và giải tích ngẫu nhiên (tích phân Itô) ở bậc cao học.
Đại số tuyến tính giúp gì ở đây?
Rất nhiều: xác suất chuyển n bước là lũy thừa ma trận, phân phối dừng là vectơ riêng, tốc độ hội tụ gắn với trị riêng thứ hai và thời gian chạm là nghiệm hệ phương trình tuyến tính.
Học xong có thể đọc về giải tích ngẫu nhiên và tài chính định lượng không?
Bạn sẽ có nền tốt về martingale và mô hình nhị thức. Để đi tiếp tới chuyển động Brown, tích phân Itô và mô hình Black–Scholes liên tục, nên học thêm Độ đo và tích phân Lebesgue.
Mất bao lâu để học xong?
Khoảng 45 giờ, tức 8–10 tuần với 5 giờ mỗi tuần, gồm cả thời gian viết mô phỏng cho các mô hình.


