Bài tập có lời giải về xích markov
|
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 Mục lục
Mở đầu1. 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 Chương 1Mô hình xích Markov rời rạcTrong 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. Xích Markov và ma trận chuyển1.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 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: 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ệupijlà xác suất di chuyển từ trạng tháiitới trạng tháijtrong một khoảng quan sát được. Chẳng hạn, xác suấtp 12 mà chuột di chuyển từ trạng thái 1 tới trạng thái 2 làp 12 = 12 , 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àp 13 = 14. Ta cóp 14 = 0vì không có đường đi trực tiếp từ phòng 1 tới 4. Khi đóp 11 = 14 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. Ta gọi ma trận P =p 11 p 12 p 13 p 14 p 21 p 22 p 23 p 24 p 31 p 32 p 33 p 34 p 41 p 42 p 43 p 44 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àPlà 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ậnP có thể là: P =1 4 1 2 1 1 4 0 6 2 3 0 1 6 1301313 0141214 .Ta cũng có thể biểu diễn các phần tử củaP bằng cách sử dụng sơ đồ cây. Ở hình 1 dưới đây, các phần tử củaP 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. (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 P =p 11 p 12... p 1 m p 21 p 22... p 2 m ............ pm 1 pm 2... pmm .4 1.1. 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. Trong hình 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à: { 1313130 }. Ở đâ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à 13 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: { 1313013 }; { 1301313 }; { 0 13 13 13 }. Ta hãy tìm:
Lời giải:
1 3 1 3 1 1 3 0 3 1 3 0 1 1 3 3 0 1 3 1 3 0131313 ;6
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ìp 41 = 0ừ 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 dưới đây: Hình 1: 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à, Xác suất di chuyển từ 4 tới 1 trong hai phép thử = 29. 7 Lời giải: Phân phối xác suất ban đầu làv(0)= [0 0 0 1],như vậy, theo (1.1), v(1)=v(0)P = [0 0 0 1] 1 3 1 3 1 1 3 0 3 1 3 0 1 3 1301313 0131313 \= [0 131313 ].Áp dụng (1.1) một lần nữa ta có v(2)=v(1)P = [0 131313 ] 1 3 1 3 1 3 0 1313013 1301313 0131313 \= [ 29292913 ].Bằng cách này ta vẫn thu đượcv(2)như đã tính trong Ví dụ 1.1 phần 3. Ta thấy rằng, sau một vài tính toán từ (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 ([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)Pk (1.1) trong đó Pk 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ínhv(2)=v(0)P 2 ,ta có v(2)=v(0)P 2 = [0 0 0 1] 1 3 2 9 2 9 2 2 9 9 1 3 2 9 2 2 9 9 2 9 1 3 2 2 9 9 2 9 2 9 1 3 \= [ 29292913 ].9 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. 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ăm7%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ứnvà 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 0]. 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à P = [0 .93 0. 070 .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ại93%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ại99%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ínhv(5).Ta áp dụng (1.1) 10 1.2. Định nghĩa xích Markov chính quy Định nghĩa 1.2 (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. Cho trước ma trận chuyểnPcủa một xích Markov nào đó P = [ 12 1 2 1 0 ].Ta có P 2 = [ 12 1 2 1 0 ] 2\=[ 12 1 2 1 0 ][ 12 1 2 1 0 ]\=[ 34 1 4 1212 ]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 (Xích Markov không chính quy). Xét xích Markov có ma trận chuyển P = [1 03414 ].Bằng quy nạp ta thấy rằng, mỗi lũy thừa củaP luôn có phần tửp 12 = 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 (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ểnPcủa phép thử nghiệm này là P =( E 1 E 2E 1 0 .75 0. 25E 2 0 .35 0. 65)12
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. a) Xác suấtp(2) 11 của quá trình chuyển từE 1 sangE 1 trong hai lần thực hiện là p(2) 11 = (0)(0) + (0)(0) = 0. 65 Xác suấtp(2) 12 từE 1 sangE 2 sau hai lần thực hiện là Hình 1: p(2) 12 = (0)(0) + (0)(0) = 0. 35.
Xác suấtp(2) 12 từE 1 sangE 2 sau hai lần thực hiện là p(2) 22 = (0)(0) + (0)(0) = 0. 51. 13 1.1 và tính từP 2 tớiP 12. P = [0 .7500 0. 25000 .3500 0. 6500]P 2 =[0 .6500 0. 35000 .4900 0. 5100]P 3 =[0 .6100 0. 39000 .5460 0. 4540]P 4 =[0 .5940 0. 40600 .5684 0. 4316]P 5 =[0 .5876 0. 41240 .5774 0. 4226]P 6 =[0 .5850 0. 41500 .5809 0. 4191]P 7 =[0 .5840 0. 41600 .5824 0. 4176]P 8 =[0 .5836 0. 41640 .5830 0. 4176]P 9 =[0 .5834 0. 41660 .5832 0. 4168]P 10 =[0 .5834 0. 41660 .5833 0. 4167]P 11 =[0 .5834 0. 41660 .5833 0. 4167]P 12 =[0 .5833 0. 41670 .5833 0. 4167].Lưu ý rằng các lũy thừa cao hơn củaPndườ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ậnP 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ấtt = [0 0]được gọi là vector trạng thái dừngtcủa xích Markov có ma trận chuyển làP. 1.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 ([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 Pn tiến tới một ma trận bất động T khi n đủ lớn. Khi đó, ta viết Pn→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) và từP 12 , đặt t= [0 0]. Ta tínhtP, tP = [0 0] [0 .75 0. 250 .35 0. 65]\= [0 0] =t. Vector dòngtthỏa mãn phương trìnhtP =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ơnncủa ma trậnPđể tìm ma trận bất độngTì tính chất 3 cho phép ta tìm vectort 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. Tìm vector trạng thái dừngtcủa xích Markov có ma trận chuyển là P = [0 .93 0. 070 .01 0. 99],đây là ma trận chuyển của xích Markov trong Ví dụ 1.1 biểu diễn sự di chuyển dân số. Lời giải: Trước tiên, ta quan sát rằngP 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ừngtcó hai tính chất:t = [t 1 t 2 ]là một vector xác suất nên t 1 +t 2 = 1, 16 |
