Chương 6. Sơ lược về qua trình ngẫu nhiên và xích Markov | Học viện phụ nữ Việt Namất thống kê

Chương6.Sơlượcvềquatrìnhngẫunhiên v
 àxíchMarkov Ch−¬ng 6
S¬ l−îc vÒ qu¸ tr×nh ngÉu nhiªn vμ xÝch Markov
i. kh¸i niÖm vÒ qu¸ tr×nh ngÉu nhiªn
Mét qu¸ tr×nh ngÉu nhiªn {X(t), t∈T} lµ mét tËp hîp c¸c biÕn ngÉu nhiªn
X(t), cã nghÜa lµ mét t∈T th× X(t) lµ mét biªn ngÉu nhiªn.
ChØ sè t th−êng lµ chØ thêi gian vµ do ®ã ta coi X(t) nh− lµ tr¹ng th¸i cña
qu¸ tr×nh thêi gian t. Ch¼ng h¹n ta cã thÓ coi X(t) lµ
a. Tæng sè kh¸ch hµng ®· vµo mét siªu thÞ trong kho¶ng thêi gian t.
b. Tæng sè kh¸ch hµng b−íc vµo mét siªu thÞ ë thêi ®iÓm t.
c. Tæng sè doanh thu cña mét siªu thÞ trong kho¶ng thêi gian t. .................
TËp hîp T ®−îc gäi lµ tËp chØ sè cña qu¸ tr×nh ngÉu nhiªn ®−îc gäi lµ
qu¸ tr×nh rêi r¹c theo thêi gian.
NÕu T lµ mét kho¶ng ®−êng th¼ng thùc th× qu¸ tr×nh ngÉu nhiªn ®−îc gäi
lµ qu¸ tr×nh liªn tôc theo thêi gian. ThÝ dô:
a. {X , n = 0, 1, 2,....} lµ mét qu¸ tr×nh ngÉu nhiªn rêi r¹c víi tËp chØ sè n
lµ nh÷ng sè nguyªn kh«ng ©m. Lê ă
V nPhong‐TrầnTrọngNguyên,ĐHKTQD 238
Chương6.Sơlượcvềquatrìnhngẫunhiên v
 àxíchMarkov
b. {X(t), t ≥ 0} lµ mét qu¸ tr×nh ngÉu nhiªn liªn tôc theo thêi gian mµ tËp
chØ sè lµ c¸c sè thùc kh«ng ©m.
TËp hîp tÊt c¶ c¸c gi¸ trÞ cã thÓ cã mµ c¸c biÕn ngÉu nhiªn X(t) cã thÓ
nhËn sÏ ®−îc gäi lµ k«ng gian c¸c tr¹ng th¸i.
Tãm l¹i: Mét qu¸ tr×nh ngÉu nhiªn lµ mét hÖ 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 (lµ chñ yÕu).
ii. kh¸i niÖm vÒ xÝch markov 1. Chó ý më ®Çu
Sau ®©y ta dÏ xÐt mét qu¸ tr×nh ngÉu nhiªn {X , n = 0, 1, 2,....} víi mét n
tËp h÷u h¹n hoÆc ®Õm ®−îc c¸c gi¸ trÞ cã thÓ cã.
NÕu kh«ng cã chó thÝch g× kh¸c th× tËp hîp c¸c gi¸ trÞ cã thÓ cã cña qu¸
tr×nh (kh«ng gian c¸c tr¹ng th¸i) còng sÏ ®−îc ký hiÖu lµ tËp hîp c¸c sè
nguyªn kh«ng ©m {0,1, 2, 3,...}.
NÕu X =i th× ta b¶o t¹i thêi ®iÓm n qu¸ tr×nh ë voµ tr¹ng th¸i i. n
2. §Þnh nghÜa vÒ xÝch Markov
Qu¸ tr×nh ngÉu nhiªn {X } ®−îc gäi lµ mét xÝch Markov nÕu n P(X = j X = i ,X = i ,......., X = i , X = i ) = P(X = j X = i ) n+1 0 0 1 1 n−1 n−1 n n n+1 n
víi mäi (n, i, j, i , i ,......, i ) 0 1 n-1
ý nghÜa: §iÒu kiÖn nªu trong ®Þnh nghÜa muèn nãi r»ng x¸c suÊt cã ®iÒu kiÖn
cña tr¹ng th¸i t−¬ng lai X khi biÕt c¸c tr¹ng th¸i qu¸ khø X , X n+1 0 ρ, ...., Xn-1
vµ tr¹ng th¸i hiÖn t¹i X th× chØ phô thuéc vµo tr¹ng th¸i hiÖn t¹i X mµ th«i. n n
Ghi chó 1: NÕu ký hiÖu P(X
=j⎮X =i) lµ P th× P gäi lµ x¸c suÊt truyÒn n+1 n ij ij
mét b−íc. Do c¸c suÊt cña mäi biÕn cè ®Òu kh«ng ©m vµ do qu¸ tr×nh thÓ nµo
còng ph¶i ë voµ mét tr¹ng th¸i nµo ®ã nªn ta cã: Lê ă
V nPhong‐TrầnTrọngNguyên,ĐHKTQD 239
Chương6.Sơlượcvềquatrìnhngẫunhiên v
 àxíchMarkov ∞ P ≥ = = ∑ ij 0, i, j ≥ 0 ; P ( 1 i , 0 , 1 ...) ij . j =0
