Giáo trình Xác suất quá trình ngẫu nhiên và tính toán ngẫu nhiên

pdf 238 trang vanle 3000
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Xác suất quá trình ngẫu nhiên và tính toán ngẫu nhiên", để 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:

  • pdfgiao_trinh_xac_suat_qua_trinh_ngau_nhien_va_tinh_toan_ngau_n.pdf

Nội dung text: Giáo trình Xác suất quá trình ngẫu nhiên và tính toán ngẫu nhiên

  1. GIÁO TRÌNH XÁC SUẤT Quá trình ngẫu nhiên và tính toán ngẫu nhiên Đặng Hùng Thắng NXB ĐHQG Hà Nội
  2. Simpo PDF Merge and Split Unregistered Version - Chương 1. Quá trình Markov Đặng Hùng Thắng Quá trình ngẫu nhiên và tính toán ngẫu nhiên. NXB Đại học quốc gia Hà Nội 2007, Tr 5 - 63. Từ khoá: Quá trình ngẫu nhiên, Quá trình Markov, Xích Markov, Trạng thái hữu han, Trạng thái vô hạn đếm được. Tài liệu trong Thư viện điện tử ĐH Khoa học Tự nhiên có thể sử dụng cho mục đích học tập và nghiên cứu cá nhân. Nghiêm cấm mọi hình thức sao chép, in ấn phục vụ các mục đích khác nếu không được sự chấp thuận của nhà xuất bản và tác giả.
  3. Simpo PDF Merge and Split Unregistered Version - Chương 1 Quá trình Markov 1.1 XíchMarkov 5 1.2 Phân loại trạng thái xích Markov . . . . . . . . . 20 1.3 QuátrìnhMarkov 34 1.3.1 Trường hợp không gian trạng thái hữu hạn . . . . 36 1.3.2 Trường hợp không gian trạng thái vô hạn đếm được 42 1.3.3 Trường hợp tổng quát . . . . . . . . . . . . . . . . 54 1.4 Bàitập 58 1.1 Xích Markov Xét một hệ nào đó được quan sát tại các thời điểm rời rạc 0, 1, 2, Giả sử các quan sát đó là X0,X1, , Xn, Khi đó ta có một dãy các đại lượng ngẫu nhiên (ĐLNN) (Xn) trong đó Xn lg thái của hệ tại thời điểm n. Giả thiết rằng mỗi Xn,n=0, 1, là một ĐLNN rời rạc. Ký hiệu E là tập giá trị của các (Xn). Khi đó E là một tập hữu hạn hay đếm được, các phần tử của nó được ký hiệu là i, j, k Ta gọi E là không gian trạng thái của dãy.
  4. Simpo PDF Merge and Split Unregistered Version - 6 Chương 1. Quá trình Markov Định nghĩa 1.1. Ta nói rằng dãy các ĐLNN (Xn) là một xích Markov nếu với mọi n1 < <nk <nk+1 và với mọi i1,i2, ik+1 ∈ E P {Xnk+1 = ik+1|Xn1 = i1.Xn2 = i2 , Xnk = ik} = P {Xnk+1 = ik+1|Xnk = ik}. Ta coi thời điểm nk+1 là tương lai, nk là hiện tại còn n1, ,nk−1 là quá khứ. Như vậy, xác suất có điều kiện của một sự kiện B nào đó trong tương lai nếu biết hiện tại và quá khứ của hệ cũng giống như xác suất có điều kiện của B nếu chỉ biết trạng thái hiện tại của hệ. Đó chính là tính Markov của hệ. Đôi khi tính Markov của hệ còn phát biểu dưới dạng: Nếu biết trạng thái hiện tại của hệ thì quá khứ và tương lai độc lập với nhau. Giả sử P {Xm+n = j|Xm = i} là xác suất để xích tại thời điểm m ở trạng thái i sau n bước, tại thời điểm m + n chuyển sang trạng thái j. Đây là một con số nói chung phụ thuộc vào i, j, m, n. Nếu đại lượng này không phụ thuộc m ta nói xích là thuần nhất. Trong giáo trình này ta chỉ xét xích Markov thuần nhất. Ký hiệu Pij = P {Xn+1 = j|Xn = i} Pij(n)=P {Xm+n = j|Xm = i}. Ta gọi (Pij ,i,j ∈ E) là xác suất chuyển sau một bước hay xác suất chuyển còn (Pij(n),i,j ∈ E) là xác suất chuyển sau n bước. Chú ý rằng X Pij =1 j∈E X Pij (n)=1. j∈E Phân bố của X0 được gọi là phân bố ban đầu. Ta ký hiệu ui = P (X0 = i). Định lý 1.1. Phân bố đồng thời của (X0,X1, , Xn) được hoàn toàn xác định từ phân bố ban đầu và xác suất chuyển. Cụ thể ta có P (X0 = i0,X1 = i1, , Xn = in)=ui0 Pi0i1 Pin−1in .
  5. Simpo PDF Merge and Split Unregistered Version - 1.1. Xích Markov 7 Thật vậy theo công thức nhân xác suất ta có P (X0 = i0,X1 = i1, , Xn = in)= = P (X0 = i0)P (X1 = i1|X0 = i0) × × P (Xk = ik|X0 = i0, , Xk−1 = ik−1) × × P (Xn = in|X0 = i0, , Xn−1 = in−1). Sử dụng tính Markov ta có P (Xk = ik|X0 = i0, , Xk−1 = ik−1)=P (Xk = ik|Xk−1 = ik−1) = Pik−1ik . Thành thử P (X0 = i0,X1 = i1, , Xn = in)=ui0 Pi0i1 Pin−1in Định lý 1.2. (Phương trình C - K (Chapman-Kolmogorov)) Pij (n + m)=X Pik(n)Pkj(m). k∈E Chứng minh. Theo công thức xác suất đầy đủ và tính Markov ta có Pij (n + m)=P (Xn+m = j|X0 = i) = X P (Xn = k|X0 = i)P (Xn+m = j|Xn = k,X0 = i) k∈E = X Pik(n)Pkj(m). k∈E Trong trường hợp E có d phần tử, ta ký hiệu P =(Pij ),P(n)=(Pij(n)) là các ma trận vuông cấp d×d. P được gọi là ma trận xác suất chuyển, P (n) được gọi là ma trận xác suất chuyển sau n bước. Khi đó từ phương trình Chapman-Kolmogorov tương đương với P (n + m)=P (n)P (m).
  6. Simpo PDF Merge and Split Unregistered Version - 8 Chương 1. Quá trình Markov Vì P = P (1) nên bằng quy nạp ta dễ thấy P (n)=P n. Gọi ui(n)=P (Xn = i). Ký hiệu vecto U(n)=(u1(n), , ud(n)) là vector hàng d - chiều mô tả phân bố của Xn, U = U(0) = (u1,u2, , ud) là vector hàng d - chiều mô tả phân bố ban đầu (phân bố của X0). Định lý 1.3. Ta có U(m + n)=U(m)P n. Nói riêng U(n)=UPn. Chứng minh. Thật vậy, theo công thức xác suất đầy đủ ta có d uj(m + n)=P (Xn+m = j)=X P (Xm = i)P (Xn+m = j|Xm = i) i=1 d = X ui(m)Pij (n). i=1 Ví dụ 1.1. Cho (ξn),n=0, 1, 2, là dãy các ĐLNN độc lập, cùng phân bố. n Giả sử P (ξn = i)=ai,i ∈ Z. Đặt Xn = P ξi. Khi đó (Xn) là một xích i=1 Markov với không gian trạng thái Z. P {Xn+1 = in+1|X0 = i0.X1 = i1 , Xn = in} = P {Xn + ξn+1 = in+1|ξ0 = i0,ξ1 = i1 − i0, , ξn = in − in−1} = P {ξn+1 = in+1 − in} = P {Xn+1 = in+1|Xn = in}. Vậy thì (Xn) là một xích Markov với không gian trạng thái Z. Xác suất chuyển là Pij = ai−j.
  7. Simpo PDF Merge and Split Unregistered Version - 1.1. Xích Markov 9 Ví dụ 1.2. (Mô hình Ehrenfest) Ta có hai bình A, B và có d quả cầu đánh số 1, 2, d. Tại thời điểm ban đầu có a quả cầu trong A và d−a quả cầu trong B. Tại mỗi thời điểm n ta chọn ngẫu nhiên một số trong tập {1, 2, d}. Khi đó quả cầu mang chỉ số được chọn sẽ được chuyển từ bình đang chứa nó sang bình kia. Ký hiệu Xn là số quả cầu trong bình A tại thời điểm n. Hiển nhiên (Xn) là xích Markov. Ta hãy tính xác suất chuyển P (Xn+1 = j|Xn = i).Vì A chứa i quả cầu nên với xác suất i/d ta sẽ chọn được quả cầu từ A. Khi đó quả cầu này được chuyển sang B.VậyP (Xn+1 = i − 1|Xn = i)=i/d. Tương tự với xác suất 1 − i/d sẽ chọn được quả cầu của B và quả cầu này sẽ được chuyển vào A.VậyP (Xn+1 = i +1|Xn = i)=1− i/d. Thành thử i  nếu j = i − 1 d d − i Pij = nếu j = i +1 (1.1) d  0 nếu j =6 i +1,j =6 i − 1. Mô hình này được nhà vật lý nổi tiếng Ehrenfest đưa ra năm 1907 nhằm mô tả sự truyền nhiệt giữa hai vật thể. Ví dụ 1.3. Ta nghiên cứu một vấn đề xã hội nào đó chẳng hạn vấn đề nghiện hút. Ta ký hiệu trạng thái 0 là không nghiện và trạng thái 1 là nghiện. Đơn vị thời gian là một quý (3 tháng). Thống kê nhiều năm cho thấy xác suất để một người không nghiện sau một quý vẫn không nghiện là 0,99 và xác suất để một người nghiện sau một quý vẫn tiếp tục nghiện là 0,88. Như vậy trạng thái của một người (nghiện hay không nghiện) được mô tả bởi một xích Markov với hai trạng thái E = {0, 1} với ma trận xác suất chuyển như sau 0, 99 0, 01! P = 0, 12 0, 88 Giả sử lúc đầu có 17% số người nghiện. Như vậy phân bố ban đầu là U(0) = (0, 83, 0, 17). Sang quý hai, theo định lý 1.3 phân bố số người nghiện và không nghiện sẽ là 0, 99 0, 01! U(1) = U(0)P =(0.83, 0.17) =(0, 845, 0, 155). 0, 12 0, 88
  8. Simpo PDF Merge and Split Unregistered Version - 10 Chương 1. Quá trình Markov Sang quý ba nữa phân bố số người không nghiện và nghiện sẽ là 0, 99 0, 01! U(2) = U(1)P =(0.845, 0.155) =(0, 855, 0, 145) 0, 12 0, 88 tức là lúc này có 14,5% số người nghiện. Ví dụ 1.4. Giả sử ta có d cửa hàng ký hiệu là 1, 2, d cùng bán một sản phẩm nào đó. Khách hàng có thể chọn mua sản phẩm ở một trong d cửa hàng này tuỳ theo sở thích của họ và trong từng tháng họ không thay đổi chỗ mua hàng. Gọi Xn là cửa hàng mà khách hàng chọn mua sản phẩm ở tháng thứ n. Đây là một xích Markov có d trạng thái, xác suất chuyển Pij có nghĩa là xác suất để khách hàng, hiện tại đang mua hàng tại cửa hàng i sang tháng sau chuyển sang mua ở cửa hàng j. Xét d =3và ma trận xác suất chuyển là 0, 800 0, 100 0, 100 P = 0, 070 0, 900 0, 030 0, 083 0, 067 0, 850 Giả sử tháng giêng cửa hàng 1 chiếm 20% khách hàng, cửa hàng 2 chiếm 50% khách hàng và cửa hàng 3 chiếm 30% khách hàng. Như vậy phân bố ban đầu là U(0) = (0, 2, 0, 5, 0, 3). Sang tháng 2 phân bố khách hàng trong 3 cửa hàng sẽ là U(1) = U(0)P =(0, 22, 0, 49, 0, 29). Sang tháng 3 phân bố khách hàng trong 3 cửa hàng sẽ là U(2) = U(1)P =(0, 234, 0, 483, 0, 283). Tiếp tục quá trình như vậy ta có thể tính ở tháng 12 phân bố khách hàng trong 3 cửa hàng sẽ là U(11) = (0, 270, 0, 459, 0, 271) tức là trong tháng 12 cửa hàng 1 chiếm 27% khách hàng, cửa hàng 2 chiếm 45,9% khách hàng và cửa hàng 3 chiếm 27,1% khách hàng. Ví dụ 1.5. Cho (Xn) là một xích Markov có 2 trạng thái E = {0, 1} với ma trận xác suất chuyển là 1 − aa! P = b 1 − b
  9. Simpo PDF Merge and Split Unregistered Version - 1.1. Xích Markov 11 trong đó a, b > 0, 0 <a+ b<1. Ta hãy tìm biểu thức của ma trận xác suất chuyển sau n bước P (n).Tacó P00(n +1)=P (Xn+1 =0|X0 =0) = P (Xn =0|X0 =0)P (Xn+1 =0|Xn = 0)+ + P (Xn =1|X0 =0)P (Xn+1 =0|Xn =1) = P00(n)(1 − a)+(1− P00(n))b. (1.2) Nếu ký hiệu un = P00(n),q =1− a − b từ (1.2) ta có công thức truy hồi sau un+1 = un(1 − a)+(1− un)b =(1− a − b)un + b = qun + b. Chú ý rằng u0 =1, từ công thức truy hồi trên dễ thấy b(1 − qn) b u = qn + =(1− a − b)n + (1 − (1 − a − b)n) n 1 − q a + b hay b a P (n)= +(1− a − b)n . 00 a + b a + b Suy ra a a P (n)=1− P (n)= − (1 − a − b)n . 01 00 a + b a + b Tương tự ta có P10(n +1)=P (Xn+1 =0|X0 =1) = P (Xn =0|X0 =1)P (Xn+1 =0|Xn = 0)+ + P (Xn =1|X0 =1)P (Xn+1 =0|Xn =1) = P10(n)(1 − a)+(1− P10(n))b. (1.3) Nếu ký hiệu vn = P00(n),q =1− a − b từ (1.3) ta có công thức truy hồi sau vn+1 = vn(1 − a)+(1− vn)b =(1− a − b)vn + b = qvn + b. Chú ý rằng v0 =0, từ công thức trên ta thu được b(1 − qn) b v = = (1 − (1 − a − b)n). n (1 − q) a + b
  10. Simpo PDF Merge and Split Unregistered Version - 12 Chương 1. Quá trình Markov Suy ra b b P (n)= − (1 − a − b)n 10 a + b a + b a b P (n)=1− P (n)= +(1− a − b)n . 11 10 a + b a + b Viết dưới dạng ma trận ta có 1 ba! (1 − a − b)n a −a! P (n)= + . a + b ba a + b −bb Định nghĩa 1.2. Phân bố ban đầu U =(ui),i∈ E được gọi là phân bố dừng nếu ta có U(n)=U với mọi n tức là ui(n)=ui ∀i ∈ E,∀n. Khi đó dãy (Xn) có cùng phân bố. Từ định lý 3 ta suy ra U =(ui) là phân bố dừng nếu và chỉ nếu 1. ui ≥ 0 và P ui =1 i∈E 2. uj = P uiPij ∀j ∈ E. i∈E Ví dụ 1.6. Cho (Xn) là một xích Markov có 3 trạng thái E = {1, 2, 3} với ma trận xác suất chuyển là 1/31/31/3 P = 1/41/21/4 1/61/31/2 Hãy tìm tất cả các phân bố dừng. Đặt U =(x, y, z). Khi đó U là phân bố dừng khi và chỉ khi x, y, z là nghiệm không âm của hệ sau x/3+y/4+z/6=x  x/3+y/2+z/3=y  x/3+y/4+z/2=z   x + y + z =1.
  11. Simpo PDF Merge and Split Unregistered Version - 1.1. Xích Markov 13 Từ phương trình thứ nhất và thứ hai của hệ khử z ta rút ra y =5x/3. Từ đó z =3x/2. Thế vào phương trình (4) ta thu được x =6/25,y =10/25,z = 9/25. Ví dụ 1.7. Cho (Xn) là một xích Markov có 2 trạng thái E = {0, 1} với ma trận xác suất chuyển là 1 − aa! P = b 1 − b trong đó a, b > 0, 0 <a+ b<1 (xem ví dụ 1.5). Ta hãy tìm phân bố dừng. Đặt U =(x, y). Khi đó U là phân bố dừng khi và chỉ khi x, y là nghiệm không âm của hệ sau (1 − a)x + by = x   ax +(1− b)y = y x + y =1.  by Phương trình (1) và (2) của hệ tương đương với ax = by hay x = a . Thế vào phương trình (3) của hệ ta thu được b a x = ,y = . a + b a + b Như sau này ta sẽ thấy phân bố dừng không phải bao giờ cũng tồn tại. Câu hỏi đặt ra là: Với điều kiện nào thì tồn tại phân bố dừng? Phân bố dừng nếu tồn tại thì có duy nhất không? Định lý 1.4. Giả sử (Xn) là xích Markov với không gian trạng thái E = {1, 2, } với ma trận xác suất chuyển P =(Pij ) và ma trận xác suất chuyển sau n bước là P (n)=(Pij (n)). Giả sử rằng với mọi i, j ∈ E tồn tại giới hạn lim Pij (n)=πj n→∞ và giới hạn này không phụ thuộc i. Khi đó
  12. Simpo PDF Merge and Split Unregistered Version - 14 Chương 1. Quá trình Markov 1. P πj ≤ 1 và πj = P πiPij . j∈E i∈E 2. Hoặc πj =0với mọi j ∈ E, hoặc P πj =1. j∈E 3. Nếu P πj =1thì U =(π1,π2, ) là phân bố dừng và phân bố dừng là j∈E duy nhất. Nếu πj =0với mọi j ∈ E thì phân bố dừng không tồn tại. Chứng minh. 1. Theo bổ đề Fatou ta có X πj = X lim Pij (n) ≤ lim inf X Pij (n)=1. n→∞ n→∞ j∈E j∈E j∈E Sử dụng bổ đề Fatou và phương trình C-K ta có X πiPij = X lim Pki(n)Pij n i∈E i∈E ≤ lim inf X Pki(n)Pij = lim inf Pkj(n +1)=πj. n→∞ n→∞ i∈E Đặt sj = πj − Pi∈E πiPij ≥ 0 ∀j ∈ E.Tacó X sj = X πj − X X πiPij j∈E j∈E j∈E i∈E = X πj − X X πiPij = X πj − X πi X Pij j∈E i∈E j∈E j∈E i∈E j∈E = X πj − X πi =0. j∈E i∈E Vậy sj =0 ∀j ∈ E hay πj = P πiPij ∀j ∈ E. i∈E 2. Ta có πj = X πiPij = X(X πkPki)Pij i∈E i∈E k∈E = X πk(X PkiPij )=X πkPkj(2). k∈E i∈E k∈E
  13. Simpo PDF Merge and Split Unregistered Version - 1.1. Xích Markov 15 Bằng quy nạp dễ thấy với mọi n πj = X πkPkj(n). k∈E Vì chuỗi hội tụ đều đối với n nên πj = lim X πkPkj(n)=X πk lim Pkj(n)=πj X πk n→∞ n→∞ k∈E k∈E k∈E Suy ra ! πj 1 − X πk =0 ∀j ∈ E. k∈E Vậy nếu Pk∈E πk < 1 thì πj =0 ∀j ∈ E. 3. Nếu P πk =1thì từ khẳng định 1 ta suy ra π =(π1,π2, ) là phân k∈E bố dừng. Ta chứng minh đây là phân bố dừng duy nhất. Thật vậy giả sử U =(ui) là phân bố dừng. Lập luận tương tự như trên ta có uj = X ukPkj(n). k∈E Vì chuỗi hội tụ đều đối với n nên uj = X uk lim Pkj(n)=X ukπj = πj. n→∞ k∈E k∈E Do đó nếu P πj < 1 thì phân bố dừng không tồn tại. Nếu P πj =1thì j∈E j∈E π =(π1,π2, ) là phân bố dừng duy nhất. Định nghĩa 1.3. Giả sử (Xn) là xích Markov với không gian trạng thái E = {1, 2, } với ma trận xác suất chuyển P =(Pij ) và ma trận xác suất chuyển sau n bước là P (n)=Pij (n). Ta nói rằng xích có phân bố giới hạn nếu với mọi i, j ∈ E tồn tại giới hạn lim Pij (n)=πj. n→∞ Giới hạn này không phụ thuộc i ∈ E và P πj =1. Nói cách khác, vecto giới j∈E hạn π =(π1,π2, ) lập thành một phân bố xác suất trên E.
  14. Simpo PDF Merge and Split Unregistered Version - 16 Chương 1. Quá trình Markov Ý nghĩa của phân bố giới hạn là như sau: Gọi ui(n)=P (Xn = i).Ký hiệu vecto U(n)=(u1(n),u2(n), ) là vector hàng d-chiều mô tả phân bố của Xn.Tacó P (Xn = j)=X P (X0 = i)Pij(n). ß∈E Do đó lim P {Xn = j} = X P {X0 = i} lim Pij (n) n→∞ n→∞ ß∈E = X P {X0 = i}πj = πj. ß∈E Vậy phân bố U(n) của Xn hội tụ tới phân bố giới hạn π. Khi n khá lớn ta có P (Xn = j) ≈ πj. Theo định lý 1.4 nếu phân bố giới hạn tồn tại thì phân bố dừng cũng tồn tại và duy nhất. Hơn nữa hai phân bố này trùng nhau. Tuy nhiên điều ngược lại không đúng tức là có những xích Markov có tồn tại phân bố dừng nhưng không tồn tại phân bố giới hạn. Ví dụ 1.8. Cho xích Markov (Xn) có hai trạng thái với ma trận xác suất chuyển là 01! P = . 10 Ta có 01! P (2n)= 10 và 01! P (2n +1)= . 10 Do đó không tồn tại lim P (n). Tuy nhiên dễ dàng kiểm tra được π = n→∞ (1/2, 1/2) là phân bố dừng duy nhất.
  15. Simpo PDF Merge and Split Unregistered Version - 1.1. Xích Markov 17 Một trong những bài toán quan trọng trong nghiên cứu xích Markov là tìm những điều kiện để đảm bảo sự tồn tại của phân bố giới hạn và sự tồn tại của phân bố dừng. Dưới đây là một định lý như vậy. Định lý 1.5. Cho (Xn) là xích Markov với không gian trạng thái hữu hạn E = {1, 2, , d} với ma trận xác suất chuyển sau n bước là P (n)=(Pij (n)). Khi đó có tồn tại phân bố giới hạn π =(π1, , πd) với πj > 0 ∀j ∈ E khi và chỉ khi xích là chính quy theo nghĩa: Tồn tại n0 sao cho Pij (n0) > 0, ∀i, j ∈ E. Chứng minh. Giả thiết xích là chính quy. Ta cố định j và đặt mj(n) = min Pij(n) i∈E Mj(n) = max Pij (n). i∈E Ta có Pij (n +1)=X PikPkj(n) ≥ X Pikmj(n)=mj(n). k k Suy ra mj(n +1) ≥ mj(n). Vậy dãy (mj(n)),n =1, 2, là dãy tăng và bị chặn trên bởi 1, do đó tồn tại giới hạn lim mj(n)=aj. n Lập luận tương tự dãy (Mj (n)),n =1, 2, ) là dãy giảm bị chặn bởi 0,do đó tồn tại giới hạn lim Mj(n)=Aj. n Ta có mj(n) ≤ Pij (n) ≤ Mj (n) do đó định lý được chứng minh nếu ta chỉ ra aj = Aj. Ký hiệu r = mini,j Pij (n0) > 0.TacóPik(n0) ≥ r.1 ≥ Pjk(n) nên Pik(n0) ≥ rPjk(n) ∀i, thành thử Pij (n0 + n)=X Pik(n0)Pkj(n) k = X (Pik(n0) − rPjk(n)) Pkj(n)+r X Pjk(n)Pkj(n) k k ≥ mj(n) X (Pik(n0) − rPjk(n)) + rPjj(2n) k = mj(n)(1 − r)+rPjj(2n).
  16. Simpo PDF Merge and Split Unregistered Version - 18 Chương 1. Quá trình Markov Vì bất đẳng thức này đúng với mọi i nên ta có mj(n0 + n) ≥ mj(n)(1 − r)+rPjj(2n). Tương tự ta có Mj (n0 + n) ≤ Mj (n)(1 − r)+rPjj(2n). Suy ra Mj(n0 + n) − mj(n0 + n) ≤ (1 − r)(Mj (n) − mj(n)) . (1.4) Ta chứng minh quy nạp rằng với mọi k k Mj(kn0 +1)− mj(kn0 +1)≤ (1 − r) (Mj (1) − mj(1)) . (1.5) Thật vậy với k =1đúng (Cho n =1ở (1.4)). Giả sử đúng với k.Tacó Mj ((k +1)n0 +1)− mj((k +1)n0 +1) = Mj(kn0 +1+n0) − mj(kn0 +1+n0) ≤ (1 − r)((Mj (kn0 +1)− mj(kn0 + 1)) k+1 ≤ (1 − r) (Mj(1) − mj(1)) . Cho k →∞trong (1.5) ta nhận được Aj − aj ≤ 0.VìAj − aj ≥ 0 nên ta kết luận Aj = aj. Đảo lại giả sử với mọi i, j ∈ E tồn tại limn Pij (n)=πj > 0. Khi đó tồn tại n0(i, j) sao cho Pij (n) > 0 ∀n>n0(i, j). Đặt n0 = maxi,j n0(i, j) ta có Pij (n) > 0 ∀i, j ∈ E∀n>n0 Ví dụ 1.9. Mỗi người dân trong một vùng nào đó có thể ở trong ba tầng lớp: giàu, trung lưu và nghèo. Con cái của họ có thể ở trong một trong ba tầng lớp nói trên với các xác suất khác nhau tuỳ thuộc vào việc họ đang ở trong tầng lớp nào. Giả sử bằng thống kê ngưòi ta xác định được: Nếu một người giàu thì với xác suất 0,448 con họ giàu, với xác suất 0,484 con họ trung lưu với xác suất 0,068 con họ nghèo. Tương tự, với một người trung lưu thì xác suất để con họ giàu, trung lưu hay nghèo tương ứng là 0,054. 0,699 và 0,247. Với
  17. Simpo PDF Merge and Split Unregistered Version - 1.1. Xích Markov 19 một người nghèo thì xác suất để con họ giàu, trung lưu hay nghèo tương ứng là 0,011, 0,503 và 0,486. Như vậy sự thay đổi trạng thái của một gia đình trong xã hội từ thế hệ này qua thế hệ khác có thể mô tả bởi một xích Markov ba trạng thái : 1(giàu), 2(trung lưu), 3(nghèo) với xác suất chuyển như sau 0, 448 0, 484 0, 068 P = 0, 054 0, 699 0, 247 . 0, 011 0, 503 0, 486 Xích Markov này là chính quy. Thành thử tồn tại phân bố giới hạn π = (π1,π2,π3). Phân bố này chính là phân bố dừng duy nhất và được tìm bằng cách giải hệ phương trình sau (π1,π2,π3)P =(π1,π2,π3). Giải ra ta tìm được π1 =0, 067; π2 =0, 624; π3 =0, 369. Như vậy qua nhiều thế hệ ở vùng dân cư nói trên sẽ có 6,7% người giàu, 62,4% trung lưu và 36.9% người nghèo. Ví dụ 1.10. Xét xích Markov có d trạng thái E = {1, 2, , d} và ma trận xác suất chuyển của nó là chính quy đồng thời là một ma trận kép nghĩa là X Pij = X Pij =1. j∈E i∈E Theo định lý trên, phân phối giới hạn tồn tại. Ta hãy tìm phân bố giới hạn đó.Ta nhận xét rằng phân bố đều π= (1/d, 1/d, , 1/d) là phân bố dừng. Thật vậy đặt pij =1/d ta có X pikPkj =1/d X Pkj =1/d = πj. k∈E k∈E Vì phân bố dừng là duy nhất và phân bố giới hạn chính là phân bố dừng nên ta kết luận rằng phân bố giới hạn là phân bố đều π =(1/d, 1/d, , 1/d) . Chẳng hạn ta tung con xúc sắc liên tiếp một cách độc lập. Ký hiệu ξn là n số chấm xuất hiện ở lần gieo thứ n, Sn = Pk=1 ξk. Sn là một xích Markov
  18. Simpo PDF Merge and Split Unregistered Version - 20 Chương 1. Quá trình Markov với không gian trạng thái E = {1, 2, }. Gọi Xn là số dư khi chia Sn cho 7. Khi đó Xn cũng là một là một xích Markov với không gian trạng thái E = {0, 1, 2, , 6}. Ma trận xác suất chuyển của Xn là  01/61/61/61/61/61/6 1/601/61/61/61/61/6   1/61/601/61/61/61/6     P = 1/61/61/601/61/61/6 .   1/61/61/61/601/61/6     1/61/61/61/61/601/6 1/61/61/61/61/61/60 Xích Markov này chính quy vì ma trận xác suất chuyển sau 2 bước  1/65/36 5/36 5/36 5/36 5/36 5/36 5/36 1/65/36 5/36 5/36 5/36 5/36   5/36 5/36 1/65/36 5/36 5/36 5/36   2   P (2) = P = 5/36 5/36 5/36 1/65/36 5/36 5/36   5/36 5/36 5/36 5/36 1/65/36 5/36     5/36 5/36 5/36 5/36 5/36 1/65/36 5/36 5/36 5/36 5/36 5/36 5/61/6  có tất cả các phần tử là số dương. Vậy phân bố giới hạn là π =(1/7, 1/7, 1/7, 1/7, 1/7, 1/7, 1/7, 1/7). 1.2 Phân loại trạng thái xích Markov Để giải quyết đầy đủ hơn bài toán về sự tồn tại của phân bố dừng cũng như bài toán về sự tồn tại của phân bố giới hạn dẫn ta đến việc phân loại các trạng thái của xích Markov như sau:
  19. Simpo PDF Merge and Split Unregistered Version - 1.2. Phân loại trạng thái xích Markov 21 Định nghĩa 1.4. Ta nói rằng trạng thái i đến được trạng thái j và ký hiệu là i → j nếu tồn tại n ≥ o sao cho Pij (n) > 0.(TaquyướcPii(0) = 1,Pij (0) = 0 nếu i =6 j) Hai trạng thái i và j được gọi là liên lạc được nếu i → j và j → i. Trong trường hợp đó ta viết i ↔ j. Bổ đề 1.1 (Tính chất bắc cầu). Nếu i → j, j → k thì i → k. Thật vậy theo giả thiết tồn tại n, m sao cho Pij (n) > 0,Pjk(m) > 0. Theo phương trình Chapman - Kolmogorov ta có Pik(n + m)=X Pij (n)Pjk(m) ≥ Pij(n)Pjk(m) > 0. j∈E Từ bổ đề, dễ kiểm tra rằng quan hệ "liên lạc được" là một quan hệ tương đương trên không gian trạng thái E. Theo quan hệ này không gian E được phân hoạch thành các lớp rời nhau. Hai trạng thái bất kỳ cùng thuộc một lớp thì liên lạc được với nhau, hai trạng thái khác lớp không thể liên lạc được với nhau. Định nghĩa 1.5. Xích Markov được gọi là tối giản nếu hai trạng thái bất kỳ là liên lạc được. Có nghĩa là theo cách phân lớp trên thì E không thể phân hoạch thành các lớp con nhỏ hơn. Nếu xích không tối giản thì E được phân hoạch thành các lớp rời nhau E = E1 ∪ E2 ∪ ∪ Ek. Có thể xem mỗi Ek là không gian trạng thái của xích Markov tối giản. Như vậy việc nghiên cứu xích Markov có thể quy về việc nghiên cứu các xích tối giản. Ví dụ 1.11. Cho xích Markov với 5 trạng thái E = {1, 2, 3, 4, 5} với ma trận xác suất chuyển là P 0 ! P = 1 0 P2
  20. Simpo PDF Merge and Split Unregistered Version - 22 Chương 1. Quá trình Markov trong đó 1/32/3! P1 = 1/43/4 và  010 P2 = 1/201/2 .  010 Khi đó P n 0 ! P (n)=P n = 1 . n 0 P2 Do đó E = E1 ∪ E2 với E1 = {1, 2},E2 = {3, 4, 5}. Ví dụ 1.12. Cho xích Markov với 4 trạng thái E = {1, 2, 3, 4} với ma trận xác suất chuyển là  001/21/2  001/21/2 P2 =   1/21/20 0   1/21/20 0 Xích này là tối giản. Thật vậy rõ ràng 1 ↔ 3, 1 ↔ 4, 2 ↔ 3, 2 ↔ 4.Tacó 1 → 3, 3 → 2 suy ra 1 → 2.Lạicó2 → 3, 3 → 1 suy ra 2 → 1.Vậy1 ↔ 2 . Tương tự ta có 3 ↔ 4. Vậy hai trạng thái bất kỳ là liên lạc được do đó đây là xích tối giản. Định nghĩa 1.6. Chu kỳ của trạng thái i ký hiệu là d(i) là ước chung lớn nhất của tất cả các số nguyên dương n ≥ 1 mà Pii(n) > 0. Nếu Pii(n)=0 với mọi n ≥ 1 thì ta quy ước đặt d(i)=0. Định lý 1.6. Nếu i ↔ j thì d(i)=d(j). Vậy các trạng thái cùng một lớp có cùng một chu kỳ d và ta gọi số d chung đó là chu kỳ của lớp. Chứng minh. Do i ↔ j nên tồn tại k,l sao cho Pij(k) > 0,Pji(l) > 0. Theo phương trình C-K ta có Pii(k + l)=Ph∈E Pih(k)Phi(l) ≥ Pij (k)Pji(l) > 0. Vậy d(i)|k + l. Giả sử n ≥ 1 sao cho Pjj(n) > 0. Sử dụng phương trình C-K
  21. Simpo PDF Merge and Split Unregistered Version - 1.2. Phân loại trạng thái xích Markov 23 như trên ta có Pii(k + l + n) ≥ Pij (k)Pjj(n)Pji(l) > 0.Vậyd(i)|k + l + n → d(i)|n.Vậyd(i)|d(j). Tương tự d(j)|d(i). Thành thử d(i)=d(j). Giả sử d là chu kỳ của một xích tối giản với không gian trạng thái E. Nếu d =1ta nói rằng xích không có chu kỳ. Nếu d>1 thì có thể chứng minh rằng E được phân hoạch thành d tập conE = C0 ∪ C1 ∪ ∪ Cd−1 sao cho sau một bước hệ sẽ chuyển từ một trạng thái thuộc Ck sang một trạng thái thuộc Ck+1 (quy ước Cd = C0). Vì vậy mỗi tập con có thể lấy làm không gian trạng thái của một xích Markov mới. Xích này tối giản và không có chu kỳ. Tóm lại chúng ta có thể quy việc nghiên cúu xích Markov tổng quát về việc nghiên cứu xích tối giản, không có chu kỳ. Định nghĩa 1.7. Ký hiệu fii(n) là xác suất để hệ xuất phát từ i lần đầu tiên quay lại i ở thời diểm n. Nghĩa là fii(n)=P (Xn = i, Xn−1 =6 i, , X1 =6 i|X0 = i) và ký hiệu ∞ ∗ fii = X fii(n) n=1 là xác suất để hệ xuất phát từ i quay trở lại i sau một số hữu hạn bước. Nếu ∗ ∗ fii =1ta nói i là trạng thái hồi quy (quay lại). Nếu trái lại fii < 1 ta nói i là trạng thái không hồi quy. Định lý cơ bản sau đây cho ta một tiêu chuẩn để xác định tính hồi quy của một trạng thái. Định lý 1.7. Trạng thái i là hồi quy khi và chỉ khi ∞ X Pii(n)=∞. (1.6) n=1 Chứng minh. Chứng minh sử dụng hai bổ đề sau
  22. Simpo PDF Merge and Split Unregistered Version - 24 Chương 1. Quá trình Markov Bổ đề 1.2. Ta có n Pii(n)=X fii(k)Pii(n − k) k=0 trong đó fii(0) = 0. Chứng minh bổ đề 1.2. Với mỗi 0 ≤ k ≤ n gọi Ek là biến cố :" Xn = i và hệ lần đầu tiên quay lại i ở bước thứ k " ta có n Pii(n)=P (Xn = i|X0 = i)=X P (Ek)P (Xn = i|Ek,X0 =1) k=0 n n = X fii(k)P (Xn = i|Xk = i)=X fii(k)Pii(n − k). k=0 k=0 Bổ đề 1.3. (Aben) ∞ (i) Nếu chuỗi Pk=0 ak = a hội tụ thì ∞ ∞ k lim X aks = X ak = a. s→1− k=0 k=0 ∞ k (ii) Nếu ak ≥ 0 và lims→1− Pk=0 aks = a<∞ thì ∞ ∞ k X ak = lim X aks = a. s→1− k=0 k=0 Ta bắt đầu chứng minh định lý. Xét các chuỗi luỹ thừa sau ∞ n Pii(s)=X Pii(n)s ,,|s| < 1 n=0 ∞ n Fii(s)=X fii(n)s ,,|s| < 1 n=0 Ta có ∞ k Fii(s)Pii(s)=X cks , |s| < 1 n=0
  23. Simpo PDF Merge and Split Unregistered Version - 1.2. Phân loại trạng thái xích Markov 25 n với cn = Pk=0 fii(k)Pii(n − k)=Pii(n) n ≥ 1 theo bổ đề 1. Vì c0 = 0,Pii(0) = 1 nên ta suy ra Fii(s)Pii(s)=Pii(s) − 1 hay 1 Pii(s)= . (1.7) 1 − Fii(s) ∞ Giả sử i hồi quy tức là Pn=0 fii(n)=1. Theo bổ đề Abel ∞ n lim Fii(s) = lim X fii(n)s =1. s→1− s→1− n=0 Từ (1.7) suy ra ∞ n lim Pii(s) = lim X Pii(n)s = ∞. s→1− s→1− n=0 Vậy lại theo bổ đề Abel (ii) ta có ∞ X Pii(n)=∞. n=0 ∞ Đảo lại giả sử i không hồi quy tức là P fii(n) 0,Pji(m) > 0.Với mỗi số nguyên dương h từ phương trình C-P suy ra Pii(n + h + m) ≥ Pij(n)Pjj(h)Pji(m). Vậy ∞ ∞ X Pii(n + h + m) ≥ Pij (n)Pji(m) X Pjj(h)=∞. h=1 h=1 Thành thử i hồi quy.
  24. Simpo PDF Merge and Split Unregistered Version - 26 Chương 1. Quá trình Markov Ví dụ 1.13. Cho (rn) là dãy các ĐLNN độc lập có phân bố xác suất như sau P (rn =1)=p, P (rn = −1) = q, 0 <p<1,p+ q =1. (Dãy này được gọi là dãy Rademakher). Xét dãy (Xn) xác định như sau X0 = a, Xn+1 = Xn + rn+1. . Khi đó (Xn) lập thành xích Markov với không gian trạng thái E = {0 ± 1, ±2}xác suất chuyển là P =(Pij ) ởđó q nếu j = i − 1   Pij = p nếu j = i +1 0 nếu j =6 i +1,j =6 i − 1.  Xích này được gọi là du động ngẫu nhiên 1 chiều mô tả sự chuyển động ngẫu nhiên của một hạt trên đường thẳng: Sau mỗi đơn vị thời gian hạt dịch sang phải với xác suất p và dịch sang trái với xác suất q. Dễ thấy đây là một xích tối giản có chu kỳ d =2và 2n P (2n)= pnqn.P(2n +1)=0. ii n ii Sử dụng công thức Stirling √ n! ∼ 2πne−nnn ta có (4pq)n P (2n) ∼ √ . ii πn 1 Nếu du động ngẫu nhiên là đối xứng p = q =1/2 thì P (2n) ∼ √ do đó ii πn X Pii(n)=∞. n
  25. Simpo PDF Merge and Split Unregistered Version - 1.2. Phân loại trạng thái xích Markov 27 Vậy theo định lý 1.7 mọi trạng thái đều hồi quy. Nếu p =6 q thì 4pq = a qthì có một xác suất dương để hạt xuất phát từ trạng thái i sẽ đi sang bên phải mãi mãi ( sang bên trái mãi mãi nếu p<q) không quay lại điểm xuất phát. Ví dụ 1.14. Xét du động ngẫu nhiên của một hạt trên lưới điểm nguyên trên mặt phẳng. Giả sử xác suất để hạt dịch lên trên, dịch xuống dưới một đơn vị (theo phương thẳng đứng), dịch sang phải,sang trái một đơn vị (theo phương nằm ngang) đều bằng nhau và bằng 1/4. Có thể thấy rằng P00(2n +1)=0 và (2n)! P (2n)= X (1/4)2n 00 i!i!j!j! i,ji+j=n 2n n n n =(1/4)2n  X    n i n − i i=0 2n 2 =(1/4)2n  . n Công thức Stirling cho ta 1 P (2n) ∼ . 00 πn Vậy X P00(n)=∞. n Vậy trạng thái 0 là hồi quy. Vì xích là tối giản (dễ thấy) nên mọi trạng thái đều hồi quy. Người ta đã chứng minh được một điều thú vị là với du động ngẫu nhiên đối xứng trong không gian ba chiều, mọi trạng thái đều không hồi quy.
  26. Simpo PDF Merge and Split Unregistered Version - 28 Chương 1. Quá trình Markov Định lý 1.9. Ký hiệu Qii là xác suất để hệ xuất phát từ i quay lại i vô số lần, Qij là xác suất để hệ xuất phát từ i đi qua j vô số lần. Khi đó (i) Nếu i hồi quy thì Qii =1, nếu i không hồi quy thì Qii =0. (ii) Nếu i hồi quy i ↔ j thì Qij =1. Nói riêng, với xác suất 1 hệ xuất phát từ i sau một số hữu hạn bước sẽ đi qua j. Chứng minh. (m) (i) Giả sử Qii là xác suất để hệ quay lại i ít nhất m lần. Sử dụng công thức xác suất đầy đủ và tính Markov của hệ ta thu được phương trình ∞ (m) ∗ (m−1) ∗ (m−1) Qii = X fii(k)Qii = fiiQii k=1 Từ đó m ∗ m−1 1 ∗ m Qii =(fii) Qii =(fii) 1 ∗ (m) vì rõ ràng Qii = fii. Vì rằng Qii = lim Qii ta rút ra Qii =0 hay 1 m→∞ ∗ tuỳ theo fii 0 Suy ra Qij =1.
  27. Simpo PDF Merge and Split Unregistered Version - 1.2. Phân loại trạng thái xích Markov 29 Ví dụ 1.15. (Sự phá sản chắc chắn của nguời chơi cờ bạc) Một người vào sòng bạc với số tiền trong túi là 1000 đôla và chơi đánh bạc như sau: Mỗi ván chơi anh ta tung một đồng tiền cân đối đồng chất. Nếu đồng tiền ra mặt ngửa anh ta được một đôla, nếu ra mặt sấp anh ta mất một đô la. Gọi Xn là số tiền anh ta có sau n ván chơi. Khi đó X0 = 1000 và X0,X1, là một du động ngẫu nhiên đối xứng với trạng thái ban đầu X0 = 1000. Theo định lý trên với xác suất 1 Xn sẽ viếng thăm trạng thái 0. Nói cách khác sớm hay muộn anh ta sẽ nhẵn túi. Định lý 1.10. Cho (Xn) là xích tối giản không hồi quy. Khi đó với mọi i, j ∞ X Pij (n) k ∞ ∞ = X fij(k) X Pjj(m) k=1 m=1 ∞ ∞ ∗ = fij X Pjj(m) ≤ X Pjj(m) < ∞. m=1 m=1
  28. Simpo PDF Merge and Split Unregistered Version - 30 Chương 1. Quá trình Markov Định lý 1.11. Cho (Xn) là xích tối giản hồi quy không có chu kỳ . Khi đó với mọi i, j 1 lim Pij (n)= n µj ởđó ∞ µj = X kfjj(k). k=1 Chứng minh. Chứng minh dựa cơ bản trên một kết quả sau đây của giải tích mà ta sẽ phát biểu dưới dạng một bổ đề ( không chứng minh): Bổ đề 1.4. Cho (fn) là một dãy các số không âm có tổng bằng 1 và ưóc chung lớn nhất của tất cả các số j>0 mà fj > 0 bằng 1. Cho (un) là dãy xác định truy hồi theo cách sau n u0 =1,un = X fkun−k. k=1 Khi đó 1 lim un = ∞ . n→∞ P kfk k=1 Cố định j. Đặt un = Pjj(n),fk = fjj(k). Bổ đề 4 cho phép ta kết luận 1 lim Pjj(n)= . n µj Tiếp theo với quy ước Pij(s)=0nếu s<0 ta viết lại hệ thức (1.10) dưới dạng ∞ Pij(n)=X fij (k)Pjj(n − k). k=1 Chú ý rằng 1 lim Pjj(n − k)= n→∞ µj
  29. Simpo PDF Merge and Split Unregistered Version - 1.2. Phân loại trạng thái xích Markov 31 ∞ ∗ và Pk=1 fij(k)=fij = Qij =1( theo định lý 1.7) áp dụng định lý hội tụ bị chặn ta thu được ∞ lim Pij (n)=X fij(k) lim Pjj(n − k) n n→∞ k=1 ∗ 1 1 = fij = . µj µj Nếu i là trạng thái hồi quy thì µi chính là thời gian trung bình ( hay số bước trung bình) để hệ lần đầu tiên quay lại i. Thời gian trung bình này có thể hữu hạn hay vô hạn. Ta có định nghĩa sau: Định nghĩa 1.8. Trạng thái hồi quy i được gọi là trạng thái hồi quy dương nếu µi < ∞ và được gọi là trạng thái hồi quy không nếu µi = ∞. Ví dụ 1.16. Giả sử (Xn) là du động ngẫu nhiên đối xứng trên đường thẳng. Trong ví dụ ta đã thấy mọi trạng thái là hồi quy. Ta chứng minh mọi trạng thái là hồi quy không. Thật vậy ta có 2n P (2n)= (1/2)n(1/2)n,P(2n +1)=0. ii n ii Thành thử 2m P (s)=X P (n)sn = X  (1/2)2ms2m ii ii m n m 2m = X  (s2/4)m = ((1 − s2)−1/2. m m Từ phương trình (1.7) ta suy ra −1 2 1/2 Fii(s)=1− Pii(s) =1− (1 − s ) . (1.11) Theo bổ đề Abel k−1 µi = X kfii(k) = lim X kfii(k)s s→1− k k 0 2 −1/2 = lim Fii(s) = lim s(1 − s ) = ∞. s→1− s→1−
  30. Simpo PDF Merge and Split Unregistered Version - 32 Chương 1. Quá trình Markov Định lý 1.12. Giả sử i → j. Nếu i hồi quy dương thì j hồi quy dương. Nếu i hồi quy không thì j hồi quy không. Chứng minh. Ta chỉ cần chứng minh nếu tồn tại trạng thái j là hồi quy dương thì mọi trạng thái i mà i ↔ j cũng hồi quy dương. Thật vậy tồn tại m, n sao cho Pij(n) > 0,Pji(m) > 0. Với mọi k ta có Pii(n + k + m) ≥ Pij(n)Pjj(k)Pji(m). Từ đó và từ định lý 1.11 ta có 1 = lim Pii(n + k + m) µi k 1 ≥ lim Pij (n)Pjj(k)Pji(m)=Pij (n)Pji(m) > 0. k µj Vậy µi < ∞ tức i là hồi quy dương. Theo định lý 1.4, π =(π1,π2, ) là phân bố giới hạn duy nhất của xích. Từ định lý 1.11 và 1.12 suy ra Định lý 1.13. Giả sử (Xn) là xích tối giản không có chu kỳ với không gian trạng thái đếm được E. Khi đó sẽ xảy ra một trong ba khả năng sau đây: 1) Mọi trạng thái là không hồi quy. Khi đó với mọi i, j lim Pij(n)=0. n Xích không có phân bố dừng. 2) Mọi trạng thái là hồi quy không. Khi đó với mọi i, j lim Pij (n)=0 n Xích không có phân bố dừng.
  31. Simpo PDF Merge and Split Unregistered Version - 1.2. Phân loại trạng thái xích Markov 33 3) Mọi trạng thái là hồi quy dương. Khi đó với mọi i, j lim Pij (n)=πj > 0 n và π =(π1,π2, ) là phân bố giới hạn (và cũng là phân bố dừng) của xích. Định lý 1.14. Giả sử (Xn) là xích tối giản không có chu kỳ với không gian trạng thái hữu hạn E = {1, 2, , d}. Khi đó mọi trạng thái đều hồi quy dương và xích có phân bố giới hạn π =(π1,π2, , πd). Phân bố này cũng là phân bố dừng duy nhất của xích. Chứng minh. Theo định lý 1.13 ta chỉ cần chứng tỏ khả năng 1) hoặc 2) không xảy ra. Thật vậy nếu trái lại thì với mọi i, j lim Pij (n)=0. n Vậy d d 1 = lim X Pij(n)=X lim Pij (n)=0. n n j=1 j=1 Mâu thuẫn. Đối với xích tối giản (có thể có chu kỳ) ta có định lý sau đây (không chứng minh): Định lý 1.15. Giả sử Xn là xích tối giản với không gian trạng thái E đếm được. Khi đó 1. Với mỗi i, j ∈ E n −1 1 lim n X Pij (k)= . n→∞ µj k=1 1 Nói cách khác dãy Pij(n) hội tụ theo trung bình Cesaro tới πj = µj không phụ thuộc i. 2. Dãy π =(πj) thoả mãn
  32. Simpo PDF Merge and Split Unregistered Version - 34 Chương 1. Quá trình Markov ∞ • P πj ≤ 1 j=1 ∞ • πj = P πiPij . i=1 Như là một hệ quả của định lý trên ta có định lý sau (so sánh với 1.13): Định lý 1.16. Cho (Xn) là xích Markov tối giản. Khi đó 1. Nếu E hữu hạn có d phần tử thì (π1, , πd) là phân bố dừng duy nhất. 2. Chỉ có các khả năng sau: • Mọi trạng thái của E là không hồi quy • Mọi trạng thái của E là hồi quy không • Mọi trạng thái của E là hồi quy dương. 3. Nếu E là vô hạn đếm được thì xích có phân bố dừng khi và chỉ khi mọi trạng thát của E là hồi quy dương. Trong trường hợp này phân bố dừng là duy nhất. 1.3 Quá trình Markov Xét họ các ĐLNN rời rạc (Xt),t ≥ 0 với tập chỉ số t là các số thực không âm t ∈ [0, ∞). Ký hiệu E = Xt(Ω) là tập giá trị của Xt. Khi đó E là một tập hữu hạn hay đếm được, các phần tử của nó được ký hiệu là i, j, k .Ta gọi (Xt) là một quá trình ngẫu nhiên với không gian trạng thái E . Định nghĩa 1.9. Ta nói rằng (Xt) là một quá trình Markov nếu với mọi t1 < <tk <tvà với mọi i1,i2, in,i∈ E P {Xt = i|Xt1 = i1,Xt2 = i2 , Xtk = ik} = P {Xt = i|Xtk = ik}.
  33. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 35 Như vậy, xác suất có điều kiện của một sự kiện B nào đó trong tương lai nếu biết hiện tại và quá khứ của hệ cũng giống như xác suất có điều kiện của B nếu chỉ biết trạng thái hiện tại của hệ. Đó chính là tính Markov của hệ. Đôi khi tính Markov của hệ còn phát biểu dưới dạng: Nếu biết trạng thái hiện tại Xt của hệ thì quá khứ Xu,u t là độc lập với nhau. Giả sử P {Xt+s = j|Xs = i} là xác suất để xích tại thời điểm s ở trạng thái i sau một khoảng thời gian t , tại thời điểm t + h chuyển sang trạng thái j. Đây là một con số nói chung phụ thuộc vào i, j, t, s. Nếu đại lượng này không phụ thuộc s ta nói xích là thuần nhất. Trong giáo trình này ta chỉ xét xích Markov thuần nhất. Ký hiệu Pij(t)=P {Xt+s = j|Xs = i}. Ta gọi Pij (t) là xác suất chuyển của hệ từ trạng thái i sang trạng thái j sau một khoảng thời gian t . Ký hiệu P (t)=(Pij (t),i,j ∈ E). P (t) là một ma trận hữu hạn hay vô hạn chiều. Chú ý rằng i)Pij (t) ≥ 0 ii) X Pij (t)=1. j∈E Phân bố của X0 được gọi là phân bố ban đầu. Ta ký hiệu ui = P (X0 = i). Chứng minh tương tự như trường hợp xích Markov ta có kết luận sau: Định lý 1.17. Phân bố hữu hạn chiều của quá trình (Xt) được hoàn toàn xác định từ phân bố ban đầu và xác suất chuyển. Cụ thể với t1 <t2 < < tn phân bố đồng thời của (Xt1 , , Xtn) được tính theo công thức sau P (Xt1 = i1, , Xtn = in)= = X uiPii1 (t1)Pi1i2 (t2 − t1) Pin−1in (tn − tn−1). i∈E
  34. Simpo PDF Merge and Split Unregistered Version - 36 Chương 1. Quá trình Markov Định lý 1.18. (Phương trình Chapman-Kolmogorov) Pij (t + s)=X Pik(t)Pkj(s). k∈E 1.3.1 Trường hợp không gian trạng thái hữu hạn Giả sử E = {1, 2, , d}. Khi đó từ phương trình C-K P (t),t > 0 là một họ các ma trận thoả mãn đẳng thức sau P (t + s)=P (t)P (s). Nói cách khác họ (P (t),t>0) lập thành một nửa nhóm các ma trận. Từ nay về sau ta sẽ luôn giả thiết thêm rằng 1. Pij (0) = δij 2. limt→0 Pij (t)=δij ởđâyδij là ký hiệu Kronecke 1 nếu i = j δij =  0 nếu i =6 j.  Định lý 1.19. Hàm ma trận P (t) là một hàm liên tục và tồn tại P (t) − I P 0(0) = lim . h→0+ h Chứng minh. Theo giả thiết thì P (0) = I và limt→0 P (t)=I tức là P (t) liên tục tại 0. Ta chứng minh P (t) liên tục tại t>0. Ta có do tính chất nửa nhóm lim P (t + h) = lim P (t)P (h)=P (t)I = P (t). h→0+ h→0 Vậy P (t) liên tục phải. Ta lại có với 0 <h<tthì P (t)=P (h)P (t − h) .Do P (h) → I khi h → 0 nên tồn tại P (h)−1 với h đủ nhỏ. Vậy lim P (t − h) = lim P (t)P (h)−1 = P (t)I = P (t). h→0+ h→0−
  35. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 37 Vậy P (t) cũng liên tục trái do đó liên tục. (Thực ra có thể chứng minh được rằng P (t) liên tục đều trên [0, ∞). Tiếp theo sử dụng tính chất nửa nhóm ta có với mọi h>0,n: P (nh) − I =(P (h) − I)(I + P (h)+P (2h)+ + P ((n − 1)h)) . (1.12) Vì P (t) liên tục nếu h → 0 sao cho nh → t>0 thì n−1 t h X → Z P (u)du. k=0 0 t Tồn tại t>0 để tích phân R0 P (u)du là ma trận không suy biến. Ta lại có lim P (nh) − I = P (t) − I. Từ (1.12) suy ra n − P (h) − I t 1 lim =(P (t) − I) Z P (u)du h→0+ h 0 Ký hiệu P (h) − I A = P 0(0) = lim . h→0+ h A =(aij) được gọi là ma trận cực vi của nửa nhóm (P (t)).Tacó Pij (t) lim = aij nếu i =6 j t→0 t 1 − Pii(t) lim = ai (1.13) t→0 t ởđâyai = −aii. Từ (1.13) ta có Pij (t)=aijt + o(t) 1 − Pii(t)=ait + o(t). Thành thử aij được gọi là cường độ chuyển từ trạng thái i sang trạng thái j và ai là cường độ thoát khỏi trạng thái i của hệ.
  36. Simpo PDF Merge and Split Unregistered Version - 38 Chương 1. Quá trình Markov Từ đẳng thức 0= P Pij (t)+Pii − 1 chia hai vế cho t và cho t → 0 ta j:j=6 i thu được X aij =0 j hay tương đương ai = X aij j:j=6 i Định lý 1.20. Cho quá trình Markov với nửa nhóm P (t),t>0 các xác suất chuyển. Gọi A là ma trận cực vi của nửa nhóm. Khi đó ta có P 0(t)=P (t)A 0 ↔ Pij(t)=X Pik(t)akj − Pij(y)aj (1.14) k=6 j và P 0(t)=AP (t) 0 ↔ Pij (t)=X Pkjaik − Pij (y)ai. (1.15) k=6 i Phương trình ( (1.14)) được gọi là phương trình thuận và phương trình (1.15) được gọi là phương trình ngược Kolmogorov. Chứng minh. Ta có do tính chất nửa nhóm P (t + h) − P (t) P (t)(P (h) − I) = h h (P (h) − I)P (t) = . h Cho h → 0 ta có điều cần chứng minh. Phương trình thuận và nghịch là các phương trình vi phân với điều kiện ban đầu P (0) = I có thể giải được bằng phương pháp quen thuộc trong lý thuyết phương trình vi phân. Ta có kết quả sau (không chứng minh):
  37. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 39 Định lý 1.21. Phưong trình (1.14) và phương trình (1.15) có nghiệm là ∞ Antn P (t)=eAt = I + X . n! n=1 Ngược lại cho trước ma trận A =(aij) cấp d × d thoả mãn aij ≥ 0 nếu i =6 j và P aij =0. Đặt j P (t)=eAt. Khi đó tồn tại quá trình Markov với d trạng thái nhận P (t) làm họ ma trận xác suất chuyển. Ví dụ 1.17. (Quá trình Markov hai trạng thái) Xét quá trình Markov với hai trạng thái E = {0, 1}. (Chẳng hạn ta xét sự tiến triển theo thời gian của một hệ thống nào đó trong đó trạng thái 0 biểu thị trạng thái trì trệ còn trạng thái 1 biểu thị trạng thái làm việc tích cực của hệ thống). Giả sử cường độ chuyển từ trạng thái 0 sang trạng thái 1 là λ và cường độ chuyển từ trạng thái 1 sang trạng thái 0 là µ. Ma trận cực vi là −λλ! A = . µ −µ Ta đi tìm công thức cho xác suất chuyển Pij (t) bằng cách giải phương trình ngược. Phương trình (1.15) cho ta 0 P00(t)=−λP00(t)+λP10(t) 0 P10(t)=µP00(t) − µP10(t). Trừ hai phương trình trên vế với vế ta có: 0 (P00(t) − P10(t)) = −(λ + µ)(P00(t) − P10(t)) −(λ+µ)t ⇒ P00(t) − P10(t)=(P00(0) − P10(0))e = e−(λ+µ)t.
  38. Simpo PDF Merge and Split Unregistered Version - 40 Chương 1. Quá trình Markov Vậy 0 −(λ+µ)t P00(t)=−λ(P00(t) − P10(t)) = −λe t Z 0 ⇒ P00(t)=P00(0) + P00(s)ds 0 λ =1− (1 − e−(λ+µ)t) µ + λ µ λ = + e−(λ+µ)t. µ + λ µ + λ Từ đó −(λ+µ)t P10(t)=P00(t) − e µ µ = − e−(λ+µ)t. µ + λ µ + λ Hoàn toàn tương tự từ phương trình (1.15) ta có 0 P01(t)=−λP01(t)+λP11(t) 0 P11(t)=µP01(t) − µP11(t). ta tìm được λ λ P (t)= − e−(λ+µ)t 01 µ + λ µ + λ λ µ P (t)= + e−(λ+µ)t. 11 µ + λ µ + λ Bây giờ chúng ta xét dáng điệu tiệm cận của ma trận xác suất chuyển P (t) khi t →∞. Cho quá trình Markov (Xt) với không gian trạng thái E hữu hạn và ma trận xác suất chuyển P (t)=Pij(t). Ta nói rằng quá trình là tối giản nếu Pij (t) > 0 với mọi i, j ∈ E. (Chú ý rằng ta không có khái niệm "chu kỳ của một trạng thái" như là đối với xích Markov). Định lý 1.22. Cho quá trình Markov tối giản (Xt)với không gian trạng thái E = {1, 2, , d} hữu hạn và ma trận xác suất chuyển P (t)=Pij (t). Khi đó với mỗi i, j ∈ E tồn tại giới hạn hữu hạn lim Pij (t)=πj t→∞
  39. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 41 chỉ phụ thuộc j không phụ thuộc i. Thêm vào đó π =(π1,π2, , πd) là phân bố xác suất duy nhất thoả mãn phương trình π = πP(t), ∀t>0. Chứng minh. Với mỗi h>0 cố định P (h) là một ma trận xác suất chuyển với các phần tử đều dưong, vậy theo định lý 1.5 ta có tồn tại lim P (nh) = lim P (h)n =Π(h) n→∞ n→∞ trong đó Π(h) là ma trận với các dòng như nhau và bằng π(h) .Thêm vào đó π(h)=(π1(h),π2(h), , πd(h)) là phân bố xác suất duy nhất thoả mãn phương trình π(h)=π(h)P (h), ∀t>0. Mặt khác ta biết rằng P (t) liên tục đều trên [0, ∞). Trong giải tích ta biết rằng nếu một hàm P (t) liên tục đều sao cho lim P (nh) tồn tại với mỗi h>0 n→∞ thì kéo theo limt→∞ P (t) tồn tại. Vậy ta kết luận tồn tại lim P (t)=Π t→∞ với Π=Π(h) với mọi h>0. Từ đó suy ra kết luận của định lý. Ví dụ 1.18. Trong ví dụ về quá trình Markov hai trạng thái từ biểu thức của Pij (t) ta có lim Pij (t)=πj t→∞ với µ λ π = ,π= . 0 λ + µ 1 λ + µ Nếu chọn π =(π0,π1) là phân bố ban đầu của quá trình thì P (Xt =0)=P (X0 =0)P00(t)+P (X0 =1)P10(t) µ = π P (t)+π P (t)=π = . 0 00 1 10 0 λ + µ Tương tự λ P (X =1)=π = . t 1 λ + µ Như vậy phân bố của Xt không phụ thuộc vào t.
  40. Simpo PDF Merge and Split Unregistered Version - 42 Chương 1. Quá trình Markov 1.3.2 Trường hợp không gian trạng thái vô hạn đếm được Trong trường hợp không gian trạng thái E là vô hạn đếm được ta gặp những khó khăn về toán học khi muốn mở rộng các kết quả trong trường hợp hữu hạn. Ta có kết quả sau đây (công nhận không chứng minh): Định lý 1.23. (1) Với mọi i =6 j giới hạn 0 Pij (t) Pij(0) = lim = aij t→0 t luôn tồn tại hữu hạn. (2) Với mỗi i giới hạn 0 Pii(t) − 1 Pii(0) = lim = aii = −ai t→0 t tồn tại nhưng có thể bằng vô cùng. Đối với trường hợp không gian trạng thái hữu hạn ta có P aij =0hay j X aij = ai. j=6 i Trong trường hợp E vô hạn nói chung ta chỉ có bất đẳng thức sau X aij ≤ ai ∀i ∈ E (1.16) j=6 i Thật vậy ta có X Pij (t)=1− Pii(t) j=6 i thành thử với mọi m n X Pij(t) ≤ 1 − Pii(t). j=1,j=6 i
  41. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 43 Chia hai vế cho t và đẩy t → 0 ta thu được m X aij ≤ ai. j=1,j=6 i Cho m →∞ta thu được (1.16). Từ nay về sau ta chỉ xét các quá trình Markov thoả mãn điều kiện X aij = ai < ∞. (1.17) j=6 i Ma trận vô số chiều A =(aij) cũng được gọi là ma trận cực vi của quá trình đang xét. Định lý 1.24. Cho quá trình Markov với P (t)=(Pij (t)) là họ các ma trận xác suất chuyển. Gọi A là ma trận cực vi của quá trình. Khi đó ta có P 0(t)=P (t)A 0 ⇔ Pij (t)=X Pik(t)akj − Pij(y)aj (1.18) k=6 j và P 0(t)=AP (t) 0 ⇔ Pij(t)=X aikPkj − Pij (y)ai (1.19) k=6 i Phương trình (1.18) được gọi là phương trình thuận và phương trình (1.19) được gọi là phương trình ngược Kolmogorov. Chứng minh. Ta chỉ chứng minh cho phương trình ngược còn thừa nhận sự đúng đắn của phương trình thuận vì chứng minh khá phức tạp về toán học. Ta có: Pij (s + t) − Pij (t)=X Pik(s)Pkj(t) − Pij (t) k = X Pik(s)Pkj(t)+(Pii(s) − 1)Pij (t) (1.20) k=6 i
  42. Simpo PDF Merge and Split Unregistered Version - 44 Chương 1. Quá trình Markov Với mỗi m cố định ta có m −1 −1 lim inf s X Pik(s)Pkj(t) ≥ lim inf s X Pik(s)Pkj(t) s→0 s→0 k=6 i k=1,k=6 i m = X aikPkj(t). k=1,k=6 i Cho m →∞ta được −1 lim inf s X Pik(s)Pkj(t) ≥ X aikPkj(t). (1.21) s→0 k=6 i k=6 i Tiếp theo với m>ita có m ∞ X Pik(s)Pkj(t) ≤ X Pik(s)Pkj(t)+X Pik(s) k=6 i k=1,k=6 i m+1 m m = X Pik(s)Pkj(t)+1− Pii(s) − X Pik(s). k=1,k=6 i k=1,k=6 i Chia hai vế cho s và lấy lim sup ta thu đươc m m −1 lim sup s X Pik(s)Pkj(t) ≤ X aikPkj(t)+ai − X aik(s). s→0 k=6 i k=1,k=6 i k=1,k=6 i Cho m →∞và chú ý đến điều kiện (1.17) ta được −1 lim sup s X Pik(s)Pkj(t) ≤ X aikPkj(t). s→0 k=6 i k=6 i So sánh với (1.21) ta nhận được −1 lim s X Pik(s)Pkj(t)=X aikPkj(t). s→0 k=6 i k=6 i Trong 1.20 chia hai vế cho s rồi cho s → 0 và áp dụng đẳng thức trên ta suy ra (1.19).
  43. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 45 Bây giờ chúng ta xét dáng điệu tiệm cận của ma trận xác suất chuyển P (t) khi t →∞. Cho quá trình Markov (Xt) với không gian trạng thái E vô hạn đếm được và ma trận xác suất chuyển P (t)=Pij (t). Ta nói rằng quá trình là tối giản nếu Pij (t) > 0 với mọi i, j ∈ E. ( Chú ý rằng ta không có khái niệm "chu kỳ của một trạng thái" như là đối với xích Markov). Định lý 1.25. Cho quá trình Markov tối giản (Xt)với không gian trạng thái E = {1, 2, , } đếm được và ma trận xác suất chuyển P (t)=Pij (t). Khi đó với mỗi i, j ∈ E tồn tại giới hạn hữu hạn lim Pij (t)=πj t→∞ chỉ phụ thuộc j không phụ thuộc i. Thêm vào đó giới hạn π =(π1,π2, , ) hoặc là tất cả bằng không πj =0 ∀j ∈ E hoặc là tất cả dương và lập thành một phân bố xác suất. Phân bố đó được gọi là phân bố giới hạn của quá trình πj > 0 ∀j ∈ E, X πj =1. j Ta công nhận và không chứng minh định lý này. Định lý 1.26. Phân bố giới hạn π =(π1,π2, , ) thoả mãn hệ phương trình tuyến tính sau πjaj = X πkakj. k=6 j Chứng minh. Từ phương trình C-K Pij (s + t)=X Pik(s)Pkj(t) k∈E cho s →∞ta thu được πj = X πkPkj(t). k
  44. Simpo PDF Merge and Split Unregistered Version - 46 Chương 1. Quá trình Markov Suy ra πj(1 − Pjj(t)) = X πkPkj(t). k=6 j Chia hai vế cho t và cho t → 0 ta được hệ thức phải chứng minh. Ví dụ 1.19. (Quá trình sinh và chết.) Xét quá trình Markov (Xt) với không gian trạng thái E = {0, 1, 2, }. (Xt) được gọi là quá trình sinh và chết nếu các xác suất chuyển Pij (t) thoả mãn các điều kiện sau đây 1. Pi.i+1(t)=λit + o(t) ∀i ≥ 0 khi t → 0 2. Pi.i−1(t)=µit + o(t) ∀i ≥ 1 khi t → 0 3. Pii(t)=1− (λi + µi)t + o(t), ∀i ≥ 0 khi t → 0 4. Pij (t)=o(t) với |i − j| > 1 5. Pij (0) = δij 6. µi =0,λ0 > 0,µi,λi > 0,i=1, 2, Quá trình Xt được sử dụng để mô tả sự phát triển của một quần thể A nào đó. Mỗi cá thể của quần thể A tại mỗi thời điểm có thể sinh ra một cá thể mới hoặc bị chết đi. Ký hiệu Xt là số lượng cá thể của quần thể tại thời điểm t. Các điều kiện trên có nghĩa là nếu tại thời điểm t quần thể có i cá thể thì trong một khoảng thời gian bé (s, s + t) xác suất để số lượng quần thể tăng thêm một cá thể là λit + o(t) và xác suất để giảm đi một cá thể là µit + o(t), xác suất để tăng giảm ít nhất hai cá thể là o(t). Các tham số λi,i=0, 1, 2 được gọi là cường độ sinh, các tham số µi,i=1, 2, được gọi là cường độ chết. Ma trận cực vi A =(aij) có dạng ai,i+1 = λi ai,i−1 = µi, ai = λi + µi, aij =0 nếu |i − j| > 1
  45. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 47 tức là −λ0 λ0 000   µ1 −(λ1 + µ1) λ1 00    A =  0 µ −(λ + µ ) λ   2 2 2 2        Phương trình thuận (1.14) trong trường hợp này có dạng 0 Pij(t)=Pi,j−1(t)λj−1 + Pi,i+1(t)µj+1 − (λj + µj )Pij(t) (1.22) 0 Pi0(t)=−λ0Pi0(t)+µ1Pi1(t). (1.23) Giả sử quá trình sinh và chết có phân bố giới hạn π =(πi). Từ định lý 1.26 ta có λ0π0 = µ1π1 (λk + µk)πk = λk−1πk−1 + µk+1πk+1 Đặt ak = µkπk − λk−1πk−1. Từ phương trình trên suy ra ak = ak+1.Vì a1 = µ1π1 − λ0π0 =0nên suy ra ak =0 ∀k hay µkπk = λk−1πk−1 ∀k =1, 2, (1.24) λk−1 ⇒ πk = πk−1 (1.25) µk λk−1λk−2 λ0 ⇒ πk = π0. (1.26) µkµk−1 µ1 Vì P πk =1nên từ (1.24) suy ra k ∞ λk−1λk−2 λ0  1=π0 + π0 X . µkµk−1 µ1 k=1 Vậy điều kiện cần để có phân bố giới hạn là chuỗi ∞ λ λ λ X  k−1 k−2 0  (1.27) µkµk−1 µ1 k=1 hội tụ. Ngược lại có thể chứng minh được điều kiện chuỗi (1.27) hội tụ cũng là điều kiện đủ để quá trình có phân bố giới hạn.
  46. Simpo PDF Merge and Split Unregistered Version - 48 Chương 1. Quá trình Markov Ta xét một số ví dụ. Ví dụ 1.20. (Một mô hình đơn giản trong lý thuyết xếp hàng) Giả sử cửa hàng dịch vụ A chỉ có một người phục vụ. Khách đến xếp hàng đợi đến lượt mình được phục vụ và cửa hàng chỉ phục vụ từng khách một. Khi cửa hàng đang phục khách thì các khách mới có thể đến và xếp hàng chờ. Khách được phục vụ xong thì lập tức rời khỏi cửa hàng. Giả sử xác suất để trong khoảng thời gian (t, t + h) có một khách mới vào hàng là λh + o(h) và cũng giả sử rằng nếu tại thời điểm t khách đang được phục vụ thì xác suất để sự phục vụ hoàn tất trong khoảng thời gian (t, t + h) là µh + o(h). Gọi Xt là số khách có mặt tại cửa hàng tại thời điểm t (tức là số khách đang xếp hàng chờ phục vụ cộng với khách đang được phục vụ tại thời điểm t). Dễ thấy đây là một quá trình sinh và chết với cưòng độ sinh và cưòng độ chết đều là hằng số λi = λ, µi = µ. Khi đó chuỗi (1.27) trở thành chuỗi ∞ λ X( )k. µ k=1 Vậy: Quá trình có phân bố giới hạn (và đây cũng là phân bố dừng) khi và chỉ khi λ<µ. Khi đó ta có λ λ π = 1 −  ( )k. k µ µ λ Tỷ số r = µ gọi là cường độ giải phóng hàng. Nếu r<1 thì khi t khá lớn, số khách có mặt ở cửa hàng Xt là một ĐLNN có phân bố hình học k P (Xt = k)=(1− r)r . 1 Suy ra số khách có mặt trung bình là EXt = 1−r . Trong một thái cực khác, ta giả sử cửa hàng có rất nhiều nhân viên phục vụ sao cho bất cứ người khách nào đến cũng được phục vụ ngay. Gọi Xt là số khách có mặt tại cửa hàng tại thời điểm t (tức là số khách đang được phục vụ tại thời điểm t).Tacó Pi,i+1(h)=P {Xt+h = i +1|Xt = i} = λh + o(h),
  47. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 49 Pi,i−1(h)=P (có đúng một khách trong i khách được phục vụ xong) i =  [µh + o(h)][1 − µh + o(h)]i−1 1 = iµh + o(h). Vậy Xt là quá trình sinh và chết với λi = λ, µi = iµ. Khi đó công thức (1.24) cho ta 1 λ π = ( )kπ k k! µ 0 và chuỗi (1.27) trở thành chuỗi ∞ 1 λ X ( )k = eλ/µ − 1. k! µ k=1 Từ điều kiện ∞ λ/µ 1=X πk = π0e k=0 rút ra rk π = e−r . k k! λ Như vậy khi t đủ lớn Xt có phân bố Poisson với tham số r = µ . Giá trị trung bình của Xt khi t đủ lớn là r, nó chính bằng tỷ số giữa thời gian phục vụ trung bình 1/µ với khoảng thời gian trung bình xuất hiện một khách mới 1/λ. Một kết luận khá phù hợp với thực tế!. Ví dụ 1.21. (Quá trình sinh thuần tuý) Nếu quá trình sinh và chết mà không xảy ra sự chết thì ta gọi là quá trình sinh thuần tuý. Như vậy đối với quá trình sinh thuần tuý ta có µj =0 ∀j ≥ 1 và Pij(t)=0 nếu j<i.
  48. Simpo PDF Merge and Split Unregistered Version - 50 Chương 1. Quá trình Markov Phương trình thuận (1.22) trở thành 0 Pij(t)=λj−1Pi,j−1 − λj Pij(t) (1.28) 0 Pii(t)=−λiPii(t). (1.29) Vì Pii(0) = 1 ta suy ra −λit Pii(t)=e . (1.30) Để giải phương trình vi phân (1.28) ta có bổ dề sau: Bổ đề 1.5. Phương trình vi phân f 0(t)=−λf(t)+g(t) (1.31) có nghiệm là t f(t)=f(0)e−λt + Z e−λ(t−s)g(s)ds. 0 Thật vậy nhân hai vế của (1.36) với eλt ta được 0 eλtf(s) = eλsg(s). Lấy tích phân hai vế từ 0 tới t ta được t eλtf(t) − f(0) = Z e−λsg(s)ds. 0 Nhân hai vế với e−λt ta có kết luận của bổ đề. Vì Pij (0) = 0 i =6 j nên từ bổ đề và phương trình (1.28) ta có t Z −λj(t−s) Pij(t)=λj−1 e Pi,j−1(s)ds. (1.32) 0 Ta có thể sử dụng (1.30) và (1.32) như một công thức truy hồi để tìm lần lượt Pij (t) với j = i +1,i+2, Chẳng hạn ta có t Z −λi+1(t−s) −λis Pi,i+1(t)=λi e e ds. 0 Suy ra  λi −λit −λi+1t (e − e nếu λi+1 =6 λi λi+1−λi  Pi,i+1(t)= (1.33) λ te−λit nếu λ = λ .  i i+1 i
  49. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 51 Ví dụ 1.22. (Quá trình sinh tuyến tính) Xét sự tăng trưởng cá thể của một quần thể nào đó. Giả sử rằng mỗi cá thể của quần thể độc lập với nhau trong khoảng thời gian (t, t + h) có xác suất sinh thêm một cá thể mới là λh + o(h) và xác suất để không sinh thêm cá thể nào trong khoảng thời gian (t, t + h) là 1 − λh + o(h). Goị Xt là số lượng cá thể ở thời điểm t. Xt là một quá trình sinh thuần tuý và Pii(h)=P {Xt+h = i|Xt = i} =[1− λh + o(h)]i =1− λih + o(h), Pi,i+1(h)=P {Xt+h = i +1|Xt = i} i =  [λh + o(h)][1 − λh + o(h)]i−1 1 = iλh + o(h). Như vậy cường độ sinh là λi = λi. Từ (1.33) ta có −iλt −λt Pi,i+1(t)=ie (1 − e ). Để tính Pi,i+2(t) ta đặt j = i +2trong (1.32) và thu được t Z −(i+2)λ(t−s) −iλs −λs Pi.i+2(t)=(i +1)iλ e e (1 − e )ds 0 t =(i +1)iλe−(i+2)λt Z e2λi(1 − e−λs)ds 0 t =(i +1)iλe−(i+2)λt Z eλt(eλs − 1)ds 0 (eλt − 1)2 =(i +1)iλe−(i+2)λt 2λ i +1  e−iλt(1 − e−λt)2. 2
  50. Simpo PDF Merge and Split Unregistered Version - 52 Chương 1. Quá trình Markov Tiếp tục như vậy áp dụng công thức truy hồi (1.32) và bằng quy nạp ta thu được i + k − 1 P (t)= e−iλt(1 − e−λt)k. i,i+k k Như vậy sự gia tăng dân số Xs+t − Xs trong khoảng thời gian t có phân bố −λt nhị thức âm với các tham số p = e và r = i,ởđói = Xs. Thành thử λt −λt E[Xs+t − Xs|Xs = i]=ie (1 − e ). Nếu tại thời điểm ban đầu s =0quần thể có số lượng i cá thể thì tại thời điểm t số cá thể trung bình sẽ là λt E[Xt]=E[Xt − X0]+i = ie . Quá trình sinh tuyến tính này đôi khi còn được gọi là quá trình Yule, do nhà toán sinh người Anh Yule đưa ra năm 1924. Ví dụ 1.23. (Quá trình Poisson.) Xét quá trình sinh thuần tuý Xt với cường độ sinh là hằng số λi = λ,i=0, 1, Khi đó công thức (1.32) trở thành t Z −λ(t−s) Pij(t)=λ e Pi,j−1(s)ds. (1.34) 0 Từ công thức (1.33) ta thu được −λt Pi,i+1(t)=λte . Để tính Pi,i+2(t) ta đặt j = i +2 trong (1.34) và thu được t Z −λ(t−s) −λs Pi,i+2(t)=λ e e ds 0 t (λ)2 = λ2e−λt Z sds = e−λt. 0 2
  51. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 53 Tiếp tục như vậy áp dụng công thức truy hồi (1.34) và bằng quy nạp ta thu được (λt)k P (t)= e−λt. i,i+k k! Như vậy sự gia tăng dân số Xs+t − Xs trong khoảng thời gian t có phân bố Poisson với tham số λt. Một cách tổng quát ta sẽ chứng minh rằng với 0 <s<tthì ĐLNN Xt − Xs sẽ có phân bố Poisson với tham số λ(t − s). Thật vậy ta có ∞ P (Xt − Xs = k)=X P (Xs = i)P (Xt = k + i|Xs = i) i=0 ∞ = X P (Xs = i)Pi,i+k(t − s) i=0 ∞ (λ(t − s))k = X P (X = i) e−λ(t−s) s k! i=0 ∞ (λ(t − s))k = e−λ(t−s) X P (X = i) k! s i=0 (λ(t − s)k) = e−λ(t−s). k! Tiếp theo ta chứng minh rằng Xt là quá trình ngẫu nhiên có gia số độc lập. Thật vậy, với 0 ≤ t1 <t2 < ···<tn ta có P Xt2 − Xt1 = i1, , Xtn − Xtn−1 = in−1 ∞ = X P (Xt1 = i)P0i1 (t2 − t1) P0in−1(tn − tn−1) i=0 ∞ = P0i1 (t2 − t1) P0in−1(tn − tn−1) X P (Xt1 = i) i=0 = P0i1 (t2 − t1) P0in−1(tn − tn−1) = P (Xt2 − Xt1 = i1) P (Xtn − Xtn−1 = in−1). Thành thử Xt2 − Xt1 , , Xtn − Xtn−1 là các ĐLNN độc lập.
  52. Simpo PDF Merge and Split Unregistered Version - 54 Chương 1. Quá trình Markov Quá trình Xt,t≥ 0 được gọi là quá trình Poisson với cường độ λ>0 nếu nó thoả mãn các điều kiện sau 1. X0 =0. 2. Với 0 ≤ s 0 . Quá trình Poisson có rất nhiều ứng dụng trong thực tế. Nó dùng để mô tả số lần xuất hiện của một sự kiện ngẫu nhiên nào đó trong khoảng thời gian t, chẳng hạn số lần gọi đến tổng đài, số khách hàng đến một cửa hàng nào đó, số lần hỏng hóc của một đường dây, 1.3.3 Trường hợp tổng quát Một vài khái niệm cơ bản về quá trình ngẫu nhiên. Xét quá trình Markov với không gian trạng thái E bất kỳ. Cho (E,A) là một không gian đo. Quá trình ngẫu nhiên Xt được gọi là quá trình Markov nếu P (Xt+s ∈ A|F≤t)=P (Xt+s ∈ A|Ft). Nghĩa là : Nếu ta biết trạng thái của hệ tại thời điểm hiện tại t thì mọi thông tin về hành vi của hệ trong quá khứ không có ảnh hưởng đến sự biến diễn trong tương lai của hệ. Nói cách khác: Quá khứ và tương lai độc lập với nhau khi biết hiện tại. Ký hiệu P (s, x, t, A)=P (Xt ∈ A|Xs = x) P (s, x, t, A) là xác suất để hệ tại thời điểm s đang ở trạng thái x sang thời điểm t rơi vào tập A. Ta gọi P (s, x, t, A) là xác suất chuyển. Họ các xác suất chuyển có các tính chất sau:
  53. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 55 Định lý 1.27. 1. Với mỗi s ≤ t, x ∈ EP(s, x, t, .) là một độ đo xác suất trên E 2. Với mỗi s ≤ t, A ∈Ahàm P (s, ., t, A) là một hàm đo được trên E 3. ( Phương trình C-K (Chapman- Kolmogorov) ) P (s, x, t, A)=Z P (s, x, u, dy)P (u, y, t, A). E Quá trình Markov Xt được gọi là thuần nhất nếu xác suất chuyển P (s, x, t, A) chỉ phụ thuộc vào hiệu số t − s nghĩa là P (s + u, x, t + u, A)=P (s, x, t, A) ∀u Khi đó P (s, x, t, A) có dạng P (s, x, t, A)=P (t − s, x, A) ởđóP (t, x, A)=P (Xs+t ∈ A|Xs = x) là xác suất để hệ tại thời điểm s ở trạng thái x sau một khoảng thời gian t ( tại thời điểm t + s) rơi vào A. Phương trình Chapman- Kolmogorov khi ấy trở thành P (t + s, x, A)=Z P (t, x, dy)P (s, y, A). E Trong giáo trình này ta chỉ xét quá trình Markov thuần nhất. Trong trường hợp độ đo P (t, x, .) có mật độ f(t, x, u) thì phương trình C-K tương đương với f(t + s, x, z)=Z f(t, x, y)f(s, y, z)dy. E Ngược lại cho trước một họ các hàm P (t, x, A) thoả mãn các điều kiện nêu trong định lý (1.27). Với mỗi độ đo xác suất µ trên (E,A) ta xác định họ
  54. Simpo PDF Merge and Split Unregistered Version - 56 Chương 1. Quá trình Markov các phân bố hữu hạn chiều (µt1, ,tn) như sau µt1, ,tn(A1, , An) Z Z Z = µ(dx)P (t1, x, dy1)P (t2 − t1,y1,dy2) yn∈An y1∈A1 x∈E P (tn − tn−1,yn−1,dyn). Sử dụng các tính chất của họ xác suất chuyển ta chứng minh được họ các phân bố xác suất này thoả mãn điều kiện tương thích Kolmogrov. Thành thử tồn tại một quá trình ngẫu nhiên (Xt) sao cho: • Phân bố của X0 ( phân bố ban đầu) là µ. • Với mọi 0 ≤ t1 < < tn phân bố đồng thời của (Xt1 , , Xtn) là µt1, ,tn. Hơn nữa có thể chứng minh rằng Xt là một quá trình Markov thuần nhất nhận P (t, x, A) làm xác suất chuyển. Ví dụ 1.24. (Chuyển động Brown hay quá trình Wiener.) Xét hàm f(t, x, y) cho bởi công thức 2 1 − (u−x) f(t, x, u)=√ e 2t 2πt và P (t, x, .) là độ đo xác suất trên R nhận f(t, x, .) làm hàm mật độ P (t, x, A)=Z f(t, x, du). A Khi đó ta có thể chứng minh rằng họ P (t, x, A) thoả mãn các điều kiện của định lý (1.27). Thật vậy, gọi φt(u) là hàm mật độ của N(0,t) thì như ta biết φt+s = φt ∗ φs hay Z φt+s(u)= φs(v)φt(u − v)dv. Đặt u = x − z,v = y − z → dv = dy suy ra Z φt+s(x − z)= φs(y − z)φt(x − y)dy
  55. Simpo PDF Merge and Split Unregistered Version - 1.3. Quá trình Markov 57 hay f(t + s, x, z)=Z f(t, x, y)f(s, y, z)dy. Do đó tồn tại quá trình Markov với họ P (t, x, A) là họ xác suất chuyển và phân bố ban đầu µ = δ0. Quá trình Markov này được gọi là chuyển động Brown hay quá trình Wiener và được ký hiệu là (Wt). Các phân tích sâu sắc hơn nữa chứng tỏ (Wt) có các tính chất sau 1. W0 =0. 2. Với mỗi 0 ≤ s<tthì Wt − Ws là ĐLNN có phân bố chuẩn với kỳ vọng 0 và phương sai là t − s . 3. W (t) là một quá trình gia số độc lập tức là với mọi 0 ≤ t1 <t2 < < tn các ĐLNN Wt2 − Wt1 ,Wt3 − Wt2 , , Wtn − Wtn−1 là độc lập. 4. Wt có quỹ đạo liên tục. Bây giờ chúng ta sẽ trình bày phương pháp xây dựng các hàm xác suất chuyển. Như đã biết mỗi độ đo µ trên R ta cho ứng với phiếm hàm T trên Cb(R) bởi Z Tµξ = ξ(u)dµ(u). R Tương ứng này là một-một. Nếu biết Tξ với mỗi ξ thì có thể xác định được µ.Ta định nghĩa φ(t, x)=Z ξ(u)P (t, x, du). (1.35) R Nếu với mỗi ξ ta tìm được hàm φ(t, x) tương ứng thì coi như tìm được P (t, x, .). Ta có kết quả sau: Định lý 1.28. Ký hiệu B(x, )=[x − , x + ],Bc(x, )=R \ B(x, ). Giả
  56. Simpo PDF Merge and Split Unregistered Version - 58 Chương 1. Quá trình Markov sử rằng lim t−1P (t.x, Bc(x, )) = 0 ∀x,  t→0+ lim t−1 Z (u − x)P (t, x, du)=a(x) → t 0+ B(x,) lim t−1 Z (u − x)2P (t, x, du)=b(x) → t 0+ B(x,) Khi đó hàm φ(t, x) xác định bởi (1.35) thoả mãn phương trình vi phân sau ∂φ ∂φ b(x) ∂2φ = a(x) + (1.36) ∂t ∂x 2 ∂x2 với điều kiện ban đầu lim φ(t, x)=ξ(x). (1.37) t→0+ Ngược lại cho trước hai hàm a(x),b(x). Khi đó với một số giả thiết về hai hàm a(x),b(x) với mỗi hàm liên tục bị chặn ξ phương trình (1.36) với điều kiện ban đầu (1.37) sẽ có nghiệm duy nhất φ(t, x) và do đó xác định cho ta độ đo P (t, x, .). Họ độ đo này lập thành một họ xác suất chuyển. Hơn nữa quá trình Markov tương ứng với họ xác suất chuyển này có quỹ đạo liên tục. 1.4 Bài tập 1. Cho xích Markov Xn,n =0, 1, 2, với không gian trạng thái E = {0, 1, 2} và ma trận xác suất chuyển 0.10, 20, 7 P = 0.90, 00, 1 . 0, 10, 80.1 Biết phân bố ban đầu là p0 =0, 3,p1 =0, 4,p2 =0, 3. Tính P (X0 =0,X1 =1,X2 =2).
  57. Simpo PDF Merge and Split Unregistered Version - 1.4. Bài tập 59 2. Người ta truyền một bức điện 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 đúng tín hiệu với xác suất a. Ký hiệu X0 là tín hiệu truyền đi và Xn là tín hiệu nhận được ở trạm n. Biết rằng (Xn) lập thành xích Markov với ma trận xác suất chuyển a 1 − a! P = . 1 − aa Giả sử tín hiệu truyền đi là tín hiệu 0. i) Tính xác suất để không nhận sai tín hiệu cho tới trạm n =2. ii) Tính xác suất để nhận đúng tín hiệu của trạm n =2. ii) Tính xác suất để nhận đúng tín hiệu của trạm n =5. 3. Cho xích Markov Xn,n=0, 1, 2, với không gian trạng thái E =0, 1, 2 và ma trận xác suất chuyển 0.10, 20, 7 P = 0.20, 20, 6 0, 60, 10.3 2 Tính P , P (X3 =1|X1 =0)và P (X3 =1|X0 =0). 4. Cho xích Markov Xn,n=0, 1, 2, với không gian trạng thái E =0, 1, 2 và ma trận xác suất chuyển 0.00, 50, 5 P = 0.50, 00, 5 0, 50, 50.0 Tính P (X2 =1|X0 =0)và P (X3 =0|X0 =0). 5. Giả sử Xn chất lượng của chi tiết tại công đoạn thứ n của dây chuyền sản xuất với Xn =0có nghĩa là tốt còn Xn =1có nghĩa là xấu. Biết rằng (Xn)là xích Markov với ma trận xác suất chuyển 0.99 0.01! P = 0.12 0, 88
  58. Simpo PDF Merge and Split Unregistered Version - 60 Chương 1. Quá trình Markov Tính P (X4 =1|X1 =1). 6. Cho xích Markov Xn,n=0, 1, 2, với không gian trạng thái E =1, 2, 3 và ma trận xác suất chuyển 0.10, 50, 4 P = 0.60, 20, 2 0, 30, 40.3 Phân bố ban đầu là (0, 7; 0, 2; 0, 1). i) Lập bảng phân bố xác suất của X2. ii) Tính P (X0 =1,X1 =3,X2 =3,X3 =2). iii) Tìm phân bố dừng. 7. Cho xích Markov Xn,n =0, 1, 2, với không gian trạng thái E = {1, 2, 3} và ma trận xác suất chuyển  3/73/71/7  P = 1/11 2/11 8/11 1/11 4/11 6/11 Giả sử P (X0 =1)=1. Đặt  1 nếu Xn =1 Yn =  2 nếu X =16  n Chứng minh rằng (Yn) là một xích Markov. Tìm ma trận xác suất chuyển. 8. Cho (rn) là dãy Rademakher P (rn =1)=p, P (rn = −1) = q =1− p. Trong các dãy ĐLNN sau đây dãy nào lập thành xích Markov (a) Xn = rnrn+1 (b) Xn = r1r2 rn
  59. Simpo PDF Merge and Split Unregistered Version - 1.4. Bài tập 61 (c) Xn =Φ(rn,rn+1) trong đó Φ(−1, −1)=1, Φ(−1, 1)=2, Φ(1, −1) = 3, Φ(1, 1) = 4 Đối với dãy lập thành xích Markov hãy tìm ma trận xác suất chuyển. 9. Mỗi người dân của thị trấn N có một trong ba nghề A, B, C. Con cái của họ nối tiếp nghề của cha mình với xác suất tương ứng cho các nghề A, B, C 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. Giả sử thế hệ hiện tại 20% theo nghề A 30% theo nghề B và 50% theo nghề C. Hãy tìm (a) Tìm phân bố nghề nghiệp ở thế hệ tiếp theo. (b) Tìm phân bố giới hạn theo nghề nghiệp của dân cư thị trấn trong tương lai xa xôi. 10. Cho xích Markov (Xn),n =0, 1, 2, với không gian trạng thái E = {1, 2, 3} và ma trận xác suất chuyển  001 P =  100 1/21/20 (a) Chứng minh rằng xích tối giản. (b) Tìm chu kỳ của xích. (c) Tìm phân bố dừng. 11. Cho xích Markov (Xn),n =0, 1, 2, với không gian trạng thái E = {1, 2, 3, 4, 5} và ma trận xác suất chuyển 01/32/30 0 00 01/43/4   P = 00 01/43/4     10000 10000
  60. Simpo PDF Merge and Split Unregistered Version - 62 Chương 1. Quá trình Markov (a) Chứng minh rằng xích tối giản. (b) Tìm chu kỳ của xích. (c) Tìm phân bố dừng. 12. Giả sử ta theo dõi sự xuất hiện của biến cố A theo thời gian. Ký hiệu Xt là số lần xuất hiện A trong khoảng thời gian (0,t] và giả thiết Xt là quá trình Poisson với cường độ λ. (a) Tìm xác suất để trong khoảng thời gian (0,s] biến cố A xảy ra m lần nếu biết rằng trong khoảng thời gian (0,t] biến cố A xảy ra n lần ở đó 0 jta có i P (t)= (e−µt)j(1 − e−µt)i−j . ij j 14. Cho quá trình sinh và chết Xt với λi = iλ, µi = iµ ởđóλ, µ là các hằng số dương. Cố định i. Đặt ∞ mi(t)=EiX(t)=X jPij(t) j=0
  61. Simpo PDF Merge and Split Unregistered Version - 1.4. Bài tập 63 (a) Viết phương trình thuận cho quá trình Xt. 0 (b) Sử dụng phương trình thuận để chứng minh rằng mi(t)=(λ − µ)mi(t). (c) Suy ra (λ−µ)t mi(t)=ie . 15. Cho quá trình sinh và chết Xt với λi = iλ, µi = iµ ởđóλ, µ là các hằng số dương. Cố định i. Đặt ∞ 2 2 si(t)=EiX (t)=X j Pij (t). j=0 (a) Sử dụng phương trình thuận chứng minh rằng 0 si(t)=2(λ − µ)si(t)+(λ + µ)mi(t). (b) Tìm si(t). (c) Tìm VarXt nếu X0 = i. 16. Chứng minh rằng họ t f(t, x, y)= π(t2 +(x − y)2) lập thành họ mật độ chuyển thoả mãn phương trình Chapman - Kol- mogorov. Quá trình Markov tương ứng có tên là quá trình Cauchy.
  62. Simpo PDF Merge and Split Unregistered Version - Chương 2. Quá trình dừng Đặng Hùng Thắng Quá trình ngẫu nhiên và tính toán ngẫu nhiên NXB Đại học quốc gia Hà Nội 2007 Tr 64 -142. Từ khoá: Quá trình dừng, Hàm tự tương quan, Độ do phổ, mật độ phổ, Biểu diễn phổ, Tiếng ồn trắng, Trung bình trượt tích phân. Tài liệu trong Thư viện điện tử ĐH Khoa học Tự nhiên có thể sử dụng cho mục đích học tập và nghiên cứu cá nhân. Nghiêm cấm mọi hình thức sao chép, in ấn phục vụ các mục đích khác nếu không được sự chấp thuận của nhà xuất bản và tác giả.
  63. Simpo PDF Merge and Split Unregistered Version - Chương 2 Quá trình dừng 2.1 Quá trình dừng thời gian rời rạc . . . . . . . . . 65 2.1.1 Hàm tự tương quan . . . . . . . . . . . . . . . . . 65 2.1.2 Một số dãy dừng quan trọng . . . . . . . . . . . . 71 2.1.3 Độ đo phổ và mật độ phổ . . . . . . . . . . . . . . 86 2.1.4 Biểu diễn phổ . . . . . . . . . . . . . . . . . . . . . 95 2.1.5 Bài toán dự báo . . . . . . . . . . . . . . . . . . . 107 2.1.6 Tính chất ergodich . . . . . . . . . . . . . . . . . . 111 2.2 Quá trình dừng thời gian liên tục . . . . . . . . . 119 2.2.1 Hàm tự tương quan, độ đo phổ, biểu diễn phổ . . . 119 2.2.2 Tiếng ồn trắng, trung bình trượt tích phân . . . . 124 2.2.3 Phương trình vi phân, dự báo và tính ergodic . . . 130 2.3 Bàitập 139 Trong chương 1 ta đã nghiên cứu sự tiến triển theo thời gian của một hệ thống vật lý mà tương lai chỉ phụ thuộc vào hiện tại và độc lập với quá khứ.
  64. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 65 Tuy nhiên trong thực tế đặc biệt là trong các lĩnh vực kinh tế, thị trường chứng khoán, cơ học thống kê, khí tượng thuỷ văn ta thường gặp các hệ ngẫu nhiên mà trong quá trình phát triển tương lai không chỉ phụ thuộc vào hiện tại mà còn phụ thuộc cả vào quá khứ nữa. Khi dự báo cho tương lai của một quá trình như vậy chúng ta không chỉ quan tâm tới hiện tại mà còn phải quan tâm tới quá khứ của hệ nữa. Mô hình xác suất để mô ta quá trình như vậy gọi là quá trình dừng. 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 cuả Lý thuyết xác suất. Chương này được chia làm hai phần. Phần thứ nhất trình bày quá trình dừng với thời gian rời rạc. Phần thứ hai trình bày các kết quả tương ứng cho trường hợp quá trình dừng với thời gian liên tục. Tuy nhiên do khuôn khổ cuốn sách trong phần B chúng tôi tập trung vào việc giới thiệu các khái niệm, định nghĩa. Các định lý được nêu ra và giải thích ý nghĩa, nêu ví dụ minh hoạ chứ không chứng minh chi tiết. 2.1 Quá trình dừng thời gian rời rạc 2.1.1 Hàm tự tương quan Cho dãy (Xn) các ĐLNN với tập chỉ số n ∈ Z={0, ±1, ±2, }. Khi đó ta nói (Xn) là một quá trình ngẫu nhiên với thời gian rời rạc. Ký hiệu m(k)=EXk,r(k,h)=cov(Xk,Xh)=E(Xk − m(k))(Xh − m(h)). Ta gọi m(k) là hàm trung bình còn r(k,h) là hàm tự tương quan của dãy. Định nghĩa 2.1. (Xn) được gọi là một quá trình dừng (còn gọi là dãy dừng hoặc chuỗi thời gian) nếu hàm trung bình là một hằng số và hàm tương quan r(k,h) chỉ phụ thuộc vào hiệu |k − h|. Như vậy nếu (Xn) là một quá trình dừng thì tồn tại hàm K(h) xác định trên tập số nguyên Z sao cho với mọi n ∈ Z K(h)=cov(Xn+h,Xn).
  65. Simpo PDF Merge and Split Unregistered Version - 66 Chương 2. Quá trình dừng Hàm K(n) gọi là hàm tự tương quan (autocovariance function) của dãy (Xn). Ta có DXn = cov(Xn,Xn)=K(0). Định lý 2.1. Hàm tự tương quan K(n) có các tính chất sau 1. K(n) là một hàm chẵn K(n)=K(−n). 2. |K(n)|≤K(0), ∀n ∈ Z . 3. K(n) là một hàm xác định không âm trên Z tức là với mọi số nguyên dương n, với mọi số thực hay phức a1,a2, , an ta có n n X X aiajK(i − j) ≥ 0 . i=1 j=1 Chứng minh. 1. Hiển nhiên do định nghĩa. 2. Ta có theo bất đẳng thức Cauchy-Schwartz 2 2 2 |K(n)| = |E(Xn − m)(X0 − m)| ≤ (DXn)(DX0)=|K(0)| . 3. n ! " n n # 0 ≤ D X aiXi = Cov X aiXi, X ajXj = i=1 i=1 i=1 n n n n = X X bibjCov[Xi,Xj ]=X X aiajK(i − j). i=1 j=1 i=1 j=1 Ngược lại ta có kết quả sau (công nhận không chứng minh): Định lý 2.2. Nếu K(n) là một hàm chẵn xác định không âm trên Z thì tồn tại một quá trình dừng Gaussian (Xn) nhận K(n) làm hàm tự tương quan.
  66. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 67 Ví dụ 2.1. Cho Wn là dãy các ĐLNN không tương quan với EWn = 2 0,EWnWm = δmn và DWn = σ .Tacó r(k + n, k)=EWk+nWk =0 nếu n =06 . Do đó Wn là một quá trình dừng với hàm tự tương quan σ2 nếu h =0 K(h)= . 0 nếu h =06  Ta gọi Wn là dãy ồn trắng với tham số σ. Ví dụ 2.2. Xét dãy (Xn) xác định như sau Xn = Wn + rWn−1 trong đó r là hằng số thực. Ta có r(n + h, h)=cov(Xn+h,Xh) = E[(Wn+h + rWn+h−1)(Wn + rWn−1)] = EWn+hWn + rEWn+hWn−1 + rEWn+h−1Wn+ 2 + r EWn+h−1Wn−1. 2 2 Do đó nếu h =0thì r(n, n)=σ (1+r ).Vớih =1thì r(n+1,n)=rDXn = 2 2 rσ với h = −1 thì r(n−1,n)=rDXn = rσ và r(n+h, n)=0nếu h =6 ±1. Thành thử (Xn) là một quá trình dừng với hàm tự tương quan là σ2(1 + r2) nếu h =0   K(h)=σ2r nếu h = ±1 0 nếu |h| > 1  Để chứng minh một hàm là xác định không âm ta thường chứng minh bằng cách chứng tỏ rằng nó là hàm tự tương quan của một quá trình dừng nào đó.
  67. Simpo PDF Merge and Split Unregistered Version - 68 Chương 2. Quá trình dừng Ví dụ 2.3. a. Chứng minh rằng hàm K(h)=σ2 cos λh là hàm xác định không âm, ở đó λ là một số thực, σ là một số dương cho trước. b. Tổng quát hơn cho trước các số thực λ1, , λn và các số dương σ1, , σn. Chứng tỏ rằng hàm n 2 T (h)=X σk cos λkh k=1 là hàm xác định không âm. Giải: a. Thật vậy giả sử U và V là hai ĐLNN không tương quan EU = EV = 2 2 2 0,EU = EV = σ . Xét dãy (Xn) xác định bởi Xn = U cos λn + V sin λn. Ta có mn = cos λnEU + sin λnEV =0. r(k,h)=EXkXh = E [(U cos λk + V sin λk)(U cos λh + V sin λk)] = E[U 2 cos λk cos λh + V 2 sin λk sin λh + UV cos λk sin λh + UV sin λk cos λh] = σ2(cos λk cos λh + sin λk sin λh) = σ2 cos λ(h − k)=K(h − k). 2 Vậy (Xn) là một quá trình dừng với hàm tự tưong quan K(h)=σ cos λh. b. Tiếp theo, giả sử U1,U2, , Um và V1,V2, , Vm là các ĐLNN với EUk = 2 2 2 EVk =0 ,EUk = EVk = σk , EUiUk =0 (i =6 k) EViVk =0 (i =6 k) EUiVj =0,λ1, , λm ∈ R . Xét dãy (Xn) xác định bởi m Xn = X(Uk cos λkn + Vk sin λkn). k=1 Tính toán tương tự như trên ta có (Xn) là quá trình dừng với hàm tự tương quan m 2 T (h)=X σi cos λih. i=1
  68. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 69 Ví dụ 2.4. Chúng ta sẽ chứng minh rằng hàm sau đây 1 nếu h =0   K(h)=θ nếu h = ±1 0 nếu |h| > 1  là hàm xác định không âm nếu và chỉ nếu |θ|≤1/2. Thật vậy giả sử |θ|≤1/2. Theo ví dụ 2.2 ở trên ta chỉ cần chứng tỏ rằng tồn tại các số σ, r sao cho σ2(1 + r2)=1 σ2r = θ có nghiệm. Quả vậy, từ hai phương trình trên suy ra r (1 + r2)= . θ Từ đó √ 1 ± 1 − 4θ2 1 r = ,σ2 = . 2θ 1+r2 n−1 Đảo lại nếu θ>1/2 xét các số a1 =1,a2 = −1,a3 =1, , an =(−1) . Khi đó n n n n−1 2 X X aiajK(i − j)=X ai +2X aiai+1 i=1 j=1 i=1 i=1 = n − 2θ(n − 1) 2θ/(2θ−1).VậyK(h) không là hàm xác định không âm. Tương tự nếu θ 2θ/(2θ − 1).
  69. Simpo PDF Merge and Split Unregistered Version - 70 Chương 2. Quá trình dừng Ví dụ 2.5. (Dãy tự hồi quy cấp 1 hay dãy AR(1).) Giả sử (Xn) là một quá trình dừng thoả mãn phương trình sai phân sau đây Xn = pXn−1 + Wn trong đó p là một hằng số |p| 0 K(h)=EXn−hXn = EXn−h(pXn−1 + Wn)= pEXn−1Xn−h + EXn−hWn = pK(h − 1). Suy ra K(h)=phK(0). Lại có K(0) = EXnXn = EXn(pXn−1 + Wn) 2 = pK(1) + E(WnXn)=pK(1) + pE(WnXn−1)+EWn = pK(1) + σ2 = p2K(0) + σ2. Suy ra σ2 K(0) = . 1 − p2 Tóm lại p|h|σ2 K(h)= . 1 − p2 Ví dụ 2.6. (Du động ngẫu nhiên.) Cho (Xn) là dãy các ĐLNN độc lập cùng 2 phân bố với kỳ vọng 0 và phương sai là σ . Xét dãy Sn cho bởi Sn =0 nếu n ≤ 0,Sn = X1 + X2 + ···+ Xn.
  70. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 71 Tacóvớih>0 r(n + h, n)=ESn+hSn = E(Sn + Xn+1 + ···Xn+h)Sn 2 = DSn = nσ phụ thuộc vào n.VậySn không phải là quá trình dừng. Nếu (Xn) là một quá trình dừng thì từ định nghĩa ta suy ra với mọi số nguyên h, n véc tơ (X1, , Xn) và véc tơ (X1+h, ,Xn+h) có cùng giá trị trung bình và có cùng ma trận tương quan. Tuy nhiên chưa chắc chúng đã có cùng phân bố. Một quá trình dừng mạnh là quá trình mà hai vector trên không chỉ có cùng giá trị trung bình và ma trận tương quan mà có cùng luật phân bố. Ta có định nghĩa sau: Định nghĩa 2.2. Dãy (Xn) được gọi là một quá trình dừng mạnh nếu mọi số nguyên h, n hai vector ngẫu nhiên (X1, , Xn) và vector (X1+h, , Xn+h) có cùng phân bố. 2 Rõ ràng một quá trình dừng mạnh với EXn = E(XY )=Z X(ω)Y (ω)dP. Ω
  71. Simpo PDF Merge and Split Unregistered Version - 72 Chương 2. Quá trình dừng Sự hội tụ trong L2(Ω, F,P) được gọi là sự hội tụ bình phương trung bình (bptb). Như vậy dãy (Xn) hội tụ bình phương trung bình tới X khi và chỉ khi 2 lim E(Xn − X) =0 n→∞ và ta viết lim Xn = X trong L2 n→∞ hay L2 − lim Xn = X. n→∞ ∞ n Ta nói chuỗi S = P Xn hội tụ bptb tới S nếu dãy tổng riêng Sn = P Xk n=1 k=1 hội tụ bptb tới S. Ta có các tính chất cơ bản sau đây của sự hội tụ bptb. Định lý 2.3. 1. Điều kiện cần và đủ để dãy (Xn) hội tụ bptb là 2 lim E|Xn − Xm| =0 m,n→∞ hoặc tồn tại lim EXnXm. (2.1) m,n→∞ 2. Nếu lim Xn = X,lim Yn = Y trong L2 n→∞ n→∞ thì (i) lim EXn = EX. n 2 2 (ii) lim EXn = EX . n→∞ (iii) lim limn EXnYn = EXY . n→∞ (iv) lim cov(Xn,Yn)=cov(X, Y ). n Chứng minh.
  72. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 73 1. Do tiêu chuẩn Cauchy trong không gian Hilbert L2(Ω, F,P). 2. Nếu tồn tại giới hạn trong (2.1) bằng c thì 2 lim E|Xn − Xm| m,n→∞ = lim EXnXn − 2 lim EXnXm + lim EXmXm n m,n→∞ m = c − 2c + c =0. Đảo lại nếu Xn → X trong L2 thì do tính liên tục của tích vô hướng suy ra lim EXnXm = lim = . m,n→∞ m,n→∞ Theo bất đẳng thức Cauchy-Schwartz 2 lim |EXn − EX|≤lim pE|Xn − X| =0 n n Lại có vì cov(Xn,Yn)= −(EXn)(EYn)nên lim cov(Xn,Yn)= −(EX)(EY ) n = cov(X, Y ). 2 Định lý 2.4. Giả sử Wn là một dãy ồn trắng với tham số σ và (hi),i∈ Z là dãy số thoả mãn 2 X |hi| < ∞. i∈Z Khi đó chuỗi Xn = X hiWn−i i∈Z hội tụ bptb và dãy (Xn) là một quá trình dừng với hàm tự tương quan 2 K(h)=σ X hihi+h. i∈Z
  73. Simpo PDF Merge and Split Unregistered Version - 74 Chương 2. Quá trình dừng Chứng minh. Đặt Sn = P|i|≤n hiWn−i Khi đó Sn − Sm = X hiWn−i. m<|i|≤n Sử dụng tính chất EWiWj =0, (i =6 j) suy ra 2 E|Sn − Sm| = X hihj EWiWj m<|i|,|j|≤n 2 2 = σ ( X |hi| ). m<|i|≤n Vậy chuỗi Xn = lim Sn = X hiWn−i n i∈Z hội tụ bptb và K(h) = lim ESn+hSn n = lim X hihjEWn−iWn+h−j n |i|,|j|≤n = X hihj EWn−iWn+h−j . i∈Z,j∈Z Nhưng σ2 nếu i = j − h EWn−iWn+h−j =  . 0 nếu i =6 j − h  Suy ra 2 K(h)=σ X hihi+h. i∈Z Định nghĩa 2.3. 1. Quá trình (Xn) có biểu diễn dưới dạng Xn = X hiWn−i i∈Z được gọi là một trung bình trượt hai phía.
  74. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 75 2. Quá trình (Xn) có biểu diễn dưới dạng ∞ Xn = X hiWn−i i=0 được gọi là một trung bình trượt (moving average) một phía. Ký hiệu là MA(∞). 3. Quá trình (Xn) có biểu diễn dưới dạng q Xn = X hiWn−i i=0 được gọi là một trung bình trượt cấp q ký hiệu là MA(q). Quá trình (Xn) trong ví dụ 2.2 là một trung bình trượt cấp 1 MA(1). Vì một quá trình trung bình trượt một phía là quá trình trung bình trượt hai phía với hi =0nếu i q do đó hàm tự tương quan của nó là  2 q−h σ P hihi+h nếu 0 ≤|h|≤q K(h)= i=0 . 0 nếu |h| >q  Một quá trình dừng có tính chất : nếu |k − h| >qthì Xh và Xk không tương quan với nhau được gọi là một quá trình q-tương quan. Một quá trình mà các số hạng của nó đôi một không tương quan ( chẳng hạn như dãy ồn trắng) là một quá trình 0-tương quan. Như vậy một quá trình trung bình trượt cấp q là một quá trình q-tương quan. Điều thú vị là khẳng định ngược lại cũng đúng
  75. Simpo PDF Merge and Split Unregistered Version - 76 Chương 2. Quá trình dừng Định lý 2.5. Nếu (Xn) là một quá trình q-tương quan với giá trị trung bình 0 thì nó là một quá trình trung bình trượt cấp q. Một quá trình trung bình trượt có thể xem như được tạo thành bởi một phép biến đổi tuyến tính dãy ồn trắng Wn.Tổng quát hơn ta có Định lý 2.6. Cho (Yn) là một quá trình dừng với trung bình không và hàm tự tương quan KY (h). Cho dãy số thực (hi) thoả mãn X |hi| < ∞. i∈Z Khi đó chuỗi Xn = X hiYn−i i∈Z hội tụ hầu chắc chắn và hội tụ bptb. Dãy (Xn) là một quá trình dừng với hàm tự tương quan K(h)=X hihj KY (h + i − j). i∈Z Chứng minh. Ta có E|hiYn−i| = |hi|E|Yn−i| ≤|hi|pKY (0) Vậy thì X E|hiYn−i|≤pKY (0) X |hi| < ∞ i∈Z i∈Z Suy ra X |hiYn−i| < ∞ hầu chắc chắn i∈Z Vậy chuỗi Xn = X hiYn−i i∈Z hội tụ hầu chắc chắn .
  76. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 77 Tiếp theo, đặt Sn = P|i|≤n hiYn−i. Khi đó Sn − Sm = X hiYn−i. m<|i|≤n Vậy thì 2 E|Sn − Sm| = X hihj EYiYj m<|i|,|j|≤n ≤ X |hi||hj||KY (i − j)| m<|i|,|j|≤n ≤ KY (0) X |hi||hj| m<|i|,|j|≤n = KY (0) X |hi|→0 khi m, n →∞. n<|i|<m Vậy chuỗi Xn = lim Sn = X hiWn−i n i∈Z hội tụ bptb và K(h) = lim ESn+hSn n = lim X hihjEYn−iYn+h−j n |i|,|j|≤n = X hihj KY (h + i − j). i∈Z,j∈Z Ví dụ 2.7. Cho trước số thực p. Quá trình dừng (Xn) được gọi là một quá trình tự hồi quy cấp 1 hay một quá trình AR(1) nếu Xn thoả mãn phương trình sai phân sau đây Xn = pXn−1 + Wn. Sau đây ta sẽ chứng minh rằng nếu |p|6=1thì tồn tại và và duy nhất dãy AR(1) (Xn). Ngoài ra khi |p| < 1 thì (Xn) là có biểu diễn trung bình trượt
  77. Simpo PDF Merge and Split Unregistered Version - 78 Chương 2. Quá trình dừng một phía AM(∞ ): ∞ i Xn = X p Wn−i i=0 còn khi |p| > 1 thì (Xn) là có biểu diễn trung bình trượt dạng −1 i Xn = X (−p )Wn−i. i=−∞ Khi |p| =1thì không tồn tại dãy AR(1). Thật vậy, xét trường hợp |p| < 1. Đặt ∞ i Xn = X p Wn−i. i=0 ∞ 2i Vì P p < ∞ nên theo định lý 2.4 dãy (Xn) tồn tại và i=0 ∞ ∞ i i+1 Xn − pXn−1 = X p Wn−i − X p Wn−1−i i=0 i=0 ∞ ∞ i i = X p Wn−i − X p Wn−i i=0 i=1 = Wn. Sự tồn tại được chứng minh. Tiếp theo giả sử (Yn) là một dãy AR(1) bất kỳ. Ta có Yn = pYn−1 + Wn = Wn + p(pYn−2 + Wn−1 2 = Wn + pWn−1 + p Yn−2. Từ đó bằng quy nạp ta có với mọi k =0, 1, k i k+1 Yn = X p Wn−i + p Yn−k−1. (2.2) i=0
  78. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 79 Ký hiệu KY (h) là hàm tự tương quan của (Yn).Ta có k i 2 2(k+1) 2 E|Yn − X p Wn−i| = |p| E|Yn−k−1| i=0 2(k+1) |p| KY (0) → 0 khi k →∞. ∞ i Vậy Yn = P p Wn−i = Xn. i=0 Tiếp theo xét trường hợp |p| > 1. Đặt ∞ −i Xn = − X p Wn+i. i=1 ∞ −2i Vì P p < ∞ nên theo định lý 2.4 dãy (Xn) tồn tại và i=1 ∞ ∞ −i −(i−1) Xn − pXn−1 = − X p Wn+i + X p Wn+(i−1) i=1 i=1 ∞ ∞ −i −i = − X p Wn+i + X p Wn+i = Wn. i=1 i=0 Sự tồn tại được chứng minh. Tiếp theo giả sử (Yn) là một dãy AR(1) bất kỳ. Ta có −1 −1 Yn+1 = pYn + Wn+1 → Yn = p Yn+1 − p Wn+1 −1 −1 −1 −1 = p (p Yn+2 − p Wn+2) − p Wn+1 −1 −2 −2 = −p Wn+1 − p Wn+2 + p Yn+2. Từ đó bằng quy nạp ta có với mọi k =0, 1, k −i −(k+1) Yn = − X p Wn+i + p Yn+k+1. i=1 Lý luận tương tự như trên ta suy ra ∞ −i Yn = − X p Wn+i i=1 −1 i = Xn = X (−p )Wn−i. i=−∞
  79. Simpo PDF Merge and Split Unregistered Version - 80 Chương 2. Quá trình dừng Xét trường hợp |p| =1. Giả sử tồn tại dãy AR(1) (Xn). Từ đẳng thức (2.2) ta có k k+1 2 2i 2 2 E(Xn − p Xn−k−1) = X |p E|Wn−i| = σ (k +1). (2.3) i=0 Mặt khác vế trái của đẳng thức (2.3) là 2 2 EXn + E|Xn−k−1| ± 2E(XnXn−k−1) =2K(0) ± 2K(k +1)≤ 4K(0). Suy ra với mọi k σ2(k +1)≤ 4K(0). Đó là điều vô lý. Vậy không tồn tại dãy AR(1) khi |p| =1. Định nghĩa 2.4. Dãy (Xn) được gọi là một dãy tự hồi quy cấp p hay một dãy AR(p) nếu nó là một dãy dừng có trung bình 0 và thoả mãn phương trình sai phân sau Xn = α1Xn−1 + α2Xn−2 + ···αpXn−p + Wn Ta có các kết quả sau đây (xem chứng minh ở định lý 2.9 và 2.10). Định lý 2.7. Dãy AR(p) tồn tại và duy nhất khi và chỉ khi đa thức kết hợp 2 p Φ(z)=1− α1z − α2z −···−αpz không có nghiệm trên vòng tròn đơn vị |z| =1 Định lý 2.8. Dãy AR(p) có biểu diễn trung bình trượt một phía ∞ Xn = X hiWn−i i=0 khi và chỉ khi đa thức kết hợp 2 p Φ(z)=1− α1z − α2z −···−αpz không có nghiệm bên trong vòng tròn đơn vị |z|≤1.
  80. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 81 Mô hình tổng quát bao hàm cả mô hình tự hồi quy và mô hình trung bình trượt là mô hình hỗn hợp tự hồi quy trung bình trượt. Định nghĩa 2.5. Dãy (Xn) được gọi là một dãy hỗn hợp tự hồi quy trung bình trượt cấp (p, q) hay một dãy ARMA(p, q) nếu nó là một dãy dừng có trung bình 0 và thoả mãn phương trình sai phân sau q Xn = α1Xn−1 + α2Xn−2 + ···αpXn−p + X βiWn−i (2.4) i=0 2 p q i ởđóh0 =1và hai đa thức Φ(z)=1−α1z−α2z −· · ·−αpz , Θ(z)=Pi=0 βiz không có nhân tử chung (tức là chúng nguyên tố cùng nhau). Như vậy dãy tự hồi quy cấp p AR(p) chính là dãy ARMA(p, 0) và dãy trung bình trượt cấp q chính là dãy ARMA(0,q). Ký hiệu B là toán tử lùi một bước xác định bởi BXn = Xn−1. Khi đó i B Xn = Xn−i. m i Nếu P (z)=Pi=0 ciz là một đa thức bậc m thì toán tử P (B) được định nghĩa như sau m m i P (B)Xn = X ciB Xn = X ciXn−i. i=0 i=0 Khi đó phương trình sai phân (2.4) của dãy ARMA(p, q)(Xn) có dạng sau Φ(B)Xn =Θ(B)Wn. (2.5) Định lý 2.9. Dãy ARMA(p, q) tồn tại và duy nhất khi và chỉ khi đa thức 2 p Φ(z)=1− α1z − α2z −···−αpz không có nghiệm trên vòng tròn đơn vị |z| =1
  81. Simpo PDF Merge and Split Unregistered Version - 82 Chương 2. Quá trình dừng Chứng minh. Giả sử đa thức Φ(z) không có nghiệm trên vòng tròn đơn vị |z| =1. Khi đó từ một kết quả của lý thuyết hàm biến phức tồn tại δ>0 sao cho ∞ 1 Λ(z)= = X c zi Φ(z) i i=−∞ ∞ trong miền 1 − δ<|z| < 1+δ với Pi=−∞ |ci| < ∞. Đặt ∞ Θ(z) H(z)= =Θ(z)Λ(z)= X h zi Φ(z) i i=−∞ và ∞ Xn =Θ(B)Λ(B)=H(B)Wn = X hiWn−i. i=−∞ Khi đó (Xn) là một dãy dừng trung bình trượt hai phía và Φ(B)Xn =Φ(B)H(B)Wn Θ(B) Φ(B) W =Θ(B)W . Φ(B) n n Sự tồn tại được chứng minh. Ta chứng minh sự duy nhất. Giả sử có đẳng thức (2.5). Khi đó tác động Λ(B) vào hai vế của (2.5) ta được Xn =Λ(B)Θ(B)Wn = H(B)Wn Ta thừa nhận phần đảo của định lý. Định lý 2.10. Dãy ARMA(p, q) có biểu diễn trung bình trượt một phía ∞ Xn = X hiWn−i (2.6) i=0 khi và chỉ khi đa thức 2 p Φ(z)=1− α1z − α2z −···−αpz không có nghiệm bên trong vòng tròn đơn vị |z|≤1.
  82. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 83 Chứng minh tương tự như trên dựa trên sự kiện có khai triển thành chuỗi luỹ thừa ∞ 1 Λ(z)= = X c zi Φ(z) i i=0 do đó ∞ Θ(z) H(z)= =Θ(z)Λ(z)=X h zi. Φ(z) i i=0 Các hệ số (hi) trong biểu diễn trung bình trượt một phía (2.6) được xác định từ quan hệ Θ(z) H(z)= → Φ(z)H(z)=Θ(z) Φ(z) p q (1 − α1z −···−αpz )(h0 + h1z + ···)=1+β1z + ···+ βqz Suy ra h0 =1 h1 = β1 + α1 h2 = β2 + α1h1 + α2 j hj = βj + X αkhj−k,j=0, 1, k=1 trong đó βj =0nếu j>qvà αk =0nếu k>p. Ví dụ 2.8. Xét dãy tự hồi quy cấp 2 (Xn) sau đây Xn =0, 7Xn−1 − 0, 1Xn−2 + Wn. 2 Đa thức Φ(z)=1− 0, 7z +0, 1z có hai nghiệm z1 =2,z2 =5nằm ngoài vòng tròn đơn vị do đó dãy(Xn) tồn tại duy nhất và có biểu diễn trung bình trượt một phía ∞ Xn = X hiWn−i. i=0
  83. Simpo PDF Merge and Split Unregistered Version - 84 Chương 2. Quá trình dừng Các hệ số hi được xác định truy hồi như sau h0 =1 h1 = β1 + α1 =0, 7 h2 = β2 + α1h1 + α2 =(0, 7)(0, 7) − (0, 1)=0, 39 hj =0, 7hj−1 − 0, 1hj−2 j =2, 3, Ví dụ 2.9. Xét dãy ARMA(1, 1) (Xn) như sau Xn = αXn−1 + Wn + βWn−1 (2.7) trong đó |α| < 1, |β| < 1. Ta có Φ(z)=1− αz, Φ(B)=1− αB ∞ 1 1 = = X αizi. Φz 1 − αz i=0 Vậy ∞ H(z)=(1+βz)(X αizi) i=0 ∞ ∞ = X αi + β X αizi+1 i=0 i=0 ∞ ∞ = X αi + β X αi−1zi i=0 i=1 ∞ =1+X(αi + βαi−1)zi i=1 ∞ =1+(α + β) X αi−1zi. i=1 Thành thử ∞ i−1 Xn = H(B)Wn = Wn +(α + β) X α Wn−i i=1
  84. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 85 Tiếp theo dựa vào biểu diễn trung bình trượt này ta hãy tìm hàm tự tương quan của (Xn). Nhân hai vế của (2.7) với Xn−h ta được XnXn−h − αXn−1Xn−h = WnXn−h + βWn−1Xn−h. Lấy kỳ vọng hai vế ta được K(h) − αK(h − 1) = EWnXn−h + βEWn−1Xn−h. 2 Với h =1chú ý rằng EWkXm =0nếu k>mvà EWkXk = σ ta được K(1) − αK(0) = βσ2. Cho h =0ta được K(0) − αK(1) = σ2 + β(α + β)σ2 = σ2(1 + αβ + β2). Với h ≥ 2 thì EWnXn−h =0,EWn−1Xn−h =0do đó K(h) − αK(h − 1)=0. Từ đó với h ≥ 2 K(h)=αh−1K(1). Từ hệ K(1) − αK(0) = βσ2 K(0) − αK(1) = σ2 + β(α + β)σ2 dễ dàng tìm được (α + β)2α K(1) = σ2 α + β +  1 − α2 (α + β)2 K(0) = σ2 1+  1 − α2 và K(h)=αh−1K(1) nếu h ≥ 2.
  85. Simpo PDF Merge and Split Unregistered Version - 86 Chương 2. Quá trình dừng 2.1.3 Độ đo phổ và mật độ phổ Trong tiết này chúng ta sẽ trình bày một đặc trưng quan trọng của dãy dừng: Đó là khái niệm độ đo phổ. Định lý 2.11. Giả sử K(h) là hàm tự tương quan của dãy dừng (Xn). Khi đó tồn tại và duy nhất một độ đo hữu hạn µ trên [−π,π] sao cho K(h) có biểu diễn tích phân sau π K(h)=Z eihxdµ(x). −π Độ đo µ được gọi là độ đo phổ của dãy dừng Xn. −ixj Chứng minh. Do K(n) là hàm xác định không âm nên với zj = e ta có n n n−1 X X K(j − k)e−ix(j−k) = X K(m)e−ixm(n −|m|) , ∀x. j=1 k=1 m=−(n−1) Đặt − 1 n 1 |m| f (x)= X K(m)e−ixm 1 −  . n 2π n m=−(n−1) Ta có fn(x) ≥ 0 , ∀x và π Z fn(x)dx = K(0) −π π −imx 6 − (vì R−π e dx =0nếu m =0). Gọi µn là độ đo trên [ π,π] với hàm mật độ fn(x).Họđộđo{µn} là compact yếu nên ta trích ra được một dãy con {µnk } hội tụ yếu tới độ đo hữu hạn µ. Ta chứng tỏ µ là độ đo cần tìm. Thật vậy với mỗi m cố định ta có π π Z imx Z imx e dµnk (x)= e fnk (x)dx = −π −π  |m| = K(m) 1 − , với nk ≥|m|. nk
  86. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 87 Cho nk →∞ta được π Z eimxdµ(x)=K(m) . −π Độ đo µ là duy nhất. Thật vậy giả sử µ và ν là hai độ đo thoả mãn π π K(n)=Z einxdµ(x)=Z einxdν(x) . −π −π Vì mọi hàm liên tục g(x) hoàn toàn có thể xấp xỉ đều bằng các đa thức n ikx lượng giác P cke , do đó ta suy ra k=1 π π Z g(x)dµ(x)=Z g(x)dν(x) , với mọi hàm liên tục g(x) . −π −π Vậy ta có µ = ν . Chú ý. Nếu Xn nhận giá trị thực thì K(h) nhận giá trị thực. Khi đó ta có π K(h)=Z cos hxdµ(x). −π Nếu độ đo µ tuyệt đối liên tục dµ = f(x)dx thì mật độ f(x) của µ được gọi là mật độ phổ của Xn. Trong trường hợp này ta nói Xn có phổ liên tục. Như vậy ta có: Định nghĩa 2.6. Hàm f(x) được gọi là mật độ phổ của dãy dừng (Xn) với hàm tự tương quan K(h) nếu f(x) ≥ 0 với mọi x ∈ [−π,π] và π K(h)=Z eihxf(x)dx. −π Định lý sau đây cho biết khi nào một hàm là hàm mật độ phổ của một dãy dừng. Định lý 2.12. Hàm f(x) không âm xác định trên đoạn [−π,π] là hàm mật độ phổ của một dãy dừng khi và chỉ khi
  87. Simpo PDF Merge and Split Unregistered Version - 88 Chương 2. Quá trình dừng 1. f(x) là hàm chẵn: f(x)=f(−x) ∀x ∈ [−π,π] π ∞ 2. R−π f(x)dx < . Chứng minh. Điều kiện cần chúng ta đã chứng minh. Bây giờ ta giả thiết hàm f(x) có các tính chất vừa nêu. Đặt π K(h)=Z eihxf(x)dx. −π Đổi biến u = −x ta được π K(−h)=Z e−ihxf(x)dx −π π = Z eihuf(−u)du −π π = Z eihuf(u)du −π = K(h). Vậy K(h) là hàm chẵn. Hơn nữa nếu a1, , an là các số phức tuỳ ý thì n π n Z ix(r−s) X ara¯sK(r − s)= X ar¯ase f(x)dx r,s=1 −π r,s=1 2 π n Z ixr = X are f(x)dx −π r=1 ≥ 0. Do đó K(h) xác định không âm . Vậy theo định lý tồn tại dãy dừng (Xn) nhận K(h) là hàm tự tương quan do đó nhận f(x) là hàm mật độ phổ. Định lý sau đây cho ta một điều kiện đủ để dãy (Xn) có phổ liên tục. Định lý 2.13. Nếu ∞ X |K(h)| < ∞ h=−∞
  88. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 89 thì (Xn) có phổ liên tục và mật độ phổ của nó được cho bởi công thức sau ∞ 1 f(x)= X e−ihxK(h). (2.8) 2π h=−∞ Chứng minh. Đầu tiên nhận xét rằng chuỗi (2.8) hội tụ tuyệt đối do đó hàm f(x) được xác định đúng đắn. Với mỗi số m nguyên dương ta đặt 1 −ikx 2 fm(x)= E Xke 2πm 1 m ! = E X X X e−irxeisx 2πm r s r,s=1 1 = X (m −|h|)e−ihxK(h). 2πm |h|<m Rõ ràng fm(x) không âm với mỗi m và ∞ 1 f (x) → X e−ihxK(h)=f(x) m 2π h=−∞ khi m →∞nên f(x) không âm. Tiếp theo ta có ∞ π π 1 Z eikxf(x)dx = Z X ei(k−h)xK(h)dx 2π −π −π h=−∞ ∞ 1 π = X K(h) Z ei(k−h)xdx 2π h=−∞ −π = K(k). Vậy f(x) là mật độ phổ của dãy Xn. Hệ quả 2.1. Một hàm chẵn K(h) khả tổng tuyệt đối ∞ X |K(h)| < ∞ h=−∞
  89. Simpo PDF Merge and Split Unregistered Version - 90 Chương 2. Quá trình dừng sẽ là hàm tự tương quan của một dãy dừng khi và chỉ khi ∞ 1 f(x)= X e−ihxK(h) ≥ 0. (2.9) 2π h=−∞ Trong trường hợp này f(x) chính là mật độ phổ của dãy dừng. Chứng minh. Điều kiện cần ta vừa chứng minh. Giả sử f(x) thoả mãn (2.9). Do K(h) chẵn nên dễ thấy f(x) chẵn. Mặt khác từ công thức (2.9) suy ra π K(h)=Z eihxf(x)dx. −π Từ chứng minh của định lý 2.12 ta suy ra K(h) xác định không âm. Vậy nó là hàm tự tương quan của một dãy dừng . Hệ quả trên cho ta một phương pháp rất hiệu lực để kiểm tra một hàm chẵn khả tổng tuyệt đối có phải là hàm tự tương quan hay không. Phưong pháp này tỏ ra đơn giản hơn so với việc kiểm tra tính xác định không âm của hàm đang xét. Xét ví dụ sau (so sánh nó với ví dụ 2.4). Ví dụ 2.10. Ta sẽ chứng minh rằng hàm sau đây 1 nếu h =0   K(h)=θ nếu h = ±1 0 nếu |h| > 1  là hàm xác định không âm nếu và chỉ nếu |θ|≤1/2. Thật vậy K(h) rõ ràng là hàm chẵn và khả tổng tuyệt đối. Vậy theo hệ quả trên nó sẽ là hàm tự tương quan khi và chỉ khi hàm ∞ 1 f(x)= X e−ihxK(h) 2π h=−∞ 1 = [1 + 2θ cos x] 2π
  90. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 91 là không âm với mọi x ∈ [−π,π]. Nhưng điều này xảy ra khi và chỉ khi |θ|≤1/2. Nếu độ đo phổ µ là độ đo rời rạc ta nói dãy dừng (Xn) có phổ rời rạc. Chẳng hạn giả sử U và V là hai ĐLNN không tương quan EU = EV = 2 2 2 0,EU = EV = σ và λ là một số thực. Xét dãy (Xn) xác định bởi Xn = U cos λn + V sin λn. 2 Khi đó (Xn) là dãy dừng với hàm tự tương quan K(h)=σ cos(λh). Không giảm tổng quát có thể giả sử λ ∈ [−π,π]. Gọi µ là độ đo rời rạc như sau σ2 µ{−λ} = µ{λ} = . 2 Khi đó dễ thấy π σ2 cos(λh)=Z eihxdµ(x). −π Vậy µ là độ đo phổ rời rạc của Xn. Tổng quát hơn giả sử U1,U2, , Um và V1,V2, , Vm là các ĐLNN với 2 2 2 EUk = EVk =0,EUk = EVk = σk , EUiUk =0, (i =6 k),EViVk =0(i =6 k),EUiVj =0. Xét dãy (Xn) xác định bởi m Xn = X(Uk cos λkn + Vk sin λkn) k=1 trong đó λ1, λm ∈ [−π,π] .Như ví dụ 2.3 đã chỉ ra (Xn) là dãy dừng với hàm tự tương quan m 2 K(h)=X σk cos λkh. k=1 Khi đó dễ thấy độ đo phổ µ là độ đo rời rạc tập trung tại các điểm ±λk với khối lượng σ2 µ{−λ } = µ{λ } = k . k k 2
  91. Simpo PDF Merge and Split Unregistered Version - 92 Chương 2. Quá trình dừng Ví dụ 2.11. (Mật độ phổ của dãy ồn trắng.) Nếu Wn là dãy ồn trắng với tham số σ2 thì từ công thức (2.8) và biểu thức hàm tự tương quan của nó ( xem ví dụ 2.1) ta suy ra mật độ phổ của nó là σ2 f(x)= . 2π Đó là một hàm hằng số. Ví dụ 2.12. (Mật độ phổ của dãy MA(1).) Giả sử (Xn) là dãy MA(1) xác định như sau Xn = Wn + rWn−1 trong đó r là hằng số thực. Từ công thức (2.8) và biểu thức hàm tự tương quan của nó ( xem ví dụ 2.5) ta suy ra mật độ phổ của nó là σ2 f(x)= (1 + r2 + r(e−ix + eix)) 2π σ2 = (1 + 2r cos x + r2). 2π Ví dụ 2.13. (Mật độ phổ của dãy AR(1).) Giả sử (Xn) là một dãy AR(1) thoả mãn phương trình sai phân sau đây Xn = pXn−1 + Wn trong đó p là một hằng số |p| < 1. Từ công thức (2.8) và biểu thức hàm tự tương quan của nó (xem ví dụ 2.5) ta suy ra mật độ phổ của nó là ∞ σ2 ! f(x)= 1+X ph(e−ihx + eihx) 1 − p2 h=1 σ2 peix pe−ix = 1+ +  1 − p2 1 − peix 1 − pe−ix σ2 = (1 − 2p cos x + p2)−1. 2π
  92. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 93 Định lý 2.14. Cho (Xn) là một dãy dừng với trung bình không và hàm mật độ phổ là fX(x). Cho dãy số thực (hk) thoả mãn X |hk| < ∞. k∈Z Khi đó chuỗi Yn = X hiYn−i i∈Z hội tụ hầu chắc chắn và hội tụ bptb và dãy (Yn) là một dãy dừng với trung bình không và có mật độ phổ là −ix 2 −ix ix fY (x)=|H(e )| fX (x)=H(e )H(e )fX (x) k trong đó H(z)=Pk∈Z hkz . Chứng minh. Theo định lý 2.6 dãy (Yn) là một dãy dừng với trung bình không và hàm tự tương quan KY (h)=X hkhjKX (h + k − j). k∈Z Vì Xn có mật độ phổ fX (x) nên ta có π Z i(h+k−j)x KX (h + k − j)= e fX(x)dx. −π Thay vào ta được π Z i(h+k−j)x KY (h)= X hjhk e fX (x)dx j,k∈Z −π π Z −ijx! ikx! ihx = X hje X hke e fX (x)dx −π j∈Z k∈Z 2 π Z ihx −ijx = e X hj e fX (x)dx. −π j∈Z
  93. Simpo PDF Merge and Split Unregistered Version - 94 Chương 2. Quá trình dừng Từ đẳng thức cuối suy ra Yn có mật độ phổ fY (x) là 2 −ikx fY (x)= X hke fX (x). k∈Z Hệ quả 2.2. Nếu (Xn) là một dãy ARMA(p,q) thoả mãn phương trình sai phân Φ(B)Xn =Θ(B)Wn thì nó có mật độ phổ cho bởi công thức σ2 |Θ(e−ix)|2 f(x)= . 2π |Φ(e−ix)|2 Thật vậy ta có ∞ Θ(z) H(z)= = X h zi Φ(z) i i=−∞ và ∞ Xn = H(B)Wn = X hiWn−i. i=−∞ Khi đó theo định lý 2.14 trên −ix 2 fX(x)=|H(e )| fW (x) σ2 |Θ(e−ix)|2 = . 2π |Φ(e−ix)|2 Ví dụ 2.14. (Mật độ phổ của quá trình ARMA(1,1).) Xét quá trình ARMA (1,1) Xn − αXn−1 = Wn + βWn−1 trong đó |α| < 1, |β| < 1 Khi đó mật độ phổ của Xn là σ2(1 + βeix)(1 + βe−ix) f(x)= 2π(1 − αeix)(1 − αe−ix) σ2(1 + 2β cos x + β2) = . 2π(1 − 2α cos x + α2)
  94. Simpo PDF Merge and Split Unregistered Version - 2.1. Quá trình dừng thời gian rời rạc 95 2.1.4 Biểu diễn phổ Trong mục này chúng ta sẽ chứng minh một định lý cơ bản của dãy dừng gọi là định lý biểu diễn phổ. Ta cần một công cụ mới: Tích phân đối với một độ đo ngẫu nhiên gia số trực giao. Cho đến nay ta mới chỉ xét các đại lượng ngẫu nhiên nhận giá trị thực. Bây giờ chúng ta xét cả các ĐLNN nhận giá trị phức. Việc này làm cho nhiều công thức trong lý thuyết quá trình dừng trở nên đơn giản hơn. Giả sử (Ω, F,P) là không gian xác suất cơ bản. Ký hiệu L2(Ω, F,P) là không gian 2 các ĐLNN X nhận giá trị phức sao cho E|X| = EXY. Sự hội tụ trong L2(Ω, F,P) được gọi là sự hội tụ bình phương trung bình (bptb). Giả sử (S, A) là không gian đo được nào đó. Hàm giá trị thực (hay phức) Z(A)=Z(ω,A) xác định với ω ∈ Ω ,A ∈Ađược gọi là độ đo ngẫu nhiên cộng tính hữu hạn nếu a) Với mỗi A ∈Ata có E|Z(A)|2 < ∞ . b) Với bất kỳ hai tập A1,A2 ∈Arời nhau A1 ∩ A2 = ∅ thì Z(A1 ∪ A2)=Z(A1)+Z(A2)(P − h.c.c) . Độ đo ngẫu nhiên cộng tính hữu hạn Z được gọi là đọ đo ngẫu nhiên nếu với bất kỳ dãy các tập A1,A2, ∈Ađôi một không giao nhau thì 2 ∞ n   E Z [ Ak − X Z(Ak) → 0(n →∞) , k=1 k=1 hay ∞ ∞ Z [ Ak = X Z(Ak) , k=1 k=1