TRƢỜNG ĐẠI HỌC CẦN THƠ
KHOA KHOA HỌC TỰ NHIÊN
BỘ MÔN TOÁN
------------

LUẬN VĂN TỐT NGHIỆP ĐẠI HỌC

XÍCH MARKOV VÀ ỨNG DỤNG

GIÁO VIÊN HƢỚNG DẪN

SINH VIÊN THỰC HIỆN

TS. Võ Văn Tài

Phạm Quốc Quang MSSV: 1117495

Bộ môn Toán – Khoa KHTN

Ngành: Toán ứng dụng – Khóa 37

Cần thơ, 2015


TRƢỜNG ĐẠI HỌC CẦN THƠ
KHOA KHOA HỌC TỰ NHIÊN

PHẠM QUỐC QUANG

XÍCH MARKOV VÀ ỨNG DỤNG



i


MỤC LỤC
LỜI CÁM ƠN ................................................................................................... i
MỤC LỤC ........................................................................................................ ii
DANH MỤC BẢNG ....................................................................................... iv
PHẦN GIỚI THIỆU ........................................................................................ v
Chƣơng 1: KIẾN THỨC CHUẨN BỊ ............................................................ 1
1.1 Công thức xác suất ............................................................................... 1
1.1.1 Khái niệm................................................................................. 1
1.1.2 Công thức cộng và công thức nhân ......................................... 2
1.1.3 Công thức xác suất đầy đủ và công thức Bayes ...................... 2
1.2 Một số vấn đề liên quan đến ma trận ................................................... 3
1.2.1 Khái niệm................................................................................. 3
1.2.2 Các phép toán trên ma trận ...................................................... 4
1.2.3 Ma trận nghịch đảo .................................................................. 5
1.3 Hệ phương trình tuyến tính .................................................................. 6
1.3.1 Khái niệm................................................................................. 6
1.3.2 Giải hệ phương trình bằng phương Gauss ............................... 7
1.3.3 Hệ phương trình bằng quy tắc Cramer .................................... 8
Chƣơng 2: XÍCH MARKOV ........................................................................ 10
2.1 Tính Markov và xích Markov ............................................................ 10
2.1.1 Quá trình Markov .................................................................. 10
2.1.2 Xích Markov .......................................................................... 10
2.1.3 Một số ví dụ ........................................................................... 11
2.2 Xích Markov rời rạc và thuần nhất .................................................... 12
2.2.1 Ma trận xác suất chuyển ........................................................ 12
2.2.2 Phân phối ban đầu .................................................................. 13

3.2.5 Mô hình phân chia thị trường ................................................ 41
3.2.6 Dự báo tăng trưởng kinh tế ở Việt Nam ................................ 44
3.2.7 Chính sách thay thế vật tư thiết bị ......................................... 45
KẾT LUẬN VÀ ĐỊNH HƢỚNG NGHIÊN CỨU....................................... 47
TÀI LIỆU THAM KHẢO ............................................................................. 48

iii


DANH MỤC BẢNG
Bảng 3. 1 số lượng khách hàng của từng nhóm sau 3 năm và 4 năm .............. 39
Bảng 3. 2 Bảng chuyển đổi giữa các loại nợ từ hiện tại đến tháng tiếp theo .. 40
Bảng 3. 3: Sự chuyển đổi của khách hàng đối với 3 cửa hàng từ gia đoạn 1
sang gia đoạn 2. ............................................................................................... 42

iv


PHẦN GIỚI THIỆU
1. Lý do chọn đề tài
Từ bộ số liệu thực tế của một quá trình độc lập với quá khứ, ta đưa ra
những dự doán trong tương lai từ đó rút ra những nhận xét, đánh giá và kết
luận, nhằm đưa ra những điều chỉnh, quyết định trong công tác chỉ đạo là
phương pháp khoa học rất hiệu quả được vận dụng phổ biến ở nhiều lĩnh vực
trong thực tế.
Thực tế nhiều quá trình luôn có sự chuyển đổi qua lại giữa các trạng thái
khác nhau. Quá trình Markov giúp ta biết ở thời gian trong tương lai xác suất
chuyển của quá trình sang từng trạng thái. Quá trình Markov đã được nghiên
cứu từ lâu, tuy nhiên cho đến hiện tại nó cũng được các nhà xác suất quan tâm.
Sự quan tâm này không những lý thuyết mà còn cả sự ứng dụng của nó. Tiếp


