zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Thạc sĩ - Tiến sĩ - Cao học

Tóm tắt Luận văn Thạc sĩ Khoa học: Một số mô hình xác suất trong khoa học máy tính

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:24

Báo xấu

54
lượt xem 4
download

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

Trong luận văn này, tác giả muốn giới thiệu các loại mô hình và phân tích xác suất hữu dụng nhất trong khoa học máy tính. Giả sử với một hàm mở đầu trong xác suất, tác giả trình bày một số đề tài quan trọng như phương pháp xác suất, xích Markov, mô phỏng MCMC và quá trình Poisson không dừng. Sau đây là tóm tắt của luận văn.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt Luận văn Thạc sĩ Khoa học: Một số mô hình xác suất trong khoa học máy tính

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- PHẠM THỊ THU HẰNG MỘT SỐ MÔ HÌNH XÁC SUẤT TRONG KHOA HỌC MÁY TÍNH Chuyên ngành: Lý thuyết Xác suất và Thống kê toán học Mã số: 60406106 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - Năm 2016
Mục lục 1
Luận văn tốt nghiệp Phạm Thị Thu Hằng Công trình được hoàn thành tại: Trường Đại học Khoa hoc Tự nhiên - Đại học Quốc gia Hà Nội Người hướng dẫn khoa học: GS.TSKH Đặng Hùng Thắng Hội đồng chấm luận văn: • Chủ tịch: PGS.TS Trần Hùng Thao - Viện Toán học - Viện Hàn lâm KH và CN Việt Nam • Phản biện 1: TS. Nguyễn Thịnh - Đại học Khoa học Tự Nhiên - ĐHQGHN • Phản biện 2: TS. Ngô Hoàng Long - Đại học Sư phạm Hà Nội • Thư ký: TS. Lê Vỹ - Đại học Khoa học Tự Nhiên - ĐHQGHN • Ủy viên: TS. Trần Mạnh Cường - Đại học Khoa học Tự Nhiên - ĐHQGHN Luận văn đã được bảo vệ trước Hội đồng chấm luận văn thạc sĩ họp tại: Khoa Toán-Cơ-Tin học Trường Đại học Khoa học Tự nhiên (ĐHQGHN) vào 15h giờ 30 ngày 28 tháng 12 năm 2016 Có thể tìm đọc luận văn tại: - Trung tâm thư viện Đại học Quốc gia Hà Nội 2
LỜI NÓI ĐẦU Trong những năm gần đây, xác suất đã phát triển đa dạng và có nhiều ứng dụng quan trọng trong lĩnh vực khoa học máy tính. Ví dụ, các chủ đề liên quan đến thuật toán như thuật toán ngẫu nhiên, thuật toán ước lượng và phân tích xác suất của thuật toán đều sử dụng phương pháp xác suất. Trong luận văn này, tôi muốn giới thiệu các loại mô hình và phân tích xác suất hữu dụng nhất trong khoa học máy tính. Giả sử với một hàm mở đầu trong xác suất, tôi trình bày một số đề tài quan trọng như phương pháp xác suất, xích Markov, mô phỏng MCMC và quá trình Poisson không dừng. Luận văn này cung cấp nhiều ví dụ và bài tập mô tả các đề tài như thuật toán sắp xếp, thuật toán tìm kiếm và biểu đồ ngẫu nhiên, bài toán tự sắp xếp theo danh sách, phản xích, phân hoạch cực đại và cực tiểu trong đồ thị và nhiều đề tài khác. Cấu trúc luận văn được chia làm 3 chương chính: • Chương 1 đưa ra các ví dụ hay trong khoa học máy tính, đồng thời trình bày phương pháp xác suất và một số cách ứng dụng phương pháp này. • Chương 2 viết về xích Markov trên không gian trạng thái rời rạc, phương pháp Monte Carlo và xích Markov Monte Carlo (MCMC). • Chương 3 giới thiệu một số lớp quá trình Poisson, từ đó nghiên cứu bài toán phân loại biến cố của một quá trình Poisson không dừng và bài toán xác định phân phối có điều kiện của thời điểm đến. Trong khuôn khổ của luận văn này, do sự hạn hẹp về thời gian cũng như năng lực của bản thân, vì vậy không thể tránh khỏi những hạn chế về nội dung cũng như việc trình bầy. Tôi nhận thấy xác suất trong khoa học máy tính còn rất nhiều điều thú vị khác nữa và tôi rất mong có dịp trình bầy đầy đủ hơn. Luận văn được hoàn thành dưới sự hướng dẫn tận tâm của GS.TSKH Đặng Hùng Thắng. Tôi xin được bày tỏ lòng biết ơn và kính trọng sâu sắc của mình đến thầy. Qua đây tôi xin chân thành gửi lời cảm ơn tới các thầy cô trong Tổ 3
Luận văn tốt nghiệp Phạm Thị Thu Hằng bộ môn Xác suất thống kê và Ban Chủ nhiệm khoa Toán - Cơ - Tin học Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã chỉ bảo và hướng dẫn tận tình giúp tôi hoàn thành luận văn này! Rất mong nhận được ý kiến đóng góp của các thầy cô và các bạn! Hà Nội, tháng 11/2015 Phạm Thị Thu Hằng 4
Chương 1 Xác suất trong lý thuyết tổ hợp và đồ thị 1.1 Các ví dụ 1.1.1 Đồ thị ngẫu nhiên Giờ hãy xem xét đồ thị với tập hợp đỉnh V = {1, 2, . . . , n} và tập hợp cạnh A = {(i, X(i)), i = 1, . . . , n} trong đó X(i) là các biến ngẫu nhiên độc lập thỏa mãn n X P {X(i) = j} = Pj , Pj = 1 j=1 Đồ thị vừa xây dựng là một đồ thị ngẫu nhiên. Chúng ta sẽ tính xác suất để đồ thị ngẫu nhiên này là đồ thị liên thông. Để tìm được xác suất này, ta chọn một đỉnh, giả sử đỉnh 1 và lần theo chuỗi các đỉnh 1, X(1), X 2 (1), . . . , trong đó X n (1) = X(X n−1 (1)) để xác định giá trị của biến ngẫu nhiên N là chỉ số k nhỏ nhất sao cho X k (1) không là một đỉnh mới. Tức là, N = min(k : X k (1) ∈ {1, X(1), . . . , X k−1 (1)}) Đồng thời, gọi N X −1 W = P1 + PX i (1) i=1 Nói cách khác, N là số đỉnh tiếp xúc trong chuỗi 1, X(1), X 2 (1), . . . trước khi một đỉnh xuất hiện hai lần còn W là tổng các xác suất của các đỉnh này. 5
Luận văn tốt nghiệp Phạm Thị Thu Hằng Bổ đề 1.1.1. Xét một đồ thị ngẫu nhiên gồm các đỉnh 0, 1, . . . , r, và các cạnh (i, Yi ), i = 1, . . . , r, trong đó Yi là các biến ngẫu nhiên độc lập và r X P {Yi = j} = Qj , j = 0, ..., r, Qj = 1 j=0 Đồ thị ngẫu nhiên ở trên bao gồm r đỉnh thông thường (đánh số từ 1 đến r) và một đỉnh đặc biệt (đánh số 0); cứ mỗi đỉnh thông thường có một cạnh độc lập đi qua đỉnh j với xác suất Qj ; không có cạnh nào xuất phát từ đỉnh đặc biệt. Khi đó, P {đồ thị liên thông} = Q0 . Mệnh đề 1.1.1. P{đồ thị liên thông} = E[W] Trường hợp đặc biệt trong đó cạnh xuất phát từ mỗi đỉnh có thể đến mọi đỉnh của đồ thị với cùng xác suất 1 Pj = , j = 1, . . . , n n . Hệ quả sau cho ta công thức tính xác suất đồ thị liên thông trong trường hợp đặc biệt này. Hệ quả 1.1.1. Khi Pj = 1/n, n−1 (n − 1)! X nj P {đồ thị là liên thông} = nn j! j=0 p Hệ quả 1.1.2. Với n lớn, P {đồ thị là liên thông} v π/2n 1.1.2 Thuật toán Tìm kiếm và Sắp xếp nhanh Gọi X là số phép so sánh cần sử dụng. Để tính E[X], trước hết ta biểu diễn X thành tổng các biến ngẫu nhiên khác theo cách sau. Đầu tiên, ta đánh dấu cho các giá trị được sắp xếp: 1 biểu thị giá trị nhỏ nhất, 2 biểu thị giá trị nhỏ nhì, cứ như vậy cho tới hết. Khi đó, với 1 ≤ i < j ≤ n, lấy I(i, j) bằng 1, nếu i và j được so sánh trực tiếp và bằng 0 nếu i và j không được so sánh trực tiếp. Tính tổng các biến này với i < j cho ta tổng số phép so sánh. Đó là j−1 n X X X= I(i, j) j=2 i=1 6
Luận văn tốt nghiệp Phạm Thị Thu Hằng tức là j−1 n X X E[X] = P { i và j được so sánh } j=2 i=1 1.1.3 Mô hình danh sách tự tổ chức Xem xét n phần tử e1 , . . . , en ban đầu được sắp xếp theo một trật tự. Tại mỗi thời điểm có một yêu cầu đối với một trong số các phần tử này; ei được yêu cầu độc lập với trước đó, xác suất Pi . Sau khi đáp ứng được yêu cầu, phần tử này được chuyển lên đầu danh sách. Chúng ta sẽ xác định vị trí kỳ vọng của phần tử được yêu cầu với giả thiết quá trình này diễn ra trong thời gian dài. Đặt R là vị trí phần tử được yêu cầu, ta sẽ tìm E[R] phần tử được chọn bằng cách kiểm tra điều kiện với Y . Ta có n X E[R] = E[ vị trí của ei ]Pi i=1 Dấu bằng cuối cùng dựa trên cơ sở vị trí của ei và biến cố ei được yêu cầu độc lập với nhau. Điều này có được do xác suất để ei được yêu cầu là Pi cho dù hiện tại ei có ở vị trí nào đi nữa. Tuy nhiên, ta thấy X vị trí của ei = 1 + Ii,j j6=i trong đó 1, nếu ej đứng trước ei Ii,j = 0, ngược lại ta thu được X E[vị trí của ei ] = 1 + E[Ii,j ] j6=i X =1+ P {ej đứng trước ei } (1.1) j6=i Để xác định P {ej đứng trước ei }, ta thấy ej đứng trước ei nếu lần yêu cầu cuối cùng với một trong hai phần tử này là lần yêu cầu với ej . Tuy nhiên, biết rằng một lần yêu cầu có thể yêu cầu hoặc ei hoặc ej nên xác suất để ej được yêu cầu là Pj P (ej | ei hoặc ej ) = Pi + Pj 7
Luận văn tốt nghiệp Phạm Thị Thu Hằng Do đó, P {ej đứng trước ei } = Pj /(Pi + Pj ). Từ kết quả (??) và (??) ta có n X X Pj E[R] = 1 + Pi P i + Pj i=1 j6=i 1.1.4 Sinh hoán vị ngẫu nhiên Ta nói rằng vec-tơ X(1), . . . , X(n) ngẫu nhiên là hoán vị ngẫu nhiên của giá trị 1, . . . , n nếu P {(X(1), . . . , X(n)) = (i1 , ...in )} = 1/n! cho tất cả n! hoán vị i1 , . . . , in của 1, . . . , n. Khi đó, một hoán vị ngẫu nhiên có thể là bất cứ hoán vị nào trong n! hoán vị của 1, . . . , n. Giả sử trong phần này X(1), . . . , X(n) là một hoán vị ngẫu nhiên. Hệ quả 1.1.3. n X N= Ij j=1 trong đó I1 , . . . , In là các biến ngẫu nhiên độc lập sao cho 1 P {Ij = 1} = = 1 − P {Ij = 0}, j = 1, ..., n n−j+1 Từ Hệ quả 1.1.3 , có n n X 1 X i−1 E[N ] = Var(N ) = i i2 i=1 i=1 Ngoài ra, khi n lớn, từ Hệ quả 1.1.3 và định lý giới hạn trung tâm, N có hàm phân phối xấp xỉ chuẩn. 1.2 Phương pháp xác suất 1.2.1 Lời giới thiệu Phương pháp xác suất là một kỹ thuật phân tích thuộc tính của phần tử trong một tập hợp bằng cách đưa ra một không gian xác suất cho tập hợp này và khảo sát một phần tử ngẫu nhiên. Phương pháp này chủ yếu được ứng dụng để giải quyết các bài toán lý thuyết tổ hợp và đồ thị. 8
Luận văn tốt nghiệp Phạm Thị Thu Hằng 1.2.2 Ứng dụng xác suất để chứng minh sự tồn tại Giả sử chúng ta muốn chứng minh một phần tử của tập hợp S có một tính chất nào đó. Ta có thể nghiên cứu một phần tử ngẫu nhiên X trong tập hợp S rồi chứng minh xác suất của biến cố đối ,biến cố mà X không có tính chất này, nhỏ hơn 1. 1.2.3 Xác định cận từ kỳ vọng Gọi f là hàm của phần tử s thuộc tập hợp hữu hạn S , giả sử ta muốn tìm m = max f (s) s∈S Cận dưới hữu ích có thể được xác định bằng cách sau: gọi X là một phần tử ngẫu nhiên của S có giá trị kỳ vọng f (X) có thể tính được, với m ≥ f (X) ta có m ≥ E[f (X)] Bất đẳng thức mạnh nếu f (X) là một đại lượng ngẫu nhiên không đổi. 1.2.4 Bài toán tập hợp độc lập có trọng số tối đa: Thuật toán cận biên và ngẫu nhiên Giả sử mỗi đỉnh i, i = 1, . . . , n có trọng số wi dương liên hợp với nó. Với mỗi tập hợp đỉnh A thì X w (A) = wi i∈A và m = max w (A) A trong đó lấy cực đại trên các tập hợp A độc lập. m được gọi là số độc lập của đồ thị. Gọi Xi , i = 1, . . . , n là các biến ngẫu nhiên lũy thừa độc lập với hệ số λi , i = 1, . . . , n. Mệnh đề 1.2.1. Với mỗi số dương λi , i = 1, . . . , n, n X m≥ wi λi /∧i i=1 9
Luận văn tốt nghiệp Phạm Thị Thu Hằng trong đó X ∧i = λj j∈D(j) Đây là thuật toán sắp xếp ngẫu nhiên để ước lượng cả m và tập hợp độc lập có trọng số tối ưu. Thuật toán ước lượng ngẫu nhiên hóa 1. Đặt λi = (wi /d(i))b với tất cả các đỉnh i trong tập hợp đỉnh V 2. Tạo giá trị cho mỗi biến ngẫu nhiên I theo λj P {I = j} = X , j∈V λi i∈V 3. Đặt đỉnh I vào tập hợp độc lập, loại bỏ I và các đỉnh kề nó khỏi tập hợp đỉnh của đồ thị. Tính lại bậc của các đỉnh còn lại rồi quay lại bước 1. Lặp lại các bước này thu được tập hợp độc lập có trọng số lớn nhất là một ước lượng của tập hợp độc lập có trọng số tối đa. Ta có thể chạy lại thuật toán với cùng giá trị của b hoặc thay giá trị khác sau mỗi lần chạy. 1.2.5 Bài toán phủ tập hợp Gọi Si , i = 1, . . . , m, là tập con của S = {1, 2, . . . , s}, Gọi ni là số tập hợp con chứa i, và giả sử ni > 0 với mỗi i = 1, . . . , s. Bài toán phủ tập hợp là bài toán tìm số tập con nhỏ nhất có thể hợp lại thành tập S . Gọi r là số tập con nhỏ nhất, sử dụng phương pháp xác suất, chứng minh rằng với mỗi số nguyên k s m−ni X k m−k+1 r≤k+ m (1.2) k ni + 1 i=1 1.2.6 Phản xích Tập hợp A1 , A2 , . . . , Ar là các tập hợp con của {1, 2, . . . , n}, được gọi là một phản xích nếu không có tập hợp nào trong các tập hợp này là tập hợp con của tập khác, tức là Ai ∈ / Aj với tất cả các cặp i 6= j . Định lý Sperner chỉ ra rằng n số tập hợp lớn nhất trong một phản xích là [n/2] trong đó [n/2] là số nguyên lớn nhất nhỏ hơn hoặc bằng n/2. Do đó, tập hợp tất cả các tập hợp con của {1, 2, . . . , n} kích thước [n/2] tạo thành phản xích lớn nhất. 10
Luận văn tốt nghiệp Phạm Thị Thu Hằng 1.2.7 Bổ đề rút gọn Lovasz Xem xét tập hợp các biến cố {Ai , i = 1, . . . , n} với 0 < P (Ai ) < 1, giả sử ta muốn chứng minh không biến cố nào có thể xảy ra. Rõ ràng đây là trường hợp các biến cố độc lập với nhau nhưng ngay cả khi chúng không độc lập thì kết quả này cũng có thể xảy ra khi mỗi biến cố “độc lập lẫn nhau” với mỗi tập hợp con chứa hầu hết các biến cố khác như định nghĩa sau đây. Định nghĩa 1.2.1. Biến cố A độc lập lẫn nhau với tập hợp các biến cố {B1 , . . . , Br } nếu xác suất có điều kiện của A, với điều kiện để Bi xảy ra, bằng xác suất không điều kiện P (A). Bổ đề 1.2.1. Bổ đề rút gọn Lovasz Cho các biến cố A1 , . . . , An , nếu với mỗi i, i = 1, . . . , n, Ai độc lập lẫn nhau với một tập hợp chứa tất cả các biến cố ngoại trừ nhiều nhất d biến cố Aj khác, j 6= i và 1 P (Ai ) ≤ e(d + 1) thì n \ P Acj > 0 j=1 1.2.8 Thuật toán ngẫu nhiên để tính phân hoạch cực tiểu của một đồ thị Giả sử ta muốn tìm một cách phân hoạch có sức chứa nhỏ nhất. Tức là nếu ta đặt m0 = min c(X, X c ) thì bài toán trở thành tìm m0 cùng với một phân hoạch sức chứa m0 . Với X0 , X0c là một phân hoạch có sức chứa nhỏ nhất. Xây dựng một thuật toán xác suất để cho ra một phân hoạch mà sức chứa của nó bằng c(X0 , X0c ) với xác suất lớn hơn hoặc bằng 2/n2 . Thuật toán này còn có thể cho ta một phân hoạch cực tiểu với xác suất cao tùy ý. 11
Chương 2 Xích Markov và mô phỏng MCMC 2.1 Xích Markov 2.1.1 Giới thiệu Xét quá trình ngẫu nhiên thời gian rời rạc. Nếu Xn = i thì quá trình được gọi là “trong trạng thái i tại thời điểm n”. Giả sử khi quá trình ở trạng thái i, có một xác suất cố định Pi,j để trạng thái tiếp theo là trạng thái j . Tức là P {Xn+1 = j|Xn = i, Xn−1 = in−1 , ..., X0 = i0 } = Pi,j (2.1) X Pi,j≥0 , Pi,j = 1 j Gọi P là ma trận các xác suất chuyển tiếp một bước Pi,j P0,0 P0,1 . . . P0,j ...    P1,0 P1,1 . . . P1,j ...   ... ... P= ... ... ...  Pi,0 Pi,1 . . . Pi,j ...  ... ... ... ... ... 2.1.2 Phương trình Chapman-Kolmogorov n là xác suất để xích chuyển từ trạng thái i sang trạng thái j sau n bước. Pi,j Phương trình Chapman – Kolmogorov giúp ta tính được xác suất n bước này. Phương trình như sau: X∞ n+m n m Pi,j = Pi,k Pk,j (2.2) k=0 12
Luận văn tốt nghiệp Phạm Thị Thu Hằng 2.1.3 Phân loại trạng thái n > 0 với n ≥ 0, Ta nói trạng thái i đến được trạng thái j nếu tồn tại Pi,j kí hiệu i → j . Hai trạng thái i và j được gọi là liên thông nếu i → j và j → i, kí hiệu i ↔ j Quan hệ liên thông là quan hệ tương đương. Một Xích Markov được gọi là tối giản nếu hai trạng thái bất kỳ đều liên thông với nhau. Với mỗi trạng thái i, gọi fi là xác suất để bắt đầu từ trạng thái i, quá trình sẽ trở lại trạng thái đó. Trạng thái i được gọi là hồi quy nếu fi = 1 và trạng thái i được gọi là trans nếu fi < 1. Mệnh đề 2.1.1. Trạng thái i ∞ X n hồi quy nếu Pi,i =∞ n=0 ∞ X n trans nếu Pi,i
Luận văn tốt nghiệp Phạm Thị Thu Hằng 2.1.5 Ứng dụng Mô hình cho hiệu suất thuật toán Bài toán tối ưu hóa sau đây được gọi là quy hoạch tuyến tính: cực tiểu biểu thức cx với điều kiện: Ax = b, x ≥ 0 trong đó A là một ma trận hằng có kích thước m × n, c = (c1 , . . . , cn ) và b = (b1 , . . . , bm ) là các véc tơ hằng cố định và x = (x1 , .., xn ) ∈ R+ n được chọn để tối tiểu hóa cx = ni=1 ci xi . P Ta xem xét một mô hình xác suất (xích Markov) đơn giản thể hiện cách thuật toán di chuyển theo tập hợp các điểm cực biên. Cụ thể, giả sử nếu tại thời điểm nào đó thuật toán đang ở điểm cực biên tốt thứ j , nên sau lần lặp tiếp theo, điểm cực biên tìm thấy có thể là bất cứ điểm nào trong j − 1 điểm cực biên tốt hơn. Xem xét một xích Markov trong đó P1,1 = 1, và với i > 1 1 Pi,j = , j = 1, ..., i − 1 i−1 Gọi Ti là số lần chuyển tiếp cần thiết để đi từ trạng thái i đến trạng thái 1. Ta viết được hàm đệ quy cho E[Ti ] bằng cách lấy xác suất điều kiện với trạng thái ban đầu: i−1 1 X E[Ti ] = 1 + E[Tj ] i−1 j=1 i−1 X Chứng minh bằng phương pháp quy nạp, ta có E[Ti ] = 1/j j=1 Để biểu thị TN một cách hoàn chỉnh hơn, ta sử dụng biểu thức N X −1 TN = Ij (2.11) j=1 trong đó 1, nếu xích ở trạng thái j Ij = 0, nếu ngược lại 14
Luận văn tốt nghiệp Phạm Thị Thu Hằng Mệnh đề 2.1.3. Dãy biến ngẫu nhiên I1 , . . . , IN −1 là độc lập, và P {Ij = 1} = 1/j, j = 1, ..., N − 1 N −1 X 1 Hệ quả 2.1.2. (a) E[TN ] = j j=1 N −1 X 1 1 (b) V ar(TN ) = (1 − ) j j j=1 (c) Với n lớn, TN có phân phối xấp xỉ chuẩn với trị số trung bình và phương sai đều bằng ln N . Tổng quát, để mô hình hóa số lần lặp của một thuật toán luôn chuyển tới một trạng tối ưu hơn ta có thể sử dụng một xích Markov có xác suất chuyển thỏa mãn điều kiện: Pi,j = 0 nếu0 ≤ i < j (2.12) Gọi Di là lượng trạng thái giảm khi chuyển tiếp từ trạng thái i, khi đó P {Di = k} = Pi,i−k Mệnh đề 2.1.4. Đặt Nn là số chuyển tiếp cần để một xích Markov có xác suất chuyển tiếp thỏa mãn điều kiện (2.12) đi từ trạng thái n sang trạng thái 0. Nếu tồn tại hàm không tăng d(i), i > 0, thoả mãn E[Di ] ≥ d(i) thì n X 1 E[Nn ] ≤ (2.13) d(i) i=1 2.1.6 Xích Markov với thời gian đảo ngược Xem xét một xích Markov dừng có xác suất chuyển tiếp là Pi,j và xác suất dừng πi . Giả sử bắt đầu từ thời điểm n, ta thấy xích trạng thái quay ngược lại trình tự trước đó. Tức là với một xích các trạng thái Xn , Xn−1 , Xn−2 , . . . bản thân xích này là một xích Markov với xác suất chuyển tiếp Qi,j trong đó πj Pj,i Qi,j πi Nếu Qi,j = Pi,j thì xích Markov được gọi là đảo ngược thời gian. 15
Luận văn tốt nghiệp Phạm Thị Thu Hằng Định lí 2.1.2. Điều kiện Kolmogorov để đảo ngược thời gian Một xích Markov có Pi,j = 0 khi Pj,i = 0 có tính đảo ngược thời gian nếu bắt đầu từ trạng thái i, bất cứ đường đi từ i nào đều có cùng xác suất với đường đi từ hướng ngược lại. Tức là xích có tính đảo ngược thời gian nếu Pi,i1 Pi1 ,i2 . . . Pik ,i = Pi,ik Pik ,ik−1 . . . Pi1 ,i (2.3) với mọi k và trạng thái i, i1 , . . . , ik . Khái niệm xích nghịch đảo khá hữu dụng ngay cả khi xích Markov ban đầu không có tính đảo ngược thời gian. Để mô tả điều này, ta cần sử dụng Mệnh đề sau. Mệnh đề 2.1.5. Xem xét một xích Markov tối giản có xác suất chuyển tiếp Pi,j . Nếu có thể tìm được các số dương πi , i ≥ 0 có tổng bằng 1 và ma trận xác suất chuyển tiếp Q = [Qi,j ] thỏa mãn Pi,j = πj Qj,i (2.4) thì Qi,j là xác suất chuyển tiếp của xích nghịch đảo và πi là xác suất dừng của cả xích ban đầu và xích nghịch đảo. 2.2 Mô phỏng 2.2.1 Mô phỏng Monte Carlo Đặt X = (X1 , . . . , Xn ) là véc tơ ngẫu nhiên có hàm mật độ chung là f (x1 , . . . , xn ), giả sử ta cần xác định ZZ Z θ = E[g(X) = ... g(x1 , ..., xn )f (x1 , ..., xn )dx1 ...dxn với hàm n chiều g nào đó. Trong nhiều trường hợp, ta không thể tính được cụ thể tích phân trên hay thậm chí cũng không thể ước lượng được một khoảng chính xác nào đó. Ta chỉ có thể ước lượng θ bằng cách mô phỏng. Để ước lượng θ bằng phương pháp mô phỏng, trước hết ta tạo một vec tơ ngẫu nhiên X(1) có hàm mật độ f, và tìm giá trị Y1 = g(X(1) ). Sau đó tạo ra một thứ ngẫu nhiên vector X(2) , độc lập đầu tiên, cũng với mật độ f, và sau đó tính Y2 = g(X(2) ) . Tiếp tục như vậy cho đến khi bạn có tạo ra các giá trị của r, một 16
Luận văn tốt nghiệp Phạm Thị Thu Hằng số được xác định trước, của các biến ngẫu nhiên Yi = g(X(i) ), i = 1, ..., r Theo luật số lớn mạnh ta có: Y1 + ... + Yr lim = E[g(X(1) )] = θ r→∞ r Do đó, ta có thể sử dụng trung bình các giá trị tạo được Yi là một ước lượng của θ. Phương pháp ước lượng E[g(X)] này được gọi là phương pháp mô phỏng Monte Carlo. 2.2.2 Tạo các biến ngẫu nhiên rời rạc Giả sử ta cần tạo giá trị của một biến ngẫu nhiên X có hàm phân bố xác suất pi = P {X = xj }, j = 0, 1, ... Ta có thể thực hiện bằng cách tạo một số ngẫu nhiên U và thiết lập    x0 , nếu U < p0  x1 ,    nếu p0 ≤ U < p0 + p1 . X = .. Pj−1 Pj nếu pi ≤ U <     xj , i=1 i=1 pi ..  . Vì P {a ≤ U < b} = b − a với 0 < a < b < 1, ta có j−1 nX j X o P {X = xj } = P pi ≤ U < pi = pj i=1 i=1 2.2.3 Tạo các biến ngẫu nhiên liên tục: Phương pháp biến đổi nghịch Xem xét một biến ngẫu nhiên liên tục X có hàm phân phối F . Một phương pháp tổng quát để tạo ra X , được gọi là phương pháp biến đổi nghịch, dựa trên mệnh đề sau. Mệnh đề 2.2.1. Gọi U là biến ngẫu nhiên đều (0, 1). Với bất kỳ hàm phân phối liện tục F , biến ngẫu nhiên X được xác định như sau X = F −1 (U ) Có phân phối F trong đó F −1 (u) là giá trị của x thỏa mãn F (x) = u. 17
Luận văn tốt nghiệp Phạm Thị Thu Hằng 2.3 Mô phỏng MCMC Gọi X là véc tơ ngẫu nhiên rời rạc có tập hợp các giá trị là xj , j ≥ 1. Đặt P {X = xj }, j ≥ 1 là hàm phân bố xác suất của X và giả sử ta cần tính X θ = E[h(X)] = h(xj )P {X = xj } j Với mọi hàm h cho trước. Trong nhiều trường hợp việc tính tất cả các h(xj ) là rất phức tạp nên ta thường chuyển sang mô phỏng để ước lượng θ. Một trong các phương pháp như vậy là Mô phỏng Monte Carlo, nó dùng các số ngẫu nhiên để tạo ra một dãy các véc tơ ngẫu nhiên độc lập {X1 , X2 , . . . , Xn } có cùng phân bố P {X = xj }. Theo luật mạnh số lớn Pn i=1 h(Xi ) lim =θ n→∞ n Nên ta có thể ước lượng θ bằng cách chọn n đủ lớn và dùng trung bình các giá trị của h(Xi ) làm ước lượng. Tuy nhiên, thông thường rất khó để tạo ra một véc tơ ngẫu nhiên có hàm phân bố xác suất cho trước, đặc biệt khi X là véc tơ của các biến ngẫu nhiên phụ thuộc. Hơn nữa, có nhiều ứng dụng trong đó hàm phân bố xác suất của X chỉ được biết sai khác một hằng số nhân, tức là hàm được cho theo dạng P {X = xj } = Cbj , j≥1 trong đó bj được cho trước nhưng phải tính C . Tuy nhiên, vẫn có một phương pháp khác bên cạnh phương pháp Monte Carlo thông thường là sử dụng mô phỏng để ước lượng θ. Bằng cách tạo ra một xích không phải gồm các véc tơ ngẫu nhiên độc lập mà là các trạng thái liên tiếp của một xích Markov mang giá trị véc tơ Xn , n ≥ 1,ở đó xác suất dừng là P {X = xj }, j ≥ 1. Khi điều này được thực hiện, ta có thể áp dụng Mệnh đề 2.1.2 và sử dụng ni=1 h(Xi )/n để P ước lượng θ. Để hiểu cách tạo một xích Markov với xác suất dừng ngẫu nhiên chỉ được cho dưới dạng một hàm hệ số bội, gọi b(j), j ≥ 1, là các số dương có tổng P∞ B = j=1 b(j) hữu hạn. Thuật toán sau đây, được gọi là thuật toán Hastings Metropolis, được sử dụng để tạo ra một xích Markov đảo ngược thời gian có xác suất dừng: π(j) = b(j)/B, j ≥ 1. 18
Luận văn tốt nghiệp Phạm Thị Thu Hằng Gọi Q ma trận xác suất chuyển của xích Markov tối giản có không gian trạng thái là tập các số nguyên, với q(i, j) biểu diễn giá trị ở hàng i cột j . Giờ ta sẽ xác định xích Markov {Xn } như sau: Khi Xn = i, tạo một biến Y ngẫu nhiên sao cho P {Y = j} = q(i, j). Nếu Y = j thì đặt Xn+1 bằng j với xác suất α(i, j) và đặt bằng i với xác suất 1 − α(i, j), trong đó giá trị của α(i, j) sẽ được cho dưới đây. Với những điều kiện này, dãy các trạng thái là một xích Markov có xác suất chuyển tiếp Pi,j thỏa mãn cho bởi Pi,j = q(i, j)α(i, j), j 6= i X Pi,i = q(i, i) + q(i, k)[1 − α(i, k)] k6=i xích Markov này có tính khôi phục ngươc thời gian và có xác suất dừng π(j) nếu π(i)Pi,j = π(j)Pj,i điều này tương đương với π(i)q(i, j)α(i, j) = π(j)q(j, i)α(j, i) (2.5) Tuy nhiên, nếu ta chọn π(j) = b(j)/B và đặt π(j)q(j, i) α(i, j) = min ,1 (2.6) π(i)q(i, j) thì đẳng thức (??) dễ dàng được thỏa mãn (vì nếu π(j)q(j, i)/π(i)q(i, j) ≤ 1 thì α(i, j) bằng tỉ lệ này và α(j, i) bằng 1; với một kết quả nghịch đảo nếu tỉ lệ này lớn hơn 1.) Do vậy, xích Markov là khả nghịch với xác suất dừng π(j) = b(j)/B . Hơn nữa, từ đẳng thức (??) ta thấy b(j)q(j, i) α(i, j) = min ,1 b(i)q(i, j) tức là để xác định xích Markov thì không cần biết giá trị của B mà chỉ cần biết các giá trị b(j), j ≥ 1 là đủ. Hơn nữa, thường thì π(j) không chỉ là xác suất dừng mà còn là xác suất giới hạn của xích Markov tìm được. Một điều kiện đủ để đảm bảo điều này là pi,i > 0 với mọi i. 19

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí

65 tài liệu

2418 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.