Giáo trình Toán học ứng dụng trong điện tử viễn thông (Phần 2) - Lê Bá Long

97 trang Gia Huy 21/05/2022 2130

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán học ứng dụng trong điện tử viễn thông (Phần 2) - Lê Bá Long", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_toan_hoc_ung_dung_trong_dien_tu_vien_thong_phan_2.pdf

Nội dung text: Giáo trình Toán học ứng dụng trong điện tử viễn thông (Phần 2) - Lê Bá Long

Chương 4: Quá trình ngẫu nhiên, chuỗi Markov CHƯƠNG IV: QUÁ TRÌNH NGẪU NHIÊN, CHUỖI MARKOV GIỚI THIỆU Hầu hết các hiện tượng xảy ra trong tự nhiên và xã hội đều cĩ tính chất ngẫu nhiên, đĩ là sự phản ánh của các mối ràng buộc phức tạp mà ta khơng biết trước được. Trong giáo trình Xác suất Thống kê chúng ta đã tìm hiểu khái niệm biến ngẫu nhiên, véc tơ 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. Lý thuyết quá trình ngẫu nhiên lần đầu tiên được nghiên cứu liên quan đến bài tốn dao động và nhiễu của các hệ vật lý. Quá trình ngẫu nhiên là một mơ hình tốn học của quá trình thực nghiệm mà sự phát triển bị chi phối bởi các quy luật xác suất. 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 khốn trong thị trường chứng khố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. Chuỗi Markov là một quá trình Markov cĩ khơng gian trạng thái rời rạc, thời gian rời rạc và thuần nhất. Chuỗi Markov thường gặp trong bài tốn chuyển mạch của hệ thống viễn thơng. Quá trình Poisson là một ví dụ về chuỗi Markov với thời gian liên tục. Quá trình Poisson X (t) mơ tả quá trình đếm số lần xuất hiện một biến cố A nào đĩ cho đến thời điểm t . Quá trình Poisson được ứng dụng nhiều trong viễn thơng, liên quan đến bài tốn truyền tín hiệu, các hệ phục vụ, bài tốn chuyển mạch Quá trình Poisson được xét trong chương 6. Tín hiệu viễn thơng, nhiễu khơng cĩ tính Markov. Các quá trình này quá khứ của nĩ cĩ ảnh hưởng lớn đến sự tiến triển của quá trình trong tương lại. Tuy nhiên hàm trung bình khơng thay đổi và hàm tương quan thuần nhất theo thời gian, đĩ là quá trình dừng. Khi các quá trình dừng biểu diễn các tín hiệu hoặc nhiễu thì biến đổi Fourier của hàm tương quan của quá trình là hàm mật độ phổ cơng suất của tín hiệu hoặc nhiễu này. Một trong những bài tốn quan trọng của lý thuyết chuyển mạch là vấn đề xung đột thơng tin, nghẽn mạch hoặc rớt cuộc gọi. Lý thuyết quá trình sắp hàng (Queueing theory) xác định và tìm các phương án tối ưu để hệ thống phục vụ tốt nhất, sẽ xét trong chương 7. Trong chương này ta chỉ nghiên cứu một cách khái quát khái niệm quá trình ngẫu nhiên và chuỗi Markov thời gian rời rạc thuần nhất. 103
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Để học tốt chương này học viên cần nắm vững khái niệm xác suất, xác suất cĩ điều kiện, cơng thức xác suất đầy đủ, biến ngẫu nhiên và các kiến thức đại số tuyến tính như ma trận, hệ phương trình tuyến tính. 4.1 KHÁI NIỆM VÀ PHÂN LOẠI QUÁ TRÌNH NGẪU NHIÊN 4.1.1 Khái niệm quá trình ngẫu nhiên Các tín hiệu của các hệ thống thơng tin là các tín hiệu ngẫu nhiên vì ngồi thành phần mang tin cịn cĩ sự tác động của giao thoa ngẫu nhiên và nhiễu của thiết bị. Giả sử một tín hiệu nào đĩ mà tại mỗi thời điểm t nhận các giá trị phụ thuộc hệ các biến cố {Ei ,i ∈ N} của phép thử. Tín hiệu này nhận giá trị là x(tE, i ) tại thời điểm t và khi biến cố Ei xảy ra. Như vậy {x(,tEi )} là một hàm mẫu của quá trình ngẫu nhiên X (t). Quá trình ngẫu nhiên X (t) vừa phụ thuộc thời gian t , vừa phụ thuộc yếu tố ngẫu nhiên Ei . x(,tE) 1 t t 2 t 1 x(,tE) 2 t1 t2 t x(,tE3) Quá trình ngẫu nhiên X (t) (t E ) t1 t2 t x(,tE4 ) t1 t t2 {x(,tE),i∈ N} {x(,tE1 i ),i∈ N} 2 i Hình 4.1: Mơ hình quá trình ngẫu nhiên Một cách tổng quát một quá trình ngẫu nhiên là một họ các biến ngẫu nhiên {Xt(,ω∈);t T} xác định trong cùng một phép thử. Các quá trình này vừa phụ thuộc vào thời gian t và khi cố định tham số t thì X (t,ω) là biến ngẫu nhiên theo ω. Các giá trị nhận được theo thời gian t được gọi là hàm mẫu hoặc một thể hiện của quá trình ngẫu nhiên. Tập chỉ số T thường biểu diễn tham số thời gian. 104
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Do tác động của các yếu tố ngẫu nhiên nên một tín hiệu {Xt(,ω∈);t T} được truyền đi là một quá trình ngẫu nhiên. Tín hiệu cụ thể nhận được là hàm mẫu (một thể hiện) của quá trình ngẫu nhiên {Xt(,ω∈);t T} . Để đơn giản trong cách viết người ta ký hiệu quá trình ngẫu nhiên {Xt();t∈T} thay cho {Xt(,ω∈);t T} , hàm mẫu tương ứng được ký hiệu {x()tt; ∈T} . 4.1.2 Phân loại quá trình ngẫu nhiên Cĩ thể phân loại các quá trình ngẫu nhiên theo các đặc trưng sau: • Khơng gian trạng thái, • Tập chỉ số thời gian T , • Quan hệ độc lập, quy luật phân bố xác suất của các biến ngẫu nhiên X (t) . 4.1.2.1 Phân loại quá trình ngẫu nhiên theo tập trạng thái E Ta ký hiệu E là tập các giá trị của X (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ì {Xt();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 thì {Xt();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 thì {Xt();t∈T} là quá trình trạng thái phức. ♦ Nếu E ⊂k thì {Xt();t∈T} là quá trình trạng thái k-véc tơ. 4.1.2.2 Phân loại quá trình ngẫu nhiên theo tập các chỉ số T Nếu T ⊂ thì quá trình {Xt();t∈T} được gọi là quá trình cĩ thời gian rời rạc hoặc tham số rời rạc. Trường hợp này ta ký hiệu X n thay cho X (t) và gọi là một dãy ngẫu nhiên. Nếu T =[0;∞) hoặc T = thì {Xt();t∈T} được gọi là quá trình cĩ thời gian liên tục. 4.1.2.3 Phân loại theo các tính chất xác suất của quá trình ngẫu nhiên Quá trình ngẫu nhiên trở thành biến ngẫu nhiên khi thời gian cố định tại thời điểm nào đĩ. Mỗi biến ngẫu nhiên cĩ các đặc trưng thống kê như kỳ vọng, phương sai, các moment các đặc trưng này nhận được từ hàm phân bố xác suất. Các hàm phân bố xác suất được xác định từ hàm mật độ xác suất (trường hợp liên tục), hoặc hàm khối lượng xác suất (trường hợp rời rạc). Hai biến ngẫu nhiên nhận được tại hai thời điểm của quá trình cĩ các đặc trưng (kỳ vọng, phương sai, hiệp phương sai ) xác định từ hàm phân bố xác suất đồng thời của hai biến ngẫu nhiên này. Tổng quát hơn, biến ngẫu nhiên N chiều nhận được tại N thời điểm cĩ các đặc trưng xác định từ hàm phân bố xác suất đồng thời của các biến ngẫu nhiên này. 105
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov a) Quá trình độc lập: Quá trình {Xt();t∈T} được gọi là quá trình độc lập nếu với mọi thời điểm t1 < t2 < < tn thì các biến ngẫu nhiên sau là độc lập X (tX12), (t), , X(tn ) (4.1) Ví dụ 4.1: Giả sử XX12, , là dãy các biến ngẫu nhiên độc lập cĩ cùng phân bố Bernoulli với xác suất PX{ n ==1} p, PX{ n ==0} q=1−p với mọi n . Khi đĩ {Xnn ,≥1} là một quá trình ngẫu nhiên gọi là quá trình Bernoulli. Quá trình Bernoulli là quá trình độc lập cĩ khơng gian trạng thái rời rạc E = {0,1} , thời gian rời rạc T = {1, 2, } . Một ví dụ về dãy mẫu của quá trình Bernoulli cĩ thể nhận được bằng cách gieo đồng xu liên tiếp. Nếu mặt sấp xuất hiện ta gán giá trị 1, nếu mặt ngửa xuất hiện ta gán giá trị 0. Chẳng hạn n 12345678910 MỈt xuÊt hiƯn SNNSSSNSSN xn 10 0111011 0 Dãy mẫu {xnn ,≥1} nhận được ở trên được minh họa trong hình sau x n 1 z z z z z z z z z z z 0 2 4 6 8 n 10 Hình 4.2: Hàm mẫu của quá trình Bernoulli b) Quá trình cĩ gia số độc lập: Quá trình {Xt();t∈T} được gọi là quá trình gia số độc lập nếu các gia số của quá trình trong các khoảng thời gian rời nhau là các biến ngẫu nhiên độc lập. Tức là với mọi cách chọn t1 < t2 < < tn thì các biến ngẫu nhiên sau là độc lập X (t2 ) − X (t1), X (t3 ) − X (t2 ), , X (tn ) − X (tn−1) . (4.2) 106
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Đặc biệt với quá trình thời gian rời rạc {X n} thì tính chất gia số độc lập dẫn đến dãy các biến ngẫu nhiên ZX00==, ZiiX−Xi−1; i=1,2, là độc lập. Ngồi ra nếu ta biết luật phân bố của từng biến ngẫu nhiên Z0 , Z1 , thì ta biết được luật phân bố của mọi Xii , = 0, 1, . Thật vậy, điều này được suy từ cách tìm phân bố xác suất của tổng các biến ngẫu nhiên độc lập và Xii= ZZ01++ +Z. c) Quá trình gia số độc lập dừng Quá trình gia số độc lập {Xt();t∈T} được gọi là quá trình gia số độc lập dừng nếu ∀ tn và với mọi a , ta cĩ PX{ (t) ≤=aX(t11) a, , X(tnn) =a} =PX{ (t) ≤aX(tn) =an} . (4.5) Nghĩa là qui luật xác suất trong tương lai chỉ phụ thuộc hiện tại và độc lập với quá khứ. Nĩi cách khác quá trình Markov mơ tả các hệ khơng cĩ trí nhớ (memoryless). Với mọi t > s; với mọi tập giá trị A ⊂ và giá trị a ta ký hiệu p(s,a;t, A) = P{X (t) ∈ A X (s) = a} (4.6) và gọi là hàm xác suất chuyển từ thời điểm s đến thời điểm t . 107
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Như vậy cơng thức (4.5) được viết lại PX{ (t) ≤=aX(t11) a, , X(tnn) =a} =p(tn,an;t, A) , trong đĩ A =−( ∞,a]. (4.7) Quá trình Markov với khơng gian trạng thái rời rạc được gọi là chuỗi Markov (hay xích Markov, Markov chains). Chuỗi Markov với thời gian rời rạc và thuần nhất được xét trong mục tiếp theo. Quy luật phân bố xác suất của biến ngẫu nhiên rời rạc được xét qua hàm khối lượng xác suất, vì vậy tính chất Markov – cơng thức (4.5) đối với chuỗi Markov {Xnn; = 0,1,2, } với thời gian rời rạc được viết lại như sau PX{ nn+10==jX i0, X1=i1, , X =i} =P{Xn+1=jXn=i}, ii01, , ,i, j∈ E. (4.8) f) Quá trình dừng (stationary) Xét quá trình ngẫu nhiên {Xt();t∈T} cĩ thời gian T = , + , hoặc ² . Nĩi một cách khái quát một quá trình ngẫu nhiên là quá trình dừng nếu các tính chất thống kê của quá trình khơng phụ thuộc thời gian Các tính chất thống kê của quá trình được xác định bởi các hàm phân bố đồng thời của quá trình tại các thời điểm. Các khái niệm dừng cụ thể phụ thuộc mức độ khơng phụ thuộc thời gian. Quá trình dừng bậc nhất nếu: với mọi h , với mọi t1 ∈T hai biến ngẫu nhiên X (t1) và X ()th1 + cĩ cùng phân bố xác suất. Quá trình dừng bậc nhất cĩ hàm trung bình là hàm hằng E(Xt)= const. Quá trình dừng bậc hai nếu: với mọi h , với mọi tt12, ∈T hai véc tơ ngẫu nhiên ( Xt()1,Xt(2)) và ( Xt()12++h,X(t h)) cĩ cùng phân bố xác suất. Hàm phân bố đồng thời của quá trình dừng bậc hai khơng phụ thuộc thời điểm mà chỉ phụ thuộc khoảng cách giữa hai thời điểm (bằng cách chọn h= −t1 ). Quá trình dừng bậc hai cũng là quá trình dừng bậc nhất vì hàm phân bố thành phần được xác định từ hàm phân bố đồng thời. Do đĩ E(Xt)= const ⎡ ⎤ E(⎣X tX+τ)(t)⎦ chỉ phụ thuộc τ . trong đĩ X (t) là số phức liên hợp của số phức X (t) Dựa vào kết quả này, ta mở rộng khái niệm dừng bậc hai theo nghĩa rộng 108
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Dừng theo nghĩa rộng hay dừng hiệp phương sai (wide sense stationary or covariance stationary) nếu thỏa mãn hai điều kiện sau: i) E(Xt)==m const ⎡⎤ ii) Với mọi E(⎣X tX+τ)(t)⎦ chỉ phụ thuộc τ . Đặt ⎡ ⎤ RXX ()τ=E⎣Xt(+τ)Xt()⎦ (4.9) gọi là hàm tự tương quan của quá trình {Xt();t∈T} . Quá trình dừng bậc hai là quá trình dừng theo nghĩa rộng, nhưng điều ngược lại khơng đúng. Quá trình dừng bậc N nếu: với mọi h , với mọi tt12,, ,tN ∈T hai véc tơ ngẫu nhiên ()Xt( 12), Xt( ), ,, Xt( N ) và ( Xt( 12++h), X(t h), ,, Xt( N +h)) cĩ cùng phân bố xác suất. Quá trình dừng bậc N cũng là quá trình dừng bậc k, với mọi kN≤ . Dừng theo nghĩa chặt (strictly stationary) nếu quá trình dừng mọi bậc. Nghĩa là: Với mọi h > 0 , với mọi N, với mọi tt12, , ,tN ∈T hai véc tơ ngẫu nhiên ( Xt( 12), Xt( ), , Xt( N )) và ( Xt( 12++h), X(t h), , Xt( N +h)) cĩ cùng phân bố xác suất. Nĩi riêng mọi X (t) cĩ cùng phân bố. 4.2 CHUỖI MARKOV Chuỗi Markov là quá trình Markov {Xt();t∈T} cĩ khơng gian trạng thái E đếm được. Tùy theo tập chỉ số T = {0,1,2, } hoặc T = (0;∞) ta cĩ tương ứng chuỗi Markov với thời gian rời rạc hoặc liên tục. Với chuỗi Markov cơng thức xác suất chuyển (4.6) được viết cụ thể ps(,i;t,j)==P{X(t) jX(s)=i},t>s;i,j∈E. (4.10) Nếu xác suất chuyển (4.10) chỉ phụ thuộc vào t − s nghĩa là p(s,i;t, j) = p(s + h,i;t + h, j) (4.11) với mọi h , thì ta nĩi quá trình là thuần nhất theo thời gian. 109
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov 4.2.1 Chuỗi Markov với thời gian rời rạc thuần nhất Định nghĩa 4.1. Quá trình {Xnn ,0= ,1,2, } với thời gian rời rạc được gọi là chuỗi Markov thời gian rời rạc thuần nhất nếu thỏa mãn hai điều kiện sau i) Khơng gian trạng thái E của mọi X n là tập đếm được. ii) Hàm xác suất chuyển là thuần nhất theo thời gian, tức là thoả mãn (4.11). Từ đây trở đi ta chỉ xét chuỗi Markov với thời gian rời rạc thuần nhất và ta gọi tắt chuỗi Markov. 4.2.2 Ma trận xác suất chuyển Giả sử {Xnn ,0= ,1,2, } là chuỗi Markov thời gian rời rạc cĩ khơng gian trạng thái E . Các phần tử của E được ký hiệu i, j,k Với mọi i, j ∈ E ; đặt pPij =={Xn+11jXn =i} =P{X=jX0=i} (4.12) khơng phụ thuộc vào n . Đĩ là xác suất để từ trạng thái i sau một bước sẽ chuyển thành trạng thái j . ⎡⎤ Định nghĩa 4.2: Ma trận P= ⎣pij ⎦ với pij xác định theo (4.12) được gọi là ma trận xác suất chuyển hay ma trận xác suất chuyển sau 1 bước của chuỗi Markov {Xnn ,0= ,1,2, }. Các phần tử pij của ma trận xác suất chuyển thỏa mãn điều kiện pij ≥ 0 ; ∑ pij =1, ∀i∈ E (4.13) jE∈ Nếu tập trạng thái E vơ hạn thì ma trận xác suất chuyển cĩ vơ số hàng, vơ số cột và tổng thứ hai trong cơng thức (4.13) là tổng của một chuỗi số dương. Nếu tập trạng thái E hữu hạn, chẳng hạn E= {1,2, ,m} thì ma trận xác suất chuyển và cơng thức (4.13) được viết dưới dạng ⎡ pp11 12 p1m ⎤ ⎢ pp p⎥ Pp==⎡⎤⎢ 21 22 2m ⎥ (4.14) ⎣⎦ij ⎢ ⎥ ⎢ ⎥ ⎣ ppmm12 pmm⎦ m pij ≥ 0 ; ∑ pij =1, ∀im=1, , (4.15) j=1 Ma trận vuơng thỏa mãn điều kiện (4.15) được gọi là ma trận Markov hoặc ma trận ngẫu nhiên. 110
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov 4.2.3 Ma trận xác suất chuyển bậc cao, Phương trình Chapman–Kolmogorov Đặt ()k pPij =={Xn+k jXn =i} =P{Xk =jX0 =i} . (4.16) Đĩ là xác suất sau k bước hệ sẽ chuyển từ trạng thái i sang trạng thái j . ()k⎡ ()k⎤ Định nghĩa 4.3: Ma trận vuơng P= ⎣ pij ⎦ gọi là ma trận xác suất chuyển sau k bước. Ký hiệu P(0) =IP, (1) =P, trong đĩ I là ma trận đơn vị. Tương tự ma trận xác suất chuyển P , số hàng số cột của P(k ) cĩ thể vơ hạn nếu khơng gian trạng thái E cĩ vơ số đếm được các phần tử. Nếu khơng gian trạng thái E hữu hạn thì ma trận xác suất chuyển sau k bước P(k ) cũng là ma trận Markov (xem bài tập 4.8). Định lý 4.1: Với mọi n ≥ 0, ta cĩ: P(n+1) = PP(n) = P(n)P (4.17) Từ đĩ suy ra P(n) = Pn (4.18) Chứng minh: Áp dụng cơng thức xác xuất đầy đủ (1.19) ta cĩ (1n+ ) pPij =={Xn+10jX=i} ==∑ PX{}n+10jX =i, X1=kP{}X1=kX0=i kE∈ (n) ==∑ PX{ n+11jX=k} P{X1=kX0=i} = ∑ pik pkj kE∈ k∈E ⇒PP(1nn+ )=P(). (1n+ ) Ta cũng cĩ pPij = {Xn+10==jXi} = ∑ PX{ nn+10==jX i, X =k} P{Xn=kX0=i} kE∈ (n) = ∑ PX{ nn+10==jX k} P{Xn==kX i} = ∑ pik pkj kE∈ k∈E ⇒PP(1nn+ )=()P. Từ (4.17) suy ra PP(2) =P=P2 , bằng quy nạp ta cĩ P(n) = Pn với mọi n = 0,1, 2, Từ cơng thức (4.18) và đẳng thức Pnm+ = PnPm, ∀ nm,0≥ ta cĩ thể viết các phần tử tương ứng dưới dạng 111
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov ()nm+ (n)(m) ppij = ∑ ik pkj (4.19) k Cơng thức (4.19) được gọi là Phương trình Chapman-Kolmogorov. Phương trình Chapman-Kolmogorov giải thích quy luật chuyến trạng thái của chuỗi Markov như sau: hệ chuyển từ trạng thái i sang trạng thái j sau n+ m bước cĩ thể đạt được bằng cách (n) chuyển từ trạng thái i sang trạng thái trung gian k trong n bước (với xác suất pik ) và tiếp tục (m) chuyển từ trạng thái k sang trạng thái j trong m bước (với xác suất pkj ). Hơn nửa biến cố “chuyển từ trạng thái i sang trạng thái trung gian k trong n bước” và biến cố “chuyển từ trạng thái k sang trạng thái j trong m bước” là độc lập. Vậy xác suất chuyển từ i sang j sau nm+ ()n(m) bước qua ik,,j bằng ppik kj . Cuối cùng xác suất chuyển từ i sang j cĩ được bằng cách lấy tổng theo k , với k chạy trong khơng gian các trạng thái của chuỗi. 4.2.4 Phân bố xác suất của {Xnn ,0= ,1,2, } Giả sử khơng gian trạng thái cĩ dạng E = {0,1, 2, } Ma trận hàng P()n= [ p01()np()np2()n]; pnjn( ) ==P{X j}, n=0,1,2, (4.20) gọi là ma trận phân bố của hệ tại thời điểm n hoặc phân bố của X n . Các phần tử của ma trận hàng P(n) thỏa mãn điều kiện pnkk()≥=0;∑ pn() 1 k Khi n = 0 , P(0) = [ pp01(0) (0) p2(0) ] được gọi là ma trận phân bố ban đầu. Định lý 4.2: Với mọi n ≥ 0, m ≥ 0 : PP()nP= (0) (n) (4.21) PP(1nn+ )= ()P (4.22) P()nm+=P(n)P(m). (4.23) Chứng minh: Từ định lý 4.1 ta suy ra 3 điều trên là tương đương. Vì vậy để chứng minh định lý 4.2 ta chỉ cần chứng minh (4.23), và điều này cĩ được bằng cách sử dụng cơng thức xác suất đầy đủ: (m) pjn()n+=mP{Xj++m=} =∑∑P{Xn=i}P{Xjnm=Xn=i} =pi(n)pij. iE∈∈iE Vậy chuỗi Markov rời rạc thuần nhất hồn tồn được xác định bởi ma trận xác suất chuyển một bước P và ma trận phân bố ban đầu P(0) . 112
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Ví dụ 4.2: Một mạng viễn thơng gồm một dãy các trạm chuyển tiếp các kênh viễn thơng nhị phân cho trong sơ đồ sau, trong đĩ X n ký hiệu mã số nhị phân đầu ra của trạm thứ n và X 0 ký hiệu mã số nhị phân đầu vào của trạm đầu tiên. X = 0 X n = 0 n−1 1− a a b X n−1 =1 1− b X n =1 Hình 4.3: Mạng viễn thơng nhị phân Đây là 1 mơ hình chuỗi Markov cĩ khơng gian trạng thái E = {0,1}, tập chỉ số T= {0,1, ,n, }. Ma trận xác suất chuyển của mạng viễn thơng này thường được gọi là ma trận kênh: ⎡⎤1− aa P = ⎢⎥; 01< a < , 01< b < . ⎣⎦bb1− Giả sử a = 0,1, b = 0, 2 và phân bố xác suất đầu PX{ 0==0} PX{ 0=1} =0,5 (hai tín hiệu 0, 1 đồng khả năng). a) Tìm ma trận xác suất chuyển sau 2 bước, b) Tìm phân bố của trạm thứ hai X 2 . (2) ⎡⎤0,9 0,1 ⎡⎤0,9 0,1 ⎡0,83 0,17⎤ Giải: a) P ==⎢⎥⎢⎥⎢ ⎥. ⎣⎦0, 2 0,8 ⎣⎦0, 2 0,8 ⎣0,34 0,66⎦ (2) ⎡⎤0,83 0,17 b) PP(2) ==(0)P []0,5 0,5 ⎢⎥=[0,585 0,415]. ⎣⎦0,34 0,66 Như vậy cĩ 58,5% tín hiệu 0 và 41,5% tín hiệu 1 ở đầu ra của trạm thứ hai, mặc dù đầu vào ở trạm đầu tiên hai tín hiệu này xuất hiện đồng khả năng. Ví dụ 4.3: ( Mơ hình hịa nhập cộng đồng của các bệnh nhân tâm thần được xuất viện). Các chuyên gia y tế thường tránh chuyển các bệnh nhân tâm thần lâu năm được xuất viện trực tiếp từ bệnh viện đến với cộng đồng. Chẳng hạn ở Billings, Montana, người ta thực hiện như sau: Trước hết người ta chuyển bệnh nhân đến ở tại khu vực được chăm sĩc 24/24 giờ. Nếu tình trạng sức khỏe của bệnh nhân tiến triển tốt đáp ứng những tiêu chí địi hỏi thì được chuyển đến nhĩm 40 giờ, tức là được chăm sĩc 5 ngày trong 1 tuần và 1 ngày 8 giờ. Nếu tình trạng bệnh nhân tiếp tục tiến triển 113
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov tốt hơn thì sẽ được đưa đến nhĩm cĩ sự tương tác giao tiếp cao hơn, ở đây bệnh nhân được luyện tập tự chủ hành vi của mình. Cuối cùng khi được coi là khỏi bệnh hồn tồn thì được đưa về hịa nhập với cộng đồng. Drachman (1981) đã phân tích các dữ liệu thu thập được ở Billings từ 1/1/1978 đến 31/5/1979 và nhận thấy rằng dữ liệu tuân theo mơ hình chuỗi Markov với ma trận xác suất chuyển như sau: HI 24 40 A C H ⎡⎤0,7143 0,0714 0,0714 0,0000 0,0000 0,1429 ⎢⎥ I ⎢⎥0,1177 0,0588 0,2941 0,1177 0,0000 0,4118 P = 24 ⎢⎥0,0109 0,0109 0,7283 0,0652 0,0000 0,1848 ⎢⎥ 40 ⎢⎥0,0213 0,0213 0,0213 0,7660 0,0426 0,1277 A ⎢⎥0,0000 0,0172 0,0172 0,0172 0,7931 0,1552 ⎢⎥ C ⎣⎦0,0136 0,0442 0,0578 0,0034 0,0272 0,8537 trong đĩ các trạng thái H (ở bệnh viện), I (bắt đầu chuyển khỏi bệnh viện), 24 (nhĩm chăm sĩc 24/24), 40 (nhĩm chăm sĩc 40 giờ/1 tuần), A (nhĩm được tương tác giao tiếp) và C (nhĩm được đưa về cộng đồng). Ở đây 12 tuần được qui trịn thành 3 tháng. Áp dụng cơng thức (4.18) ta tính được HI 24 40 A C H ⎡⎤0,1723 0,0424 0,2002 0,0585 0,0372 0,4894 ⎢⎥ I ⎢⎥0,0678 0,0359 0,2032 0,1010 0,0600 0,5323 P6 = 24 ⎢⎥0,0454 0,0323 0,2539 0,1167 0,0507 0,5010 . ⎢⎥ 40 ⎢⎥0,0548 0,0330 0,1256 0,2373 0,1046 0,4447 A ⎢⎥0,0282 0,0313 0,1180 0,0592 0,2870 0,4762 ⎢⎥ C ⎣⎦0,0489 0,0374 0,1758 0,0548 0,0758 0,6073 Dữ liệu ban đầu O1 = [101581053] (biểu diễn theo tần số), áp dụng cơng thức (4.17) tính được 6 eO71==P[4,17 3,09 15,51 7,20 8,52 48,51] , ở đây 17 tháng được làm trịn thành 6 chu kỳ 12-tuần. Giá trị thức tế O7 = [5 1 15 7 8 51] . Sử dụng phép thử “khi bình phương” để so sánh, người ta thấy rằng giá trị lý thuyết e7 phù hợp với giá trị thức tế O7 . Điều này chứng tỏ chuỗi Markov phù hợp với mơ hình trên. 4.2.5 Một số mơ hình chuỗi Markov quan trọng 4.2.5.1 Mơ hình phục vụ đám đơng Xét mơ hình phục vụ đám đơng (lý thuyết sắp hàng). Khách đến sắp hàng chờ phục vụ theo nguyên tắc FIFO (first in first out) và trong mỗi chu kỳ cửa hàng chỉ phục vụ một khách. Số 114
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov khách đến trong chu kỳ thứ n là biến ngẫu nhiên ξn . Giả sử ξ1, ξ2 , là các biến ngẫu nhiên độc lập cùng phân bố với biến ngẫu nhiên ξ cĩ phân bố xác suất xác định như sau P{}ξ = k = ak ; k = 0,1,2, ; aakk≥=0; ∑ 1 . (4.24) k Trạng thái của hệ (cửa hàng) là số khách xếp hàng chờ phục vụ tại thời điểm đầu của mỗi chu kỳ (khi một khách hàng vừa được phục vụ xong). Nếu hiện tại hệ ở trạng thái i và sau 1 chu kỳ hệ rơi vào trạng thái j thì ⎧i −1+ ξ nÕu i ≥ 1, j = ⎨ (4.25) ⎩ξ nÕu i = 0. Ký hiệu X n là số khách hàng tại thời điểm đầu của chu kỳ thứ n thì + + XXnn+1 =−(1)+ξn, trong đĩ X = max(0, X ) , Từ (4.24)-(4.25) suy ra ⎧aij nuÕ =≥0, j0 ⎪⎧Pj{}ξ=n +1−i nuÕ i>0⎪ PX{}nn+1 ==jX i=⎨⎨=0 nuÕ j+1 Vì các quá trình đến ξn độc lập do đĩ xác suất chuyển pPij = {Xn+1 =jXn =i} thỏa mãn điều kiện (4.7), hơn nữa các biến ngẫu nhiên ξn cĩ cùng phân bố do đĩ xác suất chuyển pij thuần nhất theo thời gian. Vậy {Xnn; = 0,1, } là chuỗi Markov thuần nhất với ma trận xác suất chuyển ⎡a0 a1 a2 a3 ⎤ ⎢ ⎥ ⎢a0 a1 a2 a3 ⎥ ⎢ ⎥ P = ⎢ 0 a0 a1 a2 ⎥ (4.26) ⎢ ⎥ ⎢ 0 0 a a ⎥ ⎢ 0 1 ⎥ ⎣⎢ ⎦⎥ 4.2.5.2 Mơ hình kiểm kê (Inventory Model) Giả thiết phải dự trữ trong kho một loại hàng nào đĩ để đáp ứng nhu cầu liên tục của khách hàng. Hàng được nhập kho tại cuối mỗi chu kỳ n = 0,1,2, Giả sử tổng số lượng hàng cần phải đáp ứng nhu cầu trong chu kỳ n là biến ngẫu nhiên ξn cĩ phân bố độc lập với chu kỳ thời gian, nghĩa là dãy biến ngẫu nhiên {ξn} độc lập cĩ cùng phân bố với ξ . P{}ξ = k = ak ; ak > 0 và ∑ak =1. (4.27) k 115
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Mức hàng dự trữ được kiểm kê tại cuối mỗi chu kỳ. Cách nhập hàng căn cứ vào 2 chỉ số tiêu chuẩn s và S (s s thì khơng cần nhập hàng. Giả sử số nhu cầu trong mỗi chu kỳ khơng vượt quá S . Ký hiệu X n là lượng hàng hiện cĩ tại cuối chu kỳ n và trước khi nhập hàng, như vậy ⎧X nn− ξ<+1 nÕu sXn≤S, X n+1 = ⎨ (4.28) ⎩ SX−ξnn+1 nÕu ≤s. Các trạng thái của quá trình {Xnn ,≥ 0} là các số lượng hàng dự trữ: S,S −1, ,1,0,−1,− 2, trong đĩ giá trị âm là nhu cầu chưa được phục vụ mà sẽ được đáp ứng ngay sau khi nhập hàng ⎧⎪Pi{ξn+1 =−j} nÕu s<i≤S, pPij =={}Xn+1 jXin ==⎨ (4.29) ⎩⎪PS{}ξ=n+1 −jnÕu i≤s. Ví dụ 4.4: Xét mơ hình kiểm kê phụ tùng thay thế, trong đĩ yêu cầu cĩ thể là 0, 1 hoặc 2 đơn vị phụ tùng cần thay thế trong một chu kỳ bất kỳ với phân bố xác suất như sau PP{ξ=00} = ,5;{ξ=1} =0,4;P{ξ=20} = ,1 và giả sử s = 0; S = 2 . Khơng gian trạng thái sẽ là E = {}−1,0,1,2 . ⎪⎧Pi{ξ =−j} nÕu 02<i≤, Ta cĩ: pPij =={}Xn+1 jXin ==⎨ ⎩⎪Pj{}ξ=20− nÕu i≤ . pP−−1, 1 =={ Xnn+1 −11X=−} =P(∅)=0, pP−+1,0 =={ Xnn1 01X=−} =P(ξ =2)=0,1, pP−+1,1 =={ Xnn1 11X=−} =P(ξ =1)=0,4, . . . . . . . . . . . . . . . . . . . . . . . . . . . Ma trận xác suất chuyển: ⎡⎤0,0 0,1 0, 4 0,5 ⎢⎥0,0 0,1 0, 4 0,5 P = ⎢⎥ ⎢⎥0,1 0, 4 0,5 0,0 ⎢⎥ ⎣⎦0,0 0,1 0, 4 0,5 Mơ hình di động ngẫu nhiên được xét trong mục 4.4. 116
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov 4.2.6 Phân bố dừng, phân bố giới hạn, phân bố ergodic * Định nghĩa 4.4. P = [ pp12 ] được gọi là phân bố dừng của chuỗi Markov với ma trân xác suất chuyển P nếu thoả mãn 2 điều kiện: ⎧ PP = Pa() ⎪ ⎨ p ≥=0, p1 (b) (4.30) ⎪ jj∑ ⎩ j Từ (4.30-a) suy ra PP ==PPP*2= =P*Pn ; ∀n. Do đĩ nếu lấy P* làm phân bố đầu của chuỗi Markov thì PP*()n= *,∀n. Như vậy nếu chuỗi Markov cĩ phân bố dừng tại thời điểm n0 nào đĩ thì hệ sẽ cĩ phân bố xác suất ổn định sau mọi bước chuyển kể từ thời điểm n0 . Điều kiện (4.30-a) cĩ thể viết lại dưới dạng PttP*= P*t (4.31) trong đĩ ma trận cột P*t là ma trận chuyển vị của P* . Cơng thức (4.31) cho thấy phân bố dừng P* là véc tơ riêng với giá trị riêng bằng 1 của ma trận Pt . Định nghĩa 4.5: Ta nĩi rằng chuỗi Markov với ma trân xác suất chuyển P cĩ phân bố giới hạn là [ pp12 ] nếu thoả mãn 2 điều kiện: ()n 1) Với mọi j tồn tại giới hạn lim pij = pj khơng phụ thuộc i , (4.32) n→∞ 2) ∑ ppjj=≥1 , 0 , (4.33) j Nếu điều kiện (4.33) được thay bởi 3) ∑ ppjj=>1 , 0 (4.34) j thì chuỗi Markov được gọi là cĩ tính ergodic và [ pp12 ] là phân bố ergodic. Nhận xét 4.1: ¾ Nếu phân bố của X (ở thời điểm thứ n ) của chuỗi là phân bố dừng thì từ thời điểm này n0 0 trở đi phân bố của chuỗi khơng thay đổi; nghĩa là với mọi m≥ n, X và X cĩ cùng phân bố. 0 m n0 ¾ Phân bố giới hạn là phân bố hệ sẽ đạt được khi thời gian tiến đến vơ cùng. Phân bố giới hạn chỉ phụ thuộc ma trận xác suất chuyển, khơng phụ thuộc phân bố đầu (ví dụ 4.6). Trong thực 117
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov tế cĩ thể đến thời điểm nào đĩ trở đi chuỗi sẽ đạt được phân bố giới hạn. Ví dụ 4.5 sau đây chứng tỏ với n = 20 thì chuỗi đạt được phân bố giới hạn. ¾ Phân bố ergodic là phân bố giới hạn với xác suất dương tại mọi trạng thái của chuỗi. Ví dụ 4.5: Cĩ 3 mạng điện thoại di động A, B, C cùng khai thác thị trường. Tỉ lệ chiếm lĩnh thị trường hiện tại tương ứng là 40%, 30% và 30%. Theo thống kê người ta thấy xác suất thay đổi mạng của khách hàng trong mỗi tháng như sau: A BC A ⎡⎤0,6 0,3 0,1 P = ⎢⎥ B ⎢⎥0,1 0,8 0,1 C ⎣⎦⎢⎥0,1 0, 2 0,7 Áp dụng cơng thức (4.18) và (4.21) ta tính được phân bố tại thời điểm thứ n : PP()n= (0)P(n) trong các trường hợp sau. n = 0 P(0) = [0,4 0,3 0,3] , ⎡⎤0,6 0,3 0,1 ⎢⎥ n =1 P = ⎢⎥0,1 0,8 0,1 PP(1) ==(0)P [0,35 0,43 0,22], ⎣⎦⎢⎥0,1 0, 2 0,7 ⎡⎤0,2125 0,5492 0,2383 6 ⎢⎥6 n = 6 P = ⎢⎥0,1969 0,5648 0,2383 PP(6) ==(0)P [0,2047 0,5476 0,2477] , ⎣⎦⎢⎥0,1969 0,5181 0,2853 ⎡⎤0,2002 0,5503 0,2495 12 ⎢⎥12 n =12 P = ⎢⎥0,2000 0,5506 0,2495 PP(12) ==(0)P [0,2001 0,550 0,2499] , ⎣⎦⎢⎥0,2000 0,5484 0,2516 ⎡⎤0,2000 0,5500 0,2500 18 ⎢⎥18 n =18 P = ⎢⎥0,2000 0,5500 0,2500 PP(18) ==(0)P [0,2000 0,550 0,2500] . ⎣⎦⎢⎥0,2000 0,5499 0,2501 ⎡⎤0,2000 0,5500 0,2500 20 ⎢⎥20 n = 20 P = ⎢⎥0,2000 0,5500 0,2500 PP(20)==(0)P [0,20 0,55 0,25] . ⎣⎦⎢⎥0,2000 0,5500 0,2500 Ta thấy rằng khi n càng lớn xác suất trên mỗi cột càng gần bằng nhau và đạt được phân bố giới hạn khi n = 20 . Vậy thị trường đạt trạng thái ổn định với tỉ lệ tương ứng 20%, 55% và 25%. Phân bố giới hạn này chỉ phụ thuộc ma trận xác suất chuyển và khơng phụ thuộc phân bố ban đầu. Ví dụ sau đây cũng minh họa thêm về điều đĩ. 118
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Ví dụ 4.6: Về sự bình đẳng trong giáo dục giữa các nhĩm chủng tộc. Trên cơ sở báo cáo điều tra dân số của văn phịng điều tra dân số Hoa kỳ năm 1960, hai tác giả Lieberson và Fuguitt (1967) đã xác định được ma trận chuyển trình độ học vấn giữa hai thế hệ khi so sánh tình trạng học vấn của nhĩm thanh niên độ tuổi 20-24 với trình độ học vấn của bố của họ: Dưới ĐH ĐH Trên ĐH Dưới ĐH ⎡0,43 0,34 0,23⎤ ⎢ ⎥ ⎢ ⎥ P = ĐH 0,10 0,36 0,54 ⎢ ⎥ ⎢ ⎥ Trên ĐH ⎣⎢0,05 0,15 0,80⎦⎥ Hai tác giả đồng ý rằng cĩ hai loại bất lợi đối với các nhĩm chủng tộc và dân tộc. Loại bất lợi thứ nhất bắt nguồn từ nguồn gốc chủng tộc và dân tộc mà kết quả là cĩ sự khác nhau giữa ma trận chuyển của nhĩm người da trắng và nhĩm người da mầu. Ngay cả khi sự phân biệt chủng tộc bị loại bỏ thì vẫn cịn loại bất lợi thứ hai đĩ là vị trí xã hội và thu nhập của người da mầu thấp hơn nhiều so với người da trắng. Nĩi cách khác ngay cả khi ma trận chuyển về học vấn giữa hai thế hệ P (ma trận xác suất chuyển) được xem là như nhau giữa hai nhĩm thì điều kiện ban đầu P(0) (phân bố đầu) cũng khác nhau. Bảng kết quả sau được giả định rằng ma trận chuyển P giữa hai nhĩm da trắng và da mầu là như nhau nhưng cĩ xuất phát điểm khác nhau. Chỉ số khác nhau trong bảng là tỷ lệ % khoảng cách mà hai nhĩm cần phải thay đổi để đạt được phân bố trình độ học vấn bằng nhau. % Dưới % Trên Chỉ số % % ĐH ĐH ĐH khác nhau P(1) Da trắng 46 31 23 29 Da mầu 75 16 09 (1960) Da trắng 24 30 46 P(2) 13 Da mầu 34 33 33 Da trắng 16 26 58 P(3) 6 Da mầu 20 28 52 Da trắng 12 23 64 P(4) 3 Da mầu 14 25 61 Da trắng 11 22 68 P(5) 1 Da mầu 11 23 66 Da trắng 10 22 68 P(6) 1 Da mầu 11 22 67 Da trắng 10 21 69 P(7) 1 Da mầu 10 22 68 Da trắng 10 21 69 P(8) 0 119 Da mầu 10 21 69
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Như vậy khơng phụ thuộc vào xuất phát điểm, sau 8 thế hệ các nhĩm người trong cộng đồng đều cĩ trình độ học vấn như nhau theo tỷ lệ 10% dưới ĐH, 21% ĐH và 69% trên ĐH. Định lý 4.3: Nếu tồn tại phân bố giới hạn thì đĩ là phân bố dừng duy nhất. Chứng minh: Giả sử [ pp12 ] là phân bố giới hạn, khi đĩ với mọi j ta cĩ: (1n+ ) ⎛⎞(n) p ji==lim ppjlim ⎜ikpkj⎟=pkpkj nn→∞ →∞ ∑∑ ⎝⎠kk ⇒=[ p12pp ] [ 12p]P. Do đĩ [ pp12 ] là một phân bố dừng. ⎡ ⎤ Ngược lại giả sử ⎣pp12 ⎦ là một phân bố dừng bất kỳ của chuỗi Markov này thì (2) (n) p jk==∑∑ppkj ppkkj = =∑ppkkj kk k ⎛⎞()n ⇒=p jklim ⎜⎟ppkj =ppkj =pj. n→∞ ∑∑ ⎝⎠kk Nghĩa là phân bố giới hạn là phân bố dừng duy nhất. Định lý 4.4: Nếu chuỗi Markov cĩ khơng gian trạng thái hữu hạn thì chuỗi này là ergodic khi và ()n0 chỉ khi tồn tại n0 sao cho min pij > 0 . ij, Nhận xét 4.2: Từ định lý 4.3 và 4.4 ta thấy rằng nếu chuỗi Markov cĩ ma trận xác suất chuyển (n0 ) P= ⎡pij ⎤ thỏa mãn điều kiện tồn tại n0 sao cho min pij > 0 thì chuỗi này là ergodic. Phân bố ⎣⎦ i, j ergodic cũng là phân bố dừng duy nhất, đĩ là nghiệm của hệ phương trình: ⎧ ⎡ xx11⎤⎡⎤ ⎪ ⎧ x xx = x P Pxt ⎢ ⎥⎢= x⎥ ⎪ [ 12 ] [ 12 ] ⎪ ⎢ 22⎥⎢⎥ hay (4.35) ⎨ xx>=0, 1. ⎨ ⎣⎢ ⎦⎣⎥⎢⎦⎥ ⎪ jj∑ ⎪ ⎩ j ⎪ xxjj>=0, ∑ 1. ⎩⎪ j Giải hệ phương trình (4.35) cho trường hợp ví dụ 4.6 ta cũng thu được phân bố dừng tương ứng P* = [0, 20 0,550 0, 25]. Ví dụ 4.7: Xét chuỗi Markov ở ví dụ 4.2, ma trận xác suất chuyển ⎡1− a a ⎤ P = ⎢ ⎥ , 0 < a,b < 1 ⎣⎢ b 1− b⎦⎥ 120
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Theo định lý 4.4 chuỗi Markov cĩ tính ergodic với phân bố ergodic là nghiệm của hệ phương trình b ⎧⎡⎤1− ab⎡⎤xx⎡⎤ ⎧ 11 ⎪x1 = ⎪⎪⎢⎥⎢⎥= ⎢⎥ ⎧−+ax12bx =0 ab+ ⎨⎨⎣⎦ab1− ⎣⎦x22⎣⎦x⇔⇔⎨ ⎪⎪⎩ x12+=xa1 xx+=1 x2 = ⎩ 12 ⎩⎪ ab+ Mặt khác cũng cĩ thể tính trực tiếp ma trận chuyển sau n bước n nn⎡⎤1−⎧aa 1 ⎡ba⎤ ⎡a−a⎤⎫ Pa==⎢⎥⎨⎢⎥+(1 −−b) ⎢⎥⎬ (4.36) ⎣⎦bb1−−ab+ ⎩⎭⎣ba⎦ ⎣bb⎦ ⎡ ba⎤ ⎢ ⎥ ()n ab+ a+ b ⇒=lim P ⎢ ⎥ . n→∞ ⎢ ba⎥ ⎣⎢ab+ ab+ ⎦⎥ Do đĩ chuỗi tồn tại phân bố giới hạn. Đế chứng minh (4.36) ta cĩ thể tính theo một trong các cách sau: Quy nạp theo n . n nkkn−k Sử dụng cơng thức: nếu AB= BA thì ()AB+=∑ Cn AB và bằng cách đặt k=0 ⎡⎤11−−aa⎡aa⎤⎡0⎤⎡⎤−aa kk−1 P ==⎢⎥⎢⎥+⎢⎥; A=⇒⎢⎥A=(−a−b)A ⎣⎦bb10−−⎣bb⎦⎣1⎦⎣⎦bb− nn⎛⎞n PCnk==AkI+CkAk=I+Ck()−a−bk−1 A ∑∑nn⎜⎟∑n kk==01⎝⎠k=1 11nn⎧⎡ba⎤⎡a −⎫a⎤ =+Ia()(1 −−b) −1 A= ⎨⎢ ⎥+(1 −a−b) ⎢⎥⎬ . −+()ab ab+⎩⎭⎣ba⎦⎣−b b⎦ Ví dụ 4.8: Trong một bài báo viết năm 1913 A. A. Markov đã chọn 1 dãy gồm 20.000 chữ cái trong trường ca Evghenhi Onheghin của A. X. Puskin và thấy rằng các chữ cái này chuyển đổi liên tiếp theo hai trạng thái nguyên âm (Na) và phụ âm (Pa) với ma trận xác suất chuyển là Na ⎡0,128 0,872⎤ P = ⎢ ⎥ Pa ⎣0,663 0,337⎦ Na Pa Phân bố giới hạn (cũng là phân bố dừng) của chuỗi Markov này là 0,663 0,872 PN( a) ==0,423 , PP( a) ==0,568 . 0,872 + 0,663 0,872 + 0,663 121
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Vậy cĩ khoảng 42,3% nguyên âm và 56,8% phụ âm trong tác phẩm trên. 4.3 PHÂN LOẠI TRẠNG THÁI CHUỖI MARKOV Định lý 4.4 cho ta dấu hiệu nhận biết một chuỗi Markov hữu hạn trạng thái tồn tại phân bố ergodic. Trong trường hợp tổng quát, bằng cách phân tích trạng thái của chuỗi Markov ta sẽ tìm điều kiện để chuỗi tồn tại phân bố dừng, phân bố giới hạn hoặc phân bố ergodic thỏa mãn các điều kiện (4.31)-(4.34). 4.3.1 Các trạng thái liên thơng và sự phân lớp Định nghĩa 4.6: Ta nĩi rằng trạng thái j đạt được (accessible) từ trạng thái i nếu tồn tại n ≥ 0 (n) sao cho pij > 0 (xác suất để sau n bước chuyển từ trạng thái i sang trạng thái j lớn hơn 0). Ký hiệu i → j . (0) (0) Quy ước pii = 1 và pij = 0 khi i ≠ j . Hai trạng thái i và j được gọi là liên thơng (communicate) với nhau nếu i → j và j → i , lúc đĩ ta ký hiệu i ↔ j . Cĩ thể chứng minh được rằng ↔ là một quan hệ tương đương (cĩ tính phản xạ, đối xứng và bắc cầu) trên tập các trạng thái. Do đĩ ta cĩ thể phân hoạch khơng gian trạng thái thành các lớp tương đương. Các lớp tương đương này rời nhau, hai trạng thái bất kỳ cùng một lớp thì liên thơng với nhau, cịn hai trạng thái thuộc hai lớp khác nhau khơng thể liên thơng với nhau. Định nghĩa 4.7: Chuỗi Markov được gọi là tối giản (irreducible) nếu hai trạng thái bất kỳ của khơng gian trạng thái liên thơng với nhau. Như vậy chuỗi Markov tối giản chỉ cĩ một lớp tương đương. Ví dụ 4.9: Cho chuỗi Markov với ma trận xác suất chuyển ⎡1/ 3 2 / 3 0 0 0 ⎤ ⎢ ⎥ ⎢1/ 4 3/ 4 0 0 0 ⎥ ⎢ ⎥ ⎡P1 0 ⎤ P = ⎢ 0 0 0 1 0 ⎥ = ⎢ ⎥ ⎢ ⎥ ⎣⎢ 0 P2 ⎦⎥ ⎢ 0 0 1/ 2 0 1/ 2⎥ ⎢ ⎥ ⎣⎢ 0 0 0 1 0 ⎦⎥ Khơng gian trạng thái E = {1,2,3,4,5} phân thành hai lớp E1 = {1,2}, E2 = {3,4,5}. Cĩ thể xem E1, E2 lần lượt là hai khơng gian trạng thái của hai chuỗi Markov với ma trận xác suất chuyển tương ứng là P1 và P2 , hai chuỗi Markov này tối giản. Một cách tổng quát, giả sử khơng gian trạng thái được tách thành các lớp tương đương E = E1 ∪ E2 ∪ 122
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Khi đĩ cĩ thể xem mỗi Ek (k = 1,2, ) là khơng gian trạng thái của chuỗi Markov tối giản với ma trận xác suất chuyển là ma trận con Pk ứng với phép phân hoạch tương ứng của khơng gian trạng thái. Vì thế E1, E2 , được gọi là các lớp tối giản của chuỗi. 4.3.2 Trạng thái tuần hồn và khơng tuần hồn Định nghĩa 4.8: Ta định nghĩa chu kỳ của trạng thái i là ()n di()= UCLN{n≥1:pii >0} (4.37) trong đĩ UCLN viết tắc của “ước chung lớn nhất”. (n) Nếu pii = 0 đối với mọi n ≥ 1 thì đặt d(i) = 0 . Nếu di()> 1 thì trạng thái i được gọi là trạng thái tuần hồn với chu kỳ di(). Nếu di()= 1 thì trạng thái i được gọi là trạng thái khơng tuần hồn. Rõ ràng nếu pii > 0 thì i là trạng thái khơng tuần hồn. 4.3.3 Biểu đồ chuyển trạng thái của chuỗi Markov với hữu hạn trạng thái Biểu đồ chuyển trạng thái của một chuỗi Markov hữu hạn trạng thái là biểu đồ cĩ: • Các đỉnh tương ứng với các trạng thái, • Các đường nối giữa hai đỉnh i, j cĩ mũi tên theo hướng từ i đến j nếu pij > 0 . Trong biểu đồ này nếu cĩ thể di chuyển theo chiều mũi tên từ i đến j thì ij→ . Biểu đồ chuyển trạng thái rất hữu ích trong việc xác định chuỗi Markov cĩ khơng gian trạng thái tối giản hay khơng hoặc kiểm tra tính chất tuần hồn và tìm chu kỳ của trạng thái. Chuỗi Markov ở ví dụ 4.9 cĩ biểu đồ 2 / 3 1 1/ 2 1/ 3 3/ 4 3 5 4 1 2 1/ 2 1 1/ 4 Hình 4.4: Biểu đồ chuyển trạng thái Các trạng thái cĩ chu kỳ như sau dd(1)(==2)1;d(3)(==d4)d(5)=2. 123
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Ví dụ này cho thấy các trạng thái cùng lớp sẽ cĩ chu kỳ bằng nhau. Định lý sau đây khẳng định điều đĩ. Định lý 4.5: Nếu i ↔ j thì d(i) = d( j) . Do đĩ các trạng thái thuộc cùng một lớp cĩ cùng chu kỳ. Ví dụ 4.10: Vẽ biểu đồ chuyển trạng thái và phân loại các trạng thái của các chuỗi Markov cĩ ma trận xác suất chuyển sau ⎡0,3 0, 4 0 0 0,3⎤ ⎡⎤000,50,5 ⎢ ⎥ ⎡⎤00,50,5 01000 ⎢⎥10 0 0 ⎢ ⎥ (a) P = ⎢⎥0,5 0 0,5 (b) P = ⎢⎥ (c) P = ⎢ 0000,60,4⎥ ⎢⎥⎢⎥01 0 0 ⎢ ⎥ ⎣⎦⎢⎥0,5 0,5 0 ⎢⎥⎢ 00001⎥ ⎣⎦01 0 0 ⎣⎢ 00100⎦⎥ Giải: a) Biểu đồ chuyển trạng thái của chuỗi Markov (a) là hình 4.5 (a). Khơng gian trạng thái tối giản và khơng tuần hồn. Chẳng hạn cĩ thể xuất phát từ 0 và sau hai bước sẽ quay lại 0 theo đường 01→→0. Tuy nhiên cũng cĩ thể xuất phát từ 0 và sau ba bước quay lại 0 theo đường 01→→2→0. Vậy 0 là trạng thái khơng tuần hồn, do đĩ các trạng thái 1, 2 cũng khơng tuần hồn. b) Biểu đồ chuyển trạng thái của chuỗi Markov (b) là hình 4.5 (b). Khơng gian trạng thái tối giản và tuần hồn với chu kỳ 3. c) Biểu đồ chuyển trạng thái của chuỗi Markov (c) là hình 4.5 (c). Khơng gian trạng thái khơng tối giản vì trạng thái 0 và 4 khơng liên thơng. d(0)(= d1)===ddd(2)(4)(3)=1. 0 1 1 2 0,5 0,5 1 0,5 0 0,5 0,5 1 0,5 0,5 2 1 0,3 0,5 3 (a) (b) 0,3 0 0, 4 1 1 4 0, 4 1 1 124 3 0,6 2
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Trạng thái i được gọi là trạng thái hấp thụ (Absorbing state) nếu pii =1, đĩ là trạng thái mà nếu hệ đạt đến trạng thái này thì khơng bao giờ rời đi. Trạng thái 1 của chuỗi Markov 4.3-(c) là trạng thái hấp thụ. 4.3.4 Dạng ma trận xác suất chuyển của chuỗi Markov tối giản Đối với chuỗi Markov tối giản mọi trạng thái đều cĩ cùng chu kỳ, ta gọi d là chu kỳ chung của các trạng thái của chuỗi. • Nếu d = 1 (khơng tuần hồn) thì ma trận xác suất chuyển P chỉ cĩ 1 khối. • Nếu d > 1 thì tập trạng thái E tách thành d lớp con: C0 ,C1, ,Cd−1 . Trong trường hợp này sau một bước hệ xuất phát từ C0 sẽ chuyển sang C1; xuất phát từ C1 sẽ chuyển sang C2 ; v.v ; Cd −1 sẽ chuyển sang C0 . Ma trận xác suất chuyển P cĩ dạng khối như sau: C C C 0 1 d−1 C0 C0 C1 C1 Cd −1 (4.38) C C2 d−1 C3 Vì vậy mỗi lớp con Ck cĩ thể lấy làm khơng gian trạng thái của chuỗi Markov mới với ma ()d trận xác suất chuyển là ⎡⎤pij , chuỗi này tối giản cĩ chu kỳ bằng 1. Như vậy ta cĩ thể quy ⎣⎦ij, ∈Ck (n) việc nghiên cứu chuỗi Markov tổng quát (đặc biệt là vấn đề tìm lim pij ) về chuỗi Markov tối n→∞ giản cĩ chu kỳ 1. 125
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov 4.3.5 Trạng thái hồi quy và trạng thái khơng hồi quy Với mỗi trạng thái j ta gọi Tj là thời điểm (hoặc số các bước) lần đầu tiên hệ đến được trạng thái j sau thời điểm 0. Nếu hệ khơng bao giờ đến được trạng thái j ta đặt Tj =∞. Vậy Tj là biến ngẫu nhiên rời rạc nhận giá trị trong tập {1,2, ,∞} . Với mỗi trạng thái i ta đặt: ()n fij ==PT{ j nX01=i} =P{Xn =j, X ≠j, Xn−1≠jX0=i} (4.39a) (0) fij = 0 vì Tj ≥1. (4.39b) (n) Như vậy fij là xác suất để hệ xuất phát từ i lần đầu tiên chuyển sang j tại bước thứ n . (n) Đặc biệt fii là xác suất để hệ xuất phát từ i lần đầu tiên quay về i tại bước thứ n . (n) Các xác suất fij cĩ các tính chất sau: (1) fij ==PT{ j 1 X01=i} =P{X =jX0=i} =pij . (4.40) Từ tính Markov và cơng thức xác suất đầy đủ ta cĩ: ()nn(−1) fpij = ∑ ik fkj ,2n≥ (4.41) kj≠ n ()n(k) (n−k) pfij = ∑ ij pjj , n ≥1 (4.42) k=0 Xác suất để hệ xuất phát từ i chuyển đến trạng thái j tại thời điểm hữu hạn nào đĩ là ∞ ()n fij ==∑ fPij {}Tj 0 (xác suất PT{ i = ∞=X0 i} >0 ). 126
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Trường hợp trạng thái i hồi quy ( fii = 1), khi đĩ kỳ vọng của (|TXi 0 = i) (thời điểm trung bình để lần đầu tiên hệ quay lại trạng thái i với điều kiện hệ xuất phát từ i tại thời điểm 0) được ký hiệu và tính theo cơng thức sau. ∞ ()n µ=iiE ⎣⎦⎡⎤TX0 =i=∑ nfii (4.45) n=0 Định nghĩa 4.10: Giả sử i là trạng thái hồi qui, ta nĩi: • i là trạng thái hồi quy dương (positive recurrent) nếu µi <∞. • i là trạng thái hồi quy khơng (null recurrent) nếu µi = ∞ . Như vậy khơng gian trạng thái E được phân loại như sau: 1. Các trạng thái hồi quy: ¾ Trạng thái hồi quy dương, ¾ Trạng thái hồi quy khơng. 2. Các trạng thái khơng hồi quy. Ví dụ 4.11: Xét chuỗi Markov với khơng gian trạng thái E = {0,1} cĩ ma trận xác suất chuyển ⎡ 10⎤ P = ⎢ ⎥ . ⎣1/2 1/2⎦ 1 Ta cĩ fp(1) ==1 f(1) = p= 00 00 10 10 2 (2) (1) ⎛⎞1 fp00 ==01 f10 00⎜⎟= ⎝⎠2 ()n f00 = 0 , ∀n ≥ 2 Theo cơng thức (4.43) ∞ ()n fP00 =<{}T0 ∞X0 =0 =∑ f00 =1+0 +0 + =1 n=0 ∞ ()n µ=00E0⎣⎦⎡⎤TX0= =∑ nf00 =1 n=0 Như vậy 0 là trạng thái hồi quy dương. 1 Tương tự ta cĩ fp(1) == f(1) = p= 0 11 11 2 01 01 (2) (1) ⎛⎞1 fp11 ==10 f01 ⎜⎟0=0 ⎝⎠2 ()n f11 = 0 , ∀n ≥ 2 Theo cơng thức (4.43) 127
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov ∞ ()n 11 fP11 ={}T1 1. Khi đĩ: 1. Nếu i và j liên thơng; i thuộc vào lớp con Cr cịn j thuộc vào lớp Cr+a thì (nd +a) d lim pij = , ( a = 0,1, , d −1) (4.49) n→∞ µ j 2. Nếu i bất kỳ thì 128
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov ∞ (nd+a) ⎡ (rd+a) ⎤ d lim pij = ⎢∑ fij ⎥ , ( a = 0,1, , d −1) (4.50) n→∞ ⎣⎢r=0 ⎦⎥ µ j 4.3.6. Sự tồn tại phân bố dừng và phân bố giới hạn Định lý 4.10: Giả sử {Xn} là chuỗi Markov với khơng gian trạng thái E . Khi đĩ phân bố dừng tồn tại và duy nhất khi và chỉ khi trong số các lớp tương đương của khơng gian trạng thái E cĩ đúng một lớp hồi quy dương. Giả sử lớp hồi quy dương là C , khi đĩ phân bố dừng cĩ dạng ⎧ 1 ⎪ nÕu jC∈ p j = ⎨µ j (4.51) ⎪ ⎩ 0.nÕu jC∉ Định lý 4.11: Điều kiện cần và đủ để tồn tại phân bố giới hạn là khơng gian trạng thái E cĩ đúng một lớp hồi quy dương C khơng tuần hồn ( d(C) = 1) sao cho fij = 1; ∀j ∈C, ∀i ∈ E . Khi đĩ phân bố giới hạn cũng là phân bố dừng duy nhất thỏa mãn (4.51). Định lý 4.12: Giả sử {Xnn ,≥ 0} là một chuỗi Markov cĩ khơng gian trạng thái hữu hạn. Khi đĩ các điều sau là tương đương: (i) {Xnn ,≥ 0} tối giản, khơng tuần hồn. (ii) {Xnn ,≥ 0} tối giản, khơng tuần hồn và tất cả các trạng thái là hồi quy dương. (iii) {Xnn ,≥ 0} cĩ tính ergodic, nghĩa là tồn tại phân bố ergodic (thỏa mãn 4.32, 4.34). (n) (iv) Tồn tại n0 sao cho min pij > 0 với mọi n ≥ n0 (xem định lý 4.4). i, j 4.4. DI ĐỘNG NGẪU NHIÊN TRÊN ĐƯỜNG THẲNG 4.4.1 Di động ngẫu nhiên trên đường thẳng khơng cĩ trạng thái hấp thụ Giả sử ε ∞ là dãy các biến ngẫu nhiên độc lập cĩ cùng phân bố thỏa mãn: { n}n=1 Pp{ε=nn1,} = P{ε=−1} =1−p=q;0<p<1. (4.52) Đặt X =ε +ε +ε , ( n = 1,2, ). Khi đĩ X ∞ lập thành chuỗi Markov với ma trận xác n12 n { n}n=1 suất chuyển là ⎧ p víi ji= +1 ⎪ ⎡⎤ víi P= ⎣pij ⎦ trong đĩ pij = ⎨11−pj=i− (4.53) ⎪ ⎩ 01víi ji≠ ± 129
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov Khơng gian trạng thái của chuỗi này là E =±{0, 1, ±2, } p p p p p 1− p 1− p 1− p 1− p Hình 4.6: Di động ngẫu nhiên trên đường thẳng khơng cĩ trạng thái hấp thụ Chuỗi này dùng để mơ tả di động ngẫu nhiên trên đường thẳng của hạt vật chất nào đĩ (cĩ tài liệu gọi là du động ngẫu nhiên): Sau mỗi chu kỳ hạt dịch chuyển sang phải với xác suất p hoặc dịch sang trái với xác suất 1− p . Di động ngẫu nhiên trên đường thẳng là chuỗi Markov tối giản, cĩ chu kỳ d = 2 . 1 • Nếu pq== thì mọi trạng thái là hồi quy khơng. 2 • Nếu p ≠ q thì mọi trạng thái là khơng hồi quy. Theo định lý 4.10 chuỗi khơng tồn tại phân bố dừng và do đĩ khơng cĩ tính ergodic. 4.4.2 Di động ngẫu nhiên trên đường thẳng cĩ một trạng thái hấp thụ Đĩ là di động của hạt vật chất với khơng gian trạng thái E = {0,1, 2, } và ma trận xác suất chuyển là ⎧ pjvíi = i+≠1, i0, ⎪ ⎡⎤ víi P= ⎣pij ⎦, trong đĩ pp00 ==1, ij ⎨1−pj=i−1,i≠0, ; 0< p < 1 (4.54) ⎪ ⎩ 01víi ji≠ ±≠,i0, p p p 1 0 1 2 3 4 q q q q Hình 4.7: Di động ngẫu nhiên trên đường thẳng cĩ một trạng thái hấp thụ Lúc này {0} lập thành lớp hồi quy dương duy nhất với chu kỳ d =1: E =∪{0} {1,2, } . Tất cả các trạng thái 1,2, là khơng hồi quy (vì nếu 1 hồi quy chẳng hạn thì do 1→ 0 nên 01→ , điều này khơng thể xảy ra ). Vì vậy theo định lý 4.10 và cơng thức (4.51) tồn tại phân bố dừng duy nhất, đĩ là 130
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov ⎧10víi j = , p j = ⎨ (4.55) ⎩00víi j ≠ . Hơn nữa cĩ thể chứng minh được rằng đối với mỗi i ≥1 thì ⎧ i ()n ⎪()qp/,nÕu p> q lim pi0 = ⎨ (4.56) n→∞ ⎩⎪ 1;nÕu p ≤ qq=−1p. Vì vậy: ()n i Khi p> q thì lim pi0 = (q/ p) phụ thuộc vào i , do đĩ khơng tồn tại phân bố giới hạn. n→∞ ⎧10víi j = , Khi p ≤ q thì tồn tại phân bố giới hạn, đĩ là p j = ⎨ ⎩00víi j ≠ . 4.4.3 Di động ngẫu nhiên trên đường thẳng cĩ hai trạng thái hấp thụ Đĩ là mơ hình di động như hình vẽ p p p 1 1 0 1 2 N −1 N q q q Hình 4.8: Di động ngẫu nhiên trên đường thẳng cĩ hai trạng thái hấp thụ Ma trận xác suất chuyển là ma trận vuơng cấp N +1 cĩ dạng ⎡⎤1000 0 ⎢⎥ ⎢⎥qp00 0 ⎢⎥00qp 0 ⎢⎥ P = ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥0000 qp0 ⎢⎥ ⎣⎦0000 0 0 1 Trong trường hợp này cĩ hai lớp hồi quy dương {0} và {N}. Các trạng thái cịn lại khơng hồi quy: EN=∪{0} { }∪{1,2, , N−1}. 0 , N là hai trạng thái hấp thụ do đĩ hệ sẽ ngừng lại khi hạt rơi vào trạng thái 0 hoặc trạng thái N . 131
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov * Vì vậy tồn tại vơ số phân bố dừng P = [ p01, p, , pN ] , trong đĩ pa01==, pN1−a, p=p2= =pN−1=0, với 0≤ a ≤1. (4.57) Cĩ thể chứng minh được rằng: ⎧()qp//iN− ()qp ⎪ N nÕu pq≠ , ()n ⎪ 1/− ()qp lim pi0 = ⎨ n→∞ ⎪ i ⎪ 11−=nÕu pq=/2. ⎩ N ()nn() lim piN =−1 lim pi0 , nn→∞ →∞ ()n lim pij = 0 (∀=jN1,2, , −1). n→∞ Vì vây khơng tồn tại phân bố giới hạn. 4.4.4 Di động ngẫu nhiên trên đường thẳng cĩ một trạng thái phản hồi Đĩ là chuỗi Markov cĩ dạng như hình vẽ p p 1 p p 0 1 2 3 4 q q q q q 01<p < Hình 4.9: Di động ngẫu nhiên trên đường thẳng cĩ một trạng thái phản hồi Khơng gian trạng thái E = {0,1, 2, } . Chuỗi tối giản, cĩ chu kỳ d = 2 do đĩ khơng tồn tại phân bố giới hạn. Ma trận xác suất chuyển ⎡⎤010 0 0 ⎢⎥ ⎢⎥qp000 ⎢⎥00qp0 ⎢⎥ P = ⎢⎥00q 0 ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎣⎦ Hệ phương trình xác định phân bố dừng (4.35) cĩ dạng 132
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov ⎧xx= q ⎧xx= q ⎪ 01 ⎪ 01 ⎪x10=+xx2q ⎪x11=+xq x2q ⎪ ⎪ ⎨x21=+xp x3q hay là ⎨x22=+xq x3q (4.58) ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩xxii≥=0, ∑ 1 ⎩xxii≥=0, ∑ 1 Từ đĩ suy ra x j−1 x = 0 , x ==()pq/ x =(p/ q)x , ∀j = 2,3, (4.59) 1 q jj−11 • Khi p > q , hạt cĩ xu hướng đi sang phải, tất cả các trạng thái khơng hồi quy. Nghiệm (4.59) khơng thỏa mãn điều kiện ∑ xi = 1. Chuỗi khơng tồn tại phân bố dừng. • Khi pq==1/2, tất cả các trạng thái là hồi quy khơng. Nghiệm (4.59) khơng thỏa mãn điều kiện ∑ xi = 1. Khơng tồn tại phân bố dừng. • Khi p< q, tất cả các trạng thái là hồi quy dương. ∞∞ x00i xq2 x0 1(==∑∑xxi 00+ p/q)=x+= ii==00qq− pq− p Do đĩ chuỗi tồn tại phân bố dừng duy nhất. j−1 qp−−qp qp−⎛⎞p p01==,,pp22 ,j =⎜⎟;j≥2. (4.60) 22qq 2q⎝⎠q 4.4.5 Di động ngẫu nhiên trên đường thẳng cĩ hai trạng thái phản hồi Đĩ là chuỗi Markov cĩ dạng như hình vẽ 1 p p p 0 1 2 N N −1 q q q 1 01<p < Hình 4.10: Di động ngẫu nhiên trên đường thẳng cĩ hai trạng thái phản hồi Chuỗi tối giản, khơng gian trạng thái hữu hạn E= {0,1,2, , N} . Tất cả các trạng thái của chuỗi là hồi quy dương, cĩ chu kỳ d = 2 do đĩ khơng tồn tại phân bố giới hạn. Ma trận xác suất chuyển 133
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov ⎡⎤010 0 0 0 ⎢⎥ ⎢⎥qp000 0 ⎢⎥0qp000 ⎢⎥ P = ⎢⎥00q 0 ⎢⎥ ⎢⎥ ⎢⎥000 qp0 ⎢⎥ ⎣⎦000 0 1 0 Phân bố dừng là nghiệm duy nhất của hệ phương trình (4.35) ⎧ ⎪xx01= q ⎪xx=+xq ⎪ 102 ⎪xx21=+px3q ⎪ ⎨ (4.61) ⎪x =+xpx ⎪ NN−−12N ⎪xxNN= −1 p ⎪ N ⎪xx≥=0, 1 ⎩ ii∑i=0 Từ đĩ suy ra phân bố dừng iN−−11 1 p0 ⎛⎞pp⎛⎞ pp0 ==N −1 ;,iN⎜⎟ 1≤i≤N−1;p=p0 ⎜⎟ (4.62) Nj−−111 qq q 1/++()pq ∑()pq/ ⎝⎠ ⎝⎠ q j=1 Chuỗi tồn tại phân bố dừng nhưng khơng tồn tại phân bố giới hạn. BÀI TẬP ∞ 4.1 Cho chuỗi Markov {X n }n=1 với khơng gian trạng thái E = {0,1, 2} và ma trận xác suất chuyển ⎡0,1 0,2 0,7⎤ ⎢ ⎥ P = ⎢0,9 0,1 0,0⎥ ⎢ ⎥ ⎣⎢0,1 0,8 0,1⎦⎥ Biết phân bố ban đầu: pP00=={X0} =0,3; pP10=={X1} =0,4; pP20=={X2} =0,3. Tính PX{ 01==0, X 2, X2=1}. 134
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov ⎡ pp11 12 p1m ⎤ ⎢ pp p⎥ 4.2 Giả sử Pp==⎡⎤⎢ 21 22 2m ⎥ là một ma trận Markov, (là ma trận thỏa mãn điều ⎣⎦ij ⎢ ⎥ ⎢ ⎥ ⎣ ppmm12 pmm⎦ m kiện pij ≥ 0 ; ∑ pij =1, ∀=im1, , ). j=1 Chứng minh rằng Pn cũng là ma trận Markov, với mọi số tự nhiên dương n . ∞ 4.3 Cho chuỗi Markov {}X n n=1 với khơng gian trạng thái E = {0,1, 2} và ma trận xác suất chuyển ⎡0,1 0,2 0,7⎤ ⎢ ⎥ P = ⎢0,2 0,2 0,6⎥ ⎢ ⎥ ⎣⎢0,6 0,1 0,3⎦⎥ a) Tính ma trận xác suất chuyển 2 bước. b) Tính P{}X 3 =1 X1 = 0 ; P{}X 3 =1 X 0 = 0 . c) Tìm phân bố dừng. 4.4 Xét bài tốn truyền một bức điện gồm gồm các tín hiệu 0, 1 thơng qua kênh cĩ nhiều trạm và mỗi trạm nhận sai tín hiệu với xác suất khơng đổi bằng α ∈ (0,1) . Giả sử X 0 là tín hiệu truyền đi và X n là tín hiệu nhận được tại trạm n . Cho biết {X n ; n = 0,1, 2, } lập thành chuỗi Markov với ma trận xác suất chuyển ⎡1− αα⎤ P = ⎢ ⎥ . ⎣ α 1−α⎦ a) Tính P{}X 0 = 0, X1 = 0, X 2 = 0 . b) Tính P{}X 0 = 0, X1 = 0, X 2 = 0 + P{X 0 = 0, X1 =1, X 2 = 0}. c) Tính P{}X 5 = 0 X 0 = 0 . 4.5 Xét chuỗi Markov với khơng gian trạng thái Ea= { ,,bc,d} và ma trận xác suất chuyển ⎡0,1 0,3 0, 2 0, 4⎤ ⎢0, 2 0.3 0, 2 0,3⎥ P = ⎢ ⎥ ⎢0,3 0,5 0,1 0,1⎥ ⎢ ⎥ ⎣0, 2 0,1 0, 4 0,3⎦ a) Tìm xác suất chuỗi đi theo đường đi: b− abc−−−−ba. 135
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov b) Tính xác suất PX{ 13=a,,X=cX4===b,X5aX0b}. c) Tính P(5) . d) Tính PX{ 5==aX0b} . e) Tìm P(5) biết P(0) = [0, 2 0, 4 0,3 0,1] . 4.6 Xét chuỗi Markov với khơng gian trạng thái E = {0,1} và ma trận xác suất chuyển ⎡⎤1− aa P = ⎢⎥ , 01< a < , 01< b < . ⎣⎦bb1− Giả sử phân bố đầu PX{ 0==01} PX{ 0=} =0,5. a) Vẽ biểu đồ chuyển trạng thái. b) Tìm phân bố dừng. c) Tìm phân bố của X n . d) Tìm phân bố giới hạn khi ab+≤1. 4.7 Xét mơ hình kiểm kê phụ tùng thay thế với s = 0 và S = 3 là các mức căn cứ để nhập hàng cùng với ξn là lượng hàng khách yêu cầu trong chu kỳ n . Biết rằng P{}ξn = 0 = 0,4; P{ξn =1}= 0,3; P{ξn = 2}= 0,3 với mọi n . Xác định ma trận xác suất chuyển của chuỗi Markov {X n }, trong đĩ X n là số phụ tùng cịn lại tại cuối chu kỳ n . 4.8 Hai cơng ti A và B cung cấp cho thị trường cùng một loại sản phẩm. Hiện tại cơng ti A chiếm 60% và cơng ti B chiếm 40% thị phần. Mỗi năm A mất 2/3 thị phần của mình cho B và B mất 1/2 thị phần cho A. Tìm tỉ lệ thị phần hai cơng ti chiếm được sau hai năm. 4.9 Mỗi một người dân của thị trấn N cĩ một trong ba nghề (A, B, C). Con cái họ nối tiếp nghề của cha mình với xác suất tương ứng là (3/ 5, 2 / 3, 1/ 4) . Nếu khơng theo nghề của cha thì chúng chọn một trong hai nghề cịn lại với xác suất như nhau. Hãy tìm: a) Phân bố theo nghề nghiệp của dân cư thị trấn ở thế hệ tiếp theo, nếu thế hệ hiện tại cĩ tỉ lệ theo nghề nghiệp là 20% cĩ nghề A, 30% cĩ nghề B và 50% cĩ nghề C. b) Phân bố giới hạn theo nghề nghiệp của dân cư thị trấn ở thế hệ tương lai xa. 4.10 Chứng minh rằng ↔ là một quan hệ tương đương trong tập các trạng thái. 4.11 Cho chuỗi Markov cĩ khơng gian trạng thái E = {0,1, 2} và ma trận xác suất chuyển ⎡01/21/2⎤ P ⎢10 0⎥ = ⎢ ⎥ ⎣⎢10 0⎦⎥ 136
Chương 4: Quá trình ngẫu nhiên, chuỗi Markov a) Vẽ biểu đồ chuyển trạng thái. b) Tính P(2n) , P(2n+1) . c) Chứng tỏ rằng 0 là trạng thái tuần hồn cĩ chu kỳ 2. 4.12 Cho chuỗi Markov cĩ khơng gian trạng thái E = {0,1, 2,3, 4} và ma trận xác suất chuyển ⎡1/ 2 1/ 2 0 0 0 ⎤ ⎢ ⎥ ⎢1/ 2 1/ 2 0 0 0 ⎥ ⎢ ⎥ P = ⎢ 0 0 1/ 2 1/ 2 0 ⎥ ⎢ ⎥ ⎢ 0 0 1/ 2 1/ 2 0 ⎥ ⎢ ⎥ ⎣⎢1/ 4 1/ 4 0 1/ 4 1/ 4⎦⎥ Tìm các lớp liên thơng của khơng gian trạng thái. Vẽ biểu đồ trạng thái và tìm chu kỳ các trạng thái. 4.13 Xét di động ngẫu nhiên trên đường thẳng cĩ một trạng thái phản hồi cĩ dạng như hình vẽ 1 p p p p 0 1 2 3 4 1− p 1− p 1− p 1− p 1− p Với p = 0, 4 . Tìm phân bố dừng. 4.14 Xét di động ngẫu nhiên trên đường thẳng cĩ hai trạng thái phản hồi cĩ dạng như hình vẽ 1 p p p 0 1 2 N N −1 1− p 1− p 1− p Với Np=10; =0,6 . Tìm phân bố dừng. 137
Chương5: Quá trình dừng CHƯƠNG V: QUÁ TRÌNH DỪNG GIỚI THIỆU Chuỗi Markov, quá trình Poisson nghiên cứu sự tiến triển theo thời gian của các hệ ngẫu nhiên mà trong đĩ tương lai chỉ phụ thuộc hiện tại và độc lập với quá khứ (tính Markov). Ngồi những quá trình Markov, trong thực tế ta cịn gặp các hệ ngẫu nhiên mà quá khứ của nĩ cĩ ảnh hưởng lớn đến sự tiến triển của quá trình trong tương lai. Đặc biệt với quá trình mà hàm tự tương quan thuần nhất theo thời gian (quá trình dừng theo nghĩa rộng) cĩ rất nhiều ứng dụng trong viễn thơng. Các tín hiệu, nhiễu của một hệ thống viễn thơng là các quá trình dừng. Khái niệm quá trình dừng được nhà tốn học người Nga Khintchine đưa ra lần đầu tiên vào năm 1934. Ngày nay quá trình dừng đã trở thành một trong những lĩnh vực quan trọng và cĩ nhiều ứng dụng của lý thuyết xác suất. Các khái niệm quá trình dừng được xét trong chương 4. Trong chương này chủ yếu xét quá trình dừng theo nghĩa rộng, đĩ là quá trình ngẫu nhiên cĩ kỳ vọng khơng phụ thuộc thời gian và hàm tự tương quan thuần nhất theo thời gian. Các tín hiệu viễn thơng và nhiễu là các quá trình dừng. Các quá trình này được ký hiệu bằng chữ in hoa X (t) cịn các thể hiện tương ứng ký hiệu bằng chữ thường x(t). Áp dụng định lý Wiener-Khintchine đối với quá trình dừng biểu diễn các tín hiệu ta cĩ thể tính cơng suất trung bình của tín hiệu thơng qua phổ của quá trình dừng, đĩ là biến đổi Fourier của hàm tự tương quan của quá trình. Từ hàm mẫu ta cĩ thể tính được các giá trị trung bình theo thời gian. Vì vậy trong thực tế ta chỉ cĩ thể tính được trung bình theo giời gian (time average) của một quá trình ngẫu nhiên cịn trung bình theo tập hợp (ensemble average) được tính tốn thơng qua lý thuyết. Do đĩ khi trung bình theo thời gian trùng với trung bình theo tập hợp thì việc nghiên cứu chúng sẽ thuận lợi hơn. Quá trình cĩ trung bình theo thời gian trùng với trung bình theo tập hợp được gọi là quá trình ergodic. Chúng ta sẽ chỉ ra những tiêu chuẩn để nhận biết quá trình dừng là quá trình ergodic. Để học tốt chương này học viên nên xem lại lý thuyết xác suất và phép biến đổi Fourier. 5.1. QUÁ TRÌNH DỪNG 5.1.1. Hàm hiệp phương sai và hàm tự tương quan của quá trình dừng Giả sử {Xt();t∈ I} là quá trình dừng với giá trị trung bình m và hàm tự tương quan KX (τ), nghĩa là: 1) mt( ) ==E X(t) m=const , 2) Hàm tự tương quan chỉ phụ thuộc vào khoảng thời gian giữa hai thời điểm 138
Chương5: Quá trình dừng ⎡⎤ RsXX ()− t=E⎣⎦X(s)X(t);∀s,t∈I. (5.1) Khi đĩ cĩ thể chứng minh được rằng 2 cov(Xs(),X(t))=−E⎡⎤Xs() m X(t)−m =E⎡Xs()X(t)⎤−m (5.2) ⎣⎦()()⎣⎦ cũng chỉ phụ thuộc vào s− t, nghĩa là tồn tại hàm ký hiệu CX (τ), sao cho CsXX ( −t) =∀cov(X(s), X(t)); s,t∈I (5.3) CXX (τ) được gọi là hàm tự hiệp phương sai của quá trình dừng {Xt();t∈ I} . Từ đẳng thức (5.2) ta cĩ thể định nghĩa quá trình dừng theo nghĩa rộng là quá trình thỏa mãn hai điều kiện sau: 1’) mt( ) ==EX(t) m=const , 2’) Hàm tự hiệp phương sai CsXX (,t)= cov(X(s),X(t)) chỉ phụ thuộc vào st− ; ∀st, ∈I. Rõ ràng rằng hai định nghĩa này trùng nhau khi mt()= EX(t)=0,∀t. Chú ý : Hàm tự hiệp phương sai CXX (,st) của quá trình ngẫu nhiên X (t) cũng là hàm tự tương quan của quá trình quy tâm iX ()tX=−(t) EX(t). Ví dụ 5.1: (a) Nếu X ()tA= eiωt thì 2 Rs()−=tE⎡⎤AeisωωAeit =EAeiω()s−t;∀s,t∈I XX ⎣⎦⎢⎥ 2 (b) Giả sử các biến ngẫu nhiên Ak khơng tương quan cĩ kỳ vọng bằng 0 và phương sai σ k . iωkt 2 isωk ()−t Xét Xt()= ∑ Ake thì mt()==EX(t) 0 và RXX ()st− =∀∑σ k e ;s,t∈I. k k Hàm tự tương quan cĩ các tính chất sau. Định lý 5.1: 1) RRXX ()−=τ XX (τ ). 2) RRXX ()τ ≤ XX (0) 22 3) RXX (0) ==E Xt( ) E X(0) , ∀t. 2 Nếu X (t) là một quá trình tín hiệu ngẫu nhiên thì RXX (0) = E Xt( ) được gọi là cơng suất trung bình của tín hiệu. 139
Chương5: Quá trình dừng Quá trình dừng cĩ một số tính chất khác (Xem Cooper, G.R. và C.D. McGillem (1971): Probabilistic Methods of Signal and Analysis, Holt. Rinchart and Winston, New York) . 4) Nếu E([ Xt)] =m≠0 và X (t) khơng cĩ thành phần tuần hồn thì 2 lim RXX (τ ) = m ||τ →∞ 5) Nếu X (t) cĩ một thành phần tuần hồn thì RXX (τ ) cũng cĩ một thành phần tuần hồn với cùng chu kỳ. Ví dụ 5.2: Giả sử X (t) là một quá trình dừng với hàm trung bình mt()= 3, hàm tự tương −0.2τ quan ReXX ()τ =+9 4 . Đặt ZX= (3) , TX= (8) . Tính kỳ vọng, phương sai và hiệp phương sai của Z và T . 22 2 Giải: EEZ ==T 3. EEZT==RXX (0)=13⇒varZ=varT=13−3=4. −1 E(ZTR) =−XX (8 3) =9 +4e. 4 Ví dụ 5.3: Quá trình dừng với hàm tự tương quan RXX ()τ =+25 . 16+ τ 2 Theo tính chất 4) ta cĩ mm2 =⇒25 =±5. 2 var X (tX) =E ⎡⎤2 (t) −E X(t) []⎣⎦[] 2 Ta cĩ E Xt( ) ==RXX (0) 25 +4 =29 , do đĩ var[ Xt( )] = 29 −25 =4 . Ví dụ 5.4: Giả sử A , B là hai biến ngẫu nhiên thoả mãn EEAB= = 0, cov(AB, ) = 0 , 2 var A==var Bσ ; ω0 là một hằng số thì quá trình Xt()= Acos(ω0t)+ Bsin(ω0t) là quá 2 trình dừng cĩ hàm tự tương quan RXX ()τ = σωcos 0τ. Giải: EXt()=ωcos()00tEA+sin()ωtEB=0. RXX (st, ) ==E[ X(s)X(t)] E ⎣⎦⎡⎤()Acos(ω00s) +Bsin(ωs) ( Acos(ω0t) +Bsin(ω0t)) =E ⎡A22cos(ωst)cos(ω) +Bsin(ωωs)sin( t) +ABcos(ωs)cos(ωt) +sin(ωωs)sin( t) ⎤ ⎣ 0 0 00()0 0 00⎦ 2 2 =−σωcos()0 (ts) ⇒=RXX ()τ σωcos( 0τ). 2 Ví dụ 5.5: Quá trình ngẫu nhiên hình sin: Xt()= Acos(ω0t+Θ) , E0A = , var A = σ , Θ là biến ngẫu nhiên cĩ phân bố đều trên đoạn [0;2π] , A,Θ độc lập. Giải: Θ là biến ngẫu nhiên cĩ phân bố đều trên đoạn [0;2π] với hàm mật độ 140
Chương5: Quá trình dừng ⎧ 1 ⎪ nÕu 02≤ u ≤π fuΘ ()= ⎨ 2π ⎩⎪ 0 nÕu ng−ỵc l¹i ∞ 2π 1 E ⎡⎤cos()ωωtt+Θ = cos( +u) f(u)du= cos(ωt+u) du=0 ⎣⎦00∫Θ ∫02π −∞ 0 E(Xt)=+E⎣⎦⎡⎤Acos()ωω00t Θ=E[ A]E⎣⎡cos( t+Θ)⎦⎤=0. ⎡⎤ E([ Xs)X(t)] =+E⎣⎦()Acos()ωω00s Θ( Acos( t+Θ)) =+E ⎡⎤As22cos(ωωΘ) cos( t+Θ) =E ⎡A⎤E ⎡ cos(ωωs+Θ) cos( t+Θ) ⎤ ⎣⎦()00()⎣⎦⎣()0(0)⎦ Ev⎡⎤AA22==arσ ; ⎣⎦ Ec⎣⎦⎡⎤()os(ωω00st+Θ)(cos( +Θ)) ⎡⎤111 =+E {}cos()ωω00(st) +2Θ+{}cos (st−) =cosω0(s−t) ⎣⎦⎢⎥222 Do đĩ quá trình ngẫu nhiên hình sin là một quá trình dừng với hàm tự tương quan 1 R ()τ = σω2 cos τ. XX 2 0 Ví dụ 5.6: (Quá trình Wiener) Quá trình Wt(),t≥ 0 được gọi là một quá trình Wiener với tham số σ2 nếu nĩ thoả mãn các tính chất sau: 1) W (0) = 0. 2) Với mọi 0 ≤ s < t thì Wt()−W(s) là biến ngẫu nhiên cĩ phân bố chuẩn N(0;σ−2 (ts)). 3) Wt(),t≥ 0 là quá trình với gia số độc lập, tức là với mọi 0 ≤ t1 < t2 < tn thì các biến ngẫu nhiên: Wt(21)−−Wt(),(Wt3)Wt(2), ,(Wtn)−Wt(n−1)là độc lập. Như vậy Wt(),t≥ 0 là một quá trình cĩ: mt()= EW(t)=∀0 t≥0. ∀ts,≥0, giả sử s≤ t: RWW (,st)==E[ Ws()W(t)] E⎣⎦⎡⎤Ws()( Ws()+W(t)−Ws()) 2 =+E([]Ws) E⎣⎦⎡⎤()Ws()−W(0)(W(t)−W(s)) =σ2sW+E([ s)−W(0)]E([ Wt)−W(s)] =σ2s. (do gia số độc lập và E(Ws)= 0) 2 Do đĩ RWW (,st)= σ min(,st). 141
Chương5: Quá trình dừng Vậy quá trình Wiener là một quá trình gia số độc lập dừng và khơng phải là quá trình dừng. Ví dụ 5.7: Xét quá trình ngẫu nhiên phức Xt() là tổng của N tín hiệu phức: N itω0 +iΘn Xt()= ∑ Ane n=1 ω trong đĩ 0 (hằng số) là tần số của mỗi tín hiệu. A là biến ngẫu nhiên biểu diễn biên độ và 2π n Θn là biến ngẫu nhiên pha của tín hiệu thứ n. Giả sử các biến ngẫu nhiên An , Θn độc lập và Θn cĩ phân bố đều trên khoảng (0;2π ). Tìm hàm tự tương quan của quá trình. ⎡ NN⎤ ⎡⎤itωτ00()++iΘnmiωt+iΘ Giải: RtXX (,+=ττt)E⎣⎦X(t+)X(t)=E⎢∑∑Ane Ame ⎥ ⎣⎢nm==11⎦⎥ ⎡⎤NN NN itωτ00()++iΘnm−iωt−iΘ iω0τ ⎡⎤i(Θn−Θm) ==EE⎢⎥∑∑Anme Ae e ∑∑⎣⎦AnAem=RXX(τ ) ⎣⎦nm==11 n=1m=1 Lại cĩ, E ⎡⎤eii()Θ−nmΘ E cos( ) E sin( ) ⎣⎦=Θ[ nm−Θ]+[ Θn−Θm] 22ππ1 ⎧0 nm≠ =−[]cos(θθnm) +idsin(θθnm−) θndθm=⎨ ∫∫00(2π )2 ⎩1 nm= N iωτ0 2 Vậy RXXn()τ = eA∑ E . n=1 5.1.2. Hàm tương quan chéo và các tính chất Hàm tương quan chéo của hai quá trình ngẫu nhiên X (t) và Yt() được định nghĩa và ký hiệu ⎡ ⎤ RXY (,tt+=ττ)E⎣X(t+)Y(t)⎦ . Nếu hai quá trình dừng X (t) và Yt() cĩ hàm tương quan chéo RtXY (+τ ,t) chỉ phụ thuộc τ thì được gọi là hai quá trình dừng đồng thời và hàm tương quan chéo sẽ là ⎡ ⎤ RXY ()ττ=+E⎣Xt( )Y(t)⎦ Hai quá trình X (t) và Yt() được gọi là trực giao nhau nếu ⎡⎤ RtXY (,+=τt)E⎣X(t+τ)Y(t)⎦=0; với mọi t , với mọi τ ≠ 0 . Hai quá trình X (t) và Yt() được gọi là khơng tương quan nếu ⎡⎤ CtXY (+=ττ,t)E⎣⎦X()t+Y(t)−m()t+τm(t)=0; với mọi t và với mọi τ ≠ 0 . Hàm tương quan chéo của hai quá trình dừng đồng thời cĩ các tính chất 142
Chương5: Quá trình dừng 1) RRXY ()−=τ YX (τ ). 2) RRXY ()τ ≤ XX (0)RYY (0) RR(0) + (0) 3) R ()τ ≤ XX YY . XY 2 Ví dụ 5.8: Xét hai quá trình ngẫu nhiên X (t) và Yt() Xt()= Acos(ω00t)+ Bsin(ω t) ; Yt()= Bcos(ω00t)− Asin(ω t) trong đĩ A , B là hai biến ngẫu nhiên và ω0 là hằng số. Theo ví dụ 5.3, nếu EEA==B0, cov(AB, ) = 0 , var A= var B= σ 2 thì X (t) và Yt() là hai quá trình dừng. Hàm tương quan chéo Rt(,t+=τ )E⎡⎤X(t)Y(t+τω)=E⎡ABcos()tcos(ωt+ωτ)+B2 sin()ωtcos(ωt+ωτ)⎤ XX ⎣⎦⎣ 000 000⎦ −+E ⎡At2 cos(ω )sin(ωωtτ) +ABsin(ωt)sin(ωωt+τ)⎤ ⎣ 000 000⎦ =+EABcos(2ω t ωτ) +E ⎡⎤B22sin(ωt)cos(ωt+ωτ) −E ⎡⎤A cos(ωt)sin(ωt+ωτ) [] 00 ⎣⎦ 0 00 ⎣⎦ 0 00 2 RtXY (,t+=τ ) −σsin(ω0τ) chỉ phụ thuộc τ , do đĩ X (t) và Yt() là hai quá trình dừng đồng thời. 5.1.3. Đặc trưng phổ của quá trình dừng Cĩ thể sử dụng cả hai phương pháp phân tích theo miền thời gian và theo miền miền tần số để phân tích các hệ thống tuyến tính tín hiệu tất nhiên. Các tính chất phổ của tín hiệu tất nhiên x(t) nhận được từ biến đổi Fourier ∞ lXf()==F {}x(t) ∫ e−it2π fx(t)dt −∞ Hàm lXf() đơi khi được gọi một cách đơn giản là phổ của x(t), cĩ đơn vị volt/hertz. Nếu biết phổ lXf() thì cĩ thể khơi phục tín hiệu thơng qua phép biến đổi Fourier ngược ∞ x()tX==F −12{}l(f) ∫ eitπ flX(f)df −∞ Một cách tự nhiên ta cũng tìm cách sử dụng hai phương pháp này cho trường hợp tín hiệu ngẫu nhiên. Biểu diễn phổ của tín hiệu tất nhiên nhận được từ biến đổi Fourier của tín hiệu đĩ. Mặc dù phép biến đổi Fourier cũng cĩ vai trị rất quan trọng trong việc đặc trưng phổ của các tín hiệu ngẫu nhiên. Tuy nhiên khơng thể tính trực tiếp biến đổi Fourier các tín hiệu ngẫu nhiên, 143
Chương5: Quá trình dừng vì phép biến đổi cĩ thể khơng tồn tại đối với hầu hết các hàm mẫu của quá trình. Vì vậy phân tích phổ của các quá trình ngẫu nhiên địi hỏi tỉ mỉ hơn phân tích các tín hiệu tất nhiên. Mặt khác ta cĩ thể biểu diễn cơng suất của quá trình ngẫu nhiên dưới dạng hàm theo tần số (thay vì theo hiệu điện thế), biểu diễn như thế tồn tại. Trong mục này ta xét đến các hàm đĩ và gọi là mật độ phổ cơng suất. A. Mật độ phổ cơng suất Cho quá trình {Xt();t∈R} biểu diễn các tín hiệu. ⎪⎧ 0 xét: XtT ()= ⎨ ⎩⎪ 0 nÕu tT≥ l Đặt biến đổi Fourier của XT (t) là X T ()fX= F {}T (t) ∞ T l −πif22t −πift X T ()fX==∫∫T (t)edtX(t)edt. −∞ −T l XT (t) và XT (f) cũng là hai quá trình ngẫu nhiên. ∞∞ 2 l 2 Áp dụng đẳng thức Parseval ta cĩ: ETT==∫X ()tdt ∫XT (f) df. −∞ −∞ ET cũng là một quá trình ngẫu nhiên. Áp dụng định lý năng lượng Rayleich ta được ∞∞ ∞ 22l 2 EEETT===∫∫X (td)t EXT(td)t ∫EXT (f)df. −∞ −∞ −∞ Từ đĩ ta cĩ tính cơng suất trung bình của quá trình PA= ⎡⎤E(Xt)2 XX ⎣⎦⎢⎥ T ∞∞ 11221l 2 ==lim EX ()t dt lim EX ()t dt =lim EX T (f ) df TT→∞ 22TT∫∫→∞ ∫T→∞ 2T −−T ∞−∞ trong đĩ kí hiệu và định nghĩa 1 T A[]⋅ =⋅lim []dt T →∞ 2T ∫−T là trung bình theo thời gian. ⇒ Mật độ phổ cơng suất của quá trình, viết tắt PSD (Power Spectral Density), là 1 l 2 PXX ()f = lim EXfT (). (5.4) T →∞ 2T 144
Chương5: Quá trình dừng ∞ PfXX = ∫ PXX ()df. −∞ 2 Trường hợp quá trình ngẫu nhiên {Xt();t∈R} là quá trình dừng thì E(Xt)2 ==X const, do đĩ 2 2 PA==⎡⎤E(Xt) X. XX ⎣⎦⎢⎥ Ví dụ 5.9: Xét quá trình ngẫu nhiên Xt()= Acos(2π f0t+Θ), trong đĩ A và f0 là hai hằng số, Θ là biến ngẫu nhiên cĩ phân bố đều trên khoảng(0; π/2) . Ta tính trực tiếp cơng suất trung bình của tín hiệu: ⎡ AA22 ⎤ E(⎡⎤Xt22)=+E⎡Acos22ππftΘ⎤=E+cos4ft+2Θ ⎣⎦⎣ ()00⎦⎢ ()⎥ ⎣⎢ 22 ⎦⎥ π /2 AA222 A2A2 =+ cos()4πθf td+2 θ=−sin ()4πft 22∫ ππ002 0 T ⎡⎤22 2 ⎡⎤2 1 AA A PAXX ==E(Xt) lim ⎢⎥−sin()4π f0tdt=. ⎣⎦⎢⎥()T →∞ 22T ∫ π 2 −T ⎣⎦⎢⎥ Cũng cĩ thể tính qua mật độ phổ cơng suất như sau: ∞ TT l −−if22ππt ift −if2πt X T ()f==∫∫XT (t)edtX(t)edt=∫Acos(2π f0t+Θ)edt −∞ −TT− AATT =+eiiΘ−e2(ππif00−−f)tdt e Θe 2if(+f)tdt 22∫∫ −−TT sin2π (f −+fT) sin2π (f f)T =+ATeiiΘ−00ATe Θ 2(ππf −+fT00) 2(f f)T 2 sin 2π ( f − fT) sin 2π ( f+ f)T l 22⎡⎤2 2 00 XfT () =+AT⎣⎦αβ+2αβcos2Θ, α==; β 2(ππf −+fT00) 2(f f)T Vì Ec[ os2Θ=] 0, do đĩ 22 2 2 ⎡⎤ 1 l ATπ ⎛⎞sin 2ππ( ff−+00)T T⎛sin 2 ( ff)T⎞ E(XfT )=+⎢⎥⎜⎟⎜⎟ 22Tf⎢⎥ππ2(−+f)Tππ2(ff)T ⎣⎦⎝⎠00⎝⎠ Sử dụng kết quả (Lathi, 1968: An Introduction to Random Signals and Communication Theory, International Textbook, Scranion, Pennsylvania. p.24) 145
Chương5: Quá trình dừng 2 Ta⎡⎤sin T lim ⎢⎥= δ (a) . T →∞ π ⎣⎦aT 2 1 l 2 A π PXX ()f ==lim EXfT () []δ2π(f−f00)+δ2π(ff+) T →∞ 22T ∞∞A22π A Vậy P ==P ()f df []δπ2(f −f )+δπ2(f +f )df =. XX ∫∫XX 2200 −∞ −∞ Tính chất mật độ phổ cơng suất 1. PXX (f ) là hàm thực 2. PXX ()−=f PXX (f ) nếu X (t) là quá trình thực 3. PXX ()f ≥ 0 ∞ 2 4. ()f df = A⎡⎤EX (t) ∫ PXX ⎣⎦ −∞ ∞ if2πτ 5. ∫ PXX ()f edf=+A[]RXX (tτ ,t) ; −∞ ∞ −if2πτ PXX ()f =+∫ AR[]XX (t τ ,t)e dτ . −∞ 6. Đặc biệt nếu X (t) là quá trình dừng với hàm tự tương quan RXX (τ ) thì ∞ ∞ ifτπ2 −if2πτ RXX ()τ = ∫ efPXX ( )df và PXX ()f = ∫ eRXX (τ )dτ . −∞ −∞ Định nghĩa 5.1: Giả sử {Xt();t∈ I} quá trình dừng với hàm tự tương quan RXX . Nếu tồn tại PXX (f ) sao cho: 1/2 in2π f RXX ()ne= ∫ PXX (f)df khi I = (5.5) −1/2 hoặc ∞ ifτπ2 RXX ()τ = ∫ ePXX (f)df khi I = (5.6) −∞ thì PXX (f ) được gọi là mật độ phổ của quá trình dừng {Xt();t∈ I} . ∞ Định lý 5.2: 1) Trường hợp thời gian rời rạc I = : Nếu ∑ RnXX ()<∞ thì tồn tại mật độ n=−∞ phổ 146
Chương5: Quá trình dừng ∞ −in2π f PXX ()f = ∑ eRXX (n). (5.7) n=−∞ 2) Trường hợp thời gian liên tục I = : Nếu RXX (τ ) khả tích tuyệt đối trên thì tồn tại mật độ phổ ∞ −if2πτ PXX ()f = ∫ eRXX (τ )dτ . (5.8) −∞ Như vậy hàm mật độ phổ là biến đổi Fourier của hàm tự tương quan và hàm tự tương quan là biến đổi Fourier ngược của mật độ phổ. −1 PXX ()f ==FF{RRXX (ττ)} , XX () {PXX (f)} . (5.9) Định lý 5.3: (Định lý Wiener - Khintchine) Mật độ phổ cơng suất PSD của quá tình dừng {Xt();t∈ I} cĩ giá trị trung bình E(Xt)= 0 bằng mật độ phổ của quá trình này và bằng biến đổi Fourier của hàm tự tương quan: ∞ 1 l 2 PXX ()f = lim EXfT () và ta cĩ PXX = PXX ()fdf (5.10) T →∞ T ∫ −∞ Nhận xét: Định lý 5.3 cho ta ý nghĩa của khái niệm mật độ phổ của quá trình dừng, đĩ là mật độ phổ cơng suất của quá trình. Như vậy ta cĩ thể tính mật độ phổ của một quá trình dừng theo 2 cơng thức khác nhau (5.7)-(5.8) hoặc (5.9). Tuy nhiên tồn tại quá trình ngẫu nhiên khơng dừng (khơng cĩ mật độ phổ) nhưng cĩ mật độ phổ cơng suất. Ví dụ 5.10: Xét quá trình tín hiệu cực với dữ liệu nhị phân X (t) ∞ X ()tA=−∑ nby(tnT), (5.11) n=−∞ ⎪⎧ b , { An} là dãy các biến ngẫu nhiên độc lập biểu diễn các dữ liệu nhị phân. Các biến ngẫu nhiên An cĩ phân bố rời rạc nhận hai giá trị ±1 đồng khả năng. 11 Vậy PA{ ==11} PA{ =−} =1/2; E0[]AA= ;var[]==E⎡⎤A221+(−1)2=1; nn nn⎣⎦n22 cov[AAnm, ] =−E[AnAm] E[ An]E[ Am] =0 . Đặt T = (2N +1)Tb thì quá trình XT (t) của quá trình (5.7) sẽ là N XTn()tA=−∑ y(tnTb) nN=− 147
Chương5: Quá trình dừng NN N l −−inωωTbbinT XfT ()==FF{}XTn(t) ∑∑A {}y(t−nTb)=AnY()fe =Y()f∑Ane n=−N nN=− nN=− Trong đĩ Yf()==F {y(t)} Tbsinc(Tbf) (ví dụ 2.37 chương II) 2 ⎡⎤N l 2 −−inω ()mTb ⇒=E(XfT )E⎢⎥Y(f)∑ AnmAe ⎣⎦⎢⎥nm, =−N N N 2 22 ⎡⎤−−inω ()mTb = Yf() ∑ E⎣⎦AnmA e = Yf() ∑ 1=+Yf()(2N 1). nm, =−N nN=− Vậy mật độ phổ cơng suất PSD 22 1 l 2 Yf()(2N+1) Y()f 2 lim E X T ( fT) ==lim =bbsinc ()Tf. TT→∞ TN→∞ (2 +1)TbbT ⎡⎛⎞∞∞⎛ ⎞⎤ Tuy nhiên E(Xt)Xt(+τ)=E Ay(t−nT) Ay(t+τ−mT) []⎢⎜⎟∑∑nb⎜m b⎟⎥ ⎣⎢⎝⎠nm=−∞ ⎝=−∞ ⎠⎦⎥ ∞∞ ∞ =−∑∑E([]AnmAytnTb)y(t+τ−mTb)=−∑ yt()nTbby(t+τ−mT) nm=−∞ =−∞ n=−∞ ⎪⎧ 1/nÕu t−<nTTbb2vµ t+τ −nTTb<b/2 trong đĩ yt()−+nTbbyt(τ −mT)=⎨ ⎩⎪ 0 nÕu ng−ỵc l¹i Điều này chứng tỏ E([ Xt)Xt(+ τ)] cịn phụ thuộc vào thời điểm t nên quá trình X (t) khơng dừng. Ví dụ 5.11: (Sĩng ngẫu nhiên nhị phân) Xét quá trình ngẫu nhiên {Xt();t∈} gồm các bit 1 và các bit 0 thoả mãn các điều kiện sau: 1) Bit 1 và 0 lần lượt được biểu diễn bởi các xung chữ nhật với biên độ + A và − A volt với độ rộng của xung là T giây. 2) Các hàm mẫu (sample functions) là khơng đồng bộ và giả thiết rằng thời điểm xuất phát của xung thứ nhất td xảy ra đồng khả năng trong khoảng từ 0 đến T. Điều này cĩ nghĩa là td là giá trị mẫu của biến ngẫu nhiên Td cĩ phân bố đều trong đoạn []0;T . 3) Trong khoảng thời gian xung bất kỳ (n −1)T < t − td < nT , hai bit 1 và 0 là đồng khả năng xuất hiện, nghĩa là X (t) nhận giá trị + A hoặc − A trong suốt khoảng xung này với xác suất 1 2 . X (t) và X (s) là độc lập nếu t, s ở trong khoảng xung thời gian khác nhau. Ta cĩ: ∀=tX;E (t) A×12+(−A)×12=0. Hàm tự tương quan: RXXk(,t ti)= E[ Xt(k),Xt(i)]. 148
Chương5: Quá trình dừng * Nếu tk − ti > T thì Xt()k,Xt(i) độc lập ⇒=rtxk(,ti) E[ X(tk),X(ti)] =0. * Nếu tk − ti < T và giả sử rằng Xt()k,Xt(i) cùng cĩ trễ là td thì Xt()k,Xt(i) cùng xung khi và chỉ khi tk − ti < T − td . 0 1 0 1 1 t td ⎧ 2 ⎪At nÕu dk< T−−tti Vậy E(⎡⎤⎣⎦Xtki),Xt()td= ⎨ ⎩⎪0 nÕu ng−ỵc l¹i. Áp dụng cơng thức xác suất đầy đủ Tt−−kit T−−tkti 2 22A ⎛⎞ttk− i E([]Xt),Xt()==Af (t)dt dt =A⎜⎟1−. ki ∫∫Td dd TTd 00⎝⎠ ⎧ 2 ⎛τ⎞ ⎪A ⎜⎟1− nÕu τ<T Đặt τ = tk − t ⇒ Hàm tự tương quan RXX ()τ=⎨ ⎝⎠T ⎪ ⎩ 0. nÕu τ≥T Mật độ phổ cơng suất T 22⎛τ⎞-i πfτ 22 PFXX ()fR=τ{}XX ()=A⎜⎟1−edτ =ATsinc(fT). ∫ T -T ⎝⎠ Ví dụ 5.12: Nhiễu trắng (White Noise) được mơ tả như là một quá trình dừng (theo nghĩa N0 rộng) mà mật độ phổ cơng suất là một hằng số PW ( f ) = . 2 Hệ số 1 2 để chỉ một nửa cơng suất ứng với tần số dương và một nửa ứng với tần số âm. N0 cĩ đơn vị watt/ hertz. Hàm tự tương quan -1 ⎧⎫NN00 RWW ()τ ==F ⎨⎬ δτ(). ⎩⎭22 PW ( f ) RWW ()τ N0 2 (N0 2)δ(τ) 149 0 0 f τ
Chương5: Quá trình dừng Quá trình nhiễu trắng khơng phải là một quá trình vật lý cĩ thực vì cĩ cơng suất bằng ∞ . Trong quang học, mật độ phổ năng lượng của ánh sáng trắng là khơng đổi P (υ)= hằng số với mọi tần số υ (Năng lượng ánh sáng trắng phân bố đều theo mọi tần số υ). Vì vậy nhiễu với mật độ phổ hằng số được gọi là nhiễu trắng. 5.2 QUÁ TRÌNH DỪNG ERGODIC Trung bình theo thời gian được định nghĩa như sau 1 T A[]⋅ =⋅lim []dt T →∞ 2T ∫−T Trung bình theo thời gian được lấy qua mọi thời điểm, vì vậy trung bình theo thời gian của một quá trình ngẫu nhiên được lấy theo các hàm mẫu phụ thuộc thời gian. Đối với quá trình dừng X (t) ta quan tâm trung bình theo thời gian của hàm mẫu và tự tương quan theo thời gian của hàm mẫu x(t) 1 T x ==Ax[]()t lim x(t)dt T →∞ 2T ∫−T 1 T RXX ()τ =+A[]xt( ττ)xt()=lim xt()xt(+)dt T →∞ 2T ∫−T Trong nhiều bài tốn về quá trình ngẫu nhiên địi hỏi phải tính các giá trị trung bình của quá trình theo tập hợp. Tuy nhiên trong thực tế ta chỉ nhận được các hàm mẫu của quá trình do đĩ ta chỉ cĩ thể tính được trung bình theo thời gian. Ta cĩ thể lấy trung bình theo thời gian thay cho trung bình theo tập hợp hay khơng? Giả thiết Ergodic cho rằng trung bình theo thời gian ở các cấp trùng với trung bình theo tập hợp cùng cấp tương ứng. Giả thiết này đáng tiếc là khơng phải luơn đúng như một số các nhà kỹ thuật đầu thế kỷ 20 tin tưởng. Khoảng năm 1931 hai nhà tốn học G. D. Birkhoff (Mỹ) và A. Ia. Khintchine (Nga) đã chứng minh rằng trung bình theo thời gian luơn luơn tồn tại và đã chỉ ra các điều kiện để nĩ trùng với trung bình tập hợp. Các định lý sau chỉ ra các điều kiện quá trình dừng là quá trình ergodic. Định lý 5.4: Quá trình dừng thời gian rời rạc {Xn();n≥ 0} với hàm tự tương quan RXX (n) là ergodic khi và chỉ khi 1 n lim RmXX ( ) = 0 . (5.12) n→∞ ∑ n m=0 Định lý 5.5: Quá trình dừng {Xt();t∈R} với hàm tự tương quan RXX (τ ) là ergodic khi và chỉ khi 150
Chương5: Quá trình dừng 1 TT lim RtXX ( − s)dtds= 0 . (5.13) T →∞ 2 ∫∫ T 00 Định lý 5.6: Quá trình dừng {Xt();t∈R} với hàm tự tương quan RXX (τ ) là ergodic khi và chỉ khi T 1 ⎛⎞t lim ⎜⎟1− RXX (td) t= 0 . (5.14) T →∞ TT∫ 0 ⎝⎠ Hệ quả: Nếu lim RXX (τ ) = 0 thì quá trình {Xt();t∈R} là ergodic. τ →∞ Ví dụ 5.13: Xét quá trình ngẫu nhiên Xt()= Acos(ω+0t Θ). Trong đĩ A, ω0 là hai hằng số. Θ là biến ngẫu nhiên cĩ phân bố đều trên đoạn [0;2π] với hàm mật độ ⎧ 1 ⎪ nÕu 02≤ u ≤π fuΘ ()= ⎨ 2π ⎩⎪ 0 nÕu ng−ỵc l¹i 2π ∞ 1 E([]X tA)=ωE[]cos(t+Θ)=Acos(ωt+u)f(u)du= A cos(ω t + u) du = 0 00∫ Θ ∫ 0 2π −∞ 0 RtXX (,t+τ)=E[ X(t)X(t+τ)] =E[ Acos(ω00t+Θ)Acos(ω (t+τ)+Θ)] A2 =ωEc⎡⎤os()(2t +τ)+2Θ+cosτ 2 ⎣⎦0 AA22 =ωE ⎡⎤cos()(2t +τ) +2Θ+E[]cos τ=cos τ 22()⎣⎦0 A2 Như vậy {Xt()} là một quá trình dừng với hàm tự tương quan R ()τ = cosτ . XX 2 T 1 ⎛ τ ⎞ A2 A2 ⎛ T 1 T T ⎞ ⎜1− ⎟ cosτdτ= ⎜sin τ − (τsin τ + cosτ )⎟ T ∫ T 2 2T 0 T 0 0 0 ⎝ ⎠ ⎝ ⎠ A2 ⎛ 1− cosT ⎞ = ⎜sinT − sinT + ⎟ → 0 khi T → ∞ 2T ⎝ T ⎠ Theo định lý 5.6 {Xt()} là một quá trình dừng thoả mãn điều kiện (5.14) do đĩ là một quá trình ergodic. Ta cũng cĩ thể kiểm chứng điều này bằng cách tính trực tiếp như sau: Vì quá trình tuần 2π hồn theo thời gian với chu kỳ T0 = nên trung bình theo thời gian ω0 151
Chương5: Quá trình dừng T T 110 ⎛⎞sin(ω+t θ) 0 Acos(ω+tdθ) t= ⎜⎟A 0 =0 =E[]X(t) TT∫ 0 ⎜⎟ω 000 ⎝⎠00 T 1 0 A2 A22cos (ω+tdθ) t= =R(0) =E ⎡X2(t)⎤ . T ∫ 0 2 XX ⎣ ⎦ 0 0 5.3 BỘ LỌC TUYẾN TÍNH Giả sử X (t) là một quá trình dừng và h(t) là hàm khả tích tuyệt đối. Ta xác định quá trình mới L{(X t)} ∞ L{X (tY)}==()t∫ h(t−s)X(s)ds=h()t∗X()t (5.15) −∞ được gọi là bộ lọc tuyến tính với đáp ứng xung h(t) (impulse response). Hàm H( f ) = F {h(t)} được gọi là hàm truyền đạt (transfer function) của bộ lọc. Trường hợp quá trình với thời gian rời rạc { Xn();n≥ 0} và đáp ứng xung là dãy {}h(n) , n = 0,±1,± 2, thì đầu ra cĩ dạng ∞ L{(X nY)}==(n) ∑ h(n−m)X(m); m=−∞ ∞ Hàm truyền đạt H ( f ) = ∑h(m)e−i2πmf . m=−∞ Định lý 5.7: Đầu ra Yt() của bộ lọc tuyến tính (5.11) cũng là quá trình dừng với hàm tự tương quan RhYY ()τ = (−∗ττ) h()∗RXX (τ) (5.16) và mật độ phổ 2 PY()f = Hf()PX(f) (5.17) Ví dụ 5.14: Lọc thơng thấp (RC low - pass filter). Xét mạch điện như hình vẽ, trong đĩ điện trở thuần R , tụ điện cĩ điện dung C ; điện áp đầu vào X (t), điện áp đầu ra Yt(). dy Áp dụng định luật Kirchoff ta được RC + y(t) = x(t) dt R i(t) X (t) Yt() C 152
Chương5: Quá trình dừng Trường hợp x(t) là tất định (deterministic): y(t) = h(t)∗ x(t) , bằng cách áp dụng phép biến đổi Fourier ta tính được ⎪⎧()10RC e−tRC nÕu t ≥ ht()= ⎨ ⎩⎪ 00 nÕu t < 1 Hf()==Yl()f lX()f 1(+πiR2C)f Do đĩ nếu X (t) là quá trình dừng, theo cơng thức (5.17) ta được mật độ phổ của đầu ra của lọc thơng thấp 1 PPYX()f = ()f 14+ π 22RC2f2 N0 Nếu đầu vào Wt() là nhiễu trắng với hàm mật độ phổ cơng suất PW ( f ) = thì đầu 2 2 N0 2 ra PPYX()fH==()f ()f . 14+π2R2Cf22 Sử dụng biến đổi Fourrier ngược ta cĩ ⎧⎫NN2 −1 00−τ RC ReYY ()τ ==F ⎨⎬2222 ⎩⎭14+ π RC f 4RC N Cơng suất trung bình Py==E(⎡⎤2 t)R(0)=0 . YY⎣⎦Y4RC 5.4 QUÁ TRÌNH NGẪU NHIÊN GAUSS Định nghĩa 5.5. Quá trình ngẫu nhiên {Xt()} gọi là quát trình Gauss nếu với mọi N và mọi t1 , t2 , , tN ( Xt( 12), Xt( ), , Xt( N ) ) là véc tơ ngẫu nhiên cĩ phân bố Gauss N chiều. Như vậy hàm mật độ của ()Xt( 12), Xt( ), , Xt( N ) cĩ dạng −1 ()xm−−C−1()xmt 1 2 fxXN( 12, x, , x) = e (5.18) 2dπ etC trong đĩ x = (x12, x, , xN ) ; m =( mm12, , ,mNi), m=E[ X(ti)]; ma trận vuơng hiệp phương sai CC= ⎡⎤ ; CX= cov ⎡ (t), X(t)⎤ . ⎣⎦ij N×N ij ⎣ i j ⎦ 153
Chương5: Quá trình dừng Quá trình Gauss là quá trình dừng nếu 2 mxii=E([ t)] =m=hằng số và Cmij + =RXX (ti −tj ). (5.19) Ngồi ra, nếu X ()tXij, (t);∀≠ij khơng tương quan, nghĩa là ⎡⎤ ⎡ ⎤ E(⎣⎦Xtij)Xt()= E[]Xt(i)E(⎣Xtj)⎦ thì ma trận hiệp phương sai cĩ dạng ⎡σ 2 00" ⎤ ⎢ ⎥ ⎢ 0σ 2 " 0⎥ C = ⎢ ⎥ (5.20) ⎢ ##%#⎥ ⎢ 2 ⎥ ⎣ 00" σ ⎦ 2 trong đĩ σ=RXXi(0) =cov[ Xt( ), Xt( i)]. Quá trình Gauss cĩ các tính chất sau: 1) f X chỉ phụ thuộc vào ma trận M và vectơ m , vì vậy véc tơ ngẫu nhiên Gauss chỉ phụ thuộc vào các moment cấp 1 và cấp 2. 2) (Xt( 12), Xt( ), , Xt( N ) ) là véc tơ ngẫu nhiên cĩ phân bố Gauss N chiều, do đĩ các biến ngẫu nhiên thành phần Xt(i ) cũng cĩ phân bố Gauss. 3) Các biến ngẫu nhiên thành phần Xt()12,Xt( ), ,Xt(N ) độc lập khi và chỉ khi khơng tương quan. Điều này xảy ra khi ma trận hiệp phương sai C là ma trận đường chéo dạng (5.20). 4) Hàm mật độ đồng thời của quá trình Gauss (cơng thức 5.18) chỉ phụ thuộc giá trị trung bình và hiệp phương sai. Vì vậy quá trình Gauss dừng theo nghĩa rộng khi và chỉ khi dừng theo nghĩa chặt (Xem Chanmugan & Breipoht, 1988, trang 141). 5) Nếu (Xt( 12), Xt( ), , Xt( N ) ) là một véc tơ ngẫu nhiên Gauss thì (Yt( 12), Yt( ), ,Yt( N )) cũng là một véc tơ ngẫu nhiên Gauss, với t []Yt( 12), Yt( ), ,Yt( NN) = A[X(t1), X(t2), , X(t )] trong đĩ A là một ma trận vuơng cấp N bất kỳ. Từ tính chất 5) người ta cĩ thể chứng minh được kết quả rộng hơn như sau. Định lý 5.8: Đầu ra của một quá trình Gauss qua lọc tuyến tính là một quá trình Gauss. Nghĩa là nếu X (t) là quá trình Gauss thì ∞ Y()t = ht()∗=X()t ∫ ht( −λ)X(λ)dλ −∞ cũng là một quá trình Gauss. 154
Chương5: Quá trình dừng Ví dụ sau minh họa tính chất 4) Ví dụ 5.15: Giả sử X (t) là quá trình Gauss dừng với hàm trung bình mt()= 4 và hàm tự −3|τ| tương quan RXX ()τ = 25e . Ta cĩ thể tìm được hàm mật độ đồng thời của ba biến ngẫu k −1 nhiên Xt(), k =1, 2, 3 tại các thời điểm tt=+ , với t là hằng số. k k 0 2 0 k− i Vì tt−= , i và k =1, 2, 3 . ki 2 −−3|ttki|/ 2 Vậy RtXX ()k −=ti 25e −−3|ttki|/ 2 và CtXX ( k −=ti ) 25e −16 . Do đĩ ma trận hiệp phương sai của ba biến ngẫu nhiên Xt(1), Xt()2 , Xt(3) ⎡⎤(25−−16) (25ee−−3/2 16) (25 6/2 −16) ⎢⎥−−3/2 3/2 Ce=−⎢⎥(25 16) (25 −16) (25e−16) . ⎢⎥−−6/2 3/2 ⎣⎦(25ee−−16) (25 16) (25 −16) BÀI TẬP 5.1 Cho Xt() là một quá trình dừng với hàm trung bình E(X tm)=,∀t. Chứng minh { }t∈I rằng Yt() , Yt()=X(t)−m là quá trình dừng cĩ hàm trung bình E(Yt)=0,∀t và { }t∈I hàm tự tương quan RYY = RXX . 5.2 Cho Xt() là một quá trình cấp 2 cĩ tính chất E(X s) và E(X sX)(s+ t) khơng phụ { }t∈I thuộc vào s . Chứng minh rằng Xt() là quá trình dừng. { }t∈I 5.3 Cho Xt() là một quá trình dừng với hàm tự tương quan R (τ ). Chứng minh rằng { }t∈I XX Yt() , Yt()= X(t+−1) X(t) cũng là quá trình dừng. Tìm hàm trung bình và hàm tự { }t∈I tương quan. 5.4 Cho Θ là biến ngẫu nhiên liên tục cĩ phân bố đều trên đoạn [0,2π], A0 ,ω0 là hai hằng số. Chứng minh rằng Xt()=ωA00sin( t+Θ) là một quá trình dừng. Tìm hàm tự tương quan. Quá trình X (t) cĩ phải là quá trình ergodic? 5.5 Cho Θ là biến ngẫu nhiên liên tục cĩ phân bố đều trên đoạn [0,2π], R là biến ngẫu ⎧ −r2 ⎪ r 2σ2 nhiên liên tục cĩ hàm mật độ f (r) = e , nÕu 0 0 . Chứng minh rằng Xt()= Rcos(λ+t Θ)là một quá trình 2 dừng với trung bình 0 và hàm tự tương quan RXX ()tt= σ cosλ . 155
Chương5: Quá trình dừng 5.6 Cho A là biến ngẫu nhiên cĩ phân bố chuẩn N(0;σ 2 ) . Đặt X ()tA=cos(10πt). Tìm hàm mật độ xác suất của X (t). Quá trình Xt() cĩ phải là quá trình dừng khơng? { }t∈I 5.7 Cho Z1 và Z2 là hai biến ngẫu nhiên độc lập cĩ cùng phân bố xác suất 1 P{}Z = −1 = P{Z = 1}= . Đặt X()t= Ztcosλ+Zsinλt, λ là hằng số. Chứng minh 1 1 2 12 Xt() là quá trình dừng. Tìm hàm tự tương quan. { }t∈I 5.8 Cho quá trình dừng Xn()∞ cĩ trung bình E(Xn)2 và hàm tự tương quan {}n=−∞ = n 13⎛⎞ RnXX ()=−⎜⎟. Tìm mật độ phổ. 74⎝⎠ 5.9 Cho W (t) là quá trình Wiener với tham số σ2 . Đặt Xt()= e−ααttW(e2 ), α > 0 là hằng số. Chứng minh rằng x(t) là quá trình Gauss dừng với hàm tự tương quan 2 −α t RtXX ()= σ e , − ∞ < t < ∞ . Tìm mật độ phổ. ⎧ 1 nÕu ⎪ 2 ()B −≤ff, B 5.10 Cho quá trình dừng ergodic X (t) cĩ mật độ phổ PX ()f = ⎨σ . ⎩⎪ 0, nÕu ng−ỵc l¹i Tìm hàm tự tương quan. 156
Chương 6: Quá trình Poisson CHƯƠNG VI: QUÁ TRÌNH POISSON GIỚI THIỆU Quá trình Poisson là dạng đặc biệt của quá trình Markov với thời gian liên tục. Quá trình Poisson X (t) mơ tả quá trình đếm số lần xuất hiện một biến cố A nào đĩ cho đến thời điểm t . Quá trình Poisson được ứng dụng nhiều trong viễn thơng, liên quan đến bài tốn truyền tín hiệu, các hệ phục vụ, bài tốn chuyển mạch Nếu số cuộc gọi đến một tổng đài là một quá trình Poisson, mỗi cuộc gọi chiếm dụng thiết bị trong một khoảng thời gian nào đĩ, giả sử các khoảng thời gian này là các biến ngẫu nhiên độc lập cùng phân bố, khi đĩ tổng số giờ gọi là một quá trình Poisson phức hợp. Quá trình Poisson X (t) mơ tả quá trình đếm số lần xuất hiện một biến cố A nào đĩ cho đến thời điểm t . Giả sử biến cố A được phân thành 2 loại A1, A2 và tại mỗi thời điểm việc xuất hiện biến cố A1 hoặc A2 là độc lập nhau, khi đĩ ta cĩ quá trình Poisson cĩ phân loại. Quá trình Poisson phức hợp và quá trình Poisson phân loại giúp ta tính được sản lượng trung bình khi khai thác dịch vụ viễn thơng. Trong chương này chúng ta khảo sát các vấn đề sau: • Quá trình đếm, quá trình điểm. • Quá trình Poisson. • Các phân bố liên quan đến quá trình điểm Poisson: thời điểm đến thứ n (hay thời gian chờ) và khoảng thời gian giữa hai lần đến liên tiếp thứ n . • Quá trình Poissson cĩ phân loại. • Quá trình Poisson phức hợp. Quá trình Poisson là cơ sở quan trọng để khảo sát quá trình sắp hàng được nghiên cứu trong chương tiếp theo. Để học tốt chương này học viên phải nắm các kiến thức cĩ bản của lý thuyết xác suất. 6.1 KHÁI NIỆM QUÁ TRÌNH POISSON 6.1.1 Quá trình đếm Quá trình đếm rất thường gặp trong thực tế. Giả sử A là biến cố nào đĩ. Ký hiệu X (t), t > 0 là số lần biến cố A xuất hiện trong khoảng thời gian từ 0 đến t . Khi đĩ {X (t), t > 0} được gọi là quá trình đếm. Chẳng hạn ta cĩ những ví dụ sau về quá trình đếm: A là biến cố khách vào điểm phục vụ nào đĩ. Khi ấy X (t) là số khách vào điểm phục vụ tính đến thời điểm t . 157
Chương 6: Quá trình Poisson A là biến cố cĩ cuộc gọi đến một tổng đài nào đĩ. Khi ấy X (t) là số cuộc gọi đến tổng đài tính đến thời điểm t . Quá trình đếm {X (t); t ≥ 0} cĩ các tính chất đặc trưng sau: 1. X (0) = 0 ; (6.1) 2. X (t) chỉ nhận giá trị là các số tự nhiên; (6.2) 3. X (s) ≤ X (t), 0 ≤ s ≤ t . (6.3) 6.1.2 Quá trình Poisson Định nghĩa 6.1: Ta nĩi rằng quá trình {X (t); t ≥ 0} là quá trình Poisson với cường độ λ (hoặc tham số λ ) nếu: i) X (0) = 0 ; ii) X (t) chỉ nhận giá trị là các số tự nhiên; iii) {X (t); t ≥ 0} là quá trình cĩ gia số độc lập, tức là, với bất kỳ 0 = t0 0 . Định lý 6.1: Nếu quá trình đếm {X (t); t ≥ 0} thỏa mãn các điều kiện sau: 1. Cĩ gia số độc lập, tức là ∀m = 2,3, và với mọi 0 = t0 0. ∀0 ≤ t1 0 (tốc độ xuất hiện biến cố A ) sao cho với h > 0 khá bé thì PX{ ()h==1} λh+o(h). (6.4) 4. Với h > 0 khá bé thì PX{ ()h≥=2} o(h), (6.5) thì {X (t); t ≥ 0} là quá trình Poisson tham số λ. Ngược lại, quá trình Poisson là quá trình đếm thỏa mãn 4 điều kiện trên. 158
Chương 6: Quá trình Poisson Chứng minh: Điều kiện i), ii) của định nghĩa quá trình Poisson được suy từ tính chất của quá trình đếm. Từ 1) ta suy ra điều kiện iii). Theo 2) để chứng minh điều kiện iv) ta chỉ cần chứng minh X (t) cĩ phân bố Poisson P (λt) . Đặt pn (t) = P{X (t) = n }, n = 0,1,2, p0 (t + h) = P{}X (t + h) = 0 = P{X (t) = 0, X (t + h) − X (t) = 0} ==p00()tp(h) p0()t(1−λh+o(h)) , pt()+−h p(t) oh() 00=−λpt()+ ⇒ p'(t)=−λpt() ⇒ pt()=Ce−λt . hh0000 p (0) = 1 ⇒ p (t) = e−λt ; t ≥ 0 . 0 0 Tương tự pn (t + h) = P{}X (t + h) = n = P{X (h) = 0, X (t + h) − X (h) = n } + P{}X (h) = 1, X (t + h) − X (h) = n −1 + ∑ P{X (h) = k , X (t + h) − X (h) = n − k } k≥2 =+ph01()pnn(t) p()hp−−1(t)+∑ pnk(t)o()h= (1 −λhp) nn(t) +λhp−1(t) +o(h) k≥2 ⇒ pn '(t) = −λ pn (t) + λ pn−1(t) . Đặt biến đổi Laplace của pn (t) là Pn (s) = L { pn (t) } λ ⇒ L {}p '(t) = sP (s) = −λP (s) + λP (s) ⇒ P (s) = P (s) n n n n−1 n λ + s n−1 n n nn ⎛⎞λλ −1 ⎧⎫λλnt−λ ⇒=Ps() P()s= pt() te . n ⎜⎟0 n+1 ⇒=n L ⎨⎬n+1 = ⎝⎠λ+s ()λ+s ⎩⎭()λ+sn! Vậy X (t) cĩ phân bố Poisson P (λt) . Ngược lại nếu {X (t); t ≥ 0} là quá trình Poisson tham số λ thì X (t) cĩ phân bố Poisson P (λt) nên E[]X (t) = var[X (t)]= λt . Khai triển Taylor ta cĩ PX{ ()h==0} e−λh =1−λh+o(h) khi h → 0, PX{ ()h==1} λhe−λh =λh(1−λh+o()h)=λh+o(h) khi h → 0. Do đĩ PX{ ()h≥2} =1−=P{X()h 0} −=PX{ (h) 1} =o(h) khi h → 0. Nhận xét 6.1: Giả sử quá trình {X (t); t ≥ 0 } đếm số lần xuất hiện biến cố A là quá trình Poisson tham số λ > 0 thì λ = E[ X (1)] (6.6) Như vậy λ là số lần trung bình xảy ra biến cố A trong khoảng 1 đơn vị thời gian. Nếu quá trình {X (t); t ≥ 0 } đếm số khách đến điểm phục vụ thì λ là tốc độ đến trung bình. 159
Chương 6: Quá trình Poisson 6.1.3 Các phân bố liên quan đến quá trình Poisson Định nghĩa 6.2: Giả sử {X (t); t ≥ 0} là quá trình Poisson đếm số lần xuất hiện biến cố A . 1) Ta ký hiệu Tn là thời điểm đến (arrival time) (hay thời gian chờ, waiting time) thứ n , đĩ là thời điểm mà biến cố A xuất hiện lần thứ n . Quy ước T0 = 0 . 2) Ký hiệu t là khoảng thời gian giữa n t3 2 lần đến liên tiếp thứ n (interarrival time), đĩ là khoảng thời gian tính từ thời điểm t2 t biến cố A xảy ra lần thứ n −1 đến thời 1 điểm xảy ra biến cố A lần thứ n . O T T T t Vậy tTnn=−Tn−1 . 1 2 3 Định lý 6.2: 1. Các thời gian đến trung gian t1 ,t2 , ,tn là các biến ngẫu nhiên độc lập cĩ cùng phân bố mũ tham số λ với hàm mật độ f ()te= λ≥−λt ;t0. (6.7) tn 2. Tn cĩ phân bố Erlang tham số n,λ với hàm mật độ λnnt −1 f ()te= −λt ;t≥ 0. (6.8) Tn (1n − )! Đặc biệt T1 cĩ phân bố mũ. 3. Với mọi 0 < s < t và 0 ≤ k ≤ n k n−k n! ⎛ s ⎞ ⎛ s ⎞ P{}X (s) = k X (t) = n = ⎜ ⎟ ⎜1− ⎟ . (6.9) k!(n − k)!⎝ t ⎠ ⎝ t ⎠ Chú ý rằng nếu X12, X, , Xn là các biến ngẫu nhiên độc lập cĩ cùng phân bố mũ tham số λ thì X =+XX12+"+Xn cĩ phân bố Erlang tham số n,λ . Do đĩ cĩ kỳ vọng và phương sai: nn E;[]XX12++"+Xnn=var[]X12++X"+X=. (6.10) λ λ2 Ví dụ 6.1: Giả sử số khách đến cửa hàng nào đĩ là 1 quá trình Poisson với tốc độ λ = 4 khách/ giờ. Cửa hàng mở cửa lúc 8h. 1. Tính xác suất để đến 8h30 cĩ cả thảy 1 khách; đồng thời đến 10h30 cĩ cả thảy 5 khách đến cửa hàng. 2. Tính thời điểm trung bình khách thứ 10 tới. 3. Tính xác suất để khoảng thời gian giữa khách thứ 10 và khách thứ 11 lớn hơn 1/2 giờ. Giải: 1. Xem t0 = 8h. Vậy xác suất cần tìm là 160
Chương 6: Quá trình Poisson P{}X (1 2) = 1; X (5 2) = 5 = P{X (1 2) = 1; X (5 2) − X (1 2) = 4} 84 = P{}X (1 2) = 1 .P{X (2) = 4}= 2.e−2. e−8 ≈ 0,0155 . 4! 10 10 2. ET (10) ===2h30'. λ 4 1 ⎛⎞−×4 3. Pt{}>=12 1−Pt{}<12 =1−⎜⎟1−e 2 =e−2 ≈0,135. 11⎜⎟ ⎝⎠ Ví dụ 6.2: Cho hai quá trình Poisson độc lập {X1(t);t ≥ 0 } và {X 2 (t);t ≥ 0 } với các tham số tương ứng λ1 ,λ2 . Tìm xác suất để X1(t) = 1 trước khi X 2 (t) = 1. 12 1 Giải: Ta cần tìm xác suất PT{ 1< T1} , trong đĩ Tn là thời điểm đến thứ n của quá trình X1(t) 2 cịn Tm là thời điểm đến thứ m của quá trình X 2 (t) . ∞∞ λ P T 12<=T λe−λ12xyλe−λ dxdy =λe−λ12xλe−λ ydxdy =1 {}11∫∫ 12 ∫ ∫ 12 00≤<xy x λ+12λ Tổng quát, ta cĩ thể chứng minh cơng thức sau kn+−m1−k nm+−1 12 k ⎛⎞λλ12⎛⎞ PT{}nm<=T ∑ Cn+−m1 ⎜⎟⎜⎟. (6.11) kn= ⎝⎠λ+12λ ⎝⎠λ12+λ 6.2 QUÁ TRÌNH POISSON CĨ PHÂN LOẠI Xét quá trình Poisson {X (t);t ≥ 0 } với cường độ λ (tương ứng với quá trình đếm số lần xảy ra biến cố A ). Giả sử mỗi khi biến cố A xảy ra thì nĩ được phân thành hai loại: loại I với xác suất p và loại II với xác suất q = 1− p . Hơn nữa, giả sử sự phân loại biến cố này là độc lập với sự phân loại biến cố kia. Chẳng hạn, khách đến cửa hàng theo quá trình Poisson {X (t);t ≥ 0 } với cường độ λ , khách được phân làm hai loại: nam với xác suất 1/2 và nữ với xác suất 1/2. Ta ký hiệu X1(t) và X 2 (t) là quá trình đếm tương ứng với biến cố loại I và biến cố loại II. Rõ ràng là X (t) = X1(t) + X 2 (t) . Định lý 6.3: Với các điều kiện trên ta cĩ X1(t) và X 2 (t) là hai quá trình Poisson với cường độ tương ứng λp và λq . Hơn nữa, hai quá trình này là độc lập. Chứng minh: Theo cơng thức xác suất đầy đủ ∞ P{}X1(t) = n, X 2 (t) = m = ∑ P{}X1(t) = n, X 2 (t) = m X (t) = k P{}X (t) = k . k=0 161
Chương 6: Quá trình Poisson Vì X (t) = X1(t) + X 2 (t) ⇒ P{}X1(t) = n, X 2 (t) = m X (t) = k = 0 ∀ k ≠ n + m , do đĩ P{}X1(t) = n, X 2 (t) = m = P{}X1(t) = n, X 2 (t) = m X (t) = n + m P{X (t) = n + m }. Mặt khác trong n + m biến cố cĩ n biến cố loại I và m biến cố loại II. Do đĩ, từ giả thiết (λt)n+m độc lập của sự phân loại biến cố và P{}X (t) = n + m = e−λt suy ra: (n + m)! (λt)n+m (λtp)n (λtq)m P{}X (t) = n, X (t) = m = C n pnq m e−λt = e−λtp e−λtq 1 2 n+m (n + m)! n! m! ∞ n (λtp) −λtp ⇒ P{}X1(t) = n = ∑ P{X1(t) = n, X 2 (t) = m }= e . m=0 n! Điều này chứng tỏ {X1(t); t ≥ 0 } là quá trình Poisson với cường độ λp . Tương tự {X 2 (t); t ≥ 0 } là quá trình Poisson với cường độ λq . 6.3 PHÂN BỐ ĐỀU VÀ QUÁ TRÌNH POISSON Giả sử ta cĩ một đoạn thẳng chiều dài bằng t và cĩ n hạt cho trước. Ta rải các hạt lên đoạn thẳng này sao cho vị trí của các hạt trên đoạn này lập thành n biến ngẫu nhiên độc lập cĩ phân bố đểu (mỗi hạt đồng khả năng rơi vào từng điểm). Ta ký hiệu U k là vị trí của hạt thứ k ; k = 1,2, ,n . Theo cách rải của ta thì U1, , U n là các biến ngẫu nhiên độc lập cĩ cùng phân bố đều với hàm mật độ. ⎧ 1 ⎪ nÕu 0 ≤ ut≤ fuU ()= ⎨ t ⎩⎪ 0.nÕu ng−ỵc l¹i Bây giờ ta sắp xếp lại dãy các vị trí theo thứ tự từ bé đến lớn. Bằng cách ấy ta được dãy TT12≤≤ ≤Tn , trong đĩ T1 là bé nhất trong số U1, , U n ; tương tự T2 là bé thứ hai trong số U1, , U n . Ta gọi TT12, , ,Tn là thống kê thứ tự của phân bố đều trên đoạn (0; t] . Định lý 6.4: Hàm phân bố đồng thời của TT12, , ,Tn cĩ hàm mật độ là n! fTT, , (ww1, , n) =<víi 0 w1 <w2 < <wn≤t. (6.12) 1 n tn Định lý 6.5: Giả sử {X (t); t ≥ 0} là quá trình Poisson với tham số λ và TT12, , ,Tn là các thời gian đến trong quá trình Poisson này. Khi đĩ, với điều kiện X (t) = n , phân bố đồng thời của TT12, , ,Tn cĩ mật độ n! fTT, , |X(t)=n(ww1, , n) = víi 0 <<w1 w2 < <wn≤t. (6.13) 1 n tn Ý nghĩa của định lý 6.5 là: Với điều kiện cĩ đúng n biến cố xảy ra trong khoảng thời gian (0;t] thì các thời gian đến là thống kê thứ tự của phân bố đều trên đoạn (0;t] . 162
Chương 6: Quá trình Poisson Ví dụ 6.3: Khách đến một cửa hàng theo quá trình Poisson với cường độ λ. Mỗi khách hàng trả 1 nghìn đồng để vào cửa tại thời điểm t = 0. Sau đĩ giá được giảm theo thời gian với tốc độ hạ giá là β . Ta cần tính số tiền trung bình M cửa hàng thu được trong khoảng thời gian (0;t] . −βTk Khách hàng thứ k đến tại thời điểm Tk nên phải trả vé vào cửa với giá e . Gọi N (t) là số khách đến trong khoảng thời gian (0;t] thì ⎛⎞Nt() Me= E −βTk . ⎜⎟∑ ⎝⎠k=1 Theo cơng thức xác suất đầy đủ ta cĩ ∞ ⎛⎞Nt() M ==E(⎜⎟eN−βTk t)nPN(t)=n. ∑∑⎜⎟{} nk==11⎝⎠ Giả sử U1, , U n là các biến ngẫu nhiên độc lập và cĩ phân bố đều trên đoạn [0;t]. Do tính ⎛⎞Nt() chất giao hốn của phép cộng trong cơng thức E e−βTk và định lý 6.5 ta cĩ ⎜∑ ⎟ ⎝⎠k=1 ⎛⎞Nt() ⎛⎞n nnt E(⎜⎟eN−βTUkkt)==nEe−β ==neE1−βU1 e−βutdu=−e−β . ⎜⎟∑∑⎜⎟()∫ () ⎝⎠kk==11⎝⎠ tt0 β 11∞ λ Suy ra Me=−()1(−βtt∑nP{}Nt)=n=()1−e−β EN(t)=()1−e−βt . ββttn=1 β 6.4 QUÁ TRÌNH POISSON PHỨC HỢP Định nghĩa 6.3: Giả sử {X (t);t ≥ 0} là quá trình Poisson với cường độ λ > 0 . Y1, ,Yn dãy các biến ngẫu nhiên độc lập, cùng phân bố và dãy này độc lập với {X (t);t ≥ 0}. Khi đĩ ta gọi X (t) Z(t) = ∑Yk ; t ≥ 0 (6.14) k=1 là quá trình Poisson phức hợp. Ví dụ 6.4: 1. Nếu Yk ≡ 1 thì Z (t) = X (t) . Do đĩ, quá trình Poisson thơng thường là quá trình Poisson phức hợp. 2. Giả sử khách rời cửa hàng là quá trình Poisson và tiền mua hàng của khách là dãy các biến ngẫu nhiên độc lập, cùng phân bố và dãy này độc lập với số khách. Khi đĩ ta cĩ quá trình Poisson phức hợp Z(t) là tiền bán hàng thu được tính đến thời điểm t . 3. Các cuộc gọi đến tổng đài là quá trình Poisson và thời gian gọi của mỗi cuộc là dãy các biến ngẫu nhiên độc lập, cùng phân bố và dãy này độc lập với các cuộc gọi đến. Khi đĩ tổng thời gian của tất cả các cuộc gọi cho đến thời điểm t là một quá trình Poisson phức hợp. 4. Giả sử các lần chuyển đổi tại thị trường chứng khốn diễn ra theo quá trình Poisson. Gọi Yk là lượng thay đổi giá cổ phiếu giữa lần chuyển đổi thứ k −1 và thứ k . Khi đĩ ta cĩ quá trình Poisson phức hợp Z (t) là sự biến động tổng cộng giá cổ phiếu tính đến thời điểm t . 163
Chương 6: Quá trình Poisson Định lý 6.6: Kỳ vọng và phương sai của quá trình Poisson phức hợp: 2 EZ(t) = λtEY1 ; var Z(t) = λtEY1 , (6.15) Hàm phân bố ∞ n (λt) −λt P{}Z(t) t khi và chỉ khi Z(t) t}= {Z(t) t = P{Z(t) {}Ttdt=⎜⎟e−λt dtFa)=F(a). ∫∫∑∑⎜⎟n! nnλ 00nn==00⎝⎠ Đặc biệt khi các Yk cĩ phân bố mũ tham số µ thì 1∞∞(µµaa)1kk∞k ()1∞ (µa)1k Te==∑∑ −µaa∑∑ e−µ =∑(1 +k) e−µa=(1 +µa) . λλnk==00nkk!!k=n=0λk=0k!λ Nhận xét 6.2: Trong ví dụ trên ta đã sử dụng cơng thức tính kỳ vọng của biến ngẫu nhiên nhận ∞ giá trị khơng âm. Nếu X là biến ngẫu nhiên, X ≥ 0 thì EX = ∫ P{X > x}dx . Đặc biệt X là biến 0 ∞∞ ngẫu nhiên rời rạc nhận các giá trị k = 0,1, 2, thì EX = ∑∑kP{}X ==k P{X ≥k}. kk==11 164
Chương 6: Quá trình Poisson BÀI TẬP 6.1 Các bức điện gửi tới bưu điện là quá trình Poisson với tốc độ trung bình 3 bức trong 1 giờ. a) Tính xác suất để từ 8h00 đến 12h00 khơng cĩ bức điện nào. b) Tính phân bố của thời điểm tại đĩ nhận được bức điện đầu tiên sau 12h00. 6.2 Số cuộc gọi đến tổng đài là quá trình Poisson X (t) với tốc độ trung bình 2 cuộc gọi trong một đơn vị thời gian. Hãy tính: a) P{}X (1) = 2 và P{}X (1) = 2, X (3) = 6 . b) PX{ (1) ==2 X(3) 6} và PX{ (3) = 6 X(1) = 2}. 6.3 Cho X (t),t ≥ 0 là quá trình Poisson với cường độ λ = 2 . Hãy tính: a) EX (2), EX 2 (1), E[]X (1) ⋅ X (2) . b) P{}X (1) ≤ 2 , P{X (1), X (2) = 3}. 6.10 Cho {}X1(t),t ≥ 0 và {X 2 (t),t ≥ 0} là các quá trình Poisson độc lập với các cường độ là λ1 và λ2 tương ứng. Chứng minh rằng {X (t) = X1(t) + X 2 (t),t ≥ 0} là quá trình Poisson với cường độ là λ = λ1 + λ2 . 6.11 Cho {}X1(t),t ≥ 0 và {X 2 (t),t ≥ 0} là hai quá trình Poisson độc lập với các cường độ là λ1 và λ2 tương ứng. a) Tính xác suất để X1(t) = 1 trước khi X 2 (t) = 1. b) Tính xác suất để X1(t) = 2 trước khi X 2 (t) = 2 . c) Tính xác suất để X1(t) = n trước khi X 2 (t) = m . 6.12 Khách tới cửa hàng theo quá trình Poisson với cường độ 5 người một giờ. Biết rằng trong 2 giờ đầu đã cĩ 12 khách tới, tính xác suất (cĩ điều kiện) để cĩ 5 khách tới trong giờ đầu tiên. 6.13 Khách tới cửa hàng theo quá trình Poisson với cường độ 10 người một giờ. Khách cĩ thể mua hàng với xác suất p = 0,3 và khơng mua hàng với xác suất q = 0,7 . Tính xác suất để trong giờ đầu tiên cĩ 9 người vào cửa hàng trong số đĩ 3 người mua hàng, 6 người khơng mua. 6.14 Cho quá trình Poisson {X (t),t ≥ 0} với tham số λ. Gọi tn là thời gian đến trung gian thứ n . Hãy tính Et4 và E(⎣⎦⎡⎤XX4)−=(2)X(1)3. 165
Chương 7: Lý thuyết sắp hàng CHƯƠNG VII: LÝ THUYẾT SẮP HÀNG GIỚI THIỆU Trong nhiều hệ thống phục vụ, các khách hàng (costumer) phải dùng chung tài nguyên, phải chờ để được phục vụ và đơi khi bị từ chối phục vụ. Lý thuyết quá trình sắp hàng (queueing process) xác định và tìm các phương án tối ưu để hệ thống phục vụ tốt nhất. Trong nửa đầu của thế kỷ 20 lý thuyết sắp hàng đã được ứng dụng để nghiên cứu thời gian đợi trong các hệ thống điện thoại. Ngày nay lý thuyết sắp hàng cịn cĩ nhiều ứng dụng trong các lĩnh vực khác nhau như trong mạng máy tính, trong việc quản lý xí nghiệp, quản lý giao thơng và trong các hệ phục vụ khác Ngồi ra lý thuyết sắp hàng cũng cịn là cơ sở tốn học để nghiên cứu và ứng dụng trong nhiều bài tốn kinh tế như đầu tư, kiểm kê, rủi ro của bảo hiểm, thị trường chứng khốn Chuỗi Markov là quá trình sắp hàng với thời gian rời rạc đã được xem xét trong chương 6. Quá trình sinh tử cũng là quá trình sắp hàng, trong đĩ sinh biểu thị sự đến và tử biểu thị sự rời hàng của hệ thống. Người ta phân loại các quá trình sắp hàng dựa vào luật phân bố của quá trình đến, luật phân bố phục vụ, nguyên tắc phục vụ và cơ cấu phục vụ. Trên cơ sở phân loại này ta cĩ ký hiệu Kendall A/ B / k hoặc A/ B / k / N , trong đĩ A là ký hiệu luật phân bố của quá trình đến (hay quá trình đến trung gian), B ký hiệu luật phân bố của quá trình phục vụ, k ký hiệu số server và N ký hiệu dung lượng tối đa của hàng. Đối với lý thuyết sắp hàng ta quan tâm đến các số đo hiệu năng, đĩ là các giá trị trung bình khi quá trình đạt trạng thái dừng bao gồm: độ dài hàng đợi trung bình của hàng, độ dài hàng đợi trung bình của hệ thống, thời gian đợi trung bình của hàng (trễ của hàng) và thời gian đợi trung bình của hệ thống (trễ của hệ thống). Để tính các đại lượng này ta cĩ thể sử dung phương pháp giải phương trình tích phân dạng Wiener-Hopf hoặc phương pháp khảo sát chuỗi Markov nhúng. Từ đĩ suy ra các cơng thức tính các phân bố ổn định cho các loại hàng M / M / k , M / M / k / N ; Cơng thức tổng quát tính các giá trị trung bình này cho các hàng G / G /1 và cơng thức cụ thể cho các hàng đặc biệt M / M /1, M / D /1 và M / Ek /1. Tuy nhiên trong chương này chúng tơi chỉ cung cấp các kết quả dưới dạng các cơng thức và khơng chứng minh. Hướng ứng dụng vào viễn thơng: Một trong những bài tốn quan trọng của lý thuyết chuyển mạch là vấn đề xung đột thơng tin, nghẽn mạch hoặc rớt cuộc gọi. Lý thuyết sắp hàng sẽ xác lập phương án tối ưu để khắc phục những vấn đề trên. Ngồi ra lý thuyết sắp hàng cũng được ứng dụng rộng rãi trong các hệ phục vụ khác. 7.1. KHÁI NIỆM VÀ PHÂN LOẠI QUÁ TRÌNH SẮP HÀNG 7.1.1. Khái niệm quá trình sắp hàng Mơ hình tổng quát của lý thuyết sắp hàng là khách hàng đến ở một thời điểm ngẫu nhiên nào đĩ và yêu cầu được phục vụ theo một loại nào đĩ. Giả thiết thời gian phục vụ cĩ thể ngẫu nhiên 166
Chương 7: Lý thuyết sắp hàng Các khách hàng yêu cầu Nguồn vào và tìm kiếm dịch vụ Quá trình đến Quá trình đến trung gian tn Hàng đợi Độ dài ♦ Dung lượng: Hữu hạn hoặc vơ hạn hàng Độ đợi ♦ Quy tắc phục vụ: dài FIFO hoặc LIFO hàng của hệ thống Phương tiện phục vụ Các khách hàng đã được phục vụ Đầu ra Đặt tn là khoảng thời gian giữa 2 lần đến của khách hàng thứ n −1 và thứ n , khách hàng thứ 0 đến tại thời điểm 0. Ta giả định rằng tất cả các tn ( n ≥ 1) là độc lập và cĩ cùng phân bố. Vì 1 vậy việc đến của các khách hàng tạo thành 1 hàng kế tiếp nhau với tốc độ đến là λ= . Ta E(t1) gọi quá trình {tn ;n = 1,2, } là quá trình đến. Khách hàng đến hệ thống yêu cầu các server của hệ thống phục vụ. Ta giả sử rằng khách hàng thứ n cần một thời gian phục vụ là sn (n ≥ 1), tất cả các sn độc lập và cĩ cùng phân bố. Quá trình {sn ;n = 1,2, } được gọi là quá trình phục vụ. Ta cũng giả thiết rằng các thời gian đến trung gian độc lập với thời gian phục vụ. Quá trình sắp hàng được phân loại dựa vào các tiêu chí sau: 1) Phân bố của quá trình đến (input process) {tn ;n = 1,2, }. 167