Tài liệu Phương pháp xích markov monte carlo 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 —————————————- HOÀNG THỊ ANH SANG PHƯƠNG PHÁP XÍCH MARKOV MONTE CARLO VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN 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 —————————————- HOÀNG THỊ ANH SANG PHƯƠNG PHÁP XÍCH MARKOV MONTE CARLO VÀ ỨNG DỤNG Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. NGÔ HOÀNG LONG HÀ NỘI, 2017 Lời cảm ơn Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy Ngô Hoàng Long, giảng viên khoa Toán-Tin, trường Đại học Sư phạm Hà Nội đã hướng dẫn tôi tận tình, cho tôi những kiến thức và kinh nghiệm quý báu, tạo điều kiện thuận lợi cho tôi trong quá trình thực hiện và hoàn thành Luận văn này. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Toán, trường Đại học sư phạm Hà Nội 2 đã dạy bảo tôi tận tình trong suốt quá trình học tập tại khoa. Nhân dịp này tôi cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên tôi, cổ vũ, động viên, giúp đỡ tôi trong suốt quá trình học tập và thực hiện Luận văn tốt nghiệp. Hà Nội, ngày 12 tháng 06 năm 2017 Học viên cao học Hoàng Thị Anh Sang i Lời cam đoan Tôi xin cam đoan Luận văn thạc sĩ "Phương pháp xích Markov Monte Carlo và ứng dụng" là nghiên cứu của riêng tôi và được sự hướng dẫn khoa học của TS. Ngô Hoàng Long. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được công bố dưới bất kì hình thức nào trước đây. Nếu phát hiện có bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách nhiệm về nội dung Luận văn của mình. Hà Nội, ngày 12 tháng 06 năm 2017 Học viên cao học Hoàng Thị Anh Sang ii Mục lục Lời cảm ơn i Lời cam đoan ii Danh mục các kí hiệu, chữ viết tắt v Danh sách bảng vi Danh sách hình vẽ vii MỞ ĐẦU viii NỘI DUNG 1 1 Xích Markov 1 1.1 Một số khái niệm cơ bản của lý thuyết xác suất . . . . . . . . . . . . . 1 1.2 Xích Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Mô phỏng Xích Markov . . . . . . . . . . . . . . . . . . . . . . 7 1.2.3 Xích Markov tối giản và phi tuần hoàn . . . . . . . . . . . . . . 12 1.2.4 Phân phối dừng . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.5 Xích Markov khả nghịch . . . . . . . . . . . . . . . . . . . . . . 15 2 Phương pháp Monte-Carlo 2.1 16 Số ngẫu nhiên và phương pháp sinh số ngẫu nhiên . . . . . . . . . . . . 16 2.1.1 16 Bài toán tổng quát . . . . . . . . . . . . . . . . . . . . . . . . . iii 2.1.2 17 2.1.3 Sinh ra các đại lượng ngẫu nhiên với phân phối không đều . . . 19 2.1.4 Các phân phối đặc biệt . . . . . . . . . . . . . . . . . . . . . . . 22 Phương pháp Monte-Carlo . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.1 Phương pháp lấy mẫu phân tầng . . . . . . . . . . . . . . . . . 24 2.2.2 Chọn mẫu quan trọng . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.3 2.2 Sinh số giả ngẫu nhiên . . . . . . . . . . . . . . . . . . . . . . . Các số ngẫu nhiên chung . . . . . . . . . . . . . . . . . . . . . . 28 3 Xích Markov Monte Carlo 32 3.1 Phương pháp Xích Markov Monte Carlo . . . . . . . . . . . . . . . . . 32 3.2 Một số phương pháp cải tiến . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.1 Các phương pháp tăng tốc cho thuật toán . . . . . . . . . . . . 40 3.2.2 Xấp xỉ ngẫu nhiên . . . . . . . . . . . . . . . . . . . . . . . . . 48 Mô phỏng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3 KẾT LUẬN 59 Tài liệu tham khảo 60 PHỤ LỤC: Code mô phỏng bằng Python 61 iv Danh mục các kí hiệu, chữ viết tắt E[X] Kì vọng của biến X Var[X] Phương sai của biến X ψ(x) Hàm khởi tạo φ(x) Hàm cập nhật dTV Biến phân toàn phần ƯCLN Ước chung lớn nhất MCMC Phương pháp xích Markov Monte Carlo Kết thúc chứng minh v Danh sách bảng 3.1 Kết quả với đồ thị 4 đỉnh. . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2 Kết quả với đồ thị 5 đỉnh. . . . . . . . . . . . . . . . . . . . . . . . . . 58 vi Danh sách hình vẽ 3.1 Một cấu hình thực hiện được (lựa chọn bất kì theo độ đo xác suất µG ). . . . 33 3.2 Đồ thị G với 4 đỉnh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3 Đồ thị G với 5 đỉnh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 vii MỞ ĐẦU 1. Lý do chọn đề tài Trong nhiều ứng dụng thực tế, bài toán thường được quy về việc xác định kì vọng của hàm của một đại lượng ngẫu nhiên theo phân phối nhất định. Khi đó, người ta thường tìm cách xây dựng dãy biến ngẫu nhiên độc lập có phân phối này trên máy tính và sử dụng luật số lớn để xấp xỉ kì vọng cần tính. Tuy nhiên, trong nhiều trường hợp, việc mô phỏng chính xác một phân phối nào đó là hết sức khó khăn. Phương pháp xích Markov Monte Carlo ra đời nhằm khắc phục khó khăn này. Theo đó, ta sẽ xây dựng một xích Markov có phân phối dừng là phân phối đã cho và áp dụng định lý ergodic để xấp xỉ kì vọng. Ngày nay phương pháp xích Markov Monte Carlo đã được phát triển và sử dụng rộng rãi trong rất nhiều lĩnh vực, từ vật lý cho đến sinh vật, tài chính, khoa học máy tính... Với mong muốn tìm hiểu sâu về phương pháp xích Markov Monte Carlo và các ứng dụng của nó, tôi lựa chọn đề tài nghiên cứu: “Phương pháp xích Markov Monte Carlo và ứng dụng” cho luận văn thạc sĩ của mình. Tài liệu tham khảo chính của luận văn là các chuyên khảo [3] và [4]. 2. Mục đích nghiên cứu ˆ Cơ sở lý thuyết của phương pháp xích Markov Monte Carlo. ˆ Mô phỏng phương pháp xích Markov Monte Carlo. viii 3. Nhiệm vụ nghiên cứu ˆ Nghiên cứu các phương pháp sinh số ngẫu nhiên theo phân phối cho trước. ˆ Phương pháp Monte-Carlo. ˆ Phương pháp xích Markov Monte Carlo và các phương pháp cải tiến. ˆ Mô phỏng phương pháp Monte Carlo và xích Markov Monte Carlo trên máy tính để giải quyết một vấn đề cụ thể. 4. Đối tượng và phạm vi nghiên cứu ˆ Xích Markov ˆ Phương pháp xích Markov Monte Carlo 5. Phương pháp nghiên cứu ˆ Nghiên cứu lý thuyết. ˆ Nghiên cứu thực nghiệm mô phỏng trên máy tính. 6. Dự kiến đóng góp mới Luận văn hệ thống hoá và làm rõ cơ sở lý thuyết của phương pháp xích Markov Monte Carlo và ứng dụng phương pháp này trong một vấn đề thực tiễn. NỘI DUNG Luận văn tốt nghiệp sẽ được chia làm ba chương cộng với phần Mở đầu, Kết luận và Tài liệu tham khảo. Nội dung cụ thể trong Chương 1, Chương 2, Chương 3 của luận văn dự kiến sẽ được phân bổ như sau: Chương 1: Xích Markov 1.1. Một số khái niệm cơ bản của lý thuyết xác suất ix 1.2. Xích Markov Chương 2: Phương pháp Monte-Carlo 2.1. Số ngẫu nhiên và phương pháp sinh số ngẫu nhiên 2.2. Phương pháp Monte-Carlo Chương 3: Xích Markov Monte Carlo 3.1. Phương pháp xích Markov Monte Carlo 3.2. Một số phương pháp cải tiến 3.3. Mô phỏng x Chương 1 Xích Markov 1.1 Một số khái niệm cơ bản của lý thuyết xác suất Cho Ω là một tập hợp khác rỗng và Σ là một σ-đại số các tập con của Ω. Mỗi phần tử của Σ được gọi là một biến cố. Cho A ⊆ Ω, ta viết Ac là phần bù của A trong Ω, nghĩa là: Ac = {s ∈ Ω : s ∈ A}. / Một độ đo xác suất trên Ω là một hàm P : Σ → [0, 1], thỏa mãn (i) P(∅) = 0, P(Ω) = 1. (ii) Nếu A1 , A2 , ... là dãy gồm đếm được các biến cố đôi một rời nhau, (tức là Ai ∩Aj = ∞ ∅ với mọi i = j), khi đó P( i=1 ∞ Ai ) = P(Ai ). i=1 Nếu A và B là các biến cố với P(B) > 0, ta định nghĩa xác suất điều kiện của A khi biến cố B đã xảy ra, kí hiệu P(A|B) P(A|B) = P(A ∩ B) . P(B) Giải thích trực quan của P(A|B) là xem xét khả năng xảy ra của biến cố A khi ta đã biết biến cố B đã xảy ra. Hai biến cố A và B được gọi là độc lập nếu P(A ∩ B) = P(A)P(B). Tổng quát hơn, các biến cố A1 , A2 , . . . , Ak được gọi là độc lập nếu với mỗi l ≤ k và 1 i1 , . . . , il ∈ {1, 2, . . . , k} bất kì với i1 < i2 < · · · < il ta có l P(Ai1 ∩ Ai2 ∩ · · · ∩ Ail ) = P(Ain ). n=1 Chú ý rằng nếu P(B) > 0, A và B độc lập thì ta có P(A|B) = P(A), nghĩa là sự xảy ra của biến cố B không làm ảnh hưởng đến khả năng xảy ra của biến cố A. Biến ngẫu nhiên là đại lượng mà giá trị của nó phụ thuộc vào kết quả ngẫu nhiên của phép thử. Thông thường, một biến ngẫu nhiên là một giá trị thực, trong trường hợp này nó là một hàm X : Ω → R. Tuy nhiên, xem xét các biến ngẫu nhiên trong một ý nghĩa tổng quát hơn, đó là những hàm X : Ω → S, S là tập bất kì. Biến cố A được xác định dưới dạng biến ngẫu nhiên X nếu ta có thể có hoặc không có A xảy ra từ giá trị của X. Ví dụ các biến cố được xác định dưới dạng biến ngẫu nhiên X là A = {X ≤ 4.7} = {ω ∈ Ω : X(ω) ≤ 4.7} và B = {X là một số nguyên chẵn}. Hai biến ngẫu nhiên được gọi là độc lập nếu trong trường hợp bất kì mà biến cố A được xác định dưới dạng của X, và biến cố B được xác định dưới dạng của Y , khi đó A và B là độc lập. Nếu X1 , X2 , . . . , Xk là các biến ngẫu nhiên, ta nói X1 , X2 , . . . , Xk gọi là độc lập nếu A1 , A2 , ..., Ak là độc lập với mỗi Ai được xác định dưới dạng của Xi . Phân phối thì giống như độ đo xác suất. Nếu X là một biến ngẫu nhiên giá trị thực, khi đó phân phối µX của X là độ đo xác suất trên R thỏa mãn µX (A) = P(X ∈ A) với tất cả A ⊆ R (thích hợp). Phân phối của biến ngẫu nhiên giá trị thực đặc trưng là hàm phân phối FX : R → [0, 1] được xác định bởi FX (x) = P(X ≤ x) với mọi x ∈ R. Phân phối µ trong tập hữu hạn S = {s1 , s2 , . . . , sk } thông thường được mô tả là một vectơ (µ1 , µ2 , . . . , µk ), ở đây µi = µ(si ). Theo định nghĩa của độ đo xác suất, ta k có µi ∈ [0, 1] với mỗi i và µi = 1. i=1 Một dãy các biến ngẫu nhiên X1 , X2 , ... gọi là độc lập và cùng phân phối nếu các biến ngẫu nhiên 2 (i) là độc lập, (ii) có cùng phân phối, tức là P(Xi ≤ x) = P(Xj ≤ x) với mọi i, j và x. Thông thường, dãy (X1 , X2 , ...) thể hiện sự phát triển theo thời gian của đại lượng ngẫu nhiên: Xn là đại lượng tại thời điểm n. Một dãy như vậy được gọi là một quá trình ngẫu nhiên (hoặc quá trình mang tính ngẫu nhiên). Xích Markov trong phần tiếp theo là một lớp đặc biệt của quá trình ngẫu nhiên. Ta xét hai loại biến ngẫu nhiên giá trị thực: biến ngẫu nhiên rời rạc và biến ngẫu nhiên liên tục. Biến ngẫu nhiên rời rạc thì các giá trị của chúng là tập con hữu hạn hoặc đếm được của R. Biến ngẫu nhiên liên tục X là một biến ngẫu nhiên mà tồn tại một hàm mật độ fX : R → [0, ∞) sao cho x fX (x)dx = FX (x) = P(X ≤ x), −∞ với mọi x ∈ R. Một ví dụ rất nổi tiếng của biến ngẫu nhiên liên tục X sinh ra bằng cách cho X bởi hàm mật độ Gaussian fX (x) = √ 1 2 /2σ 2 2πσ 2 e−(x−µ) , với các thông số µ và σ > 0. Tuy nhiên, các biến ngẫu nhiên liên tục đó có phân phối đều trên [0, 1], khi đó ta có hàm mật độ fX (x) =    1 nếu x ∈ [0, 1]  0 ngược lại, và hàm phân phối x FX (x) = −∞   0 nếu x ≤ 0     fX (x)dx = x nếu x ∈ [0, 1]      1 nếu x ≥ 1. Nếu X là một biến ngẫu nhiên có phân phối đều trên [0, 1], khi đó X có khả năng xảy ra như nhau tại mọi giá trị trong khoảng đơn vị [0, 1]. Chính xác hơn, với mỗi 3 khoảng I có độ dài a trong đoạn [0, 1], ta có: P(X ∈ I) = a. Kì vọng (hoặc giá trị kì vọng, hoặc trung bình) E[X] của một biến ngẫu nhiên giá trị thực X là, trong một nghĩa nào đó, giá trị "trung bình" mong đợi từ x. Nếu X là một biến ngẫu nhiên liên tục với hàm mật độ fX (x), khi đó kì vọng được xác định như sau ∞ E[X] = xfX (x)dx. −∞ Trong trường hợp X có phân phối đều trên [0, 1] thì 1 1 xdx = . 2 E[X] = 0 Trong trường hợp X là biến ngẫu nhiên có giá trị nguyên không âm, kì vọng được xác định như sau ∞ kP(X = k). E[X] = k=1 Ta có thể chứng minh tương đương với công thức ∞ P(X ≥ k). E[X] = (1.1) k=1 Một đặc trưng quan trọng khác bên cạnh E[X] của biến ngẫu nhiên X là phương sai Var[X], được xác định bởi Var[X] = E[(x − µ)2 ] ở đây µ = E[X]. (1.2) Do đó, phương sai là kì vọng của bình phương độ lệch của X so với kì vọng của nó . Phương sai có thể tính toán bằng cách sử dụng công thức (1.2) hoặc bởi đẳng thức Var[X] = E[X 2 ] − (E[X])2 . được gọi là công thức Steiner. Đối với các kì vọng ta có: E[X1 + X2 + · · · + Xn ] = E[X1 ] + E[X2 ] + · · · + E[Xn ]. Nếu c là một hằng số thì E[cX] = cE[X]. 4 (1.3) Đối với các phương sai ta có Var[cX] = c2 Var[X]. Khi X1 , X2 , . . . , Xn độc lập Var[X1 + X2 + · · · + Xn ] = Var[X1 ] + Var[X2 ] + · · · + Var[Xn ]. Định lý 1.1. (Bất đẳng thức Chebyshev) Cho X là một biến ngẫu nhiên với kì vọng µ và phương sai σ 2 . Cho a > 0 bất kì, ta có xác suất P[|X − µ| ≥ a] của độ lệch trung bình nhỏ nhất, thỏa mãn P(|X − µ| ≥ a) ≤ σ2 . a2 Định lý 1.2. (Luật Số Lớn) Cho X1 , X2 , ... là các biến ngẫu nhiên độc lập khả tích và có cùng phân phối với trung bình µ. Cho Mn biểu thị giá trị trung bình của n biến Xi đầu tiên, có nghĩa là: Mn = 1 (X1 + X2 + · · · + Xn ). n Khi đó, Mn hội tụ hầu chắc chắn tới µ. Định lý 1.3. (Định lí giới hạn trung tâm) Cho X1 , X2 , . . . là dãy biến ngẫu nhiên độc lập và có cùng phân phối. Đặt µ = EXn và σ 2 = DXn < +∞. Đặt Sn = X1 + X2 + · · · + Xn . Khi đó x Sn − nµ P √ - Xem thêm -