CHƯƠNG 1: TỔNG QUAN VỀ XÍCH MARKOV 1. Tìm hiểu về quá trình Markov ngẫu nhiên Hầu hết các hiện tượng xảy ra trong tự nhiên và xã hội đều có tính chất ngẫu nhiên, đó là sự phản ánh của các mối ràng buộc phức tạp mà ta không biết trước được. Trong xác suất Thống kê chúng ta đã biết khái niệm biến ngẫu nhiên, véc tơ ngẫu nhiên, đó là các biến nhận giá trị nào đó phụ thuộc vào các yếu tố ngẫu nhiên. Khi các biến ngẫu nhiên phụ thuộc vào thời gian ta có quá trình ngẫu nhiên.
Lý thuyết quá trình ngẫu nhiên lần đầu tiên được nghiên cứu liên quan đến bài toán dao động và nhiễu của các hệ vật lý. Quá trình ngẫu nhiên là một mô hình toán học của quá trình thực nghiệm mà sự phát triển bị chi phối bởi các quy luật xác suất. Quá trình ngẫu nhiên cung cấp những mô hình hữu ích để nghiên cứu nhiều lĩnh vực khác nhau như vật lý thống kê, viễn thông, điều khiển, phân tích chuỗi thời gian, sự tăng trưởng dân số và các ngành khoa học quản lý. Các tín hiệu video, tín hiệu thoại, dữ liệu máy tính, nhiễu của một hệ thống viễn thông, nhiễu điện trong các thiết bị điện, số khách hàng đến một điểm phục vụ, chỉ số chứng khoán trong thị trường chứng khoán… là các quá trình ngẫu nhiên.
Quá trình ngẫu nhiên có nhiều ứng dụng đó là quá trình Markov (quá trình không nhớ, memoryless) và quá trình dừng. Chuỗi Markov là một quá trình Markov có không gian trạng thái rời rạc, thời gian rời rạc và thuần nhất. Chuỗi Markov thường gặp trong bài toán chuyển mạch của hệ thống viễn thông. Trong chương này ta nghiên cứu một cách khái quát khái niệm quá trình ngẫu nhiên với chuỗi Markov thời gian rời rạc.
Khái niệm về quá trình ngẫu nhiên Giả sử một tín hiệu nào đó mà tại mỗi thời điểm t nhận các giá trị phụ thuộc hệ các biến cố {𝐸𝑖 , 𝑖 𝜖 𝑁} của phép thử. Tín hiệu này nhận giá trị là 𝑥(𝑡, 𝐸𝑖 ) tại thời điểm t và khi biến cố Ei xảy ra. Quá trình ngẫu nhiên 𝑋(𝑡) vừa phụ thuộc thời gian t , vừa phụ thuộc yếu tố ngẫu nhiên Ei .1 Mô phỏng quá trình ngẫu nhiên Một cách tổng quát một quá trình ngẫu nhiên là một họ các biến ngẫu nhiên {𝑋(𝑡, 𝜔); 𝑡 𝜖 𝑇} xác định trong cùng một phép thử. Các quá trình này vừa phụ thuộc vào thời gian t và khi cố định tham số t thì 𝑋(𝑡, 𝜔) là biến ngẫu nhiên theo ω.
Các giá trị nhận được theo thời gian t được gọi là hàm mẫu hoặc một thể hiện của quá trình ngẫu nhiên. Tập chỉ số T thường biểu diễn tham số thời gian. Do tác động của các yếu tố ngẫu nhiên nên một tín hiệu {𝑋(𝑡, 𝜔); 𝑡 𝜖 𝑇} được truyền đi là một quá trình ngẫu nhiên. Tín hiệu cụ thể nhận được là hàm mẫu (một thể hiện) của quá trình ngẫu nhiên {𝑋(𝑡, 𝜔); 𝑡 𝜖 𝑇}.
Để đơn giản trong cách viết người ta ký hiệu quá trình ngẫu nhiên {𝑋(𝑡); 𝑡 𝜖 𝑇} thay cho {𝑋(𝑡, 𝜔); 𝑡 𝜖 𝑇}, hàm mẫu tương ứng được ký hiệu {𝑋(𝑡); 𝑡 𝜖 𝑇}. Phân loại quá trình ngẫu nhiên Có thể phân loại các quá trình ngẫu nhiên theo các đặc trưng sau: Không gian trạng thái; Tập chỉ số thời gian T; Quan hệ độc lập, quy luật phân bố xác suất của các biến ngẫu nhiên X(t). 8 Tập trung phân tích quá trình Markov tuân thủ theo 4 giả thiết: Có một số hữu hạn các trạng thái; Xác suất thay đổi trạng thái không thay đổi theo thời gian; Chúng ta có thể dự đoán bất kỳ trạng thái tương lai dựa trạng thái trước đó và ma trận xác suất chuyển đổi; Qui mô và cấu trúc của hệ thống không thay đổi trong quá trình phân tích. Phân loại quá trình ngẫu nhiên theo tập trạng thái E: Ta ký hiệu 𝐸 là tập các giá trị của 𝑋(𝑡) và gọi là không gian trạng thái của quá trình, mỗi giá trị của X(t) được gọi là một trạng thái.
Nếu 𝐸 là tập đếm ngược thì {𝑋(𝑡); 𝑡 𝜖 𝑇} gọi là quá trình có trạng thái rời rạc; Nếu 𝐸 là 1 khoảng của tập số thực ℝ thì {𝑋(𝑡); 𝑡 𝜖 𝑇} gọi là quá trình thực hoặc quá trình trạng thái liên tục; Nếu 𝐸 tập con của tập số phức ℂ thì {𝑋(𝑡); 𝑡 𝜖 𝑇} là quá tình trạng thái phức; Nếu 𝐸 ⊂ ℝ𝑘 thì {𝑋(𝑡); 𝑡 𝜖 𝑇} là quá trình trạng thái k - véc tơ. Phân loại quá trình ngẫu nhiên theo tập các chỉ số 𝑻: Nếu 𝑇 ⊂ ℤ thì quá trình {𝑋(𝑡); 𝑡 𝜖 𝑇} được gọi là quá trình có thời gian rời rạc hoặc tham số rời rạc. Trường hợp này ta ký hiệu 𝑋𝑛 thay cho 𝑋(𝑡) và gọi là một dãy ngẫu nhiên; Nếu T = [0 , ∞ ) hoặc 𝑇 = ℝ thì {𝑋(𝑡); 𝑡 𝜖 𝑇} được gọi là quá trình có thời gian liên tục. [1] Phân loại theo các tính chất xác suất của quá trình ngẫu nhiên Quá trình ngẫu nhiên trở thành biến ngẫu nhiên khi thời gian cố định tại thời điểm nào đó.
Mỗi biến ngẫu nhiên có các đặc trưng thống kê như kỳ vọng, phương sai, các moment… Các đặc trưng này nhận được từ hàm phân bố xác suất. Các hàm phân bố xác suất được xác định từ hàm mật độ xác suất (trường hợp liên tục), hoặc hàm khối lượng xác suất (trường hợp rời rạc). Hai biến ngẫu nhiên nhận được tại hai thời điểm của quá trình có các đặc trưng (kỳ vọng, phương sai, hiệp phương sai…) xác định từ hàm phân bố xác suất đồng thời của hai biến ngẫu nhiên này. 9 Tổng quát hơn, biến ngẫu nhiên N chiều nhận được tại N thời điểm có các đặc trưng xác định từ hàm phân bố xác suất đồng thời của các biến ngẫu nhiên này.
a) Quá trình độc lập Quá trình {𝑋(𝑡); 𝑡 ∈ 𝑇 } được gọi là quá trình độc lập nếu với mọi thời điểm 𝑡1 < 𝑡2 <. < 𝑡𝑛 thì các biến ngẫu nhiên sau là độc lập 𝑋(𝑡1 ), 𝑋(𝑡2 ), … , 𝑋(𝑡𝑛 ) b) Quá trình gia số độc lập Quá trình {𝑋(𝑡); 𝑡 ∈ 𝑇 } được gọi là quá trình gia số độc lập nếu các gia số của quá trình trong các khoảng thời gian rời nhau là các biến ngẫu nhiên độc lập. Tức là với mọi cách chọn các thời điểm 𝑡1 < 𝑡2 <. < 𝑡𝑛 thì các biến ngẫu nhiên sau là độc lập.
Đặc biệt với quá trình thời gian rời rạc { 𝑋𝑛 } thì tính chất gia số độc lập dẫn đến dãy các biến ngẫu nhiên 𝑍0 = 𝑋0 , 𝑍𝑖 = 𝑋𝑖 − 𝑋𝑖−1 ; 𝑖 = 1,2, … là độc lập. Ngoài ra nếu ta biết luật phân bố của từng biến ngẫu nhiên 𝑍0 , 𝑍1 , … thì ta biết được luật phân bố của mọi 𝑋𝑖 , 𝑖 = 0,1, … Thật vậy, điều này được suy từ cách tìm phân bố xác suất của tổng các biến ngẫu nhiên độc lập: 𝑋𝑖 = 𝑍0 + 𝑍1 + ⋯ + 𝑍𝑖 c) Quá trình gia số độc lập dừng Quá trình gia số độc lập {𝑋(𝑡); 𝑡 ∈ 𝑇 } được gọi là quá trình gia số độc lập dừng nếu ∀𝑠, 𝑡, 𝑠 < 𝑡; ∀ℎ ≥ 0; 𝑋(𝑡) − 𝑋(𝑠) 𝑣à 𝑋(𝑡 + ℎ) − 𝑋(𝑠 + ℎ) có cùng phân bố Quá trình Poisson, Wiener là hai ví dụ của quá trình gia số độc lập dừng. d) Quá trình Martingal Quá trình {𝑋(𝑡); 𝑡 ∈ 𝑇 } được gọi là quá trình Martingal nếu với bất kỳ 𝑡1 < 𝑡2 < ⋯ < 𝑡𝑛+1 và 𝑎1 , 𝑎2 , 𝑎3 , … , 𝑎𝑛 thì 𝐸(𝑋(𝑡𝑛+1 )|𝑋(𝑡1 ) = 𝑎1 , … , 𝑋(𝑡𝑛 ) = 𝑎𝑛 ) = 𝑎𝑛 Martingal có thể xem như là mô hình mô tả trò chơi may rủi, trong đó 𝑋(𝑡) là số tiền của người chơi ở thời điểm t. Tính chất Martingal nói rằng số tiền trung bình của người chơi sẽ có ở thời điểm 𝑡𝑛+1 bằng số tiền anh ta có ở thời điểm 𝑡𝑛 và không phụ thuộc vào những gì anh ta có trước đó trong quá khứ.
10 Nếu {𝑋(𝑡); 𝑡 ∈ 𝑇 } là quá trình gia số độc lập với kỳ vọng bằng 0 thì {𝑋(𝑡); 𝑡 > 0 } là quá trình Martingal với thời gian liên tục. e) Quá trình Markov Quá trình {𝑋(𝑡); 𝑡 ∈ 𝑇 } được gọi là quá trình Markov nếu: Với mọi thời điểm 𝑡1 < 𝑡2 <. < 𝑡𝑛 , với mọi giá trị 𝑎1, 𝑎2,. , 𝑎𝑛 cho trước, với mọi thời điểm 𝑡 > 𝑡𝑛 và với mọi a, ta có 𝑃{𝑋(𝑡) ≤ 𝑎|𝑋(𝑡1 ) = 𝑎1 , … , 𝑋(𝑡𝑛 ) = 𝑎𝑛 } = 𝑃{𝑋(𝑡) ≤ 𝑎|𝑋(𝑡𝑛 ) = 𝑎𝑛 } (1) Nghĩa là quy luật xác suất trong tương lai chỉ phụ thuộc hiện tại và độc lập với quá khứ.
Nói cách khác quá trình Markov mô tả các hệ không có trí nhớ (memoryless) Với mọi t > s; với mọi tập giá trị A ⊂ R và giá trị a ta ký hiệu 𝑝(𝑠, 𝑎; 𝑡, 𝐴) = 𝑃{𝑋(𝑡) ∈ 𝐴|𝑋(𝑠) = 𝑎} (2) và gọi là hàm xác suất chuyển từ thời điểm s đến thời điểm t Như vậy công thức (1) được viết lại 𝑃{𝑋(𝑡) ≤ 𝑎|𝑋(𝑡1 ) = 𝑎1 , … , 𝑋(𝑡𝑛 ) = 𝑎𝑛 } = 𝑝(𝑠, 𝑎; 𝑡, 𝐴), trong đó 𝐴 = (−∞, 𝑎] Quá trình Markov với không gian trạng thái rời rạc được gọi là chuỗi Markov (hay xích Markov, Markov chains). Chuỗi Markov với thời gian rời rạc và thuần nhất được xét trong mục tiếp theo. Quy luật phân bố xác suất của biến ngẫu nhiên rời rạc được xét qua hàm khối lượng xác suất, vì vậy tính chất Markov – công thức (1) đối với chuỗi Markov {𝑋𝑛 ; 𝑛 = 0,1,2, … } với thời gian rời rạc được viết lại như sau: 𝑃{𝑋𝑛+1 ≤ 𝑎|𝑋(𝑡1 ) = 𝑎1 , … , 𝑋(𝑡𝑛 ) = 𝑎𝑛 } = 𝑝(𝑠, 𝑎; 𝑡, 𝐴) f) Quá trình dừng (stationary) Xét quá trình ngẫu nhiên {𝑋(𝑡); 𝑡 ∈ 𝑇 } có thời gian 𝑇 = ℝ, ℝ+ , ℤ ℎ𝑜ặ𝑐 ℕ Nói một cách khái quát một quá trình ngẫu nhiên là quá trình dừng nếu các tính chất thống kê của quá trình không phụ thuộc thời gian. Các tính chất thống kê của quá trình được xác định bởi các hàm phân bố đồng thời của quá trình tại các thời điểm.
Các khái niệm dừng cụ thể phụ thuộc mức độ không phụ thuộc thời gian.