Chƣơng 1

KIẾN THỨC CHUẨN BỊ
1.1 Công thức xác suất
1.1.1 Khái niệm
Biến cố A được gọi là tổng của n biến cố A1 , A2 ,..., An nếu A xảy ra khi và
chỉ khi có ít nhất một trong n biến cố Ai , i  1,2,..., n xảy ra.
Kí hiệu là : A  A1  A2  ...  An .
Biến cố A được gọi là tích của n biến cố A1 , A2 ,..., An nếu A xảy ra khi và
chỉ khi tất cả n biến cố Ai , i  1,2,..., n xảy ra.
Kí hiệu là : A  A1. A2 ... An .
Hai biến cố A và B được gọi là xung khắc với nhau khi và chỉ khi chúng
không xảy ra đồng thời trong một phép thử.
Nhóm n biến cố A1 , A2 ,..., An gọi là xung khắc từng đôi, nếu hai biến cố
bất kỳ trong n biến cố đó xung khắc với nhau.
Hai biến cố A và B được gọi là độc lập nếu việc xảy ra hay không của
biến cố A không làm ảnh hưởng đến việc xảy ra hay không của biến cố B, và
ngược lại.
Các biến cố A1 , A2 ,..., An được gọi là độc lập toàn phần nếu mỗi biến cố
trong chúng độc lập với tích của một tổ hợp bất kỳ các biến cố còn lại.
Nhóm biến cố A1 , A2 ,..., An được gọi là đầy đủ nếu tổng chúng là biến cố
chắc chắn và chúng xung khắc từng đôi


 A1  A2  ...  An  


 Ai  Aj   i  j
Xác suất của biến cố A với điều kiện biến cố B xảy ra được gọi là xác


Nếu Ai , i  1,2,..., n độc lập toàn phần thì
P

n
i 1

A  P  A1  P  A2  ....P  An 

1.1.3 Công thức xác suất đầy đủ và công thức Bayes
Cho A1 , A2 ,..., An là nhóm biến cố đầy đủ, A là biến cố có thể xảy ra cùng
với một trong các biến cố Ai , i  1,2,..., n . Khi đó ta có.
a) Công thức xác suất đầy đủ
n

Ρ  Α =  Ρ  Ai  Ρ  Α| Ai 
i=1

b) Công thức Bayes
Ρ  Ai | Α =

Chú ý:

(i)

Ρ  Ai  Ρ  Α| Ai 
P  A

P  A | A  1




 am1
amn 
trong đó aij ký hiệu số ở dòng i và cột j  i  1,

, m; j  1,

n  . Các số aij

được gọi là các phần tử của ma trận. Người ta thường viết ma trận trên dưới
dạng  aij  .
mn
Một ma trận vuông là một ma trận có số dòng bằng số cột

 a11

 
 

 an1

a1n 

 
 

ann 

số dòng của ma trận được gọi là cấp của ma trận đó. Hệ các phần tử aii của A

A  B   aij  bij 

mn

hay

 a11

 
 

 am1

a1n   b11
 
   

   
 
amn  bm1

Phép nhân vô hƣớng:
 a11


c
 

 am1



camn 

Phép nhân hai ma trận:
Giả sử A   aij 

mn

là một ma trận cấp m  n và B  b jk 

np

là một ma

trận cấp n  p . Ma trận tích AB là ma trận  dik mp có cấp m  p với:

dik  ai1b1k  ai 2b2k 

 ainbnk

Phép nhân hai ma trận chỉ có thể thực hiện được khi ma trận thứ nhất có
số cột bằng với số dòng của ma trận thứ hai. Ta có thể xác định các phần tử
dik của ma trận tích AB bằng cách nhân lần lượt n phần tử của dòng thứ i của
ma trận A (từ trái sang phải) với n phần tử của cột thứ k của ma trận B (từ trên
xuống dưới) rồi lấy tổng của chúng.
Tính chất:

 AB  C  A BC 
(ii) A  B  C   AB  AC
(iii)  A  B  C  AC  BC

