Header Page 1 of 132.

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

Footer Page 1 of 132.


Header Page 2 of 132.

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ư


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


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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


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

Footer Page 5 of 132.


Header Page 6 of 132.

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

Footer Page 6 of 132.


Header Page 7 of 132.


Đị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



p11 p12 . . . p1m


 p21 p22 . . . p2m 

P =
... ... ... ... .


pm1 pm2 . . . pmm
4

Footer Page 8 of 132.


Header Page 9 of 132.

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.

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
1
3

1
3
1
3




Header Page 11 of 132.

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

·

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ỏ


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

Á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

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

2
9

2
9

1
].
3


Header Page 14 of 132.

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 đó

Footer Page 14 of 132.


Header Page 15 of 132.

năm lần.
v (1) = v (0) P = [0.85

0.15]

v (2) = v (1) P = [0.792

0.93 0.07
= [0.792
0.01 0.99

0.208]

0.208]

0.93 0.07
= [0.73864
0.01 0.99

0.26136]

v (3) = v (2) P = [0.73864

0.26136]


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

Footer Page 15 of 132.


Header Page 16 of 132.

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ó
2

1 0

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.

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

Footer Page 17 of 132.


p21 p22
2

Đ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

Footer Page 18 of 132.


Header Page 19 of 132.

1.1.3 và tính từ P 2 tới P 12 .
P =

0.7500 0.2500
0.3500 0.6500

P2 =


0.5836 0.4164
0.5830 0.4176

P9 =

0.5834 0.4166
0.5832 0.4168

P 10 =

0.5834 0.4166
0.5833 0.4167

P 11 =

0.5834 0.4166
0.5833 0.4167

P 12 =

0.5833 0.4167
.
0.5833 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

tP = [0.5833

0.4167]

0.75 0.25
= [0.5833
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


t + t
1
2
0.07t1 − 0.01t2

=1

(1.2.1)

= 0.

Giải hệ này ta thu được t1 = 18 và t2 = 78 . Do đó vector trạng thái dừng là
t = [ 81 78 ]. Ta giải thích t = [ 81 78 ] như sau: sau thời gian đủ dài 81 hay 12.5%
tổng số dân sẽ sống ở thành phố trong khi đó 87 hay 87.5% số dân sẽ sống ở
ngoại ô.
Ví dụ 1.2.5. Tìm vector trạng thái dừng t của ma trận chuyển

1
1
0
2
2
1 1 
P =  2 2 0 .
1
3

1
3

17

Footer Page 21 of 132.

t3 ] là vector bất động


Header Page 22 of 132.

hay
1
2

t1 + t2 + t3 = 1 và [t1


t3 ]  12

t2

1
3

Sau một vài tính toán ta có hệ

1


t + 1t + 1t


1
3

= t1
= t2
= t3

hay



t1 + t2 + t3




3t − 3t − 2t
1

2



−3t2 + 2t3




3t1 − 4t3


trưng đáng chú ý hơn của xích Markov là sự vector cân bằng t đạt được mà
không phụ thuộc vào các phân bố xác suất ban đầu.
Định lý 1.2.3 ([5]). Trong một xích Markov chính quy, vector cân bằng t đạt
được không phụ thuộc vào các phân bố xác suất ban đầu.
Để đơn giản, ta sẽ chứng minh nhận xét này cho ma trận chuyển cỡ 2 × 2,
trường hợp ma trận chuyển có cỡ cao hơn được chứng minh hoàn toàn tương
tự.
Chứng minh. Giả sử v (0) = [a b] là phân phối xác suất ban đầu tùy ý của
xích Markov chính quy với ma trận chuyển cỡ 2 × 2 là P. Đặt t = [t1 t2 ] là
18

Footer Page 22 of 132.


Header Page 23 of 132.

vector bất động của ma trận này. Khi đó theo tính chất 1 trong Định lý 1.2.2,
ta có
t1 t2
Pn → T =
khi n đủ lớn.
t1 t2
Nhân cả hai vế với v (0) ta có
v (0) P n → v (0) T khi n đủ lớn.
Do v (n) = v (0) P n , nên
v (n) → v (0) T khi n đủ lớn.
Mặt khác,
v (0) T = [a

b]



Header Page 24 of 132.

hấp thụ. Ma trận chuyển là


1 1/2 0
0 0


0 0 1/2 0 0



P =
0
1/2
0
1/2
0




0 0 1/2 0 0
0 0
0 1/2 1
.
Lưu ý rằng chỉ hai dáng điệu tiệm cận của xác suất là tồn tại với xích này


0 0.000015
0
0.000015 0


.
P 30 = 
0
0
0.000030
0
0




0
0.000015 0
0 0.000015
0 0.249985 0.499985 0.749985 1
Ta thấy rằng P n hội tụ tới ma trận

1 0.75 0.5 0.25

0 0
0
0

0 0



q


 0 


 0 




 0 
1−q
trạng thái dừng của P. Ma trận này có vô hạn các vector trạng thái dừng, do
đó xn không thể dự đoán sự hội tụ mà không phụ thuộc vào x0 .
Ví dụ 1.2.7. Một cộng đồng nhất định có ba cửa hàng tạp hóa. Trong cộng
đồng này có tồn tại một sự thay đổi khách hàng từ một cửa hàng tạp hóa này
tới cửa hàng khác. Một nghiên cứu được thực hiện vào ngày 01 tháng Một, và
nó đã cho ta thấy rằng 14 số dân đi mua sắm ở cửa hàng I, 31 tại cửa hàng II, và
2
15 tại cửa hàng III. Mỗi tháng cửa hàng I giữ lại 90% khách hàng của mình
và mất 10% trong số họ đến cửa hàng II. Cửa hàng II giữ lại 5% khách hàng
của mình và mất 85% trong số họ vì họ mua ở cửa hàng I và 10% trong số họ
mua ở cửa hàng III. Cửa hàng III vẫn giữ được 40% khách hàng của mình và
mất 50% trong số họ tới mua ở cửa hàng I và 10% ở cửa hàng II. Giả sử dân
số của cộng đồng vẫn không đổi. Hãy tìm
(a) Ma trận chuyển P ;
(b) Phân phối xác suất ban đầu;