Chương 1 Kiến thức chuẩn bị 1.1 Sự hội tụ của dãy đại lượng ngẫu nhiên Giả sử (Ω, F, P ) là không gian xác suất. Một dãy các đại lượng ngẫu nhiên hay biến ngẫu nhiên (Xn ) được gọi là hội tụ hầu chắc chắn đến biến ngẫu nhiên X nếu: P {ω ∈ Ω : lim Xn (ω) 6= X(ω)} = 0. n→∞ Ký hiệu là limn→∞ Xn = X(h. Cho dãy (Xn ) các biến ngẫu nhiên.
Fn (x), F (x) tương ứng là hàm phân phối của Xn , X. Gọi C(F ) là tập các điểm liên tục của hàm F. n→∞ d Ký hiệu là Xn → − X. Một dãy các biến ngẫu nhiên (Xn ) được gọi là hội tụ theo xác suất đến biến ngẫu nhiên X nếu ∀ε > 0 ta có : P {ω ∈ Ω : |Xn (ω) − X(ω)| > ε} = 0.
P Ký hiệu là Xn − → X. 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Định nghĩa 1. Một dãy các biến ngẫu nhiên (Xn ) được gọi là hội tụ theo trung bình bậc r đến biến ngẫu nhiên X nếu r ≥ 1, E|Xn |r < ∞ ∀n, E|X|r < ∞ và : lim E{|Xn − X|r } = 0. n→∞ r L Ký hiệu là Xn −→ X.
(luật số lớn) Cho dãy (Xn ) các biến ngẫu nhiên độc lập cùng phân phối, có cùng kỳ vọng EXi = µ (i = 1, 2,. Ta nói dãy (Xn ) tuân theo luật số lớn nếu Sn sẽ hội tụ theo xác suất đến µ. (định lý giới hạn trung tâm) Cho dãy (Xn ) các biến ngẫu nhiên độc lập cùng phân phối, có cùng kỳ vọng EXi = µ và phương sai √ n −nµ. Khi đó Zn sẽ hội tụ DXi = σ 2 (i = 1, 2, .+X σ n theo phân phối đến biến ngẫu nhiên Z có phân phối chuẩn tắc.2 Dãy mixingale Định nghĩa 1.
Cho dãy (Xn )n≥1 các biến ngẫu nhiên bình phương khả tích trong không gian xác suất (Ω, F, P ) và dãy (Fn )+∞ n=−∞ là dãy tăng các σ - đại số con của F. Khi đó, (Xn , Fn ) được gọi là dãy mixingale nếu với mọi dãy hằng không âm cn và ψm , trong đó ψm → 0 khi m → ∞, ta có: ||E(Xn |Fn−m )||2 ≤ ψm cn và ||Xn − E(Xn |Fn+m )||2 ≤ ψm+1 cn , với mọi n ≥ 1 và m ≥ 0. 41] Nếu {Xn , Fn } là một mixingale và {bn } là một dãy hằng dương tăng đến ∞ sao cho ∞ X b−2 2 n cn < ∞ và ψn = O(n −1/2 (logn)−2 ) khi n → ∞ n=1 Pn thì b−1 n i=1 Xi → 0(h. 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Các thuật toán mô phỏng cơ bản Các kết quả thống kê thường liên quan đến tích phân.
Nhắc lại rằng cả kỳ vọng và xác suất đều nhận được từ tích phân (hoặc tổng). Vì vậy, xét tích phân sau: Z 1 I= h(x)dx 0 Thông thường, người ta tiếp cận dạng tổng Riemann. Chúng ta đánh giá hàm h(x) tại n điểm (x(1) ,. n i=1 Tuy nhiên, trong nhiều trường hợp, việc xác định lấy các điểm (x(1) , ., x(n) ) là không thể hoặc chi phí quá tốn kém, người ta đã đưa ra một cách tiếp cận khác.
Đó là quá trình Monte Carlo. Chúng ta bắt đầu bằng việc viết lại tích phân như sau: Z 1 h(x) I= f (x)dx 0 f (x) trong đó f (x) là một mật độ trên [0, 1] sao cho nếu h(x) 6= 0 thì f (x) > 0. Nhưng điều này nghĩa là: I = Ef (h(X)/f (X)), trong đó Ef là ký hiệu của kỳ vọng đối với phân phối xác định bởi f. Bây giờ, chúng ta lấy mẫu độc lập cùng phân phối (x(1) ,.
n i=1 Luật số lớn cho ta thấy rằng Iˆn hội tụ với xác suất 1 tới tích phân I khi n tiến tới ∞ nghĩa là Iˆn → I(h. Hơn nữa, định lý giới hạn trung tâm chỉ ra rằng q (Iˆn − I)/ V ar(Iˆn ) 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com xấp xỉ phân phối chuẩn. Vì vậy phương sai V ar(Iˆn ) cho ta biết về độ chính xác ước lượng của chúng ta và nó có thể được ước lượng như sau: n 1 X vn = (h(xj )/f (xj ) − Iˆn )2 .1 Phương pháp biến đổi nghịch đảo Định lí 1. Xét hàm phân phối lũy tích (cdf) F (x).
Gọi F −1 là nghịch đảo mở rộng của F , tức là: F −1 (u) = min{x ∈ S : F (x) ≥ u} u ∈ (0, 1] Gọi U là một biến ngẫu nhiên phân phối đều (0, 1) và đặt X = F −1 (U ), khi đó phân phối của X có cdf F (x). Bằng định nghĩa của nghịch đảo mở rộng và tính đơn điệu của F , ta có: P (X ≤ x) = P(F −1 (U ) ≤ x) = P (U ≤ F (x)) = F (x). Mô phỏng một biến ngẫu nhiên phân phối mũ với tham số λ. Một biến ngẫu nhiên có phân phối mũ với tham số λ có hàm phân phối là: F (x) = 1 − exp(−λx) với x ≥ 0.
λ Khi đó Y có phân phối mũ với tham số λ. Điều này có thể đơn giản hóa hơn bằng cách thừa nhận rằng 1 − U cũng là phân phối đều trên (0, 1) và vì thế 1 Y = − log(U ) λ có phân phối mũ với tham số λ. 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Mô phỏng biến ngẫu nhiên có phân phối Bernoulli (p) và biến ngẫu nhiên có phân phối nhị thức B(n, p) Cho U là một biến ngẫu nhiên phân phối đều (0, 1).
Nếu ta xét 1 nếu U < p X= 0 ngược lại thì X là biến ngẫu nhiên có phân phối Bernoulli với xác suất thành công p., Xn là một mẫu độc lập cùng phân phối Bernoulli(p). Khi đó Y = ni=1 Xi có phân phối nhị thức B(n, p). Mô phỏng biến ngẫu nhiên tuân theo phân phối hình học (p) Giả sử X nhận giá trị trong N và P(X = j) = pj. Khi đó: j X −1 F (u) = min{j ∈ N : u ≤ pi }.
i=1 Bây giờ, nếu X ∼ G(p) thì P(X > j) = (1 − p)j .2 Phương pháp loại bỏ Giả sử chúng ta muốn lấy mẫu X là một biến ngẫu nhiên liên tục với hàm mật độ f (x). Chúng ta không biết cách lấy mẫu từ X nhưng chúng ta biết cách lấy mẫu từ một biến ngẫu nhiên Y tương tự với hàm mật độ g(y). Gọi giá của f là supp(f ) = {x : f (x) > 0}. Nếu ta có supp(f ) ⊆ supp(g) 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com và f (x)/g(x) ≤ M ∀x thì ta có thể lấy mẫu từ Y để tạo ra mẫu cho X.
Chúng ta lặp lại các bước sau cho đến khi một mẫu được trả về. • Bước 1: Lấy mẫu Y = y từ g(y) và U = u từ phân phối đều U(0, 1). • Bước 2: Nếu u ≤ Mf g(y) (y) thì đặt X = y. Ngược lại, quay lại bước 1.
Phân phối của biến ngẫu nhiên X được lấy mẫu trong phương pháp loại bỏ như trên có mật độ f (x). Thật vây, ta có f (Y ) P(X ≤ x) = P Y ≤ x|U ≤ M g(Y ) f (Y ) P Y ≤ x, U ≤ M g(Y ) = . f (Y ) P U ≤ M g(Y ) Để tính được xác suất trên, ta cần biết mật độ chung của Y và U. Bởi tính độc lập nên: h(y, u) = g(y)1[0≤u≤1].
P U ≤ Mf g(Y (Y ) ) −∞ Có bao nhiêu lần lặp trong thuật toán chúng ta dùng đến? Trong mỗi lần 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com lặp, chúng ta tạo ra một mẫu với xác suất P(U ≤ Mf g(Y (Y ) 1 ) ) = M nên tổng số lần lặp tuân theo phân phối hình học với tham số 1/M. Do vậy trung bình cần số lần lặp là M. Chú ý sau đây: 1. Cận M nhỏ hơn thì thuật toán hiệu quả hơn trong tổng số lần lặp.
Vì vậy chúng ta nên tìm kiếm một mật độ g gần f. Nếu giá của f không bị chặn thì để có thể tìm thấy cận M , mật độ g cần có đuôi lớn hơn f. Giả sử chúng ta muốn lấy mẫu |X| trong đó X là biến ngẫu nhiên phân phối chuẩn tắc. Mật độ của |X| được cho bởi r 2 2 x f (x) = exp − với x ∈ R+.
π 2 Ta đã biết cách lấy mẫu một biến ngẫu nhiên phân phối mũ vì thế chúng ta chọn mật độ g là mật độ của một phân phối mũ với tham số 1. π q Từ đó, đặt M = 2e π dẫn đến (x − 1)2 f (x) = exp −. 2 • Bước 2: Nếu u ≤ exp − (y−1) 2 thì đặt X = y. Ngược lại, trở lại bước 1.
Xét một biến ngẫu nhiên Y với mật độ g(x) được xác định trên không gian trạng thái S. Bây giờ, giả sử A ⊂ S và chúng ta muốn lấy 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com mẫu biến ngẫu nhiên có điều kiện X = (Y |Y ∈ A) với không gian trạng thái A. Trong trường hợp này mẫu loại bỏ có thể hoàn thành bởi lấy mẫu lặp đi lặp lại X cho đến khi mẫu của chúng ta nằm trong A. Cụ thể hơn, X có mật độ f (x) = P(Yg(x) ∈A) với x ∈ A.
g(x) P(Y ∈ A) M g(x) Giả sử U có phân phối đều trên khoảng đơn vị. Khi đó 1 nếu Y ∈ A P(U ≤ f (Y )/M g(y)) = 0 nếu Y ∈ /A Vì vậy, trong thuật toán lấy mẫu loại bỏ tiêu chuẩn, chúng ta chấp nhận nếu Y ∈ A và ngược lại, chúng ta loại bỏ. Chúng ta không cần lấy mẫu U để đưa ra quyết định này. Nếu đánh giá mật độ mục tiêu f là tốn kém thì phương pháp loại bỏ có thể dùng máy điện toán ít tốn kém hơn.
Nếu thêm cận trên M g(x) trên mật độ mục tiêu f (x) thì chúng ta cũng có thể dễ dàng ước lượng cận dưới h(x). Vì thế gọi là thuật toán lấy mẫu loại bỏ hình bao, tiến hành như sau: 1. Giả sử Y = y từ g(y) và U = u từ phần phối đều U (0, 1). Chấp nhận nếu u ≤ h(y)/M g(y) và đặt X = y là một mẫu.
Ngược lại, đi đến bước 3. Chấp nhận nếu u ≤ f (y)/M g(y) và trả lại X = y là một mẫu.