Tài liệu Xích markov và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Lê Thị Linh XÍCH MARKOV VÀ ỨNG DỤNG KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Hà Nội - 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Lê Thị Linh XÍCH MARKOV VÀ ỨNG DỤNG Chuyên ngành: Toán Ứng Dụng KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Trần Vĩnh Đức Hà Nội - 2017 LỜI CẢM ƠN Trước khi trình bày nội dung chính của khóa luận, tôi xin bày tỏ lòng cảm ơn tới các thầy cô khoa Toán, trường Đại Học Sư Phạm Hà Nội 2, các thầy cô trong tổ bộ môn Toán ứng dụng cũng như các thầy cô tham gia giảng dạy đã tận tình truyền đạt những tri thức quý báu và tạo điều kiện thuận lợi để tôi hoàn thành tốt nhiệm vụ khóa học và khóa luận. Đặc biệt, tôi xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc tới Tiến sĩ Trần Vĩnh Đức, người đã trực tiếp hướng dẫn, chỉ bảo tận tình giúp đỡ để tôi có thể hoàn thành tốt khóa luận này. Hà Nội, tháng 5 năm 2017 Sinh viên Lê Thị Linh 1 LỜI CAM ĐOAN Khóa luận này là kết quả nghiên cứu của bản thân tôi dưới sự hướng dẫn tận tình của thầy giáo Trần Vĩnh Đức. Trong khi nghiên cứu hoàn thành đề tài nghiên cứu này tôi đã tham khảo một số tài liệu đã ghi trong phần tài liệu tham khảo. Tôi xin khẳng định kết quả của đề tài "Xích Markov và ứng dụng" là kết quả của việc nghiên cứu, học tập và nỗ lực của bản thân, không có sự trùng lặp với kết quả của đề tài khác. Nếu sai tôi xin chịu hoàn toàn trách nhiệm. Hà Nội, tháng 5 năm 2017 Sinh viên Lê Thị Linh 2 Mục lục LỜI CẢM ƠN 1 LỜI CAM ĐOAN 2 GIỚI THIỆU 5 1 KIẾN THỨC CƠ SỞ 7 1.1 1.2 1.3 Sơ lược về lý thuyết xác suất . . . . . . . . . . . . . . . 7 1.1.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . 7 1.1.2. Biến ngẫu nhiên . . . . . . . . . . . . . . . . . . 9 1.1.3. Công thức xác suất đầy đủ và công thức Bayes . 10 Sơ lược về ma trận . . . . . . . . . . . . . . . . . . . . 11 1.2.1. Định nghĩa ma trận . . . . . . . . . . . . . . . . 11 1.2.2. Phép toán đại số trên ma trận . . . . . . . . . . 12 1.2.3. Ma trận nghịch đảo . . . . . . . . . . . . . . . . 13 Hệ phương trình tuyến tính . . . . . . . . . . . . . . . . 13 2 XÍCH MARKOV 15 2.1 Xích Markov hữu hạn . . . . . . . . . . . . . . . . . . . 15 2.2 Biểu diễn ánh xạ ngẫu nhiên . . . . . . . . . . . . . . . 20 2.3 Tính tối giản và phi tuần hoàn . . . . . . . . . . . . . . 23 3 4 2.4 Hành trình ngẫu nhiên trên đồ thị . . . . . . . . . . . . 25 2.5 Phân phối dừng . . . . . . . . . . . . . . . . . . . . . . 26 2.6 Tính khả nghịch và thời điểm nghịch đảo . . . . . . . . 31 2.7 Phân loại trạng thái của xích Markov . . . . . . . . . . 33 3 ỨNG DỤNG 37 3.1 Người chơi bạc phá sản . . . . . . . . . . . . . . . . . . 37 3.2 Sưu tập phiếu giảm giá . . . . . . . . . . . . . . . . . . 39 3.3 Siêu lập phương và mô hình bình Ehrenfest . . . . . . . 40 3.4 Mô hình bình Polya . . . . . . . . . . . . . . . . . . . . 43 3.5 Chuỗi sinh tử . . . . . . . . . . . . . . . . . . . . . . . 44 3.6 Mô hình phục vụ đám đông . . . . . . . . . . . . . . . . 46 3.7 Xích Markov trong di truyền . . . . . . . . . . . . . . . 48 3.8 Mô hình kiểm kê . . . . . . . . . . . . . . . . . . . . . . 49 3.9 Hành trình ngẫu nhiên trên Z và định luật đối xứng . . 51 KẾT LUẬN 56 TÀI LIỆU THAM KHẢO 57 GIỚI THIỆU 1. Lý do chọn đề tài Nhiều quá trình trong thực tế luôn có sự chuyển đổi qua lại giữa các trạng thái khác nhau, điển hình là quá trình Markov. Quá trình Markov giúp ta biết, từ bộ số liệu thực tế độc lập với quá khứ, ta sẽ đưa ra được những dự doán trong tương lai nhờ vào ma trận xác suất chuyển. Rồi từ đó rút ra những nhận xét, đánh giá, kết luận, nhằm điều chỉnh và quyết định trong công tác chỉ đạo được vận dụng phổ biến ở nhiều lĩnh vực như: kinh tế, kỹ thuật, dân số học, di truyền học,... Thấy được tầm quan trọng của quá trình này và được sự giúp đỡ tận tình của thầy giáo Trần Vĩnh Đức nên tôi đã mạnh dạn lựa chọn đề tài "Xích Markov và ứng dụng" làm đề tài nghiên cứu. 2. Mục đích nghiên cứu - Nhằm tìm hiểu một số kết quả về lý thuyết xích Markov và một số mô hình ứng dụng của nó. - Rèn luyện tư duy nghiên cứu khoa học và nâng cao trình độ nhận thức của bản thân. 5 6 3. Đối tượng và phạm vi nghiên cứu - Đối tượng nghiên cứu: Xích Markov và ứng dụng. - Phạm vi nghiên cứu: Các tính chất và một số ứng dụng cơ bản của xích Markov. 4. Phương pháp nghiên cứu - Tổng hợp tài liệu, sắp xếp các vấn đề nghiên cứu một cách lôgic và có hệ thống. 5. Nội dung nghiên cứu Khóa luận gồm ba chương: Chương 1: Kiến thức cơ sở . Trình bày các kiến thức liên quan đến xác suất, ma trận và hệ phương trình tuyến tính. Chương 2: Xích Markov . Trình bày định nghĩa xích Markov, tính Markov và điều kiện cần để tồn tại duy nhất một phân phối dừng. Chương 3: Ứng dụng . Trình bày một số ứng dụng của xích Markov. Chương 1 KIẾN THỨC CƠ SỞ Mục đích của chương này là trình bày các kiến thức cơ bản về lý thuyết xác suất, ma trận và hệ phương trình tuyến tính. Các kiến thức này sẽ được sử dụng ở chương sau khi nghiên cứu về xích Markov và ứng dụng của xích Markov. 1.1 1.1.1. Sơ lược về lý thuyết xác suất Định nghĩa Phép thử ngẫu nhiên, kí hiệu là E . Các kết quả của E là ngẫu nhiên, không thể xác định trước. Tuy nhiên ta có thể liệt kê ra tất cả các kết quả có thể của E . Tập hợp tất cả các kết quả có thể của E được gọi là không gian mẫu của E và kí hiệu là Ω. Chữ w dùng để kí hiệu một phần tử của Ω và ta gọi mỗi phần tử w của Ω là một biến cố sơ cấp. Định nghĩa xác suất cổ điển Định nghĩa 1.1.1. Giả sử phép thử E có một số hữu hạn các kết quả có thể. Khi đó xác suất của biến cố A là tỉ số giữa số kết quả thuận lợi 7 Chương 1. KIẾN THỨC CƠ SỞ của A và số kết quả có thể. Kí hiệu: P (A) = 8 |A| , trong đó |A| là số |Ω| phần tử của tập A. Định nghĩa xác suất bằng tần suất Định nghĩa 1.1.2. Giả sử phép thử E có thể được thực hiện lặp đi lặp lại nhiều lần trong những điều kiện giống nhau. Nếu trong n lần thực k(A) hiện phép thử E , biến cố A xuất hiện k(A) lần thì tỉ số fn (A) = n được gọi là tần suất xuất hiện của biến cố A trong n phép thử. Phương pháp tiên đề trong lý thuyết xác suất Giả sử E là một phép thử ngẫu nhiên và Ω là tập hợp các kết quả của E . Mỗi tập con của Ω được gọi là một biến cố. Một họ F nào đó các tập con của Ω được gọi là một σ - đại số các biến cố nếu: (i) Ω ∈ F , Ø ∈ F . (ii) Nếu A ∈ F thì Ω\A ∈ F . (iii) Nếu A1 , A2 , ... là một dãy các tập hợp của họ F thì hợp ∪∞ n=1 An cũng thuộc F . Xác định một quy luật xác suất trên σ - đại số F là gán cho mỗi biến cố A ∈ F một số P (A) gọi là xác suất của A. Phép gán đó phải thỏa mãn các điều kiện sau: 1) ∀A ∈ F , 0 ≤ P (A) ≤ 1. 2) P (Ω) = 1, P (Ø) = 0. 3) Nếu A1 , A2 , ... là dãy các biến cố thuộc F đôi một xung khắc với P∞ nhau (Ai Aj = Ø nếu i 6= j ) thì P (∪∞ n=1 An ) = n=1 P (An ). Chương 1. KIẾN THỨC CƠ SỞ 9 Khi đó, (Ω, F, P ) được gọi là không gian xác suất. 1.1.2. Biến ngẫu nhiên Biến ngẫu nhiên Một đại lượng (hay một biến) nhận các giá trị của nó với xác suất tương ứng nào đó gọi là đại lượng ngẫu nhiên (ĐLNN) hay biến ngẫu nhiên (BNN). Nếu tập các giá trị mà biến ngẫu nhiên nhận là một tập gồm một số hữu hạn hoặc vô hạn nhưng đếm được, khi đó biến ngẫu nhiên gọi là biến ngẫu nhiên rời rạc. Nếu tập các giá trị mà biến ngẫu nhiên gồm các số lấp kín một khoảng trên trục số, số phần tử của tập giá trị là vô hạn không đếm được, khi đó biến ngẫu nhiên gọi là biến ngẫu nhiên liên tục. Hàm phân phối Phân phối xác suất của một ĐLNN rời rạc X là một bảng mà trên đó ta ghi các giá trị mà X có thể kèm theo các xác suất để nó nhận các giá trị đó và bảng phân phối xác suất có dạng X x1 x2 ... xn ở đó pi = P {X = xi }. ( P Pn p1 p2 ... pn i=1 pi = 1). Hàm phân phối xác suất của ĐLNN X là một hàm F (x) xác định với mọi x theo công thức sau F (x) = P {X < x}. Chương 1. KIẾN THỨC CƠ SỞ 10 Kì vọng Định nghĩa 1.1.3. Cho X là đại lượng ngẫu nhiên rời rạc có bảng xác suất như sau X x1 x2 ... P p1 p2 ... kì vọng (giá trị trung bình) của X được kí hiệu là EX cho bởi công thức sau: EX = 1.1.3. X x i pi , (1 ≤ i ≤ +∞). Công thức xác suất đầy đủ và công thức Bayes Các biến cố B1 , B2 , ..., Bn được gọi là một hệ đầy đủ các biến cố nếu chúng đôi một xung khắc với nhau (Bi Bj = Ø nếu i 6= j ) và hợp của chúng là biến cố chắc chắn Ω = B1 ∪ B2 ∪ ... ∪ Bn . Định lí 1.1.1. Nếu B1 , B2 , ..., Bn là một hệ đầy đủ thì với mỗi biến cố A ta có P (A) = n X P (Bi ) · P (A/Bi ). (1.1) i=1 Công thức (1.1) được gọi là công thức xác suất đầy đủ. Một công thức khác có liên quan mật thiết với công thức xác suất đầy đủ là công thức Bayes. Định lí 1.1.2. Nếu B1 , B2 , ..., Bn là một hệ đầy đủ các biến cố và A là một biến cố với P (A) > 0 thì với mỗi k = 1, 2, ..., n P (Bk ) · P (A/Bk ) . P (Bk /A) = Pn i=1 P (Bi ) · P (A/Bi ) Công thức (1.2) được gọi là công thức Bayes. (1.2) Chương 1. KIẾN THỨC CƠ SỞ 11 * Ta chứng minh công thức (1.1). A = AΩ = A(B1 ∪ B2 ∪ ... ∪ Bn ) = AB1 ∪ ... ∪ ABn . Các biến cố ABi , i = 1, 2, ..., n xung khắc nên: P (A) = n X P (ABi ). i=1 Theo quy tắc nhân P (ABi ) = P (Bi ) · P (A/Bi ). Thay vào ta được P (A) = n X P (Bi ) · P (A/Bi ). i=1 * Công thức (1.2) suy ra từ đẳng thức sau: P (Bk ) · P (A/Bk ) = P (A) · P (Bk /A) = P (Bk A). Suy ra được: P (Bk /A) = Mặt khác P (A) = P (Bk ) · P (A/Bk ) . P (A) n X P (Bi ) · P (A/Bi ). i=1 1.2 1.2.1. Sơ lược về ma trận Định nghĩa ma trận Giả sử K là một trường tùy ý. Định nghĩa 1.2.1. Mỗi bảng có  a  11   a21 A=   ...  am1 dạng a12 ... a1n a22 ... am2    ... a2n  ,  ... ...   ... amn Chương 1. KIẾN THỨC CƠ SỞ 12 trong đó aij ∈ K (1 ≤ i ≤ m, 1 ≤ j ≤ n), được gọi là một ma trận m hàng, n cột với các phần tử trong K. Nếu m = n, thì ta nói A là một ma trận vuông cấp n. Vectơ hàng ai1 ai2 ... ain , được gọi là hàng thứ i của ma trận A. Vectơ cột a1j a2j ... atmj , được gọi là cột thứ j của ma trận A. Ma trận nói trên thường được kí hiệu là A = (aij)m×n . Tập hợp tất cả các ma trận m hàng, n cột với các phần tử trong K được kí hiệu là M (m × n, K) hay M at(m × n, K). 1.2.2. Phép toán đại số trên ma trận Phép cộng ma trận Có thể cộng hai hay nhiều ma trận có cùng kích thước là m × n. Cho hai ma trận A = (aij )m×n và B = (bij )m×n . Tổng của A và B là ma trận C = (aij + bij )m×n . Với A, B, C ∈ M (m × n, K). Phép nhân ma trận với một số Cho c 6= 0 và ma trận A = (aij )m×n ∈ M (m × n, K). Khi đó cA = (caij )m×n ∈ M (m × n, K). Phép nhân ma trận Cho hai ma trận A = (aij )m×n ∈ M (m × n, K) và B = (bjk )n×p ∈ M (n × p, K). Tích AB của ma trận A và B là ma trận Chương 1. KIẾN THỨC CƠ SỞ 13 C = (cik ) ∈ M (m × p, K), với các phần tử được xác định như sau: cik = n X aij bjk (1 ≤ i ≤ m, 1 ≤ k ≤ p). j=1 1.2.3. Ma trận nghịch đảo Định nghĩa 1.2.2. Ma trận A ∈ M (n × n, K) được gọi là một ma trận khả nghịch (hoặc ma trận không suy biến) nếu có ma trận B ∈ M (n × n, K) sao cho AB = BA = En (En là ma trận đơn vị). Khi đó, ta nói B là nghịch đảo của A và kí hiệu là B = A−1 . Định lí 1.2.1. Cho A ∈ M (n × n, K). Khi đó A khả nghịch khi và chỉ khi detA 6= 0. 1.3 Hệ phương trình tuyến tính Xét hệ phương trình gồm m phương trình với n ẩn x1 , ..., xn có dạng:    a11 x1 + a12 x2 + ... + a1n xn = b1 ;      a x + a x + ... + a x = b ; 21 1 22 2 2n n 2 (1.3)   .............................................      a x + a x + ... + a x = b . m1 1 m2 2 mn n m Trong đó aij , bi là các phần tử cho trước trong trường K. Kí hiệu:     x b  1   1       x2   b2  ,β =  . A = (aij )m×n , x =       ...   ...      xn bm Chương 1. KIẾN THỨC CƠ SỞ 14 Khi đó, hệ phương trình (1.3) nói trên có thể viết dưới dạng phương trình vectơ Ax = β . Một nghiệm của hệ này là một vectơ x0 = Kn sao cho Ax0 = β . Một hệ phương trình có ít nhất một nghiệm được gọi là một hệ phương trình tương thích. Hệ phương trình Ax = 0 được gọi là hệ phương trình tuyến tính thuần nhất liên kết với hệ Ax = β . Hai hệ phương trình được gọi là tương đương nhau nếu chúng có cùng tập nghiệm. Nhận xét 1.3.1. Khi giải một hệ phương trình tuyến tính, các phép biến đổi sau đây là tương đương: • Hoán đổi hai phương trình cho nhau. • Nhân hai vế của một phương trình cho một số khác 0. • Cộng vào một phương trình một bội của phương trình khác. Nhận xét 1.3.2. Hệ phương trình thuần nhất của hệ phương trình (1.3) luôn có một nghiệm u = (0, 0, ..., 0). Nghiệm này được gọi là nghiệm tầm thường. Chương 2 XÍCH MARKOV Chương này trình bày định nghĩa xích Markov, biểu diễn ánh xạ ngẫu nhiên, hành trình ngẫu nhiên trên đồ thị và trình bày được những xích tối giản, phi tuần hoàn luôn hội tụ tới phân phối dừng của chúng. 2.1 Xích Markov hữu hạn Một xích Markov hữu hạn là một quá trình chuyển động giữa các phần tử của một tập hữu hạn Ω theo cách sau: tại x ∈ Ω, vị trí tiếp theo được chọn tương ứng với một phân phối xác suất P (x, ·). Chi tiết hơn, một dãy các biến ngẫu nhiên(X0 , X1 , ...) là một xích Markov với không gian trạng thái Ω và ma trận xác suất chuyển P nếu ∀x, y ∈ Ω, với t ≥ 1 và Ht−1 = ∩t−1 s=0 {Xs = xs } thỏa mãn P(Ht−1 ∩{Xt = x}) > 0, ta có: P{Xt+1 = y | Ht−1 ∩ {Xt = x}} = P{Xt+1 = y | Xt = x} = P (x, y). (2.1) Phương trình (2.1) được gọi là tính chất Markov, nghĩa là xác suất có điều kiện của việc thay đổi từ trạng thái x tới trạng thái y , không phụ thuộc x0 , x1 , ...xt−1 là các trạng thái đứng trước x. 15 Chương 2. XÍCH MARKOV 16 Dòng thứ x của ma trận P được kí hiệu là P (x, ·). Ma trận P như vậy được gọi là ma trận xác suất, các phần tử của dòng này không âm và X P (x, y) = 1, ∀x ∈ Ω. y∈Ω Ví dụ 2.1.1. Một con ếch sống trong một cái ao trên hai chiếc lá sen, phía đông và tây, trên mỗi lá sen có một đồng xu. Mỗi buổi sáng con ếch quyết định nhảy sang chiếc lá sen kia bằng việc tung đồng xu trên lá sen mà nó đang đứng. Sau khi tung đồng xu, nếu đồng xu xuất hiện mặt ngửa thì nó sẽ nhảy sang lá sen kia. Nếu đồng xu xuất hiện mặt sấp thì nó ở lại lá sen cũ. Hình 2.1: Bước nhảy ngẫu nhiên của con ếch, khi đồng tiền suất hiện mặt ngửa thì nhảy sang chiếc lá khác. Giả sử Ω = {e, ω} và (X0 , X1 , ...) là dãy các lá sen mà con ếch đã ở vào ngày chủ nhật, thứ hai,... Gọi đồng xu ở chiếc lá phía đông và xuất hiện mặt ngửa có xác suất là p, khi đó đồng xu xuất hiện mặt ngửa ở chiếc lá phía tây có xác suất là q . Quy tắc nhảy của con ếch đơn giản Chương 2. XÍCH MARKOV như sau, nếu đặt:  P = 17  P (e, e) P (e, w)  = P (w, e) P (w, w) 1−p p q 1−q  , (2.2) thì (X0 , X1 , ...) là một xích Markov với ma trận chuyển P . Để ý rằng hàng đầu tiên của ma trận P là phân phối có điều kiện của Xt+1 cho bởi Xt = e, khi đó hàng thứ hai là phân phối có điều kiện của Xt+1 cho bởi Xt = w. Giả thiết rằng con ếch đã ở lá phía đông vào ngày chủ nhật. Khi nó tỉnh dậy vào ngày thứ hai, thì xác suất p chuyển sang lá phía tây và lá phía đông có xác suất là 1 − p. Do đó, P{X1 = e|X0 = e} = 1 − p, P{X1 = w|X0 = e} = p. (2.3) Ngày thứ ba như thế nào? Xem xét hai khả năng như X1 , ta thấy rằng: P{X2 = e|X0 = e} = (1 − p)(1 − p) + pq (2.4) P{X2 = w|X0 = e} = (1 − p)p + p(1 − q). (2.5) và Ta có thể viết công thức như (2.4) và (2.5) một cách hệ thống hơn. µt := (P{Xt = e|X0 = e}, P{Xt = w|X0 = e}). Giả thiết con ếch bắt đầu từ lá phía đông, giờ ta có thể viết µ0 = (1, 0), khi đó (2.3) trở thành µ1 = µ0 P . Nhân P vào vế phải của phân phối ta được: µt = µt−1 P, ∀t ≥ 1. (2.6) Thay thế với phân phối đầu tiên bất kỳ µ0 nào đó ta có: µt = µ0 P t , (t ≥ 0). (2.7) Chương 2. XÍCH MARKOV 18 Hình 2.2: Xác suất theo từng thời điểm (bắt đầu từ chiếc lá phía đông) với (a) p = q = 1/2, (b) p = 0.2 và q = 0.1, (c) p = 0.95 và q = 0.7. Các xác suất giới hạn tương ứng là 1/2, 1/3 và 14/33. Làm thế nào để hình dung về phân phối µt trong khoảng thời gian dài? Hình 2.2 cho thấy µt có thể có một giới hạn π (giá trị phụ thuộc vào p và q ) khi t → ∞. Bất kỳ phân phối hữu hạn π nào đều thỏa mãn π = πP , điều đó dẫn đến π(e) = q , p+q π(w) = p . p+q Nếu ta xác định 4t = µt (e) − q , p+q ∀t ≥ 0, thì với định nghĩa của µt+1 , dãy (4t ) thỏa mãn 4t+1 = µt (e)(1 − p) + (1 − µt (e))(q) − q = (1 − p − q)4t . (2.8) p+q Ta kết luận rằng khi 0 < p < 1 và 0 < q < 1, lim µt (e) = t→∞ q , p+q lim µt (w) = t→∞ p , p+q (2.9) đối với mọi phân phối ban đầu bất kì. Như vậy, µt tiến tới π khi t → ∞.