NÕu ký hiÖu P(1) lµ ma trËn c¸c x¸c suÊt truyÒn mét b−íc th× ta cã: P P P ........ 00 01 02 P P P ........ 10 11 12
P(1) = ........ ....... ........ ......... P P P ......... i0 i1 i2
....... ........ ....... .........
Ghi chó 2: T−¬ng tù nÕu ký hiÖu P (n) lµ x¸c suÊt truyÒn n b−íc th× ta cã: ij P (n) =P(X =j⎮X =i) ij m+n m
Ghi chó 3: NÕu P kh«ng phô thuéc vµo n, tøc lµ ij
P(X =j⎮X =i)= P(X =j⎮X =i) (n = 0, 1, 2, ....) n+1 n 1 0
th× ta cã mét qu¸ tr×nh dõng.
ThÝ dô: Gi¶ sö viÖc ngµy mai trêi m−a hay n¾ng chñ phô thuéc vµo t×nh h×nh
thêi tiÕt cña ngµy h«m nay, chø kh«ng phô thuéc vµo thêi tiÕt cña nh÷ng ngµy qua.
Gi¶ sö nÕu h«m nay trêi vÉn m−a lµ α, cßn nÕu h«m nay trêi kh«ng m−a
th× x¸c suÊt ®Ó ngµy mai trêi m−a lµ β.
NÕu ta ký hiÖu tr¹ng th¸i 0 lµ “trêi m−a” vµ tr¹ng th¸i 1 lµ “trêi kh«ng
m−a” th× ta cã thÓ m« t¶ t×nh h×nh thêi tiÕt nh− võa nªu trªn b»ng mét xÝch
Markov cã 2 tr¹ng th¸i víi ma trËn cña x¸c suÊt truyÒn mét b−íc nh− sau: Lê ă
V nPhong‐TrầnTrọngNguyên,ĐHKTQD 240
Chương6.Sơlượcvềquatrìnhngẫunhiên v
 àxíchMarkov P P α 1 − α P(1) = 00 01 = P P 10 11 β 1− β
