Chương 1 Xích Markov 1.1 Các định nghĩa Giả thiết ta nghiên cứu sự tiến triển theo thời gian của một hệ vật lý hoặc sinh thái nào đó. Ký hiệu X(t) là ví trí của hệ tại thời điểm t. Tập hợp các vị trí có thể có của hệ được gọi là không gian trạng thái. Giả sử trước thời điểm t trong tương lai t > s hệ ở trạng thái j với xác suất là bao nhiêu? Nếu xác suất này chỉ phụ thuộc vào s, t, i, j thì điều này có nghĩa là: sự tiến triển của hệ trong tương lai chỉ phụ thuộc vào hiện tại và độc lập với quá khứ.
Đó là tính Markov. Hệ có tính chất này được gọi là quá trình Markov. Ta kí hiệu E là tập gồm các giá trị của X(t) và gọi E là không gian trạng thái của X(t). Nếu X(t) có tính Markov và E đánh số được thì X(t) được gọi là xích Markov.
Thêm vào đó, nếu t = 0, 1, 2, 3,. thì ta có khái niệm xích Markov với thời gian rời rạc, còn nếu t ∈ (0, +∞) thì ta có định nghĩa xích Markov có thời gian liên tục. 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Về phương diện toán học, tính Markov có thể định nghĩa như sau: Định nghĩa 1. Ta xem tn là hiên tại, tn+1 là tương lai, (t0 ,.
, tn−1 ) là quá khứ. Vì thế biểu thức trên chính là tính Markov của X(t). Đó chính là xác suất có điều kiện để hệ (quá trình) tại thời điểm s ở trạng thái i, đến thời điểm t chuyển sang trại thái j. Vì thế ta gọi là xác suất chuyển của hệ ( hay quá trình).
Nếu xác suất chuyển chị phụ thuộc vào (t − s), tức là P (s, i, t, j) = P (s + h, i, t + h, j) thì ta nói hệ (quá trình) thuần nhất theo thời gian.2 Ma trận chuyển Giả sử Xn ở hàng thứ nhất của ma trận P trong ví dụ 1.3 ở trên mô tả xác suất của biến thể hiện trạng thái thời tiết mưa. Tương tự hàng hai và hàng ba tương ứng với thời tiết đẹp trời và có tuyết rơi. Ma trận vuông như vậy gọi là ma trận xác suất chuyển hay ma trận chuyển. Giả sử Xn ; n = 0, 1, 2,.
là xích rời rạc vầ thuần nhất. Nói một cách chính xác là: giả sử (Ω, A, P ) là không gian xác suất, Xn : Ω → Elà biến (đại lượng)ngẫu nhiên nhận giá trị trong tập đếm được E. E là không gian trạng thái, các phần tử của nó được kí hiệu là i, j, k,. Khi đó, tính Markov và 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com tính thuần nhất của Xn có nghĩa là: pij = P {X(tn+1 ) = j|X(tn ) = i} = P {X(tn+1 ) = j|X(t0 ) = i0.
, X(tn−1 ) = in−1 , X(tn ) = i} không phụ thuộc vào n. P = (pij ) được gọi là ma trận xác suất chuyển sau 1 bước hay gọi tắt là ma trận chuyển. Tổng quát thì ta có định lý sau: Định lý 1. Nếu P là ma trận chuyển của xích Markov.
Phần tử pij của ma trận Pn là xác suất của xích bắt đầu từ trạng thái i sang trạng thái j sau (n) n bước là pij : (n) (n−1) X pij = pik pkj k∈E Chứng minh. Để chứng minh biểu thức của đính lý này ta lập luận như sau: Hệ xuất phát từ trạng thái i và chuyển sang trạng thái j sau n bước là kết quả của việc hệ xuất phát từ trạng thái i, sau một bước chuyển sang trạng thái k, sau n − 1 bước tiếp theo chuyển sang trạng thái j. Từ công thức xác suất đầy đủ và tính Markov ta có: (n) pij = P {Xn+1 = j|X0 = i} X = P (Xn = j|X0 = i, X1 = k).P (X1 = k|X0 = i) k∈E (n−1) X = pik pkj k∈E Định lí được chứng minh. Cho P là ma trận chuyển của xích Markov và u là véctơ xác suất miêu tả phân bố ban đầu.
Khi đó xác suất của xích ở trạng thái i sau n 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com bước là phần tử thứ i của véctơ: u(n) = uP n 1.3 Các ví dụ Các ví dụ sau về xích Markov sẽ được sử dụng trong suốt các bài tập của chương. Tổng thống Mỹ kể cho một người A về việc có hoặc không tranh cử trong cuộc tuyển cử tới. Nếu A thay dổi câu trả lời và chuyển tiếp tới B và B là người chuyển tiếp cho C,vv. luôn luôn chuyển tiếp cho một người mới.
Ta đặt xác suất là a với một người thay đổi câu trả lời từ có sang không khi truyền thông điệp cho một ng tiếp theo và xác suất là b mà người đó thay đổi từ không sang có. Ta chọn các trạng thái của thông điệp là có hoặc không. Ma trận chuyển như sau: Y es No Y es 1−a a P= No b 1−b Ví dụ 1. Mỗi một con ngựa bất kì chạy trong một cuộc đua ba con ngựa có ba trường hợp xảy ra với xác suất chiến thắng, nhì và thứ ba lần lượt là 1/2,1/4 và 1/4, độc lập với các kết quả trước đó.
Chúng ta có thể có quá trình kiểm tra độc lập nhưng cũng có thể tính toán thông qua lý thuyết của xích Markov. Ma trận chuyển: W P S W .25 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Theo Kemeny, Snell, và Thompson, vùng đất với nhiều may mắn, Land of Oz lại có một hệ thống thời thiết không hề tốt. Họ không bao giờ có hai ngày đẹp trời liên tiếp.
Nếu hôm nay là ngày đẹp trời thì ngày mai là ngày có tuyết hoặc mưa. Nếu có mưa hoặc tuyết rơi thì ngày tiếp theo cũng sẽ tương tự. Nếu có sự thay đổi giữa có tuyết rơi và mưa thì chỉ có một nửa thời gian còn lại là đẹp trời. Với những thông tin trên, chúng ta có thể xác định được xích Markov như sau.
Ta kí hiệu ba trạng thái thời tiết là R, N và S. Từ các thông tin trên ta xác định được ma trận chuyển là một ma trận vuông: R N S R 1/2 1/4 1/4 P = N 1/2 0 1/2 S 1/4 1/4 1/2 1.2 Xích Markov hấp thụ Các chủ đề của chuỗi Markov được nghiên cứu một cách tốt nhất bằng cách xem xét các loại đặc biệt của xích Markov. Một trạng thái i của xích Markov được gọi hấp thụ nếu nó không thể rời khỏi trạng thái đó ( tức là pii = 1). Một xích Markov được gọi là hấp thụ nếu nó có ít nhất một trạng thái hấp thụ và từ bất kì trạng thái nào đều có thể đi tới trạng thái hấp thụ ( không nhất thiết qua nột bước) Định nghĩa 1.
Trong một xích Markov hấp thụ, một trạng thái không phải trạng thái hấp thụ được gọi là trạng thái tức thời.1 Dạng chính tắc Nghiên cứu một xích Markov bất kì. Đánh số lại các trạng thái sao cho trạng thái bắt đầu là trạng thái tức thời. Nếu có r trạng thái hấp thụ và t 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com trạng thái tức thời thì ma trận chuyển có dạng chính tắc như sau: T R. ABS TR Q R P= ABS 0 I Trong đó I là ma trận đơn vị cỡ r, 0 là ma trận không cỡ rxt, R là ma trận khác không cỡ txr và Q là ma trận vuông cỡ t.
t trạng thái đầu tiên là trạng thái tức thời, r trạng thái còn lại là trạng thái hấp thụ.1, ta biết rằng phần tử pij của ma trận P n là xác suất để đến trạng thái j sau n bước và bắt đầu từ trạng thái i. Lập luận trên đại số các ma trận chỉ ra rằng P n có dạng T R. ABS n TR Q ∗ Pn = ABS 0 I Ở đây dấu * ở phía trên góc phải của ma trận P n thay cho ma trận cỡ txr Dạng của ma trận P n chỉ ra rằng các phần tử của Qn là xác suất của mỗi trạng thái là trạng thái tức thời sau n bước, bắt đầu từ trạng thái tức thời bất kì. Định lí ở trên đã chỉ ra rằng, xác suất của trạng thái tức thời sau n bước tiến dần đến 0.
Vì vậy mỗi phần tử của Qn tiến dần đến 0 khi n tiến ra vô cùng, tức là Qn → 0 Tiếp theo, nếu u và v là hai vecto, ta nói rằng u ≤ v nếu tất cả các thành phần của u bé hơn hoặc bằng các thành phần tương ứng của v. Một cách tương tự, nếu A và B là hai ma trận thì A ≤ B nếu mỗi phần tử của A bé hơn hoặc bằng phần tử tương ứng của B 1.2 Xác suất hấp thụ Định lý 1. Trong một xích Markov hấp thụ, xác suất để quá trình bị hấp thụ sau một số hữu hạn bước bằng 1 (tức là Qn → 0 khi n → ∞ ) 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chứng minh. Từ một trạng thái tức thời j, nó có thể tiến đến trạng thái hấp thụ.
Giả sử m là số bước nhỏ nhất có thể đạt được trạng thái hấp thụ của xích bắt đầu từ trạng thái j. Gỉa sử pj là xác suất quá trình bắt đầu từ trạng thái j không đạt tới trạng thái hấp thụ sau mj bước thì pj < 1. Nếu m = max{mj } và p = max{pj }. Xác suất để quá trình không là hấp thụ sau m bước nhỏ hơn hoặc bằng p, sau 2n nhỏ hơn hoặc bằng p2 ,.
Vì p < 1 nên những xác suất này tiến tới không. Khi xác suất để một quá trình không là hấp thụ sau n bước là hàm đơn điệu giảm, tiến dần đến không. Do đó Qn → 0 khi n → ∞.3 Ma trận cơ bản Định lý 1. Với một xích hấp thụ ma trận I − Q là ma trận nghịch đảo của ma trận N và với N = I + Q + Q2 + ., phần tử nij của ma trận N là kì vọng của số lần của xích ở trạng thái j mà bắt đầu từ trạng thái i.Trạng thái ban đầu là đếm được khi i = j Chứng minh.
Nếu (I − Q)x = 0 suy ra x = Qx lặp lại điều này ta có x = Qn x. Từ Qn → 0, ta có Qn x → 0 nên x = 0 Do vậy tồn tại (I − Q)1 = N. Mặt khác ta có (I − Q)(I + Q + Q2 + .