d) AT khả nghịch và ( AT )1  ( A1 )T
Các tính chất trên ta có thể dể dàng chứng minh.
Thuật toán tìm ma trận nghịch đảo
Ma trận nghịch đảo A1 của ma trận A được tìm theo quy luật thuật toán
gồm các bước sau:
Bước 1: Lập ma trận gồm 2 khối  A | I n  .
Bước 2: Áp dụng các thuật toán rút gọn hàng, quy khối ma trận khối trái
về I n . Khi đó khối phải là ma A1 cần tìm.
Chú ý: Thuật toán này chỉ áp dụng được với trường hợp ma trận A quy về
được ma trận I n . Nếu trường hợp ma trận A không quy vê ma trận I n được thì
sẽ dùng cách khác.
5


1 1 2 
Ví dụ 1.1 Tìm ma trận nghịch đảo của ma trận A  1 2 2 


 2 4 3 
Ta có ma trận 2 khối

1 1 2 1 0 0 
 A | I3   1 2 2 0 1 0
 2 4 3 0 0 1 
Áp dụng các thuật toán rút gọn hàng, quy khối ma trận khối trái về I 3 ta
được.

1 0 0 2 5 2 
 A | I3   0 1 0 1 1 0 
0 0 1 0 2 1 

a11 x1  a12 x2  ...  a1n xn  0
a x  a x  ...  a x  0
 21 1 22 2
2n n


am1 x1  am 2 x2  ...  amn xn  0
Nghiệm của hệ phương trình là bộ gồm n số  c1; c2 ;...; cn  mà khi thay
vào các ẩn x j ( j  1...n) , các phương trình trong hệ trở thành các đẳng thức
đúng.
Giải hệ phương trình là tìm nghiệm của nó.
1.3.2 Giải hệ phƣơng trình bằng phƣơng Gauss
Cho hệ (1), ma trận được lập bởi các hệ số aij của hệ (1): A   aij 

nm

được gọi là ma trân hệ số. Ma trận hệ số có bổ sung thêm cột cuối cùng là các
hệ số vế phải, gọi là ma trận đầy đủ. Kí hiệu A*

 a11 a12

a
a22
*
A   A | b    21


 am1 am 2

a1n b1 

Bước 1: Viết ma trận dạng đầy đủ A* của hệ tuyến tính.
Bước 2: Dùng thuật toán rút gọn hàng, quy ma trận đầy đủ A* về dạng
bậc thang. Khẳng định hệ có nghiệm hay không, nếu có nghiệm thực hiện
bước tiếp theo.
Bước 3: Quy dạng bậc thang của ma trận đầy đủ A* về dạng rút gọn.
Bước 4: Tứ dạng rút gọn, vết ra nghiệm của hệ.

 x1  2 x2  5 x3  9

Ví dụ 1.2 Giải hệ phương trình sau:  x1  x2  3x3  2
3x  6 x  x  25
2
3
 1
Bước 1: Lập ma trận đầy đủ của hệ

1 2 5 9 


A  1 1 3 2 
3 6 1 25 
*

Bước 2: Quy ma trận A* về dạng rút gọn.

1 2
1 2 5 9 
5 9 

 h3h34 h 2 

và B  M (n,1) . Gọi A j là ma trận nhờ thay cột B vào cho cột j trong A. Khi
8


đó AX  B có nghiệm duy nhất X   x1

x2 .... xn  trong đó x j được tính
T

bởi công thức như sau:

xj 

det( Aj )
det( A)

, j  1...n

 x1  2 x2  5 x3  9

Ví dụ 1.3 Giải hệ phương trình sau:  x1  x2  3x3  2
3x  6 x  x  25
2
3
 1
1 2 5
1 2 5 


Có A  1 1 3 , det( A)  1 1 3  24

, j  1...n ta có  x2  3
det( A)
 x  1
 3

det( Aj )

9


Chƣơng 2

