BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
Lê Thị Linh
XÍCH MARKOV VÀ ỨNG DỤNG
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Hà Nội - 2017
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
Lê Thị Linh
XÍCH MARKOV VÀ ỨNG DỤNG
Chuyên ngành: Toán Ứng Dụng
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. Trần Vĩnh Đức
Hà Nội - 2017
LỜI CẢM ƠN
Trước khi trình bày nội dung chính của khóa luận, tôi xin bày tỏ lòng
cảm ơn tới các thầy cô khoa Toán, trường Đại Học Sư Phạm Hà Nội 2,
các thầy cô trong tổ bộ môn Toán ứng dụng cũng như các thầy cô tham
gia giảng dạy đã tận tình truyền đạt những tri thức quý báu và tạo điều
kiện thuận lợi để tôi hoàn thành tốt nhiệm vụ khóa học và khóa luận.
Đặc biệt, tôi xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc tới Tiến
sĩ Trần Vĩnh Đức, người đã trực tiếp hướng dẫn, chỉ bảo tận tình giúp
đỡ để tôi có thể hoàn thành tốt khóa luận này.
Hà Nội, tháng 5 năm 2017
Sinh viên
Lê Thị Linh
1
LỜI CAM ĐOAN
Khóa luận này là kết quả nghiên cứu của bản thân tôi dưới sự hướng
dẫn tận tình của thầy giáo Trần Vĩnh Đức.
Trong khi nghiên cứu hoàn thành đề tài nghiên cứu này tôi đã tham
khảo một số tài liệu đã ghi trong phần tài liệu tham khảo. Tôi xin khẳng
định kết quả của đề tài "Xích Markov và ứng dụng" là kết quả của
việc nghiên cứu, học tập và nỗ lực của bản thân, không có sự trùng lặp
với kết quả của đề tài khác. Nếu sai tôi xin chịu hoàn toàn trách nhiệm.
Hà Nội, tháng 5 năm 2017
Sinh viên
Lê Thị Linh
2
Mục lục
LỜI CẢM ƠN
1
LỜI CAM ĐOAN
2
GIỚI THIỆU
5
1 KIẾN THỨC CƠ SỞ
7
1.1
1.2
1.3
Sơ lược về lý thuyết xác suất . . . . . . . . . . . . . . .
7
1.1.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . .
7
1.1.2. Biến ngẫu nhiên . . . . . . . . . . . . . . . . . .
9
1.1.3. Công thức xác suất đầy đủ và công thức Bayes .
10
Sơ lược về ma trận . . . . . . . . . . . . . . . . . . . .
11
1.2.1. Định nghĩa ma trận . . . . . . . . . . . . . . . .
11
1.2.2. Phép toán đại số trên ma trận . . . . . . . . . .
12
1.2.3. Ma trận nghịch đảo . . . . . . . . . . . . . . . .
13
Hệ phương trình tuyến tính . . . . . . . . . . . . . . . .
13
2 XÍCH MARKOV
15
2.1
Xích Markov hữu hạn . . . . . . . . . . . . . . . . . . .
15
2.2
Biểu diễn ánh xạ ngẫu nhiên . . . . . . . . . . . . . . .
20
2.3
Tính tối giản và phi tuần hoàn . . . . . . . . . . . . . .
23
3
4
2.4
Hành trình ngẫu nhiên trên đồ thị . . . . . . . . . . . .
25
2.5
Phân phối dừng . . . . . . . . . . . . . . . . . . . . . .
26
2.6
Tính khả nghịch và thời điểm nghịch đảo . . . . . . . .
31
2.7
Phân loại trạng thái của xích Markov . . . . . . . . . .
33
3 ỨNG DỤNG
37
3.1
Người chơi bạc phá sản . . . . . . . . . . . . . . . . . .
37
3.2
Sưu tập phiếu giảm giá . . . . . . . . . . . . . . . . . .
39
3.3
Siêu lập phương và mô hình bình Ehrenfest . . . . . . .
40
3.4
Mô hình bình Polya . . . . . . . . . . . . . . . . . . . .
43
3.5
Chuỗi sinh tử . . . . . . . . . . . . . . . . . . . . . . .
44
3.6
Mô hình phục vụ đám đông . . . . . . . . . . . . . . . .
46
3.7
Xích Markov trong di truyền . . . . . . . . . . . . . . .
48
3.8
Mô hình kiểm kê . . . . . . . . . . . . . . . . . . . . . .
49
3.9
Hành trình ngẫu nhiên trên Z và định luật đối xứng . .
51
KẾT LUẬN
56
TÀI LIỆU THAM KHẢO
57
GIỚI THIỆU
1. Lý do chọn đề tài
Nhiều quá trình trong thực tế luôn có sự chuyển đổi qua lại giữa các
trạng thái khác nhau, điển hình là quá trình Markov. Quá trình Markov
giúp ta biết, từ bộ số liệu thực tế độc lập với quá khứ, ta sẽ đưa ra được
những dự doán trong tương lai nhờ vào ma trận xác suất chuyển. Rồi
từ đó rút ra những nhận xét, đánh giá, kết luận, nhằm điều chỉnh và
quyết định trong công tác chỉ đạo được vận dụng phổ biến ở nhiều lĩnh
vực như: kinh tế, kỹ thuật, dân số học, di truyền học,... Thấy được tầm
quan trọng của quá trình này và được sự giúp đỡ tận tình của thầy giáo
Trần Vĩnh Đức nên tôi đã mạnh dạn lựa chọn đề tài "Xích Markov
và ứng dụng" làm đề tài nghiên cứu.
2. Mục đích nghiên cứu
- Nhằm tìm hiểu một số kết quả về lý thuyết xích Markov và một số
mô hình ứng dụng của nó.
- Rèn luyện tư duy nghiên cứu khoa học và nâng cao trình độ nhận
thức của bản thân.
5
6
3. Đối tượng và phạm vi nghiên cứu
- Đối tượng nghiên cứu: Xích Markov và ứng dụng.
- Phạm vi nghiên cứu: Các tính chất và một số ứng dụng cơ bản của
xích Markov.
4. Phương pháp nghiên cứu
- Tổng hợp tài liệu, sắp xếp các vấn đề nghiên cứu một cách lôgic và có
hệ thống.
5. Nội dung nghiên cứu
Khóa luận gồm ba chương:
Chương 1: Kiến thức cơ sở . Trình bày các kiến thức liên quan đến
xác suất, ma trận và hệ phương trình tuyến tính.
Chương 2: Xích Markov . Trình bày định nghĩa xích Markov, tính
Markov và điều kiện cần để tồn tại duy nhất một phân phối dừng.
Chương 3: Ứng dụng . Trình bày một số ứng dụng của xích Markov.
Chương 1
KIẾN THỨC CƠ SỞ
Mục đích của chương này là trình bày các kiến thức cơ bản về lý
thuyết xác suất, ma trận và hệ phương trình tuyến tính. Các kiến thức
này sẽ được sử dụng ở chương sau khi nghiên cứu về xích Markov và
ứng dụng của xích Markov.
1.1
1.1.1.
Sơ lược về lý thuyết xác suất
Định nghĩa
Phép thử ngẫu nhiên, kí hiệu là E . Các kết quả của E là ngẫu nhiên,
không thể xác định trước. Tuy nhiên ta có thể liệt kê ra tất cả các kết
quả có thể của E . Tập hợp tất cả các kết quả có thể của E được gọi là
không gian mẫu của E và kí hiệu là Ω. Chữ w dùng để kí hiệu một phần
tử của Ω và ta gọi mỗi phần tử w của Ω là một biến cố sơ cấp.
Định nghĩa xác suất cổ điển
Định nghĩa 1.1.1. Giả sử phép thử E có một số hữu hạn các kết quả
có thể. Khi đó xác suất của biến cố A là tỉ số giữa số kết quả thuận lợi
7
Chương 1. KIẾN THỨC CƠ SỞ
của A và số kết quả có thể. Kí hiệu: P (A) =
8
|A|
, trong đó |A| là số
|Ω|
phần tử của tập A.
Định nghĩa xác suất bằng tần suất
Định nghĩa 1.1.2. Giả sử phép thử E có thể được thực hiện lặp đi lặp
lại nhiều lần trong những điều kiện giống nhau. Nếu trong n lần thực
k(A)
hiện phép thử E , biến cố A xuất hiện k(A) lần thì tỉ số fn (A) =
n
được gọi là tần suất xuất hiện của biến cố A trong n phép thử.
Phương pháp tiên đề trong lý thuyết xác suất
Giả sử E là một phép thử ngẫu nhiên và Ω là tập hợp các kết quả
của E . Mỗi tập con của Ω được gọi là một biến cố. Một họ F nào đó
các tập con của Ω được gọi là một σ - đại số các biến cố nếu:
(i) Ω ∈ F , Ø ∈ F .
(ii) Nếu A ∈ F thì Ω\A ∈ F .
(iii) Nếu A1 , A2 , ... là một dãy các tập hợp của họ F thì hợp ∪∞
n=1 An
cũng thuộc F .
Xác định một quy luật xác suất trên σ - đại số F là gán cho mỗi biến
cố A ∈ F một số P (A) gọi là xác suất của A. Phép gán đó phải thỏa
mãn các điều kiện sau:
1) ∀A ∈ F , 0 ≤ P (A) ≤ 1.
2) P (Ω) = 1, P (Ø) = 0.
3) Nếu A1 , A2 , ... là dãy các biến cố thuộc F đôi một xung khắc với
P∞
nhau (Ai Aj = Ø nếu i 6= j ) thì P (∪∞
n=1 An ) =
n=1 P (An ).
Chương 1. KIẾN THỨC CƠ SỞ
9
Khi đó, (Ω, F, P ) được gọi là không gian xác suất.
1.1.2.
Biến ngẫu nhiên
Biến ngẫu nhiên
Một đại lượng (hay một biến) nhận các giá trị của nó với xác suất
tương ứng nào đó gọi là đại lượng ngẫu nhiên (ĐLNN) hay biến ngẫu
nhiên (BNN).
Nếu tập các giá trị mà biến ngẫu nhiên nhận là một tập gồm một số
hữu hạn hoặc vô hạn nhưng đếm được, khi đó biến ngẫu nhiên gọi là
biến ngẫu nhiên rời rạc.
Nếu tập các giá trị mà biến ngẫu nhiên gồm các số lấp kín một khoảng
trên trục số, số phần tử của tập giá trị là vô hạn không đếm được, khi
đó biến ngẫu nhiên gọi là biến ngẫu nhiên liên tục.
Hàm phân phối
Phân phối xác suất của một ĐLNN rời rạc X là một bảng mà trên
đó ta ghi các giá trị mà X có thể kèm theo các xác suất để nó nhận các
giá trị đó và bảng phân phối xác suất có dạng
X x1 x2 ... xn
ở đó pi = P {X = xi }. (
P
Pn
p1 p2 ... pn
i=1 pi
= 1).
Hàm phân phối xác suất của ĐLNN X là một hàm F (x) xác định
với mọi x theo công thức sau
F (x) = P {X < x}.
Chương 1. KIẾN THỨC CƠ SỞ
10
Kì vọng
Định nghĩa 1.1.3. Cho X là đại lượng ngẫu nhiên rời rạc có bảng xác
suất như sau
X x1 x2 ...
P
p1 p2 ...
kì vọng (giá trị trung bình) của X được kí hiệu là EX cho bởi công
thức sau:
EX =
1.1.3.
X
x i pi ,
(1 ≤ i ≤ +∞).
Công thức xác suất đầy đủ và công thức Bayes
Các biến cố B1 , B2 , ..., Bn được gọi là một hệ đầy đủ các biến cố nếu
chúng đôi một xung khắc với nhau (Bi Bj = Ø nếu i 6= j ) và hợp của
chúng là biến cố chắc chắn
Ω = B1 ∪ B2 ∪ ... ∪ Bn .
Định lí 1.1.1. Nếu B1 , B2 , ..., Bn là một hệ đầy đủ thì với mỗi biến cố
A ta có
P (A) =
n
X
P (Bi ) · P (A/Bi ).
(1.1)
i=1
Công thức (1.1) được gọi là công thức xác suất đầy đủ.
Một công thức khác có liên quan mật thiết với công thức xác suất
đầy đủ là công thức Bayes.
Định lí 1.1.2. Nếu B1 , B2 , ..., Bn là một hệ đầy đủ các biến cố và A là
một biến cố với P (A) > 0 thì với mỗi k = 1, 2, ..., n
P (Bk ) · P (A/Bk )
.
P (Bk /A) = Pn
i=1 P (Bi ) · P (A/Bi )
Công thức (1.2) được gọi là công thức Bayes.
(1.2)
Chương 1. KIẾN THỨC CƠ SỞ
11
* Ta chứng minh công thức (1.1).
A = AΩ = A(B1 ∪ B2 ∪ ... ∪ Bn ) = AB1 ∪ ... ∪ ABn .
Các biến cố ABi , i = 1, 2, ..., n xung khắc nên:
P (A) =
n
X
P (ABi ).
i=1
Theo quy tắc nhân P (ABi ) = P (Bi ) · P (A/Bi ). Thay vào ta được
P (A) =
n
X
P (Bi ) · P (A/Bi ).
i=1
* Công thức (1.2) suy ra từ đẳng thức sau:
P (Bk ) · P (A/Bk ) = P (A) · P (Bk /A) = P (Bk A).
Suy ra được:
P (Bk /A) =
Mặt khác
P (A) =
P (Bk ) · P (A/Bk )
.
P (A)
n
X
P (Bi ) · P (A/Bi ).
i=1
1.2
1.2.1.
Sơ lược về ma trận
Định nghĩa ma trận
Giả sử K là một trường tùy ý.
Định nghĩa 1.2.1. Mỗi bảng có
a
11
a21
A=
...
am1
dạng
a12 ... a1n
a22
...
am2
... a2n
,
... ...
... amn
Chương 1. KIẾN THỨC CƠ SỞ
12
trong đó aij ∈ K (1 ≤ i ≤ m, 1 ≤ j ≤ n), được gọi là một ma trận m
hàng, n cột với các phần tử trong K. Nếu m = n, thì ta nói A là một
ma trận vuông cấp n. Vectơ hàng
ai1 ai2 ... ain ,
được gọi là hàng thứ i của ma trận A. Vectơ cột
a1j
a2j
... atmj ,
được gọi là cột thứ j của ma trận A.
Ma trận nói trên thường được kí hiệu là A = (aij)m×n .
Tập hợp tất cả các ma trận m hàng, n cột với các phần tử trong K
được kí hiệu là M (m × n, K) hay M at(m × n, K).
1.2.2.
Phép toán đại số trên ma trận
Phép cộng ma trận
Có thể cộng hai hay nhiều ma trận có cùng kích thước là m × n. Cho
hai ma trận A = (aij )m×n và B = (bij )m×n . Tổng của A và B là ma
trận C = (aij + bij )m×n . Với A, B, C ∈ M (m × n, K).
Phép nhân ma trận với một số
Cho c 6= 0 và ma trận A = (aij )m×n ∈ M (m × n, K). Khi đó
cA = (caij )m×n ∈ M (m × n, K).
Phép nhân ma trận
Cho hai ma trận A = (aij )m×n ∈ M (m × n, K) và
B = (bjk )n×p ∈ M (n × p, K). Tích AB của ma trận A và B là ma trận
Chương 1. KIẾN THỨC CƠ SỞ
13
C = (cik ) ∈ M (m × p, K), với các phần tử được xác định như sau:
cik =
n
X
aij bjk
(1 ≤ i ≤ m, 1 ≤ k ≤ p).
j=1
1.2.3.
Ma trận nghịch đảo
Định nghĩa 1.2.2. Ma trận A ∈ M (n × n, K) được gọi là một ma trận
khả nghịch (hoặc ma trận không suy biến) nếu có ma trận
B ∈ M (n × n, K) sao cho AB = BA = En (En là ma trận đơn vị). Khi
đó, ta nói B là nghịch đảo của A và kí hiệu là B = A−1 .
Định lí 1.2.1. Cho A ∈ M (n × n, K). Khi đó A khả nghịch khi và chỉ
khi detA 6= 0.
1.3
Hệ phương trình tuyến tính
Xét hệ phương trình gồm m phương trình với n ẩn x1 , ..., xn có dạng:
a11 x1 + a12 x2 + ... + a1n xn = b1 ;
a x + a x + ... + a x = b ;
21 1
22 2
2n n
2
(1.3)
.............................................
a x + a x + ... + a x = b .
m1 1
m2 2
mn n
m
Trong đó aij , bi là các phần tử cho trước trong trường K.
Kí hiệu:
x
b
1
1
x2
b2
,β =
.
A = (aij )m×n , x =
...
...
xn
bm
Chương 1. KIẾN THỨC CƠ SỞ
14
Khi đó, hệ phương trình (1.3) nói trên có thể viết dưới dạng phương
trình vectơ Ax = β .
Một nghiệm của hệ này là một vectơ x0 = Kn sao cho Ax0 = β . Một
hệ phương trình có ít nhất một nghiệm được gọi là một hệ phương trình
tương thích.
Hệ phương trình Ax = 0 được gọi là hệ phương trình tuyến tính
thuần nhất liên kết với hệ Ax = β .
Hai hệ phương trình được gọi là tương đương nhau nếu chúng có cùng
tập nghiệm.
Nhận xét 1.3.1. Khi giải một hệ phương trình tuyến tính, các phép
biến đổi sau đây là tương đương:
• Hoán đổi hai phương trình cho nhau.
• Nhân hai vế của một phương trình cho một số khác 0.
• Cộng vào một phương trình một bội của phương trình khác.
Nhận xét 1.3.2. Hệ phương trình thuần nhất của hệ phương trình (1.3)
luôn có một nghiệm u = (0, 0, ..., 0). Nghiệm này được gọi là nghiệm
tầm thường.
Chương 2
XÍCH MARKOV
Chương này trình bày định nghĩa xích Markov, biểu diễn ánh xạ ngẫu
nhiên, hành trình ngẫu nhiên trên đồ thị và trình bày được những xích
tối giản, phi tuần hoàn luôn hội tụ tới phân phối dừng của chúng.
2.1
Xích Markov hữu hạn
Một xích Markov hữu hạn là một quá trình chuyển động giữa các
phần tử của một tập hữu hạn Ω theo cách sau: tại x ∈ Ω, vị trí tiếp
theo được chọn tương ứng với một phân phối xác suất P (x, ·). Chi tiết
hơn, một dãy các biến ngẫu nhiên(X0 , X1 , ...) là một xích Markov với
không gian trạng thái Ω và ma trận xác suất chuyển P nếu ∀x, y ∈ Ω,
với t ≥ 1 và Ht−1 = ∩t−1
s=0 {Xs = xs } thỏa mãn P(Ht−1 ∩{Xt = x}) > 0,
ta có:
P{Xt+1 = y | Ht−1 ∩ {Xt = x}} = P{Xt+1 = y | Xt = x} = P (x, y).
(2.1)
Phương trình (2.1) được gọi là tính chất Markov, nghĩa là xác suất có
điều kiện của việc thay đổi từ trạng thái x tới trạng thái y , không phụ
thuộc x0 , x1 , ...xt−1 là các trạng thái đứng trước x.
15
Chương 2. XÍCH MARKOV
16
Dòng thứ x của ma trận P được kí hiệu là P (x, ·). Ma trận P như
vậy được gọi là ma trận xác suất, các phần tử của dòng này không âm
và
X
P (x, y) = 1,
∀x ∈ Ω.
y∈Ω
Ví dụ 2.1.1. Một con ếch sống trong một cái ao trên hai chiếc lá sen,
phía đông và tây, trên mỗi lá sen có một đồng xu. Mỗi buổi sáng con
ếch quyết định nhảy sang chiếc lá sen kia bằng việc tung đồng xu trên
lá sen mà nó đang đứng. Sau khi tung đồng xu, nếu đồng xu xuất hiện
mặt ngửa thì nó sẽ nhảy sang lá sen kia. Nếu đồng xu xuất hiện mặt
sấp thì nó ở lại lá sen cũ.
Hình 2.1: Bước nhảy ngẫu nhiên của con ếch, khi đồng tiền suất hiện mặt ngửa thì
nhảy sang chiếc lá khác.
Giả sử Ω = {e, ω} và (X0 , X1 , ...) là dãy các lá sen mà con ếch đã ở
vào ngày chủ nhật, thứ hai,... Gọi đồng xu ở chiếc lá phía đông và xuất
hiện mặt ngửa có xác suất là p, khi đó đồng xu xuất hiện mặt ngửa ở
chiếc lá phía tây có xác suất là q . Quy tắc nhảy của con ếch đơn giản
Chương 2. XÍCH MARKOV
như sau, nếu đặt:
P =
17
P (e, e) P (e, w)
=
P (w, e) P (w, w)
1−p
p
q
1−q
,
(2.2)
thì (X0 , X1 , ...) là một xích Markov với ma trận chuyển P . Để ý rằng
hàng đầu tiên của ma trận P là phân phối có điều kiện của Xt+1 cho
bởi Xt = e, khi đó hàng thứ hai là phân phối có điều kiện của Xt+1 cho
bởi Xt = w.
Giả thiết rằng con ếch đã ở lá phía đông vào ngày chủ nhật. Khi nó
tỉnh dậy vào ngày thứ hai, thì xác suất p chuyển sang lá phía tây và lá
phía đông có xác suất là 1 − p. Do đó,
P{X1 = e|X0 = e} = 1 − p,
P{X1 = w|X0 = e} = p.
(2.3)
Ngày thứ ba như thế nào? Xem xét hai khả năng như X1 , ta thấy rằng:
P{X2 = e|X0 = e} = (1 − p)(1 − p) + pq
(2.4)
P{X2 = w|X0 = e} = (1 − p)p + p(1 − q).
(2.5)
và
Ta có thể viết công thức như (2.4) và (2.5) một cách hệ thống hơn.
µt := (P{Xt = e|X0 = e}, P{Xt = w|X0 = e}).
Giả thiết con ếch bắt đầu từ lá phía đông, giờ ta có thể viết µ0 = (1, 0),
khi đó (2.3) trở thành µ1 = µ0 P .
Nhân P vào vế phải của phân phối ta được:
µt = µt−1 P,
∀t ≥ 1.
(2.6)
Thay thế với phân phối đầu tiên bất kỳ µ0 nào đó ta có:
µt = µ0 P t ,
(t ≥ 0).
(2.7)
Chương 2. XÍCH MARKOV
18
Hình 2.2: Xác suất theo từng thời điểm (bắt đầu từ chiếc lá phía đông) với (a)
p = q = 1/2, (b) p = 0.2 và q = 0.1, (c) p = 0.95 và q = 0.7. Các xác suất giới hạn
tương ứng là 1/2, 1/3 và 14/33.
Làm thế nào để hình dung về phân phối µt trong khoảng thời gian
dài? Hình 2.2 cho thấy µt có thể có một giới hạn π (giá trị phụ thuộc
vào p và q ) khi t → ∞. Bất kỳ phân phối hữu hạn π nào đều thỏa mãn
π = πP , điều đó dẫn đến
π(e) =
q
,
p+q
π(w) =
p
.
p+q
Nếu ta xác định
4t = µt (e) −
q
,
p+q
∀t ≥ 0,
thì với định nghĩa của µt+1 , dãy (4t ) thỏa mãn
4t+1 = µt (e)(1 − p) + (1 − µt (e))(q) −
q
= (1 − p − q)4t . (2.8)
p+q
Ta kết luận rằng khi 0 < p < 1 và 0 < q < 1,
lim µt (e) =
t→∞
q
,
p+q
lim µt (w) =
t→∞
p
,
p+q
(2.9)
đối với mọi phân phối ban đầu bất kì. Như vậy, µt tiến tới π khi t → ∞.
- Xem thêm -