Quá trình ngẫu nhiên – xích markov
I. KHÁI NIỆM QUÁ TRÌNH NGẪẪU NHIÊN...................................................................2
1. Sơ lược vềề quá trình ngẫẫu nhiền.......................................................................2
2. Khái niệm quá trình ngẫẫu nhiền........................................................................2
3. Phẫn loại quá trình ngẫẫu nhiền..........................................................................3
3.1 Phân loại theo tập thời gian T......................................................................3
3.2 Phân loại theo tập không gian trạng thái E..................................................3
II. XÍCH MARKOV.......................................................................................................3
1. Định nghĩa:.........................................................................................................3
2. Xích Markov rời rạc và thuẫền nhẫất....................................................................5
2.1 Bài toán ví dụ...............................................................................................5
2.2 Ma trận xác suất chuyển 1 bước..................................................................5
2.3 Ma trận xác suất chuyển sau n bước............................................................6
2.4 Phương trình Chapmam-Kolmogorov:........................................................6
2.5 Các tính chất của ma trận chuyển trạng thái................................................7
2.6 Phân phối ban đầu........................................................................................7
2.7 Phân phối dừng:...........................................................................................8
2.8 Phân loại trạng thái xích Markov...............................................................10
KÊẾT LUẬN.................................................................................................................13
III. LẬP TRÌNH CHUYỂN BÀI TOÁN ĐỐI NGẪU..................................................13
1. Giao diện & Cách sử dụng:.................................................................................13
2. Mã lập trình.......................................................................................................15
TÀI LIÊU THAM KHẢO...............................................................................................23
Quá trình ngẫu nhiên – Xích Markov
I. KHÁI NIỆM QUÁ TRÌNH NGẪẪU NHIÊN
1. Sơ lược vềề quá trình ngẫẫu nhiền
Các hiện tượng diễn ra trong tự nhiên, xã hội hoặc có tính chất tất định (có tính
quy luật, có thể biết trước kết quả) hoặc có tính chất ngẫu nhiên (không biết trước kết
quả). Mặc dù không thể nói trước một hiện tượng ngẫu nhiên xảy ra hay không xảy ra khi
thực hiện một lần quan sát, tuy nhiên nếu tiến hành quan sát nhiều lần một hiện tượng
ngẫu nhiên trong các phép thử như nhau, ta có thể đánh giá được khả năng xuất hiện của
các biến cố tương ứng và rút ra được những kết luận khoa học về hiện tượng này. Lý
thuyết xác suất nghiên cứu khả năng xuất hiện của các hiện tượng ngẫu nhiên và ứng
dụng chúng vào thực tế. Trong học phần xác suất và thống kê chúng ta đã tìm hiểu khái
niệm biến ngẫu nhiên, đó là các biến nhận giá trị nào đó phụ thuộc vào các yếu tố ngẫu
nhiên. Khi họ các biến ngẫu nhiên phụ thuộc vào thời gian ta có quá trình ngẫu nhiên.
Quá trình ngẫu nhiên cung cấp những mô hình hữu ích để nghiên cứu nhiều lĩnh vực khác
nhau như vật lý thống kê, viễn thông, điều khiển, phân tích chuỗi thời gian, sự tăng
trưởng dân số và các ngành khoa học quản lý. Các tín hiệu video, tín hiệu thoại, dữ liệu
máy tính, nhiễu của một hệ thống viễn thông, nhiễu điện trong các thiết bị điện, số khách
hàng đến một điểm phục vụ, chỉ số chứng khoán trong thị trường chứng khoán… là các
quá trình ngẫu nhiên. Quá trình ngẫu nhiên có nhiều ứng dụng trong viễn thông là quá
trình Markov (quá trình không nhớ, memoryless) và quá trình dừng.
2. Khái niệm quá trình ngẫẫu nhiền
Xét một hệ thống vật lý (hay một hệ thống sinh thái, hệ thống dịch vụ,… ) tiến
triển theo thời gian. Gọi X(t) là vị trí (tình trạng) của hệ tại thời điểm t. Như vậy ứng với
mỗi thời điểm t, X(t) chính là một biến ngẫu nhiên mô tả vị trí (tình trạng) của hệ thống.
Quá trình {X(t), t∈T} được gọi là một quá trình ngẫu nhiên.
Tập T là tập chỉ thời gian và do đó ta coi X(t) là trạng thái của quá trình thời gian t.
Tập hợp các vị trí có thể có của X(t) gọi là không gian trạng thái. Kí hiệu là E.
Ví dụ 1.1: khi gieo con xúc sắc, gọi X(t) là biến ngẫu nhiên chỉ trạng thái của con
xúc sắc ở lần gieo t. Như vậy, X(t) chỉ có thể nhận giá trị là 1 trong 6 mặt của con xúc
sắc. Do đó, ta có không gian trạng thái là E = {1, 2, 3, 4, 5, 6}.
Tóm lại: Một quá trình ngẫu nhiên là một tập hợp các biến ngẫu nhiên dùng mô tả
sự tiến triển của một quá trình nào đó theo thời gian.
Ví dụ 1.2: Trong một khu phố 1000 dân (khách hàng) có 3 siêu thị là A, B, và C (A,
B, C được coi là các vị trí 1, 2, 3 của hệ thống siêu thị này). Giả sử rằng, trong từng
tháng mỗi khách hàng luôn trung thành với một siêu thị. Ngoài ra, cũng giả sử rằng trong
1
Quá trình ngẫu nhiên – Xích Markov
tháng đầu số khách vào các siêu thị lần lượt là 200, 500 và 300; tức là có 20% khách
hàng vào siêu thị A, 50% vào B và 30% vào C.
Để mô tả tình trạng phân chia thị phần trong tháng đầu (tháng 0) của hệ thống
siêu thị trên, chúng ta thiết lập biến ngẫu nhiên X(0) với quy tắc: nếu khách hàng
mua hàng ở siêu thị A thì đặt X(0)=1, ở siêu thị B thì đặt X(0) = 2, còn ở siêu thị C
thì X(0) = 3. Lúc đó, X(0) có bảng phân phối xác suất sau:
Để mô tả tình trạng phân chia thị phần trong các tháng tiếp theo, chẳng hạn,
tháng = 1, 2, 3,… vị trí của hệ thống sẽ được mô tả bởi các biến ngẫu nhiên X(1),
X(2), X(3),… với các bảng phân phối xác suất tương ứng.
Ta xây dựng được quá trình ngẫu nhiên { X(0), X(1), X(2), …} để mô tả tình trạng
phân chia thị phần của hệ thống siêu thị trên.
3. Phẫn loại quá trình ngẫẫu nhiền
3.1 Phân loại theo tập thời gian T
Xét quá trình ngẫu nhiên { X(t), t ∈ T }:
Nếu T là tập con của tập số nguyên (T
⊂Z
) thì quá trình
{ X(t), t ∈ T } được gọi là quá trình rời rạc theo thời gian. Trường hợp này ta ký
hiệu Xn thay cho X(t) và gọi là một dãy ngẫu nhiên. Theo ví dụ 1.2, ta cho t là các
tháng 0, 1,… thì tập T = { 0, 1, 2, 3, 4, 5, …} là tập rời rạc.
Nếu T = [0; ∞ ) thì quá trình {X(t); t ∈ T} được gọi là quá trình liên tục theo
thời gian.
3.2 Phân loại theo tập không gian tr ạng thái E
Ta ký hiệu E là tập tất cả các giá trị của X(t), ⊂t ⊂ T và gọi là không gian trạng
thái của quá trình, mỗi giá trị của X(t) được gọi là một trạng thái.
Nếu E là tập đếm được thì { X(t), t ∈ T } gọi là quá trình có trạng thái rời rạc.
Nếu E là 1 khoảng của tập số thực R thì { X(t), t ∈ T } được gọi là quá
trình thực hoặc quá trình trạng thái liên tục.
Nếu E tập con của tập số phức C thì { X(t), t ∈ T } là quá trình trạng thái
phức.
Nếu E ⊂ Rk thì { X(t), t ∈ T } là quá trình trạng thái k-véc tơ.
2
Quá trình ngẫu nhiên – Xích Markov
II. XÍCH MARKOV
1. Định nghĩa:
Giả thiết ta 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 đó. 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, kí hiệu là E. Giả sử trước thời điểm s hệ ở trạng thái
nào đó. Còn tại thời điểm s (hiện tại) hệ có trạng thái i. Ta cần biết tại thời điểm t trong
tương lai (t >s) hệ có trạng thái j với xác suất là bao nhiêu?
Nếu xác suất này chỉ phụ thuộc vào s, i, t, j, 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.
Về phương diện toán học, tính Markov có thể định nghĩa như sau:
Ta nói rằng X(t) có tính Markov nếu:
P { X(tn+1} = j | X(t0) = i0, … , X(tn-1) = in-1, X(tn) = i}
= P{X(tn+1} = j | X(tn) = i}
với t0 < t1 < … < tn < tn+1 < … và i0 , i1 , … , in-1 , i, j ∈ E
Ta xem tn là hiện tại, tn+1 là tương lai và t0 , t1 , … , tn-1 là quá khứ. Vì thế, biểu thức
trên chính là tính Markov của X(t). E gọi là không gian trạng thái của X(t).
Một số ví dụ về tính Markov:
Ví dụ 2.1: Nếu gọi X(t) là dân số nước ta tại thời điểm t (trong tương lai) thì 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ứ. Như vậy, X(t) có tính
Markov.
Ví dụ 2.2: Xét quá trình chơi bài của một người nào đó, nếu gọi X(t) là số tiền của
người đó tại thời điểm t (ván bài thứ t) thì có thể xem X(t) chỉ phụ thuộc vào số tiền của
người đó ở ván bài thứ t-1 và không phụ thuộc vào X(t-2), X(t-3),… là bao nhiêu. Như
vậy, ta nói X(t) có tính Markov.
Nói chung, các hệ sinh thái không có trí nhớ là những hệ có tính Markov.
Nếu E đánh số được (đếm được) thì quá trình { X(t), t ∈ T } được gọi là xích
Markov. Lúc này, có thể kí hiệu E = {1, 2, 3,...}, tức là các trạng thái được đánh số.
Nếu tập các giá trị t đếm được (chẳng hạn, t = 0, 1, 2,... ) thì ta có xích Markov với
thời gian rời rạc, hay xích Markov rời rạc.
Nếu t ⊂ [0, ∞ ) thì ta có xích Markov với thời gian liên tục, hay xích Markov
liên tục.
Đặt p(s, i, t, j) = P( X(t) = j | X(s) = i ). Đó 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ế, ta gọi
p(s, i, t, j) là xác suất chuyển của hệ (hay quá trình).
Nếu xác suất chuyển chỉ phụ thuộc vào (t – s), tức là:
3
Quá trình ngẫu nhiên – Xích Markov
p (s, i, t, j) = p (s+h, i, t+h, j) , ⊂ s, ⊂ i, ⊂ t, ⊂ j, ⊂ h 0 thì ta nói hệ là
thuần nhất theo thời gian.
Trong phần sau, ta chỉ xét xích Markov rời rạc và thuần nhất.
4
Quá trình ngẫu nhiên – Xích Markov
2. Xích Markov rời rạc và thuẫền nhẫất
2.1 Bài toán ví dụ
Ví dụ 2.3: Trong một khu phố 1000 dân (khách hàng) có 3 siêu thị là A, B, và C
(A, B, C được coi là các vị trí 1, 2, 3 của hệ thống siêu thị này). Giả sử rằng, trong từng
tháng mỗi khách hàng luôn trung thành với một siêu thị. Ngoài ra, cũng giả sử rằng trong
tháng đầu số khách vào các siêu thị lần lượt là 200, 500 và 300; tức là có 20% khách hàng
vào siêu thị A, 50% vào B và 30% vào C.
Để mô tả tình trạng phân chia thị phần trong tháng đầu (tháng 0) của hệ thống siêu
thị trên, chúng ta thiết lập biến ngẫu nhiên X(0) với quy tắc: nếu khách hàng mua hàng ở
siêu thị A thì đặt X(0)=1, ở siêu thị B thì đặt X(0) = 2, còn ở siêu thị C thì X(0) = 3. Lúc
đó, X(0) có bảng phân phối xác suất sau:
Các giá trị X(0)
1
2
3
Xác suất tương ứng
0,2
0,5
0,3
Để mô tả tình trạng phân chia thị phần trong các tháng tiếp theo, chẳng hạn,
tháng = 1, 2, 3,… vị trí của hệ thống sẽ được mô tả bởi các biến ngẫu nhiên X(1), X(2),
X(3),… với các bảng phân phối xác suất tương ứng.
Ta xây dựng được quá trình { X(t), t = {1, 2, …} để mô tả tình trạng phân chia thị
phần của hệ thống siêu thị trên.
Những tháng sau, ta giả sử:
Xác suất để một người khách, đã vào mua hàng ở siêu thị A tháng trước, vào lại A
trong tháng sau luôn là 0,8; chuyển sang mua hàng ở B luôn là 0,1 và chuyển sang
C luôn là 0,1.
Xác suất để một người khách, đã vào mua hàng ở siêu thị B tháng trước chuyển
sang A luôn là 0,07; vào lại B luôn là 0,9 và chuyển sang C luôn là 0,03.
Xác suất để một người khách, đã vào siêu thị C tháng trước chuyển sang A luôn là
0,083; chuyển sang B luôn là 0,067 và vào lại C luôn là 0,85.
Yêu cầu:
1. Cho biết xác suất để một khách hàng trong tháng đầu mua ở siêu thị A sau 2 tháng
sẽ chuyển sang mua ở siêu thị B là bao nhiêu?
2. Cho biết tỉ lệ phần trăm số khách hàng vào các siêu thị A, B, C sẽ thay đổi cho đến
tháng thứ mấy thì ổn định (thay đổi không đáng kể)?
5
Quá trình ngẫu nhiên – Xích Markov
2.2 Ma trận xác suâất chuyển 1 bước
Giả sử (Xt) , t = 0, 1, 2, … là xích Markov rời rạc và thuần nhất. Khi đó tính
Markov và tính thuần nhất của (Xt) có nghĩa là:
pij = P { X(tn+1} = j | X(t0) = i0, … , X(tn-1) = in-1, X(tn) = i}.
Ma trận P(1) = pij (với i,j ∈E) gọi là ma trận xác suất chuyển 1 bước.
Ý nghĩa: pij là xác suất có điều kiện để hệ tại thời điểm t n (hiện tại) ở trạng thái i
chuyển sang trạng thái j tại thời điểm tn+1.
Ma trận chuyển 1 bước có dạng:
P
1
pij
p 00
p 10
...
pi 0
…
p 01
p 11
…
pi 1
…
p 02
p 12
…
pi 2
…
…
…
…
…
…
Xét lại ví dụ 2.3, dựa vào định nghĩa ma trận chuyển một bước ta được:
p 11 =0.8 . Nghĩa là sau 1 tháng cửa hàng A (đặt là 1) khách hàng tiếp tục vào lại
A là 0.8.
p 12 =0.1 . Nghĩa là sau 1 tháng khách hàng của hàng A (đặt là 1) chuyển sang
cửa hàng B (đặt là 2) là 0.1
p 13 =0.1 . Nghĩa là sau 1 tháng khách hàng của hàng A (đặt là 1) chuyển sang
cửa hàng C (đặt là 3) là 0.1
Làm tương tự ta được: p 21 =0.07, p 22 =0.9, p 23 = 0.03, p 31 =0.083, p 32
=0.067, p 33 =0.85. Vậy ta được ma trận chuyển như sau.
Ρ
p11
p 21
p 31
p 12
p 22
p 32
p13
p23
p33
=
0.8
0.1
0.1
0.07
0.9 0.03
0.083 0.067 0.85
=
p
ij
3x3
2.3 Ma trận xác suâất chuyển sau n bước.
Ma trận xác suất chuyển n bước có được định nghĩa theo công thức.
p n = P(Xn+m = j|Xm = i) = P(Xn = j|X0 = i)
ij
Ma trận P(n) =
n
p ij
(với i,j ∈E) gọi là ma trận xác suất chuyển n bước.
Ý nghĩa: p n là xác suất có điều kiện để hệ tại thời điểm ban đầu ở trạng thái
ij
i, sau n bước chuyển sang trạng thái j.
6
Quá trình ngẫu nhiên – Xích Markov
2.4 Phương trình Chapmam-Kolmogorov:
Ta đã biết các xác suất truyền 1 bước là pij và các xác suất truyền n bước là
n
p ij
. Từ đó ta có các phương trình sau:
n 1
p ij
=
∑
k⊂E
pik p n
kj
p n 1 =
ij
n m
Tổng quát:
p ij
(n)
=
∑
p n p kj
ik
∑
p n p m
ik
kj
k⊂E
k⊂E
(m)
Ý nghĩa: Pik Pkj là xác suất có điều kiện để xuất phát từ trạng thái i quá trình sẽ
chuyển đến trạng thái k sau n bước, rồi chuyển đến trạng thái j sau m bước. Từ đó nếu lấy
tổng các xác suất có điều kiện này với mọi trạng thái k có thể có (k=0, 1, 2,...) ta sẽ được
xác suất Pij(n+m) .
Theo ví dụ 2.3, hỏi xác suất để một khách hàng trong tháng đầu mua ở siêu thị A
sau 2 tháng sẽ chuyển sang mua ở siêu thị B là bao nhiêu? Nghĩa là, tính p12(2).
Áp dụng phương trình Chapmam-Kolmogorov ta có:
p12(2) = P(X(2) = 2 | X(0) = 1)
3
=
∑ p1k p12
1
k
k 1
= p11(1)p12(1)+ p12(1)p22(1)+ p13(1)p32(1)
= 0.8 x 0.1 + 0.1 x 0.9 + 0.1 x 0.067 = 0.1767
2.5 Các tính châất của ma trận chuyển tr ạng thái
Giả sử ta có ma trận chuyển một bước là P và ma trận chuyển n bước là P (n). Từ đó,
ta có các tính chất sau:
P(n +1) = P. P(n)
P(n +1) = P(n).P
P(n+m) = P(n). P(m)
Từ đó suy ra: P(n)=Pn
Áp dụng các tính chất trên, tính p12(2) của ví dụ 2.3:
0,8
0,1 0,1
0,8
0,1 0,1
0,6553
0,1767
0,0915
P P . P 0,07 0,9 0,03 x 0,07 0,9 0,03 0,12149 0,81901 0,03655
0,083 0,067 0,85
0,083 0,067 0,85
0,078145 0,074295 0,017535
2
(2)
Ta dễ dàng nhận thấy p12 = 0,1767
7
Quá trình ngẫu nhiên – Xích Markov
2.6 Phân phôấi ban đâầu.
Định nghĩa: Giả sử tại thời điểm t = n, X(n) cũng có thể nhận một trong N giá trị
1, 2,…, N với các xác suất tương ứng là 1(n), 2(n),… N(n) (với 1(n)+ 2(n)+… N(n) = 1) thì
vectơ (n) = [1(n), 2(n),… N(n)] được gọi là vectơ phân phối tại thời điểm t = n. Công
thức tổng quát như sau. (n) = P n = P(Xn =j); n=0,1,2..; j ∈ E
j
Với n = 0 ta có vectơ phân phối ban đầu (0) = [1(0), 2(0),… N(0)]
Các công thức dưới dạng ma trận:
Π (n) = Π . P(n)
Π (n+1) = Π (n). P
Π (n+1) = Π (1) . P(n)
Π (n+m) = Π (n) . P(m)
8
Quá trình ngẫu nhiên – Xích Markov
Áp dụng cho ví dụ 2.3:
-
Kí hiệu P[X(0) = 1] = 1(0), P[X(0) = 2] = 2(0), P[X(0) = 3] = 3(0), thì véctơ
(0)=[ 1(0), 2(0), 3(0)] = [0,2 0,5 0,3] được gọi là véctơ phân phối xác
-
suất tại thời điểm t = 0 hay véc tơ phân phối ban đầu.
Sau 1 tháng kể từ thời điểm ban đầu, xác suất tỉ lệ khách hàng vào các cửa hàng
là:
0,8 0,1 0,1
∏ ∏ x P 0,2 0,5 0,3 x 0,07 0,9 0,03
0,083 0,067 0,85
0,2199 0,4901 0,2900
1
0
-
Tương tự sau 2 tháng tỉ lệ xác suất khách vào các cửa hàng là
0,8
0,1
0,1
∏ ∏ x P 0,2199 0,4901 0,2900 x 0,07 0,9 0,03
0,083 0,067 0,85
0,234297 0,48251 0,283193
1
2
2.7 Phân phôấi dừng:
a) Định lý ergodic:
Tính ergodic: Xích Markov được gọi là tính ergodic theo nghĩa sau: tồn tại
lim pnij không phụ thuộc vào i sao cho: i > 0,
giới hạn j =
∑∏ j
j ϵE
n→∞
⊂ jϵE,
= 1.
Giả sử P = [pij] là ma trận xác suất chuyển của xích Markov (X n) có không
gian trạng thái hữu hạn E={1,2,…,N}.
n 0
p ij
• Nếu P chính quy theo nghĩa sau: tồn tại n 0 sao cho minij
>0 thì
tồn tại các số 1,…, n sao cho j > 0,
n
lim pij
n→∞
•
j ϵE
= 1 và mỗi j ϵ E thì
= ∏j
Ngược lại , nếu tồn tại các số ∏1,…, ∏n
∏j >0,
∑
∑∏j
j ϵE
= 1 và với mỗi j ϵ E,
∑∏j
j ϵE
minij p n 0 >0 , tức là mà trận chính quy.
ij
9
thỏa mãn các điều kiện
= 1 thì sẽ tồn tại n0 thỏa mãn
Quá trình ngẫu nhiên – Xích Markov
•
Các số 1,…, n là nghiệm của hệ phương trình j =
p
∑ ∏ k kj
đó là nghiệm duy nhất thỏa mãn điều kiện j > 0 , Vj ϵ E ,
nếu ma trận P là chính quy.
10
, j ϵ E và
k ϵE
∑∏j
j ϵE
=1
Quá trình ngẫu nhiên – Xích Markov
b) Định nghĩa:
•
Nghiệm ko âm (∏1,…, ∏n) của phương trình ∏j =
∑∏j
j ϵE
•
p
∑ ∏ k kj
k ϵE
sao cho
= 1 được gọi là phân phối dừng (hay bất biến) của xích Markov
với ma trận xác suất chuyển P = [pij].
Viết dưới dạng ma trận thì phân phối dừng là vector cột bất biến đối với ma
trận chuyển vị của P, tức là:
p11
p12
…
p1N
p 21
p 22
…
p2 N
…
…
…
…
p N1
π1
pN 2 . π 2
…
⊂
p NN
πN
π1
π2
⊂
πN
=
Xét lại ví dụ 2.3: Để dự đoán sự phân chia thị trường trong tương lai sẽ cân
bằng như thế nào ta tìm phân phối dừng. Xét ma trận:
P =
0.8
0.1
0.1
0.07
0.9 0.03
0.083 0.067 0.85
Theo định lý ergodic, ta có ma trận trên là chính quý vì minij
Vậy ta có phương trình sau ∏j =
p
∑ π k kj
k ϵE
n 0
p ij
>0
, vậy ta có hệ phương trình sau:
Giải hệ trên ta có ∏ = [ 0,272 0,455 0,273] là phân phối dừng, tức là trong
tương lai:
- Cửa hàng 1 sẽ có lượng khách ổn định là 272.
- Cửa hàng 2 sẽ có lượng khách ổn định là 455.
- Cửa hàng 3 sẽ có lượng khách ổn định là 273.
Thán
g
A
B
C
1
0.2199
0.4901
0.29
2
0.234297
0.48251
0.283193
3
0.244718
0.47666263
0.2786190
11
Quá trình ngẫu nhiên – Xích Markov
Thán
g
A
3
B
C
1
5
4
0.252266
4
0.47213567
6
0.2755979
5
0.257737
3
0.46861381
0.2736489
3
6
0.261705
6
0.46586063
3
0.2724337
3
7
0.264586
8
0.46369819
4
0.2717150
5
8
0.266680
6
0.46199195
8
0.2713274
2
9
0.268204
1
0.46063976
2
0.2711561
3
10
0.269314
0.45956365
7
0.2711223
1
11
0.270123
8
0.45870389
0.2711722
8
12
0.270715
6
0.45801442
6
0.2712699
4
13
0.271148
9
0.45745963
3
0.2713914
4
14
0.271466
8
0.45701178
9
0.2715214
1
15
0.271700
5
0.45664922
5
0.2716502
3
16
0.271872
9
0.45635492
2
0.2717722
3
17
0.272000
2
0.45611545
4
0.2718843
3
18
0.272094
7
0.45592018
1
0.2719851
6
19
0.272164
0.45576063
0.2720744
12
Quá trình ngẫu nhiên – Xích Markov
Thán
g
A
B
9
C
4
6
20
0.272217
3
0.45563005
0.2721526
21
0.272256
6
0.45552300
4
0.2722203
5
Tỉ lệ phần trăm khách hàng vào các siêu thị
2.8 Phân loại trạng thái xích Markov
a) Trạng thái liên thông: Ta nói rằng trạng thái j đạt được từ trạng thái i nếu tồn
tại n>=0 sao cho pij(n) >0 .Ký hiệu i → j.Hai trạng thái được gọi là liên thông với nhau
nếu i → j và j → i. Và kí hiệu là i ⊂ j.
Các tính chất:
i ⊂ i vì pii(0) = 1 (theo quy ước).
i ⊂ j thì j ⊂ i.
i ⊂ j và j ⊂ k thì i ⊂ k
Xích Markov tối giản: xích Markov được gọi là tối giản nếu hai trạng thái bất kỳ
của nó liên thông với nhau.
Ví dụ: Cho xích Markov với ma trận xác suất chuyển
Ta có:
p 13 = ½ > 0 và
p 14 = ½ > 0 và
p 23 = ½ > 0 và
p 24 = ½ > 0 và
p 31 = ½ > 0 nên 1 ⊂ 3
p 41 = ½ > 0 nên 1 ⊂ 4
p 32 = ½ > 0 nên 2 ⊂ 3
p 42 = ½ > 0 nên 2 ⊂ 4
Xích có 4 trạng thái E = {1, 2, 3, 4} và hai trạng thái bất kỳ của nó là liên thông
với nhau. Vậy, đây là xích tối giản.
a) Trạng thái hồi quy và không hồi quy
13
Quá trình ngẫu nhiên – Xích Markov
Mở đầu: Giả sử (Xn) là xích Markov . Xét trạng thái cố định i ϵ E, ta đặt
fij(n) =P{Xn =j,X1 ≠j,…, Xn ≠j/ X0 =i}, jϵ E.
Ý nghĩa: fij(n ) là xác suất để hệ xuất phát từ i lần đầu tiên chuyển sang trạng
thái j tại thời điểm n. Và fii(n) là xác suất để hệ xuất phát từ i lần đầu tiên trở về i tại thời
điểm n.
n
Công thức:
p
n
ij
=
∑
f kj pin− k
i
j
k 0
Định nghĩa: Trạng thái i được gọi là hồi quy nếu fii = 1 , Trạng thái i được gọi là
trạng thái không hồi quy nếu fii <1.
Ý nghĩa: Theo định nghĩa thì i là hồi quy nếu và chỉ nếu hệ xuất phát từ i,
với xác suất 1 hệ trở lại i tại thời điểm hữu hạn nào đó. Trạng thái i là không hồi quy có
nghĩa biến cố hệ xuất phát từ i trở lại i ít nhất một lần có xác suất bằng fii <1
Trạng thái hồi quy dương và trạng thái hồi quy không.
Trong trường hợp i là hồi quy ta đặt µi =
∞
∑ n f inj ,
đó là thời gian trung
k 0
bình để hệ trở lại i. Trạng thái i là trạng thái dươi nếu µ i < ∞, trạn thái i là
trạng thái không nếu µi = ∞.
Ý nghĩa: Trạng thái i là trạng thái dương có nghĩa là thời gian chờ đợi để hệ
xuất phát từ i trở về i là hữu hạn,trong khi đó thời gian nay bằng ∞ nếu i là trạng thái 0.
Tiêu chuẩn hồi quy và không hồi quy.
∞
-
Trạng thái i là hồi quy khi và chỉ khi
∑
p n = ∞ và i không hồi
ii
n 1
∞
quy khi và chỉ khi
∑
p n ∞
ii
n 1
-
Nếu i → j và hồi quy thì j → i và j cũng hồi quy.
Nếu i ⊂ j và j hồi quy nếu fij=1
14
Quá trình ngẫu nhiên – Xích Markov
Ví dụ: Cho xích Markov với không gian trạng thái E={0,1,2,3} VÀ ma trận xắc
suất chuyển.
Trạng thái 2 và 3 của xích đã cho là hồi quy hay không hồi quy?
Giải
∞
- Xét trạng thái 2. Theo định lý trên ta cần tính
∑
p n , ta tính được
22
1
p22
n 1
=1/4,
p
2
22
2
= (1/4) ,....,
p
n
22
= (1/4)
n.
Do đó ta có.
∞
∑
p n
22
= 1/4 + (1/4)2
+ ...+ (1/4)n = 1/4/(1-1/4)=1/3 < ∞, suy ra 2 là
n 1
trạng thái không hồi quy.
∞
- Xét trạng thái 3: Theo định lý trên ta cần tính
∑
p n , ta có thể tinhd dược
33
n 1
p
1
33
=1,
p
2
33
= 1 ,....,
p
n
33
= 1, do đó ta có.
∞
∑
p n = 1+1+...+1=∞ , suy ra 3 là trạng thái hồi quy.
33
n 1
KÊẾT LUẬN
Trong bài báo cáo này, chúng tôi giới thiệu những khái niệm nhập môn về quá
trình ngẫu nhiên và xích Markov với thời gian rời rạc thuần nhất và ứng dụng của lý
thuyết này trong một vài bài toán thuộc lĩnh vực kinh tế.
Còn rất nhiều vấn đề cần tìm hiểu về Markov và các mô hình ứng dụng có thể đi
đến được những kết quả đẹp về mặt lý thuyết hoặc những kết quả có ý nghĩa thực tế ( áp
dụng được một cách thuận tiện trong thực tế ).
Nhiều mô hình ngẫu nhiên trong Kinh tế, Kĩ thuật, Lý thuyết nhận dạng, Vận trù
học, Dân số học, Di truyền học,... được tiếp cận nghiên cứu có thể dựa trên cơ sở là quá
trình Markov.
III. LẬP TRÌNH CHUYỂN BÀI TOÁN ĐỐI NGẪU.
1. Giao diện & cách sử dụng.
15
Quá trình ngẫu nhiên – Xích Markov
Diễn giải.
Số 1: Nhập tổng số biến của bài toán.
Số 2: Nhập hệ số hàm mục tiêu, cuối cùng hoàn thành chọn nút “Add”.
Số 3: Nhập tổng số ràng buộc.
Số 4: Nhập cac hệ số ràng buộc, xong nhấn nút “Add”.
Số 5: Nhập ràng buộc biến, xong nhấn nút “Add”.
Số 6: Sau khi nhập xong, sẽ ra bài toàn ban đầu.
Số 7: Bài toán đối ngẫu chuyển.
Số 8: Sau khi nhận nút này, sẽ cho kết quả bài toàn chuyển.
2. Mã lập trình.
using
using
using
using
using
using
using
using
System;
System.Collections.Generic;
System.ComponentModel;
System.Data;
System.Drawing;
System.Linq;
System.Text;
System.Windows.Forms;
16
Quá trình ngẫu nhiên – Xích Markov
namespace nhom5
{
public partial class Form1 : Form
{
int n,m,i=1,j=1,k=1,t=1;// lưu trữ số
int[] a = new int[20];
int[,] b = new int [10,10];
int[] c = new int[20];
string[] str = new string[10];
string[] strbien = new string[10];
string strminmax,str2,str3,str5,str6,str7;
public Form1()
{
InitializeComponent();
}
private void txtbien_KeyPress(object sender, KeyPressEventArgs e)
{
if (e.KeyChar == 13)
{
n = Convert.ToInt32(txtbien.Text);
}
if (i < n)
{
label3.Text = label3.Text + "" + "X" + i+ "" + "=";
}
private void txthammuctieu_KeyPress(object sender,KeyPressEventArgs e)
{
if (e.KeyChar == 13)
{
if (i <= n)
{
a[i] = Convert.ToInt32(txthammuctieu.Text.Trim());
txthammuctieu.Text = "";
label3.Text = "Hàm mục tiêu:";
label3.Text = label3.Text + "" + "X" + i + "" + "=";
i++;
}
}
}
private void btnadd_Click(object sender, EventArgs e)
{
string str1;
if (cmdchon.Text != "")
{
strminmax = cmdchon.Text;
for (int j = 1; j <= n; j++)
17
Quá trình ngẫu nhiên – Xích Markov
{
if (a[j] > 0)
{
if (j < n)
{
str1 = a[j].ToString() + "*" + "X" + j + "" + "+";
str2 = str2 + str1;
}
else
{
str1 = a[j].ToString() + "*" + "X" + j + "";
str2 = str2 + str1;
}
}
else
{
if (j < n)
{
str1 = a[j].ToString() + "*" + "X" + j + "" + "-";
str2 = str2 + str1;
}
else
{
}
str1 = a[j].ToString() + "*" + "X" + j + "";
str2 = str2 + str1;
}
}
str2 = str2 + "=>" + cmdchon.Text;
rtxbandau.Text = str2+"\n";
}
else MessageBox.Show("Chưa chọn giá trị Min/Max");
}
private void txtsorangbuoc_KeyPress(object sender,KeyPressEventArgs e)
{
if (e.KeyChar == 13)
{
m = Convert.ToInt32(txtsorangbuoc.Text);
if (j < m)
{
label6.Text = label6.Text + j + "X" + k + "";
}
}
}
18
Quá trình ngẫu nhiên – Xích Markov
private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
{
if (e.KeyChar == 13)
{
m = Convert.ToInt32(txtsorangbuoc.Text);
if (j < m+1)
{
if (k < n + 1)
{
label6.Text = "";
label6.Text = "Ràng buộc";
label6.Text = label6.Text + j + "X" + k + "";
b[j, k] = Convert.ToInt32(textBox1.Text.Trim());
textBox1.Text = "";
k++;
}
else
{
MessageBox.Show("Đã nhập
theo");
}
ràng
buộc+"+j+
""+"nhận
Add
nhập
ràngbuộctiếp
}
}
}
private void btnrangbuoc_Click(object sender, EventArgs e)
{
string str1;
if (cmdrangbuoc.Text != "")
str[j] = cmdrangbuoc.Text;
else MessageBox.Show("Chưa chọn dấu ràng buộc");
if (txtgiatrirangbuoc.Text != "")
c[j] = Convert.ToInt32(txtgiatrirangbuoc.Text);
else MessageBox.Show("Chưa chọn giá trị ràng buộc");
k = 1;
while (k < n + 1)
{
if (b[j, k] > 0)
{
if (k < n)
{
str1 = b[j, k].ToString() + "*" + "X" + k + "" + "+";
str3 = str3 + str1;
k++;
}
else
{
19