iii. ph−¬ng tr×nh chapmam-kolmogorov
Ta ®· biÕt c¸c x¸c suÊt truyÒn 1 b−íc lµ P vµ c¸c x¸c suÊt truyÒn n b−íc ij
lµ P (n) vµ c¸c x¸c suÊt truyÒn n b−íc lµ P (n) tõ ®ã ta cã ph−¬ng tr×nh sau: ij ij ∞ P (n) = (m) (n-m) ij ∑ Pik Pkj k= o
ý nghÜa: P (m)P (n-m) lµ x¸c suÊt cã ®iÒu kiÖn ®Ó xuÊt ph¸t tõ tr¹ng th¸i i qu¸ ik kj
tr×nh sÏ chuyÓn ®Õn tr¹ng th¸i k sau m b−íc, råi chuyÓn ®Õn tr¹ng th¸i j sau
(n-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 P (n) . ij Chøng minh ThËt vËy, ta cã P(n) = P(X = jX = i) n ij 0 ∞ = ∑ P X ( = ,j X = k X = i) n m 0 k= 0 ∞ = ∑ P X (
= ,j X = k, X = i)P(X = k X = i) n m 0 m 0 k= 0 ∞ = ∑ P(m) − ik P(n m) kj k= 0
NhËn xÐt: NÕu m=1 vµ n=2 th× ta cã Lê ă
V nPhong‐TrầnTrọngNguyên,ĐHKTQD 241
Chương6.Sơlượcvềquatrìnhngẫunhiên v
 àxíchMarkov (2) P = P P ij ∑∞ ik kj k= 0
§©y lµ phÇn tö ë vÞ trÞ (i, j) cña ma trËn P(2). VËy P(2)= P(2). B»ng quy n¹p ta suy ra: P(n)= P(n)
Tõ ®ã ph−¬ng tr×nh Chapman-Kolmogorov cã thÓ viÕt d−íi d¹ng ma trËn nh− sau: P(n)= P(m)P(n-m) P
ThÝ dô: Ta xÐt trë l¹i thÝ dô vÒ t×nh h×nh thêi tiÕt víi 2 tr¹ng th¸i vµ ®· ®−îc
m« h×nh ho¸ bëi xÝch Markov ®· nªu trªn. Gi¶ sö α= 0,7 vµ β = 0,4. Khi ®ã
h·y tÝnh x¸c suÊt ®Ó trêi sÏ m−a 4 ngµy liÒn, biÕt r»ng h«m nay trêi m−a. Bµi gi¶i
Nh− vËy ta cã ma trËn c¸c x¸c suÊt chuyÓn mét b−íc lµ 0,7 0,3 P= 0,4 0 6 , Tõ ®ã , , , , , , 0 7 0 3 0 7 0 3 0 61 0 39 P(2)=P(2)= . = 0,4 0,6 0 4 , 0 6 , 0 52 , 0,48 0,61 0 39 , 0 61 , 0 39 , 0,5749 0,4251 ` P(4) (4) =P = . = P 0 52 , 0 48 , 0 52 , 0 48 , 0,5668 0,4332
VËy x¸c suÊt ph¶i t×m lµ P =0,5749. 00 Lê ă
V nPhong‐TrầnTrọngNguyên,ĐHKTQD 242
Chương6.Sơlượcvềquatrìnhngẫunhiên v
 àxíchMarkov
Ghi chó: Tõ ®Çu ch−¬ng tíi ®©y ta ®Òu xÐt c¸c x¸c suÊt cã ®iÒu kiÖn, ch¼ng
h¹n P (n) lµ x¸c suÊt ®Ó ë thêi ®iÓm n hÖ ë vµo tr¹ng th¸i j biÕt r»ng ë thêi ij
®iÓm o hÖ ë vµo tr¹ng th¸i i.
NÕu nh− muèn x¸c ®Þnh P(X =j) tøc lµ muèn tÝnh x¸c suÊt kh«ng ®iÒu n
kiÖn ®Ó trong t−¬ng lai (ë b−íc n) hÖ sÏ ë vµo tr¹ng th¸i j th× ta cã: Lê ă
V nPhong‐TrầnTrọngNguyên,ĐHKTQD 243
Chương6.Sơlượcvềquatrìnhngẫunhiên v
 àxíchMarkov ∞ P(X = ) j = P X ( = j X = i)P(X = i) ∑ n n 0 0 i=0 ∞ = P(n) P(X = i) ∑ ij 0 i= 0
Nh− vËy nÕu biÕt ®−îc quy luËt ph©n phèi x¸c suÊt cña tr¹ng th¸i ban ®Çu, ch¼ng h¹n P(X = i)=α víi i ≥ 0 vµ 0 i ∑∞α =1 i i=0
Th× ta cã thÓ tÝnh ®−îc: ∞ P(X = j) = P n ∑ (n α) ij i i =0
ThÝ dô: Ta xÐt trë l¹i thÝ dô vÒ t×nh h×nh thêi tiÕt. NÕu ®Çu ngµy h«m nay ta
tÝnh ®−îc x¸c suÊt trêi m−a lµ α = 0,4 vµ x¸c suÊt trêi kh«ng m−a lµ α = 0,6 0 1
th× x¸c suÊt ®Ó sau 3 h«m n÷a trêi kh«ng m−a sÏ lµ
P(X =0) = (0,4)P (4) + (0,6)P (4) 4 00 10 Trong ma trËn truyÒn P(4) (4) (4) tÝnh ë trªn ta ®· cã P = 0,5749; P = P 00 10 0,5668. V× thÕ
P(X =0) = (0,4)(0,5749) + (0,6)(0,5668) = 0,5700. 4
iV. ph©n lo¹i c¸c tr¹ng th¸i cña xÝch markov
1.Tr¹ng th¸i j gäi lµ ®Õn ®−îc tõ tr¹ng th¸i i (ký hiÖu i→j) nÕu P (n) >0 víi n ij nµo ®ã (n≥ 0).
Nh− vËy j ®Õn ®−îc tõ i khi vµ chØ khi xuÊt ph¸t tõ i thÓ nµo qu¸ tr×nh
còng cã lóc sÏ ë vµo tr¹ng th¸i j.
ThËt vËy nÕu j kh«ng ®Õn ®−îc tõ i, tøc lµ P (n) =0 víi mäi n th× ta suy ra: ij
P(Qu¸ tr×nh thÓ nµo còng ë vµo tr¹ng th¸i j ⎢XuÊt ph¸t tõ i) = ∞ ∞ ∞ P( (X = j X = i) ≤ P(X j X i) P U n i ∑ = = = n 0 ∑ (n) ij = n 0 = n 0 n= 0 Lê ă
V nPhong‐TrầnTrọngNguyên,ĐHKTQD 244
Chương6.Sơlượcvềquatrìnhngẫunhiên v
 àxíchMarkov
2. Hai tr¹ng th¸i i vµ j gäi lµ th«ng nhau (ký hiÖu i↔j) nÕu (i→j, j ← i).
Nh− vËy bÊt kú mét tr¹ng th¸i nµo còng th«ng nhau víi b¶n th©n nã v× P (0)=P(X = i⎥ X =i) = 1. ii 0 0
Ta thÊy mèi quan hÖ th«ng nhau cã 3 tÝnh chÊt sau:
a. Tr¹ng th¸i i th«ng nhau víi tr¹ng th¸i i víi mäi i ≥ 0.
b. NÕu i th«ng nhau víi j th× j còng th«ng nhau víi i.
c. NÕu i th«ng nhau víi k vµ k th«ng nhau víi j th× i th«ng víi j.
TÝnh chÊt a vµ b ®−îc suy ra tõ ®Þnh nghÜa, cßn tÝnh chÊt b¾c cÇu c cã thÓ chøng minh nh− sau:
Do i↔k vµ k ↔j nªn cã tån t¹i 2 sè nguyªn n vµ m sao cho P n) >0 vµ P (m) >0. ik kj
Tõ ®ã theo ph−¬ng tr×nh Chapman- Kolmogorov ta cã: ∞ ( + n m) P = P P P P ij ∑ (n) (m) ik kj ≥ (n) (m) ik kj ; 0 i=0
Nh− vËy j ®Õn ®−îc tõ i
Chøng minh t−¬ng tù, ta thÊy i ®Õn ®−îc tõ j. Do ®ã tÝnh chÊt c ®−îc chøng minh.
3. Hai tr¹ng th¸i th«ng nhau sÏ thuéc cïng mét líp. Tõ c¸c tÝnh chÊt trªn ta
thÊy hai líp tr¹ng th¸i nµo ®ã hoÆc lµ trïng nhau hoÆc rêi nhau. Nh− vËy
kh«ng gian c¸c tr¹ng th¸i ®−îc ph©n ho¹ch thµnh c¸c líp t−¬ng øng.
NÕu kh«ng gian c¸c tr¹ng th¸i chØ gåm mét líp t−¬ng ®−¬ng th× xÝch
Markov gäi lµ kh«ng thu gän ®−îc. Khi ®ã mäi tr¹ng th¸i ®Òu th«ng nhau víi nhau. Lê ă
V nPhong‐TrầnTrọngNguyên,ĐHKTQD 245
Chương6.Sơlượcvềquatrìnhngẫunhiên v
 àxíchMarkov
4. Ta ký hiÖu f lµ x¸c suÊt ®Ó qu¸ tr×nh b¾t ®Çu tõ tr¹ng th¸i i sÏ l¹i quay l¹i Þj i ë mét lóc nµo ®ã: Khi ®ã:
a. NÕu f =1 th× tr¹ng th¸i i gäi lµ tr¹ng th¸i lÆp. ij
b. NÕu f <1 th× tr¹ng th¸i i gäi lµ tr¹ng th¸i qu¸ ®é. ij
Ta thÊy nÕu tr¹ng th¸i i lµ l¾p th× nã sÏ ®−îc quay l¹i v« h¹n lÇn. Së dÜ
nh− vËy v× qu¸ tr×nh Markov kh«ng phô thuéc vµo qu¸ khø nªn khi ë tr¹ng
th¸i i th× x¸c suÊt quay l¹i tr¹ng th¸i i b»ng 1 vµ cø nh− vËy.... nªn i sÏ ®−îc quay l¹i v« h¹n lÇn.
NÕu i lµ tr¹ng th¸i qu¸ ®é th× ng−êi ta chøng minh ®−îc r»ng kú väng cña
sè lÇn mµ qu¸ tr×nh quay l¹i i lµ mét sè h÷u h¹n 1 1 − fii
Trªn ®©y lµ mét sè giíi thiÖu s¬ l−îc vÒ qu¸ tr×nh ngÉu nhiªn vµ xÝch
Markov. MÆc dï xuÊt ph¸t tõ lý thuyÕt x¸c suÊt, nh−ng giê ®©y lý thuyÕt vÒ
c¸c qu¸ tr×nh ngÉu nhiªn ®· trë thµnh mét ngµnh ph¸t triÓn ®éc lËp vµ cã
nhiÒu øng dông trong c¸c lÜnh vùc tù nhiªn vµ x· héi. Lê ă
V nPhong‐TrầnTrọngNguyên,ĐHKTQD 246