Tài liệu Mô hình xích markov và ứng dụng trong thuật toán xếp hạng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 LÊ THANH BÌNH MÔ HÌNH XÍCH MARKOV VÀ ỨNG DỤNG TRONG THUẬT TOÁN XẾP HẠNG LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số : 60 46 01 12 Người hướng dẫn khoa học TS. Hà Bình Minh HÀ NỘI, 2016 LỜI CẢM ƠN Tôi xin bày tỏ lòng biết ơn sâu sắc tới Tiến sĩ Hà Bình Minh, thầy đã định hướng chọn đề tài và tận tình hướng dẫn để tôi có thể hoàn thành luận văn này. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới Phòng sau Đại học, các thầy, cô giáo dạy Cao học chuyên ngành Toán ứng dụng, trường Đại học Sư phạm Hà Nội 2 đã giúp đỡ tôi trong suốt quá trình học tập. Nhân dịp này tôi cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn động viên, cổ vũ, tạo mọi điều kiện thuận lợi cho tôi trong quá trình học tập và hoàn thành luận văn. Hà Nội, tháng 10 năm 2016 TÁC GIẢ Lê Thanh Bình LỜI CAM ĐOAN Tôi xin cam đoan luận văn "Mô hình xích Markov và ứng dụng trong thuật toán xếp hạng" được hoàn thành dưới sự hướng dẫn của Tiến sĩ Hà Bình Minh. Các số liệu, những kết luận nghiên cứu được trình bày trong luận văn này là trung thực, các kết quả trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Hà Nội, tháng 10 năm 2016 TÁC GIẢ Lê Thanh Bình Mục lục Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chương 1. Mô hình xích Markov rời rạc . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Xích Markov và ma trận chuyển . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1. Định nghĩa xích Markov và ma trận chuyển . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2. Phân phối xác suất của một xích Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2. Xích Markov chính quy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1. Định nghĩa xích Markov chính quy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.2. Vector trạng thái dừng của một xích Markov chính quy . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2.3. Các bài toán áp dụng có chứa xích Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Chương 2. Áp dụng mô hình xích Markov cho thuật toán xếp hạng PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1. Mô phỏng một hệ thống các trang web đơn giản dưới dạng đồ thị . . . 25 2.1.1. Đồ thị có hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.2. Mô tả một hệ thống các trang web đơn giản dưới dạng đồ thị . . . . . . . . . . . . . . . . . . . . 26 2.1.3. Ma trận biểu diễn đồ thị có hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.4. Mô hình xích Markov cho đồ thị có hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.1.5. Hạn chế của ma trận chuyển của xích Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2. Thuật toán PageRank dựa trên xích Markov . . . . . . . . . . . . . . . . . . 30 2.2.1. Ma trận Google . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.2.2. Tính toán phân phối dừng của ma trận Google và xếp hạng trang web . . . . . . . . . . . . 31 Chương 3. Áp dụng với các ví dụ thực tế . . . . . . . . . . . . . . . . . . . . . . . . 34 3.1. Đặt bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2. Mô phỏng dưới dạng đồ thị và Mô hình hóa bởi xích Markov . 38 3.3. Tính toán ma trận chuyển, trạng thái dừng và xếp hạng chuyên đề bằng phần mềm Matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 MỞ ĐẦU 1. Lý do chọn đề tài Thuật toán xếp hạng nổi tiếng PageRank của Google được phát triển trên nền tảng toán học là mô hình xích Markov. Gần đây, ý tưởng của thuật toán PageRank được ứng dụng trong việc xếp hạng các tạp chí khoa học, dẫn đến sự ra đời của chỉ số Eigen-Factor, bên cạnh những chỉ số thông dụng khác như Impact-Factor, H-Index, . . . . Việc hiểu rõ ý tưởng, cũng như cơ sở toán học của các thuật toán xếp hạng như vậy sẽ là mục tiêu của luận văn này. Cấu trúc luận văn: Luận văn sẽ được chia làm 03 chương, chương 1 của luận văn sẽ dành để giới thiệu mô hình xích Markov rời rạc với những khái niệm liên quan. Chương 2 sẽ trình bày chi tiết việc áp dụng mô hình xích Markov cho thuật toán xếp hạng PageRank. Chương 3 chúng tôi trình bày áp dụng vào bài toán Sắp xếp chuyên đề toán trong chương trình toán bậc trung học cơ sở ở Việt Nam. 2. Mục đích nghiên cứu Sử dụng mô hình xích Markov trong thuật toán xếp hạng. 3. Nhiệm vụ nghiên cứu Sử dụng mô hình xích Markov trong thuật toán xếp hạng. 4. Đối tượng và phạm vi nghiên cứu Mô hình xích Markov và ứng dụng. 1 5. Phương pháp nghiên cứu Sử dụng các mô hình xác suất rời rạc, ngôn ngữ lập trình MATLAB, . . . . 6. Đóng góp mới của luận văn Luận văn trình bày một cách hệ thống, chi tiết về mô hình xích Markov rời rạc và áp dụng mô hình này vào thuật toán xếp hạng trang web của Google. Luận văn cũng trình bày một số ví dụ cụ thể về mặt lập trình, thực hiện thuật toán. Luận văn sẽ là một tài liệu tham khảo tốt cho những ai quan tâm tới mô hình xích Markov và thuật toán xếp hạng trang web của Google. 2 Chương 1 Mô hình xích Markov rời rạc Trong chương này, chúng tôi trình bày các khái niệm cũng như các kết quả, ví dụ cơ bản về mô hình xích Markov. Nội dung chương này sẽ được viết dựa trên chương 10 của tài liệu tham khảo [5]. 1.1. Xích Markov và ma trận chuyển 1.1.1. Định nghĩa xích Markov và ma trận chuyển Để đưa ra được định nghĩa của mô hình xích Markov, trước tiên ta xét mô hình sau. Trong hình 1.1 dưới đây gồm bốn phòng, mỗi phòng có một màu khác nhau và được đánh số theo thứ tự là 1, 2, 3, 4. Ta thả một con chuột vào trong một phòng nào đó và quan sát. Vì hành vi của chuột là không thể dự đoán được, ta sẽ dùng xác suất để mô tả sự chuyển động của chuột. Ta coi Hình 1.1: các phòng là các trạng thái, trạng thái thứ i, (i = 1, 2, 3, 4) tương ứng với con chuột đang ở phòng thứ i, (i = 1, 2, 3, 4) và kí hiệu pij là xác suất di chuyển từ trạng thái i tới trạng thái j trong một khoảng quan sát được. Chẳng hạn, xác suất p12 mà chuột di chuyển từ trạng thái 1 tới trạng thái 2 là p12 = 21 , trong khi đó xác suất di chuyển từ trạng thái 1 tới trạng thái 3 phải là p13 = 41 . Ta có p14 = 0 vì không có đường đi trực tiếp từ phòng 1 tới 4. Khi đó p11 = 41 3 là xác suất mà chuột ở lại phòng 1 trong một khoảng quan sát. Định nghĩa 1.1.1. Ta gọi ma trận  p11  p21 P = p  31 p41 p12 p22 p32 p42 p13 p23 p33 p43  p14  p24   p34   p44 là ma trận chuyển của phép thử nghiệm. Trong ví dụ trên, với 4 trạng thái và P là một ma trận kích thước 4 × 4. Ta có thể có các cách điền giá trị các xác suất, ở đây ma trận P có thể là:   1 1 1 0  41 22 4 1    6 3 0 6 P = 1 0 1 1 . 3 3 3 1 1 1 0 4 2 4 Ta cũng có thể biểu diễn các phần tử của P bằng cách sử dụng sơ đồ cây. Ở hình 1.2 dưới đây, các phần tử của P là các xác suất có điều kiện biểu diễn các xác suất mà con chuột sẽ đi tới phòng kế tiếp cho trước mà ta đã biết bây giờ con chuột đang ở đó. Đây là ý tưởng cốt yếu của sự di chuyển từ trạng thái này tới trạng thái khác với các xác suất tạo thành một cơ sở của một xích Markov. Định nghĩa 1.1.2. (Xích Markov) Một xích Markov là một dãy các phép thử nghiệm mà kết quả của mỗi phép thử nghiệm là một trong số các trạng thái ta đánh số là 1, 2, . . . , m. Xác suất trong mỗi trạng thái riêng chỉ phụ thuộc vào trạng thái trước đó chiếm giữ. Nếu pij là xác suất di chuyển từ trạng thái i tới trạng thái j, thì ma trận chuyển P = [pij ] của một xích Markov là ma trận kích thước: m × m   p11 p12 . . . p1m    p21 p22 . . . p2m   P = ... ... ... ... .   pm1 pm2 . . . pmm 4 Hình 1.2: Lưu ý rằng, ma trận chuyển P là một ma trận vuông với các phần tử là các xác suất, do đó giá trị của các phần tử pij (1 ≤ i, j ≤ m) luôn ở giữa 0 và 1. Hơn nữa, tổng của các phần tử trên một dòng luôn bằng 1. Ma trận chuyển của một xích Markov chứa những thông tin cần thiết cho phép ta dự đoán được điều gì sẽ xảy ra tiếp theo nếu ta đã biết điều gì xảy ra trước đó. Như vậy, để biết được điều đó ta chỉ cần đặc biệt hóa tình huống tại lúc bắt đầu của phép thử nghiệm. Nghĩa là ta cần phải có các giá trị xác suất ban đầu tại lúc bắt đầu phép thử nghiệm. Chẳng hạn, ta cần phải đặc biệt hóa phòng mà con chuột đã ở lúc bắt đầu phép thử và dòng vector được sử dụng để biểu diễn mục đích này. Định nghĩa 1.1.3. (Phân phối xác suất ban đầu) Trong một xích Markov với m trạng thái, phân phối xác suất ban đầu là một 1 × m dòng vector v (0) , có phần tử thứ i là xác suất phép thử đã ở trạng thái i lúc bắt đầu. Chẳng hạn, nếu con chuột có khả năng được đặt ở bất kỳ một trong các phòng lúc bắt đầu, thì ta sẽ có v (0) = [ 14 41 14 14 ]. Nếu con chuột luôn luôn ở vị trí ban đầu là phòng số 1, thì ta sẽ có v (0) = [1 0 0 0]. 5 1.1.2. Phân phối xác suất của một xích Markov Trong mục này ta trình bày cách tìm phân phối xác suất của một xích Markov. Ta minh họa qua ví dụ sau: Ví dụ 1.1.1. Trong hình 1.1, giả sử rằng ta điền các xác suất chuyển khi từ phòng 1 tới các phòng 1, 2, 3, 4 là: 1 1 1 { 0}. 3 3 3 Ở đây, con chuột bắt đầu ở trong phòng 1, và xác suất là 13 của lần nó ở lại phòng 1 trong thời gian của khoảng quan sát, 13 là xác suất nó vào phòng 2, và 1 3 là xác suất nó vào phòng 3. Vì con chuột không thể tới phòng 4 trực tiếp từ phòng 1, và do đó xác suất là 0. Tương tự, xác suất chuyển từ phòng 2, phòng 3 và phòng 4 là tương ứng như sau: 1 1 1 { 0 }; 3 3 3 1 1 1 { 0 }; 3 3 3 1 1 1 }. {0 3 3 3 Ta hãy tìm: 1. Ma trận chuyển P ; 2. Nếu vị trí ban đầu của con chuột ở phòng 4, tìm phân phối xác suất ban đầu; 3. Phân phối xác suất như thế nào sau hai lần quan sát, giả thiết rằng vị trí ban đầu của con chuột ở phòng 4? Lời giải: 1. Ma trận chuyển P là  1 3 1  3 1 3 0 1 3 1 3 0 1 3 6  1 3 0 0 1 3 ; 1  3 1 3 1 3 1 3  2. Vì vị trí ban đầu của con chuột là phòng 4, phân phối xác suất ban đầu là v (0) = [0 0 0 1]; 3. Để tìm các xác suất sau hai lần quan sát, ta sử dụng sơ đồ cây. Cây bắt đầu tại 4 , vì vị trí ban đầu của chuột là ở phòng 4. Khi đó, sử dụng dòng 4 của ma trận chuyển, ta có sự phân nhánh từ 4 , tới các phòng 2 , 3 , và 4 . Ta bỏ qua phòng 1, vì p41 = 0. Từ các nhánh phòng đó ta sử dụng các dòng 2, 3 và 4 của ma trận chuyển, thể hiện ở hình 1.3 dưới đây: Hình 1.3: Từ sơ đồ cây này ta suy ra rằng, con chuột sẽ ở trạng thái 1 sau hai lần quan sát với xác suất 19 + 19 = 29 . Tức là, 2 Xác suất di chuyển từ 4 tới 1 trong hai phép thử = . 9 7 Tương tự, 1 3 1 Xác suất di chuyển từ 4 tới 3 trong hai phép thử = 3 Xác suất di chuyển từ 4 tới 4 trong hai phép thử 1 1 1 1 1 1 1 = · + · + · = . 3 3 3 3 3 3 3 Xác suất di chuyển từ 4 tới 2 trong hai phép thử = 1 1 1 2 + · = 3 3 3 9 1 1 1 2 · + · = 3 3 3 9 · Do đó, phân phối xác suất v (2) sau hai lần quan sát là v (2) = [ 2 9 2 9 2 9 1 ]. 3 Sử dụng kí hiệu v (k) là vector biểu diễn các xác suất của trạng thái sau k phép thử. Vị trí thứ i của v (k) là xác suất của trạng thái i sau k phép thử. Thay vì theo quá trình tìm v (2) trong Ví dụ 1.1.1 ta có thể tính toán trực tiếp v (k) từ ma trận chuyển P và phân phối xác suất ban đầu v (0) . Định lý 1.1.1 ([5]). (Phân phối xác suất sau k phép thử) Trong một xích Markov, phân phối xác suất v (k) sau k phép thử là v (k) = v (k−1) P (1.1.1) trong đó P là ma trận chuyển. Phương trình (1.1.1) chứng tỏ v (1) = v (0) P, k = 1; v (2) = v (1) P, k = 2; v (3) = v (2) P, k = 3; ··· . Phân phối kế tiếp có thể luôn tính được từ phân phối trước đó bằng cách nhân với ma trận chuyển P. Ví dụ 1.1.2. Ta xét lại Ví dụ 1.1.1. Hãy sử dụng phương trình (1.1.1) để tìm phân phối xác suất sau hai lần quan sát. 8 Lời giải: Phân phối xác suất ban đầu là v (0) = [0  v (1) = v (0) P = [0 0 0 1 3 1  3 1]  1 3 0 0 0 1], như vậy, theo (1.1.1),  1 1 0 3 3  1 1 0 1 1 1 3 3 = [0 ].  3 3 3 0 31 13  1 3 1 3 1 3 1 3 1 3 1 3 0 0 1 3 1 3 1 3 Áp dụng (1.1.1) một lần nữa ta có  v (2) (1) = v P = [0 1 3 1 3 1 3 1 1  ]  31 3  3 0 0 1 3 1 3 1 3   =[ 2 9 2 9 2 9 1 ]. 3 Bằng cách này ta vẫn thu được v (2) như đã tính trong Ví dụ 1.1.1 phần 3. Ta thấy rằng, sau một vài tính toán từ (1.1.1) ta có v (1) = v (0) P v (2) = v (1) P = [v (0) P ]P = v (0) P 2 vì v (1) = v (0) P v (3) = v (2) P = [v (0) P 2 ]P = v (0) P 3 vì v (2) = v (0) P 2 v (4) = v (3) P = [v (0) P 3 ]P = v (0) P 4 vì v (3) = v (0) P 3 . Tiếp tục cách này ta thu được kết quả sau. Định lý 1.1.2 ([5]). (Phân phối xác suất sau k phép thử) Trong một xích Markov, phân phối xác suất v (k) sau k phép thử là v (k) = v (0) P k (1.1.2) trong đó P k là lũy thừa mũ k của ma trận chuyển P và v (0) là phân phối xác suất ban đầu. Từ định lí này ta có thể tính v (2) = v (0) P 2 , ta có   v (2) = v (0) P 2 = [0 0 0 1  32  9 1]  2 9 2 9 9 2 9 1 3 2 9 2 9 2 9 2 9 1 3 2 9 2 9  2 9 2 9 1 3 =[ 2 9 2 9 2 9 1 ]. 3 Tiếp theo, ta xét một vài bài toán áp dụng chứa xích Markov bằng ví dụ về sự di chuyển dân số sau. Ví dụ 1.1.3. Giả sử rằng thành phố Vĩnh Yên đang trải qua sự chuyển động dân số đến các vùng ngoại ô. Hiện nay, 85% của tổng dân số sống ở thành phố và 15% sống trong các vùng ngoại ô. Nhưng mỗi năm 7% của người dân thành phố di chuyển đến các vùng ngoại ô, trong khi chỉ có 1% người dân ngoại ô di chuyển trở lại thành phố. Giả sử rằng tổng dân số (của thành phố và vùng ngoại ô) vẫn không đổi, bao nhiêu phần trăm của tổng số sẽ ở lại thành phố sau 5 năm? Lời giải: Bài toán này có thể được biểu diễn như một dãy các phép thử mà trong đó mỗi phép thử đo tỉ lệ dân số trong thành phố và tỉ lệ dân số ở ngoại ô. Trong (n + 1) năm, tỉ lệ đó chỉ phụ thuộc vào giá trị của tỉ lệ trong năm thứ n và không phụ thuộc vào tỉ lệ tìm thấy của năm trước đó. Phép thử này có thể được mô hình bởi một xích Markov như sau. Phân phối ban đầu của xích Markov này là Tp Ngoại ô v (0) =[0.85 0.15]. Tức là, tại thời điểm ban đầu, có 85% dân số sống ở bên trong thành phố và 15% sống ở ngoại ô. Ma trận chuyển là " # 0.93 0.07 P = . 0.01 0.99 Tức là, mỗi năm có 7% dân số trong thành phố di chuyển tới vùng ngoại ô (còn lại 93% vẫn sống ở trong thành phố) và 1% dân số ở vùng ngoại ô di chuyển vào trong thành phố sống (do đó còn lại 99% dân số vẫn sống ở ngoại ô). Để tìm phân phối xác suất sau 5 năm, ta cần tính v (5) . Ta áp dụng (1.1.1) 10 năm lần. # 0.93 0.07 = [0.792 0.208] = v (0) P = [0.85 0.15] 0.01 0.99 # " 0.93 0.07 = [0.73864 0.26136] = v (1) P = [0.792 0.208] 0.01 0.99 # " 0.93 0.07 = [0.68955 0.31045] = v (2) P = [0.73864 0.26136] 0.01 0.99 " v (1) v (2) v (3) v (4) = v (3) P = [0.68955 v (5) = v (4) P = [0.64439 " 0.93 0.31045] 0.01 " 0.93 0.35561] 0.01 # 0.07 = [0.64439 0.99 # 0.07 = [0.60284 0.99 0.35561] 0.39716]. Như vậy, sau 5 năm có 60.28% dân số vẫn ở trong thành phố và 39.72% dân số sống ở ngoại ô. Ví dụ 1.1.3 dẫn tới câu hỏi: khi nào dân số ở Vĩnh Yên ổn định. Tức là, sau một số năm nhất định dân số đạt được trạng thái cân bằng? Hơn nữa, dân số có cân bằng không, nếu đạt được, nó có phụ thuộc vào phân phối ban đầu không, hay nó độc lập với trạng thái ban đầu? Ta sẽ trả lời những câu hỏi này trong phần tiếp theo. 1.2. Xích Markov chính quy Một câu hỏi quan trọng về xích Markov là: Điều gì xảy ra sau một khoảng thời gian đủ dài? Phân phối của các trạng thái có tiến tới trạng thái ổn định theo thời gian không? Trong mục này ta sẽ đề xuất các điều kiện phù hợp để dưới các điều kiện đó một xích Markov tiến tới trạng thái cân bằng (hay trạng thái dừng). Ta cũng trình bày quá trình tìm phân phối cân bằng này khi nó tồn tại. 11 1.2.1. Định nghĩa xích Markov chính quy Định nghĩa 1.2.1 (Xích Markov chính quy). Một xích Markov được gọi là chính quy nếu với một lũy thừa nào đó của ma trận chuyển của xích đó có tất cả các phần tử đều dương. Ví dụ 1.2.1. Cho trước ma trận chuyển P của một xích Markov nào đó " # 1 2 P = Ta có " P2 = 1 2 1 2 #2 1 0 " = 1 2 1 0 1 2 1 2 #" 1 0 . 1 2 1 2 # " = 1 0 3 4 1 2 1 4 1 2 # có tất cả các phần tử đều dương, do đó xích Markov này là chính quy. Ví dụ 1.2.2 (Xích Markov không chính quy). Xét xích Markov có ma trận chuyển " # 1 0 P = 3 1 . 4 4 Bằng quy nạp ta thấy rằng, mỗi lũy thừa của P luôn có phần tử p12 = 0, do đó xích Markov này là không chính quy. Ví dụ tiếp theo cho ta các bước xác định dáng điệu tiệm cận của một xích Markov. Ví dụ 1.2.3 (Lòng trung thành của người tiêu dùng). Một công ty rượu vang đang xúc tiến bán rượu Syrah của công ty đó. Kết quả là 75% tổng số những người đã uống rượu vang Syrah trong một chu kỳ thời gian là 1 tháng tiếp tục uống trong tháng tiếp theo; những người uống các loại rượu vang đỏ khác trong khoảng thời gian 1 tháng, 35% thay đổi sang rượu vang Syrah ở tháng tiếp theo. Ma trận chuyển P của phép thử nghiệm này là E1 P = E2 E1 0.75 0.25 E2 0.35 0.65 12 ! a) Tìm xác suất chuyển từ E1 sang hoặc là E1 hoặc E2 trong hai phép thử; b) Tìm xác suất chuyển từ E2 sang hoặc là E1 hoặc E2 trong hai phép thử. Lời giải: Sơ đồ cây mô tả hai lần thực hiện của phép thử này được cho trong 1.4. (2) a) Xác suất p11 của quá trình chuyển từ E1 sang E1 trong hai lần thực hiện là (2) p11 = (0.75)(0.75) + (0.25)(0.25) = 0.65 (2) Xác suất p12 từ E1 sang E2 sau hai lần thực hiện là Hình 1.4: (2) p12 = (0.75)(0.25) + (0.25)(0.65) = 0.35. (2) b) Xác suất p21 của quá trình chuyển từ E1 sang E1 trong hai lần thực hiện là (2) p21 = (0.35)(0.75) + (0.65)(0.35) = 0.49 (2) Xác suất p12 từ E1 sang E2 sau hai lần thực hiện là (2) p22 = (0.35)(0.25) + (0.65)(0.65) = 0.51. 13 Nếu ta lấy bình phương ma trận chuyển, ta có " #" # 0.75 0.25 0.75 0.25 P2 = 0.35 0.65 0.35 0.65 # " (0.75)(0.75) + (0.25)(0.25) (0.75)(0.25) + (0.25)(0.65) = (0.35)(0.75) + (0.65)(0.35) (0.35)(0.25) + (0.65)(0.65) # " 0.65 0.35 = 0.49 0.51 và ta lưu ý rằng " (2) (2) # p11 p12 P 2 = (2) (2) . p21 p22 Điều này có nghĩa là, bình phương của ma trận chuyển cho ta các xác suất di chuyển từ một trạng thái này tới một trạng thái khác trong hai lần thực hiện phép thử. Điều này vẫn đúng trong trường hợp tổng quát, cụ thể ta có kết quả sau đây. Định lý 1.2.1 ([5]). [Xác suất chuyển từ trạng thái i sang trạng thái j sau n lần thực hiện] Nếu P là ma trận chuyển của một xích Markov, thì phần tử thứ (i, j) của ma trận P n cho ta các xác suất chuyển từ trạng thái i sang trạng thái j sau n lần thực hiện. Từ định lý này ta có thể thấy dáng điệu của một quá trình Markov sau khi chạy một thời gian dài bằng cách nâng lũy thừa ma trận chuyển của quá trình đó tới lũy thừa cao hơn. Chẳng hạn, ta sử dụng ma trận chuyển P trong Ví dụ 14 1.1.3 và tính từ P 2 tới P 12 . " 0.7500 P = 0.3500 " 0.6100 P3 = 0.5460 " 0.5876 P5 = 0.5774 " 0.5840 P7 = 0.5824 " 0.5834 P9 = 0.5832 " 0.5834 P 11 = 0.5833 # 0.2500 0.6500 # 0.3900 0.4540 # 0.4124 0.4226 # 0.4160 0.4176 # 0.4166 0.4168 # 0.4166 0.4167 " 0.6500 0.4900 " 0.5940 0.5684 " 0.5850 0.5809 P2 = P4 = P6 = " 0.5836 0.5830 " 0.5834 = 0.5833 " 0.5833 = 0.5833 P8 = P 10 P 12 # 0.3500 0.5100 # 0.4060 0.4316 # 0.4150 0.4191 # 0.4164 0.4176 # 0.4166 0.4167 # 0.4167 . 0.4167 Lưu ý rằng các lũy thừa cao hơn của P n dường như hội tụ và hội tụ về trạng thái ổn định, tức là bằng với một ma trận trạng thái dừng. Cũng vậy, ta thấy rằng các dòng của ma trận P 12 là bằng nhau. Điều này có nghĩa là xác suất là 0.5833, tức là một người sẽ uống rượu Syrah bất kể những gì anh ta hay cô ta đã uống trước đó! Nói cách khác, tình hình đã ổn định, với 58.33% uống Syrah và 41, 67% uống các rượu vang đỏ khác. Một vector xác suất là một ma trận dòng mà toàn bộ phần tử là các xác suất có tổng là 1. Vector xác suất t = [0.5833 0.4167] được gọi là vector trạng thái dừng t của xích Markov có ma trận chuyển là P. 1.2.2. Vector trạng thái dừng của một xích Markov chính quy Như trên ta đã nói về vector trạng thái dừng của một xích Markov chính quy, mục này ta trình bày cách tìm vector này. Ta có kết quả sau đúng với mọi xích Markov chính quy. Định lý 1.2.2 ([5]). (Dáng điệu tiệm cận của xích Markov chính quy) Cho P là ma trận chuyển của xích Markov chính quy. Khi đó các tính chất sau là đúng: 15 1. Ma trận P n tiến tới một ma trận bất động T khi n đủ lớn. Khi đó, ta viết P n → T (khi n đủ lớn); 2. Các dòng của ma trận T là trùng nhau và bằng với vector xác suất t; 3. t là vector xác suất duy nhất thỏa mãn tP = t; 4. Nếu v (0) là phân phối ban đầu tùy ý, thì v (n) → t khi n đủ lớn. Chứng minh. Các tính chất 1 và 2 đã được chứng minh. Để thấy tính chất 3, ta xét phương trình (1.1.1) và từ P 12 , đặt t = [0.5833 0.4167]. Ta tính tP, " tP = [0.5833 # 0.75 0.25 = [0.5833 0.4167] 0.35 0.65 0.4167] = t. Vector dòng t thỏa mãn phương trình tP = t. Điều này có nghĩa là không nhất thiết phải tính các lũy thừa cao hơn n của ma trận P để tìm ma trận bất động T. Vì tính chất 3 cho phép ta tìm vector t bằng cách giải một hệ phương trình.  Để tìm vector trạng thái dừng của một xích Markov chính quy, ta minh họa qua ví dụ sau. Ví dụ 1.2.4. Tìm vector trạng thái dừng t của xích Markov có ma trận chuyển là " # 0.93 0.07 P = , 0.01 0.99 đây là ma trận chuyển của xích Markov trong Ví dụ 1.1.3 biểu diễn sự di chuyển dân số. Lời giải: Trước tiên, ta quan sát rằng P là chính quy vì P = P 1 có tất cả các phần tử đều dương. Vector trạng thái dừng t có hai tính chất: t = [t1 t2 ] là một vector xác suất nên t1 + t2 = 1, 16