XÍCH MARKOV
2.1 Tính Markov và xích Markov
Đâu thế kỷ XX, A.A. Markov (14/06/1856-20/07/1922) – nhà Toán học
và Vật lý nổi tiếng người Nga đã đưa ra mô hình toán học để mô tả chuyển
động của các phân tử chất lỏng trong bình kín. Về sau mô hình này được phát
triển và sử dụng trong nhiều lĩnh vực khác nhau như cơ học, sinh học, y học,
kinh tế, v.v… và được mang tên quá trình Markov.
Xích Markov là một quá trình Markov có hữu hạn trạng thái.
2.1.1 Quá trình Markov
Ta cần 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 đó (có thể là phân tử, hạt cơ bản, người hoặc một sinh vật 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 s hệ ở trạng thái nào
đó, còn thời điểm s thì trạng thái i. Ta cần biết thời điểm t trong tương lai
 t  s  hệ ở trạng thái j với xác suất bao nhiêu? Nếu xác suất này 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.

Đặt p  s, t , i, j   P  X  t   j | X  s   i,  s  t  . Đó là xác suất có điều
kiện để hệ (hay 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ạng thái j. Vì thế p  s, t , i, j  là xác suất chuyển của hệ (hay quá trình).
Nếu xác suất chuyển p  s, t , i, j   p  s  h, t  h, i, j  , i, j, t , s và h
thì ta nói xích Markov thuần nhất theo thời gian.
2.1.3 Một số ví dụ
Ví dụ 2.1. Gọi X  t  là dân số tại thời điểm t (trong tương lai), ta có thể xem

X  t  chỉ phụ thuộc vào dân số hiện tại và độc lập với quá khứ.
Nói chung, các hệ (sinh thái, cơ học, vật lý,..) không có trí nhớ hoặc sức
ỳ là một hệ có tính Markov.
Ví dụ 2.2. Cho 0 , 1 ,

, n ,

là dãy biến ngẫu nhiên (đại lượng ngẫu nhiên)

rời rạc, độc lập, Ek là tập các giá trị của  k , Ek hữu hạn (hay đếm được)
(k=0,1,2,…).
Đặt E 


k 0

Ek  E là tập hợp không quá đếm được.

Khi đó, ta thấy

P  n1  j | 0  i0 ,  n1  in1 ,  n  in 
 P  n1  j  P  n1  j |  n  in   p  n, i, n  1, j 

 P n1  j  i | 0  1  2 

  n1   n  i
 n 1  n  i

 P  X n  n1  j  i
Vậy  X n ; n  1,2,3,... là xích Markov.
Đặc biệt: Nếu trong ví dụ 2.2 cho 0 , 1 ,

, n ,

là dãy biến ngẫu nhiên

rời rạc, độc lâp và cùng phân phối xác suất, thì n ; n  0,1,2,



là xích

Markov thuần nhất và ngược lại.
Trong ví dụ 2.3 cho 1 ,2 , n ,

là dãy đại lượng ngẫu nhiên rời rạc,

độc lập và có cùng phân phối xác suất thì  X n ; n  1,2,3,... là xích Markov
thuần nhất. Thật vậy bằng lập luận trên ta có

P  X n h  j | X n  i  P n1  n 2 
 P 1  2 



ij

 1 , i  N , ma

trận có tính chất như thế gọi là ma trận ngẫu nhiên.
Xác suất chuyển sau n bước chuyển được tính

pijn  P  X (tnm )  j | X (tm )  i   P  X (tn )  j | X (t0 )  i 
là xác suất chuyển từ trạng thái i sang trạng thái j sau n bước chuyển.
là ma trận xác suất chuyển sau n bước chuyển.
P    pij  

 N N
n

n

12


Các tính chất

pij

n m

(i)

  pik  pkj  n, m  0,1,2,... (phương trình Chapmann






Đặt Π     j   pj  , j  E là véc tơ phân phối tại thời điểm t  n .
n

n

n

Với t = 0 ta có véc tơ phân phối ban đầu   1  ,  2  ,...,  N   .


0

0

0

Xét xích Markov rời rạc và thuần nhất với ma trận chuyển P   pij 

N N

.

Phân phối Π = 1 ,  2 ,...,  N  được gọi là dừng nếu Π = 1 ,  2 ,...,  N  thoả
mãn điều kiện    I  P   0 .
Ta thấy ngay được, phân phối dừng không phụ thuộc vào Π   mà chỉ

1  
điều kiện cần và đủ để xác định (không nhất thiết duy nhất) P là     1.
 a 1  a
,  0  a, b  1 , ta có
Thật vậy, giả sử rằng P  
b 
1  b
13


 a 2  1  a 1  b 
1  
 
 a  b 1  a  
 2
2
P P 

1  

2
 
b  1  a 1  b  

  a  b 1  b 
suy ra

    a 2  1  a 1  b   b2  1  a 1  b    a  b  1  1  1
2


Ta xét trường hợp đơn giản nhất của xích Markov: không gian trạng thái
E của  X n  gồm hai phần tử. Ta ký hiệu E  0,1 .
Giả sử ma trận xác suất chuyển của xích Markov là.

a 
1  a
P

 b 1  b
với 0 < a, b < 1.
Có thể kiểm tra lại rằng a = 1 – b khi và chỉ khi X1 , X 2 ,... là các biến
ngẫu nhiên độc lập cùng phân phối với P  X n  0  b, P  X n  1  a nếu ta
xem P  X o  0  b, P  X 0  1  a . Do đó, khi a  1  b thì X n là dãy phụ
thuộc, nhưng có tính Markov.

14


Tính trực tiếp ta thấy

 1  a 2  ab a 1  a  1  b  

P 
2
b 1  a  1  b  1  b   ab 
2

Bằng quy nạp ta có

1 b a  1  a  b   a a 

ab
Mô hình xác suất hai trạng thái có ý nghĩa thực tiễn: Giả sử ta nghiên
cứu một vấn đề xã hội (tội phạm, nghiện hút, mại dâm,…) trong lớp người nào
đó. Ta ký hiệu 0 là trạng thái không mắc vấn đề xã hội và 1 là trạng thái mắc
vấn đề xã hội.
Ví dụ 2.4: Thống kê tình trạng nghiện hút của 1200 sinh viên ta có số liệu ban
đầu: 1000 không nghiện, 200 nghiện. Vậy tỉ lệ ban đầu là
1000 5
200 1
p0 
  0,833; p1 
  0,167 .
1200 6
1200 6
Sau 3 tháng, do bọn buôn bán ma tuý hoạt động mạnh và do những biện
pháp xã hội (tuyên truyền, giáo dục, cai nghiên,…) nên đã có những sinh viên
(trong số 1200 sinh viên này) sẽ chuyển từ 0  0 (trước đây không nghiện,
nay vẫn không nghiên), 0  1 (trước đây không nghiện, nay nghiện), 1  0
(trước đây nghiên, nay không nghiện), 1  1 (trước đây nghiện, nay vẫn
nghiện), với ma trận chuyển là

990 10 
 24 176 



15


Ta có các xác suất chuyển là

p01  0,99 0,01

p11   0,12 0,88

Theo mô hình trên thì a  0,01 ; b  0,12 . Ta thấy 1  a  b  1. Vì thế

 b
a  b
lim P n  
n 
 b
 a  b

a 
a  b  0,923 0,077 

a  0,923 0,077 
a  b 

Kết luận: Trong tương lai sẽ có phân phối cân bằng. Tỷ lệ người không
nghiện là xấp xỉ 92%. Tỷ lệ người nghiện là xấp xỉ 8%
Ta tính đến tốc độ hội tụ P n . Ta tính P 2 , P3 ,... và rút ra n cần thiết. Nếu
n = 24 thì có nghĩa là 24 / 3  6 năm sẽ có phân phối cân bằng nói trên.
Sau 3 tháng đầu tiên ta có tỷ lệ người nghiện là



1

0,99 0,01


16


Khi n = 24 ta được



 24

0,9257966 0,0742034 
=  P 24  5 / 6 1/ 6 
  0,9199 0,0801
0,8904407 0,1095593 

2.3.2 Định lý ergodic
Ta phải nghiên cứu những điều kiện để xich Markov có tính chất ergodic
theo nghĩa sau: tồn tại giới hạn  j  lim pij  không phụ thuộc vào i. Sao cho
n

n

 j  0 j  E ,
Định lý 2.1: Giả sử P   pij 

N N


jE


(2.5)

với mọi j  E

lim pij    j
n

(2.6)

n

(ii)

Ngược lại, nếu tồn tại các số 1 ,...,  N thoả mãn điều kiện (2.5) và

(2.6) thì sẽ tồn tại n0 thoả mãn (2.4).

(iii)

Các số 1 ,...,  N là nghiệm của hệ phương trình

 j   xk pkj

(2.7)

kE

đó cũng là nghiệm duy nhất thoả mãn điều kiện

xi  0, j  E;  jE x j  1