Quá trình ngẫu nhiên và tính toán ngẫu nhiên phần 1

Chia sẻ: Thái Duy Ái Ngọc | Ngày: | Loại File: PDF | Số trang:21

Thêm vào BST

Báo xấu

360
lượt xem 95
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: Quá trình ngẫu nhiên và tính toán ngẫu nhiên phần 1

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ả.
Chương 1 Quá trình Markov 1.1 Xích Markov . . . . . . . . . . . . . . . . . . . . . 5 1.2 Phân lo i tr ng thái xích Markov . . . . . . . . . 20 1.3 Quá trình Markov . . . . . . . . . . . . . . . . . . 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ài t 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.
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 Pij = 1 j ∈E 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 Pi0 i1 ...Pin−1in .
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−1 ik . Thành th P (X0 = i0 , X1 = i1 , ..., Xn = in ) = ui0 Pi0 i1 ...Pin−1in Đ nh lý 1.2. (Phương trình C - K (Chapman-Kolmogorov)) Pij (n + m) = 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) = P (Xn = k |X0 = i)P (Xn+m = j |Xn = k, X0 = i) k ∈E = 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 ) .
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) = U P n . 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 ) = P (Xm = i)P (Xn+m = j |Xm = i) i=1 d = 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 = ξ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 .
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 y P (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 y P (Xn+1 = i + 1|Xn = i) = 1 − i/d. Thành th i   n u j = i−1 d  Pij = d − i n u j = i + 1 (1.1) d    0 n u j = i + 1, j = 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
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 = 3 và 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−a a P= b 1−b
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). Ta có 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 − q n ) b un = q n + = (1 − a − b)n + (1 − (1 − a − b)n ) 1−q a+b hay b a + (1 − a − b)n P00 (n) = . a+b a+b Suy ra a a − (1 − a − b)n P01 (n) = 1 − P00 (n) = . 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 − q n) b (1 − (1 − a − b)n ). vn = = (1 − q ) a+b
12 Chương 1. Quá trình Markov Suy ra b b − (1 − a − b)n P10 (n) = a+b a+b a b + (1 − a − b)n P11(n) = 1 − P10 (n) = . a+b a+b Vi t dư i d ng ma tr n ta có (1 − a − b)n ba a −a 1 P ( n) = + . a+b a+b ba −b b Đ 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à ui = 1 i∈E 2. uj = ui Pij ∀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/3 1/3 1/3   P = 1/4 1/2 1/4 1/6 1/3 1/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.
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−a a 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 = . Th a 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 đó
14 Chương 1. Quá trình Markov 1. πj ≤ 1 và πj = πi Pij . j ∈E i∈E 2. Ho c πj = 0 v i m i j ∈ E , ho c πj = 1. j ∈E 3. N u πj = 1 thì U = (π1 , π2, ...) là phân b d ng và phân b d ng là j ∈E duy nh t. N u πj = 0 v 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ó πj = lim Pij (n) ≤ lim inf 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ó πi Pij = lim Pki (n)Pij n i∈E i∈E ≤ lim inf Pki (n)Pij = lim inf Pkj (n + 1) = πj . n→∞ n→∞ i∈E Đ t sj = πj − πi Pij ≥ 0 ∀j ∈ E . Ta có i∈E sj = πj − πi Pij j ∈E j ∈E j ∈E i∈E = πj − πi Pij = πj − πi Pij j ∈E i∈E j ∈E j ∈E i∈E j ∈E = πj − πi = 0. j ∈E i∈E V y sj = 0 ∀j ∈ E hay πj = πi Pij ∀j ∈ E. i∈E 2. Ta có πj = πi Pij = ( πk Pki )Pij i∈E i∈E k ∈E = πk ( Pki Pij ) = πk Pkj (2). k ∈E i∈E k ∈E
1.1. Xích Markov 15 B ng quy n p d th y v i m i n πj = πk Pkj (n). k ∈E Vì chu i h i t đ u đ i v i n nên πj = lim πk Pkj (n) = πk lim Pkj (n) = πj πk n→∞ n→∞ k ∈E k ∈E k ∈E Suy ra πj 1− πk = 0 ∀j ∈ E. k ∈E Vyn u πk < 1 thì πj = 0 ∀j ∈ E. k ∈E 3. N u πk = 1 thì 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 = uk Pkj (n). k ∈E Vì chu i h i t đ u đ i v i n nên uj = uk lim Pkj (n) = uk πj = πj . n→∞ k ∈E k ∈E Do đó n u πj < 1 thì phân b d ng không t n t i. N u πj = 1 thì 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à π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 .
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 . Ta có P (Xn = j ) = P (X0 = i)Pij (n). ß∈E Do đó lim P {Xn = j } = P {X0 = i} lim Pij (n) n→∞ n→∞ ß∈E = 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.
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) = Pik Pkj (n) ≥ Pik mj (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. Ta có Pik (n0 ) ≥ r.1 ≥ Pjk (n) nên Pik (n0 ) ≥ rPjk (n) ∀i, thành th Pij (n0 + n) = Pik (n0)Pkj (n) k = (Pik (n0) − rPjk (n)) Pkj (n) + r Pjk (n)Pkj (n) k k ≥ mj ( n) (Pik (n0) − rPjk (n)) + rPjj (2n) k = mj (n)(1 − r) + rPjj (2n).
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 Mj (kn0 + 1) − mj (kn0 + 1) ≤ (1 − r)k (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 . Ta có 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)) ≤ (1 − r)k+1 (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
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à Pij = 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ó pik Pkj = 1/d 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à s ch m xu t hi n l n gieo th n, Sn = n=1 ξk . Sn là m t xích Markov k
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à   0 1/6 1/6 1/6 1/6 1/6 1/6   1/6 1/6 0 1/6 1/6 1/6 1/6   1/6 1/6 1/6 0 1/6 1/6 1/6     P = 1/6 1/6 . 1/6 1/6 0 1/6 1/6   1/6 1/6 1/6 1/6 1/6 0 1/6   1/6 1/6 1/6 1/6 1/6 1/6 0   1/6 1/6 1/6 1/6 1/6 1/6 0 Xích Markov này chính quy vì ma tr n xác su t chuy n sau 2 bư c   1/6 5/36 5/36 5/36 5/36 5/36 5/36   5/36 5/36  1/6 5/36 5/36 5/36 5/36   5/36 5/36  5/36 1/6 5/36 5/36 5/36     P (2) = P 2 = 5/36 5/36  5/36 5/36 1/6 5/36 5/36   5/36 5/36  5/36 5/36 5/36 1/6 5/36   5/36 5/36  5/36 5/36 5/36 5/36 1/6   5/36 5/36 5/36 5/36 5/36 5/6 1/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:
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. ( Ta quy ư c Pii (0) = 1, Pij (0) = 0 n u i = 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) = 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à P1 0 P= 0 P2
22 Chương 1. Quá trình Markov trong đó 1/3 2/3 P1 = 1/4 3/4 và   010   P2 = 1/2 0 1/2 . 010 Khi đó n P1 0 n P ( n) = P = . 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à   0 0 1/2 1/2 0 0 1/2 1/2   P2 =   1/2 1/2 0 0 1/2 1/2 0 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. Ta có 1 → 3, 3 → 2 suy ra 1 → 2. L i có 2 → 3, 3 → 1 suy ra 2 → 1. V y 1 ↔ 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) = h∈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
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 y d(i)|k + l + n → d(i)|n. V y d(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 = 1 ta 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 = i, ..., X1 = i|X0 = i) và ký hi u ∞ ∗ fii = 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 = 1 ta 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 ∞ Pii (n) = ∞. (1.6) n=1 Ch ng minh. Ch ng minh s d ng hai b đ sau