Các mô hình mạng 6

Chia sẻ: Thi Sms | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

41
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'các mô hình mạng 6', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các mô hình mạng 6

q00π0 + q10π1 + q20π2 +... = 0, q01π0 + q11π1 + q21π2 +... = 0, q02π0 + q12π1 + q22π2 +... = 0, .... Do tính ch t ñ c bi t, như ñã phân tích trên, c a ma tr n cư ng ñ Q c a quá trình sinh−t , h trên ñư c vi t m t cách tư ng minh hơn như sau: −λ0π0 + µ1π1 +... = 0, λ0π0 − (λ1 + µ1)π1 + µ2π2 +... = 0, λ1π1 − (λ2 + µ2)π2 + µ3π3 +... = 0, ... T ñây ñ dàng tìm ñư c πn+1 = (λn/µn+1)πn, ∀n = 1, 2, 3,... ñ ñi t i công th c tính πi,∀i. π1 = (λ0/µ1)π0, π2 = (λ1/µ2)π1 = (λ1λ0/µ2µ1)π0, π3 = (λ2/µ3)π2 = (λ2λ1/µ3µ2)π1 = (λ2λ1λ0/µ3µ2µ1)π0, ... πn+1 = (λn/µn+1)πn =... = (λnλn−1... λ0/µn+1µn... µ1)π0, ... ∞ ∑π = 1, cu i cùng ta có: V i ñi u ki n i i =0 ∞ ∑ π0 = 1/(1 + (λkλk−1... λ0/µk+1µk... µ1)). k =0 ð c bi t khi µn = 0, ∀n thì quá trình sinh−t tr thành quá trình sinh thu n khi t (pure birth process). Quá trình sinh thu n khi t v i λn = λ là quá trình Poát−xông v i tham s λ. Ví d 2: Gi s dòng khách hàng ñ n mua vé m t văn phòng bán vé v i M qu y ph c v là dòng Poát−xông v i tham s λ = 6 khách hàng/1 phút (ñi u này cũng có nghĩa là khách hàng ñ n phòng bán vé v i các th i ñi m ñ n tuân theo lu t phân ph i mũ v i tham s λ = 6). Ngoài ra, còn bi t nguyên t c ph c v là FCFS (First come first served) và th i gian ph c v t i m i qu y có lu t phân ph i mũ v i kì v ng 1/3 (phút). C n tr l i hai câu h i sau ñây: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........150
− S qu y hàng t i thi u là bao nhiêu ñ hàng ch không tr nên dài vô h n? − Gi s Nt là s khách hàng ñang ch hay ñang ñư c ph c v t i th i ñi m t. Ch n M = 4 và m t khách hàng s ch ñ ñư c ph c v n u Nt ≤ 4, ch v i xác su t 0,5 n u Nt = 5 và s b ñi n u Nt = 6. Hãy xác ñ nh phân ph i d ng c a quá trình này? Trư c h t, trong ví d này chúng ta có m t quá trình sinh−t v i không gian tr ng thái S = {S0, S1, S2,..., Sn,...}, trong ñó Sn là tr ng thái trong văn phòng có n khách hàng. Các cư ng ñ chuy n là λk = 6 v i k = 0, 1, 2,... còn µk = 3k v i k ≤ M và µk = 3M v i k > M. ði u này là do bi n c c ti u c a các bi n n g u n hiên v i p hân ph i mũ ñ c l p cũng có phân ph i mũ v i t ham s b n g t ng các tham s c a các phân ph i mũ t ươ ng n g. Th t v y, gi s X = M in {X1, X2} v i X1 và X2 t uân theo phân ph i mũ ñ c l p v i các tham s µ1 và µ2, th t hì P(X ≥ t ) = P(X1 ≥ t ) P(X2 ≥ t ) = e−µ1t e −µ2t = e− (µ1 +µ2 )t . Do ñ ó X có phân ph i mũ v i tham s µ = µ1 + µ2. Do λk/µk+1 = 6/3M < 1 (khi k ≥ M) nên v i M ≥ 3 thì: ∞ ∑ (λ k λ k −1...λ 0 / µ k +1µ k ...µ1 ) < ∞. k=0 B i v y hàng ñ i s không dài vô h n (n u trái l i, khi chu i phân kì thì π0 = π1 = π2 = ... = 0, nên s khách trong hàng ñ i s d n t i m t s h u h n khi t → ∞ v i xác su t b ng 0). Trong câu h i th hai, ta có λ0 = λ1 = λ2 = λ3 = λ4 = 6, λ5 = 3. Theo công th c tính 5 π0 = 1/(1+ ∑ (λ k λ k −1...λ 0 / µ k +1µ k ...µ1 )) ta có ngay π0 = 12/89. T ñó tính ra π1 = 24/89, k=0 π2 = 24/89, π3 = 16/89, π4 = 8/89, π5 = 4/89 và π6 = 1/89. 3. MÔ PH NG XÍCH MARKOV 3.1. Mô ph ng xích Markov th i gian r i r c Phương pháp 1 Xích Markov r i r c và thu n nh t còn có th ñư c kí hi u là X0, X1, X2,... Gi s không gian tr ng thái là S g m h u h n tr ng thái: S = {0, 1, 2,..., N} và ma tr n xác su t chuy n tr ng thái ñã ñư c bi t là P = [pij]N × N. Chúng ta s mô ph ng xích Markov r i r c và thu n nh t thông qua ví d ñã trình bày các m c 1.2 và 2.1 c a chương này. Ta có phân ph i ban ñ u là: X0 1 2 3 Π(0) π1 (0) = 0,2 π2 (0) = 0,5 π3 (0) = 0,3
ð mô ph ng X0 ta áp d ng phương pháp mô ph ng phân ph i r i r c ñã h c chương III. Trên máy tính, ta phát sinh ra m t s ng u nhiên r = RANDOM[0,1) theo lu t phân ph i ñ u U[0,1) trong [0,1). N u r ≤ 0,2 ta l y X0 = 1; n u 0,2 < r ≤ 0,7 thì ta l y X0 = 2 ; còn n u r > 0,7 thì ñ t X0 = 3. Căn c k t qu mô ph ng X0, ta mô ph ng X1 d a trên ma tr n xác su t chuy n tr ng thái: 0,8 0,1 0,1  P = 0,07 0,9 0,03 .   0,083 0,067 0,85   Gi s ñã bi t X0 = 2, lúc ñó ta c n mô ph ng bi n ng u nhiên X1 căn c phân ph i sau: X1 1 2 3 Xác su t tương ng p21 = 0,07 p22 = 0,9 p23 = 0,03 ði u này có th ñư c th c hi n tương t như khi mô ph ng X0. C n chú ý r ng, trong hàng th hai c a b ng trên ta có phân ph i xác su t có ñi u ki n c a X1 v i ñi u ki n X0 = 2. Các bư c ti p theo mô ph ng X2, X3,... ñư c ti n hành tương t (cho t i X500 ch ng h n). L p l i quy trình này b t ñ u t X0 cho m t s bư c l p L ñ l n (ch ng h n 1000 l n), ta s có m t b 1000 s li u cho X500. T ñó, có th tìm ñư c b ng phân ph i t n su t (còn g i là xác su t th c nghi m) c a X500 qua thí nghi m mô ph ng trên ñây ñ i v i X500. Như v y, ta tìm ñư c véc tơ phân ph i (xác su t th c nghi m) Π(500). Cu i cùng, chúng ta có k t qu tìm g n ñúng phân ph i d ng là: Π ≈ Π(500). Chú ý: − Trong ví d trên ñây, ta th y có th dùng mô ph ng ñ tìm phân ph i d ng. Tuy nhiên, m c ñích ch y u c a phương pháp 1 là nh m mô ph ng các xích Markov r i r c thu n nh t, là các quá trình có th x y ra trong các h th ng ph c t p. − Khi không gian tr ng thái S g m m t s l n các tr ng thái thì phương pháp mô ph ng trên yêu c u th i gian ch y máy tính khá l n. ð kh c ph c ñi u này, chúng ta xem xét phương pháp 2 sau ñây. Phương pháp 2 Xét m t h th ng kĩ thu t ñư c bi u di n b i xích Markov r i r c thu n nh t {Xt}, t = 0, 1, 2,... v i không gian tr ng thái S có N tr ng thái (N khá l n) và ma tr n chuy n tr ng thái P = [pij]N × N. Xét th i ñi m n, t i th i ñi m này gi s ñã mô ph ng ñư c Xn = s. Ta s mô ph ng th i gian Tn là th i gian t i l n nh y ti p theo s m nh t mà Xt+Tn ≠ s. Do xích Markov là r i r c nên Tn ch có th nh n các giá tr 1, 2,... ð t p = pss, d th y Tn có phân ph i hình h c như sau: Tn 1 2 ... k ... Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........152
(1−p)pk−1 1−p (1−p)p Xác su t ... ... tương ng Mô ph ng phân ph i này ta tìm ñư c giá tr Tn. Còn Xn+Tn có phân ph i xác su t như sau: Xn+Tn 1 2 ... s ... N ps1/(1−pss) ps2 /(1−pss) psN/(1−pss) ... 0 ... Xác su t tương ng Cách mô ph ng này s ti t ki m hơn th i gian ch y máy tính (khi N khá l n), nhưng vi c l p trình s ph c t p hơn ít nhi u. Xét ví d như ñã trình bày trên, n u dùng phương pháp 2, m t cách hoàn toàn tương t , chúng ta cũng tìm ñư c phân ph i d ng Π(*) ≈ Π(500). 3.2. Mô ph ng xích Markov th i gian liên t c Xét xích Markov th i gian liên t c {X(t)}t∈[0, ∞). Gi s r ng xích ñi vào tr ng thái i t i th i ñi m nào ñó, ch ng h n th i ñi m 0 và không r i kh i tr ng thái này cho ñ n th i ñi m s. Lúc ñó, do tính “không nh ” c a quá trình Markov, xác su t ñ xích v n ti p t c nguyên tr ng thái ñó cho t i th i ñi m (t + s) s là: P{(Ti > s + t )/(Ti > s)} = P{Ti > t} trong ñó Ti là th i gian quá trình d ng l i tr ng thái i. D th y, n u Ti có phân ph i mũ v i hàm phân ph i F(Ti < τ) = 1 - e−λτ thì ñ ng th c trên ñư c tho mãn. ði u ngư c l i cũng có th ch ng minh ñư c. V y Ti có phân ph i mũ. T nh n xét trên, ta có th ñưa ra m t ñ nh nghĩa khác cho xích Markov th i gian liên t c. Xích Markov th i gian liên t c là m t quá trình ng u nhiên có các tính ch t sau m i khi nó ñi vào tr ng thái i: − Lư ng th i gian Ti xích d ng l i t i tr ng thái i trư c khi nó chuy n sang tr ng thái khác là m t bi n ng u nhiên v i phân ph i mũ có tham s vi (hay có kì v ng 1/vi). − M t khi quá trình r i kh i tr ng thái i, nó s ñi vào tr ng thái j nào ñó (ñ c l p v i Ti) v i các xác su t pij tho mãn ∑ pij = 1, pii = 0, ∀i . j V y ñ mô ph ng xích Markov th i gian liên t c, chúng ta c n mô ph ng dãy τ0, τ1, τ2,... (các lư ng th i gian τr xích d ng l i t i tr ng thái Jr trư c khi nó chuy n sang tr ng thái khác) và dãy J0, J1, J2,... (các tr ng thái mà xích chuy n ñ n). ð phát sinh τr, như trên ñã nói, ta c n bi t tham s vJr c a phân ph i mũ tương ng. Còn ñ phát sinh tr ng thái xích Markov chuy n ñ n Jr ∀r, chúng ta có b ng phân ph i xác su t sau: Tr ng thái ñ n 1 2 ... i ... N
Xác su t tương ng pi1 pi2 ... 0 ... piN Trong b ng trên, i =Jr -1 là tr ng thái c a xích t i bư c r − 1 (v i các xác su t pij tho mãn ∑ pij = 1,pii = 0, ∀i ). j ð th c hi n mô ph ng xích Markov th i gian liên t c, có th s d ng s li u c a ví d ñã xét trong m c 2.4 hay 2.5. BÀI T P CHƯƠNG V 1. Ch s tiêu th ñi n là m t lư ng ng u nhiên có phân ph i t i th i ñi m ban ñ u như sau: X0 Dư i 50 s 50 t i 100 100 t i 150 Trên 150 Tl% 5% 40% 40% 15% Bi t ma tr n xác su t chuy n tr ng thái là: 0,85 0,10 0,05 0  0,05 0,85 0,08 0,02 P=   0,02 0,03 0,90 0,05   0,05 0,05 0,10 0,80  − Hãy gi i thích ý nghĩa c a ma tr n P. − Tìm phân ph i d ng c a xích Markov th i gian r i r c trên ñây và cho bi t ý nghĩa c a k t qu thu ñư c. 2. M t ch trang tr i tr ng hoa hàng năm th c hi n phân tích thành ph n ñ t c a trang tr i. K t qu phân tích ñưa ra ñ t thu c vào m t trong ba tr ng thái: t t, bình thư ng và x u. Các kh o sát th ng kê cho bi t các ma tr n xác su t chuy n tr ng thái (sau m t năm) trong các trư ng h p không bón phân và có bón phân (h u cơ) như sau: 0, 2 0,5 0, 3  0,3 0, 6 0,1   0 0,5 0,5 và P =  0,1 0, 6 0,3  . P1 =     2 0 1  0, 05 0, 4 0, 55 0     Các ma tr n l i nhu n/năm (ñơn v tính là 10 ngàn USD) tương ng v i các ma tr n xác su t chuy n tr ng thái trên là:  6 5 −1  7 6 3  0 5 1 và R = 7 4 0  . R1 =     2  0 0 −1  6 3 −2      Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........154
Ch trang tr i c n l a ch n chính sách t t nh t trong s tám chính sách sau: không bón phân trong b t c trư ng h p nào, luôn bón phân trong m i trư ng h p, ch bón phân cho ñ t tr ng thái 1, ch bón phân cho ñ t tr ng thái 2, ch bón phân cho ñ t tr ng thái 3, bón phân m t khi ñ t vào tr ng thái 1 ho c 2, bón phân m t khi ñ t vào tr ng thái 1 ho c 2, bón phân m t khi ñ t vào tr ng thái 1 ho c 2. Các ma tr n xác su t chuy n tr ng thái và l i nhu n tương ng v i hai chính sách ñ u tiên chính là các ma tr n P1, R1 và P2, R2. Các ma tr n xác su t chuy n tr ng thái khác có th d dàng xác ñ nh ñư c, ch ng h n tương ng v i chính sách “ch bón phân cho ñ t tr ng thái 3” là các ma tr n sau:  2 0, 5 0,3   7 6 3  0 0, 5 0,5  và R =  0 5 1  . P5 =     5  6 3 −2  0,5 0, 4 0,55     Hư ng d n: V i m i m t trong tám chính sách trên hãy tìm véc tơ phân ph i d ng Π = [π1, π2, π3]. Sau ñó tìm vi là kì v ng l i nhu n/năm n u k t qu phân tích cho bi t ñ t tr ng thái i, ∀ i = 1, 2, 3. Ch ng h n ng v i P5 và R5 ta có v2 = 0×0 + 0,5×0,5 + 0,5×1 = 0,75. Cu i cùng c n tính kì v ng l i nhu n c a chính sách theo công th c: E = π1×v1 + π2×v2 + π3×v3. So sánh các kì v ng l i nhu n này ñ l a ch n chính sách t t nh t. Trong trư ng h p các ma tr n xác su t chuy n tr ng thái và l i nhu n có c N r t l n, có th thi t l p mô hình quy ho ch tuy n tính ñ l a ch n chính sách t t nh t trong s 2N chính sách. 3. M t h t v t lí (ban ñ u t i g c O) chuy n ñ ng trên tr c s Ox v i quy t c: m i bư c chuy n d ch (r t nhanh) m t cách ng u nhiên sang bên ph i ho c bên trái m t ñơn v v i xác su t p = 0,5 và 1−p = 0,5. − Hãy tính xác su t sau 4 bư c, h t n m t i v trí x = 4. − Hãy tính xác su t h t n m v trí trên sau m t th i gian ñ dài. 4. Trong bài t p này chúng ta nghiên c u Lu t Hardy − Weinberg trong Di truy n h c. Xét m t qu n th g m các cá th có c p gene m t trong các ki u AA, aa và Aa. Gi s th h ban ñ u t l các ki u c p gene ñó là p, q và r (v i p + q + r = 1). − Ch ng minh r ng khi ch n m t cá th b t kì th h th nh t và ch n b t kì m t trong hai gene (n m trong c p gene AA, aa ho c Aa), xác su t ñ có gene A là p + r/2, ñ có gene a là q + r/2. − T ñó hãy tìm t l các cá th có c p gene AA, aa, Aa t i th h th 2. − Ch ng minh r ng v i trong câu h i ñ u tiên, n u chúng ta thay c m t “ th h th nh t” b ng c m t “ th h th hai” hay “ th h th n” thì các xác su t c n tính v n không thay ñ i (Lu t Hardy − Weinberg). − Xét m t cá th c1 th h th nh t v i tr ng thái gene là X1 (có th nh n các giá tr AA, aa và Aa v i các xác su t p, q và r). G i X2 là tr ng thái gene c a c2 là con c a
c1, X3 là tr ng thái gene c a c3 là con c a c2... Hãy tìm véc tơ phân ph i gi i h n c a xích Markov {Xn} trên và cho bi t ý nghĩa c a nó. 5. Cho Xn là m t xích Markov v i không gian tr ng thái S = {1, 2, 3,...} và ma tr n xác su t chuy n tr ng thái: 1 / 2 ... 0 0 1/ 2 3 / 4 ... 1/ 4 0 0 P=   0 ... 0 1/ 8 7/8    ... ... ... ... ... Hãy tìm véc tơ phân ph i b t bi n Π = [π1, π2, π3, π4,...] sao cho Π × P = Π. Chú ý: ð tính π0 c n áp d ng phương pháp tính g n ñúng. 6. Cho {Xt}t ≥ 0 là m t xích Markov v i ma tr n cư ng ñ sau ñây:  −1 0 1 0 1 0 −3 2 Q=   0 1 −2 1   −1 0 0 1 Hãy tìm phân ph i gi i h n cho xích Markov trên ñây. 7. M t h th ng d ch v kĩ thu t có hai kênh. Gi s r ng th i gian ph c v tín hi u ñ n c a hai kênh này có phân ph i mũ ñ c l p v i nhau v i kì v ng là 20 (giây), t c là µ = 1/20, khi trong h th ng không có quá hai tín hi u. N u trong h th ng có t ba tín hi u tr lên thì µ = 1/30. Ngoài ra cũng gi s r ng dòng tín hi u ñ n là dòng Poát−xông v i tham s λ = 1/10 khi h th ng có ít hơn ba tín hi u và λ = 1/30 n u h th ng có t ba tín hi u tr lên. Tìm phân ph i gi i h n c a xích Markov Xt. 8. Xét xích Markov th i gian r i r c thu n nh t v i không gian tr ng thái S0, S1, S2, S3, S4, S5. Gi s qua kh o sát các m u th ng kê ñã bi t ñư c ma tr n xác su t chuy n tr ng thái (sau m i ñơn v th i gian, có th là phút, tu n, năm, th h …) như sau: 1 0 0 0 0 0 0 0 1 0 0 0    0, 01 0 0 0,8 0,19 0 P=   0  0, 03 0 0 0, 76 0, 21  0, 09 0,17  0 0 0 0, 74   0,19 0 0,81 0 0 0 Hãy tr l i các câu h i sau: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........156
− Các tr ng thái nào là tr ng thái h p th , các tr ng thái nào là tr ng thái truy n ng? Hãy tìm xác su t ñ quá trình b h p th vào m i m t tr ng thái h p th khi quá trình xu t phát t m t trong các tr ng thái truy n ng. − Tìm th i gian trung bình (kì v ng th i gian) t lúc quá trình xu t phát (t m t tr ng thái truy n ng nào ñó) cho t i khi b h p th . − Tính th i gian trung bình quá trình rơi vào m t tr ng thái truy n ng ñã ch n nào ñó trư c khi nó rơi vào tr ng thái h p th . Hư ng d n: Xem l i m c 2.3. C n chú ý r ng, v n ñ như mô t trong bài t p này có th phát sinh trong nhi u lĩnh v c như trong h th ng kĩ thu t ñi n − ñi n t , kinh t nông nghi p (chuy n d ch các lo i hình s d ng ñ t, quy mô s d ng ñ t, hay kinh t h ), sinh h c (chuy n d ch t n s gene qua các th h ), xã h i h c và nhi u lĩnh v c khác... 9. Bi t dòng khách hàng ñ n mua vé m t văn phòng bán vé v i M qu y ph c v là dòng Poát−xông v i tham s λ = 5 khách hàng/1. Ngoài ra, còn bi t nguyên t c ph c v là FCFS (First come first served) và th i gian ph c v t i m i qu y có lu t phân ph i mũ v i kì v ng 1/3 (phút). Hãy tr l i hai câu h i sau: − S qu y hàng t i thi u là bao nhiêu ñ hàng ch không tr nên dài vô h n? − Gi s Nt là s khách hàng ñang ch hay ñang ñư c ph c v t i th i ñi m t. Ch n M = 3 và m t khách hàng s ch ñ ñư c ph c v n u Nt ≤ 4, ch v i xác su t 0,5 n u Nt = 5 và s b ñi n u Nt = 6. Hãy xác ñ nh phân ph i d ng c a quá trình này? 10. Hãy phát bi u thu t gi i ñ mô ph ng xích Markov trong các ví d ñư c trình bày t i các m c 2.4 và 2.5. 11. ð d báo v m t ch s ng u nhiên CK các chuyên gia ñưa ra các m c giá tr có th x y như sau: 10, 11, 12, 13 và 14. Gi s nhóm các chuyên gia g m chuyên gia 1, 2, 3, 4, 5 th o lu n và m i chuyên gia ñ u ñưa ra phân ph i xác su t cho CK l n lư t như sau: F1 = (0,1 0,2 0,4 0,1 0,2)T, F2 = (0,2 0,3 0,3 0,1 0,1)T, F3 = (0,1 0,3 0,4 0,1 0,1)T, F4 = (0,3 0,1 0,3 0,1 0,2)T, F5 = (0,2 0,2 0,3 0,1 0,2)T. Xét ma tr n P các tr ng s : 0, 2 0,1 0, 2 0, 5 0   0, 2 0, 4 0, 2 0,1 0,1  P = 0, 3 0  = [pij]5×5. 0,3 0,3 0,1   0,1 0, 4  0,3 0, 2 0   0,1 0, 2  0, 2 0,1 0, 4   Ph n t pij trong ma tr n trên là tr ng s mà chuyên gia th i gán cho chuyên gia th j. Ch ng h n chuyên gia 1 t gán cho mình tr ng s 0,5 còn cho các chuyên gia 2, 3, 4 và 5 l n lư t là 0,2, 0,1, 0,2 và 0. Như v y, sau bư c ch nh s a th nh t căn c ma
tr n P, ý ki n các chuyên gia s là: Fi(1) = P × Fi , v i i =1, 2, 3, 4, 5. Tương t có th tìm ñư c ý ki n các chuyên gia sau khi ch nh s a l n 2, 3,..., n. G i F(n) và F là các ma tr n g m các c t Fi(1) , ∀i = 1,5 và Fi, ∀i = 1,5 . − Hãy ch ng minh: F( n) = P n × F . − Ch ng minh r ng ý ki n th ng nh t cu i cùng (v phân ph i xác su t c a CK) s 5 tìm ñư c sau nhi u l n s a ch nh ñư c cho b i: F∗ = ∑ πi Fi v i Π = [π1, π2, π3, π4, π5] i =1 là véc tơ phân ph i b t bi n tho mãn Π = P×Π. 12. Mô hình xích Markov nhi u (Noisy Markov Chain). Trong bài t p d ng lí thuy t này chúng ta s xét m t ví d ñơn gi n v Mô hình Markov n (Hidden Markov Model − HMM). C n chú ý r ng Mô hình Markov n có r t nhi u ng d ng r ng rãi trong Công ngh thông tin (nh n d ng văn b n, ch vi t, ti ng nói…) và Tin sinh h c. Chúng ta xem xét xích Markov Xn = X(n), n = 0, 1, 2,... v i không gian tr ng thái S = {0, 1}, v i véc tơ phân ph i ban ñ u là Π(0) = [π1(0), π2(0)] và ma tr n xác su t chuy n tr ng thái: 1 − p p A=   = [aij]2×2.  p 1 − p Xích Markov trên có th ñư c n trong m t quá trình ng u nhiên khác (không nh t thi t là m t quá trình Markov như trong ví d này) là Yn = Y(n), n = 0, 1, 2,... v i không gian tr ng thái O = {0, 1} = {o1, o2} thông qua ma tr n xác su t nh (emission matrix): 1 − ε ε B=   = [bjk]2×2.  ε 1 − ε Trong ñó, các ph n t bjk c a ma tr n B ñư c ñ nh nghĩa b i: bjk = P[Yn = ok/Xn = j]. Ngoài ra, B ph i tho mãn ñi u ki n: n P[Y0 = o0,..., Yn = on/X0 = j0,..., Xn = jn, B] = ∏ b jr r . r =0 ði u này có nghĩa là, các tín hi u phát ra Y0 = o0,..., Yn = on là ñ c l p có ñi u ki n (conditionally independent) t c là ñ c l p v i ñi u ki n ma tr n B ñã cho và dãy các tr ng thái c a c a xích Markov là ñã bi t. Xích Markov n như mô t trên ñây có th ñư c minh ho như sau: Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........158
p 1− p 1− p 0 1 p o 0 1 o 0 1 b(o/1) ε 1−ε b(o/0) 1−ε ε Ý nghĩa c a mô hình trên: Trong m t kênh truy n tin các tín hi u ñư c truy n ñi dư i d ng nh phân 0 ho c 1. T i m i th i ñi m n, tín hi u ñư c kí hi u b i Xn. Tuy nhiên do nhi u trong kênh truy n tin, chúng ta có xác su t quan sát sai tín hi u là ε. Lúc ñó tín hi u quan sát ñư c t i th i ñi m n là Yn v i các xác su t nh là: P[Yn = 0/Xn = 0] = 1 − ε, P[Yn = 1/Xn = 0] = ε, P[Yn = 0/Xn = 1] = ε, P[Yn = 1/Xn = 1] = 1 − ε. D dàng th y: Yn = Xn +2 Vn v i {Vn} là quá trình Bernoulli v i xác su t thành công trong m i phép th là ε, cũng như Xn+1 = Xn +2 Wn v i {Wn} là quá trình Bernoulli v i xác su t thành công trong m i phép th là p, ñ c l p ñ i v i {Vn} ( ñây +2 là phép c ng s nguyên theo mod 2). Tóm l i, ta nói m t Mô hình Markov n là m t b năm y u t : m t xích Markov {Xn} n trong m t quá trình ng u nhiên {Yn} v i ñi u ki n véc tơ phân ph i ban ñ u là Π(0), ma tr n xác su t chuy n tr ng thái (sau m t bư c) A c a xích Markov n và ma tr n xác su t nh B ñã bi t. Xét mô hình HMM trong bài t p này, trong ñó Π(0) = [ 0,5; 0,5], p = 0,6 và ε = 0,1, hãy tr l i các câu h i sau ñây: − Tìm P[Y0 = 1, Y1 = 0, Y2 = 1/X0 = 0, X1 = 0, X2 = 1 ]. − Tìm P[Y1 = 1, Y2 = 0, Y3 = 1/X1 = 0, X2 = 0, X3 = 1 ]. − Tìm công th c tính t ng quát P[Y0 = o0,..., Yn = on/X0 = j0,..., Xn = jn]. − Tìm P[Y0 = 1, Y1 = 0, Y2 = 1, X0 = 0, X1 = 0, X2 = 1 ]. j∗ ,..., j* sao cho xác su t P[Y0 = o0,..., Yn = on, X0 = j0,..., Xn = jn] − Tìm các ch s 0 n ñ t giá tr l n nh t (ñây là Bài toán gi i mã trong Lí thuy t truy n tin và cũng là Bài toán kh p chu i gene trong Tin sinh h c, có th gi i b ng Thu t toán Viterbi).
Chương VI M TS MÔ HÌNH RA QUY T ð NH VÀ NG D NG 1. RA QUY T ð NH TRONG MÔI TRƯ NG B T ð NH 1.1. M t s khái ni m cơ b n Các quy t ñ nh là m t ph n quan tr ng th m xuyên ñ i s ng c a chúng ta. Kh năng ñưa ra ñư c l a ch n hay ñưa ra ñư c quy t ñ nh c a mình chính là b n ch t c a con ngư i. Trong Khoa h c qu n lí, ra quy t ñ nh là trách nhi m then ch t c a b máy ñi u hành. Tuy nhiên trong t t c các ho t ñ ng, con ngư i ñ u c n ph i ra quy t ñ nh d a trên các ñi u ki n ràng bu c và tình hình th c t khách quan cũng như các nh n th c ch quan ñ tìm ra các hành ñ ng hay các phương án h p lí nh t trong vi c khai thác, s d ng các ngu n d tr hi n có nh m ñáp ng các m c tiêu ñ t ra. Trong m t tình hu ng nào ñó, ñ ñưa ra ñư c m t quy t ñ nh t t hay m t quy t ñ nh có hi u qu luôn c n thi t ti n hành phân tích kĩ lư ng trư c khi lên k ho ch ti n trình hành ñ ng. Vì v y, m t s câu h i ñư c ñ t ra là: Th nào là m t quy t ñ nh t t, vi c ñưa ra m t quy t ñ nh t t c n tuân theo các bư c nào hay d a trên phương pháp nào, các y u t c u thành c a m t quy trình ra quy t ñ nh h p lí là gì? Phương pháp ra quy t ñ nh ph thu c vào môi trư ng mà trong ñó chúng ta ph i ñưa ra quy t ñ nh. Trư c h t, c n th y r ng h u qu c a m i hành ñ ng không ch ph thu c vào chính hành ñ ng ñó mà còn ph thu c vào hàng lo t các y u t bên ngoài. Các y u t như v y thư ng không th ki m soát ñư c và chúng ñư c mô t thông qua các tình tr ng/các tr ng thái (State of Nature) ñư c coi là có th x y ra. Ph thu c vào s tr ng thái có th x y ra, các môi trư ng ra quy t ñ nh ñư c phân lo i như sau: - Môi trư ng ch c ch n hay môi trư ng n ñ nh (Certainty Environment), trong ñó ch c ch n s x y ra m t và ch m t tr ng thái và do ñó h u qu c a m i hành ñ ng ñ u có th d báo m t cách ch c ch n. - Môi trư ng không ch c ch n hay môi trư ng b t ñ nh (Uncertainty Environment), trong ñó có th x y ra nhi u tr ng thái và do ñó h u qu c a m i hành ñ ng ñ u không th th d báo m t cách ch c ch n. Môi trư ng b t ñ nh l i ñư c chia ra thành môi trư ng b t ñ nh nghiêm ng t và môi trư ng r i ro. Môi trư ng b t ñ nh nghiêm ng t (Strict Uncertainty Environment), là môi trư ng b t ñ nh mà trong ñó chúng ta không bi t ñư c thông tin v các xác su t ñ các tr ng thái x y ra. Tuy nhiên, n u thông tin v các xác su t ñ các tr ng thái x y ra ñư c bi t thì môi trư ng b t ñ nh ñư c g i là môi trư ng r i ro (Risk Environment). Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........160