Đề tài Tạo số giả ngẫu nhiên, tạo biến ngẫu nhiên

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC KHOA CÔNG NGHỆ THÔNG TIN Tiểu luận học phần Mô phỏng ngẫu nhiên TẠO SỐ GIẢ NGẪU NHIÊN TẠO BIẾN NGẪU NHIÊN Giáo viên hướng dẫn: PGS.TS. Trần Lộc Hùng Học viên thực hiện: Nguyễn Thị Liệu Lớp KHMT Khóa 2008-2010 Huế, Tháng 06 năm 2009 TẠO SỐ GIẢ NGẪU NHIÊN TẠO BIẾN NGẪU NHIÊN Contents MỞ ĐẦU Số ngẫu nhiên theo cách hiểu thông thường là một số bất kỳ nào đó. Nhưng trong toán học, số ngẫu nhiên là: “số có khả năng xuất hiện tương đương nhau”. Tuy nhiên, trong từng phạm vi sử dụng nhất định mà phải giới hạn các số ngẫu nhiên được dùng. Chẳng hạn, không thể có một số nguyên ngẫu nhiên mà chỉ có một số nguyên ngẫu nhiên trong một miền xác định nào đó. Ngoài ra, trong nhiều trường hợp không chỉ cần một số ngẫu nhiên mà còn cần đến một hoặc nhiều dãy số ngẫu nhiên. Các số ngẫu nhiên rất hữu ích trong nhiều ứng dụng khác nhau. Trong thuật toán mật mã, thuật toán sử dụng các số ngẫu nhiên để mã hoá và giải mã thông tin, ví dụ thuật toán mã hoá khóa như RSA, Diffiel-Hellman, DES, 3DES, AES... Bên cạnh đó, các số ngẫu nhiên đóng vai trò quan trọng trong việc mô phỏng. Ngay cả khi không cần các số ngẫu nhiên, việc mô phỏng vẫn cần các số tùy ý dùng làm dữ liệu nhập, và điều này được cung cấp rất thuận lợi bởi các công cụ tạo số ngẫu nhiên. Việc tạo ra các số giả ngẫu nhiên có thể được coi là một mẫu mô phỏng của một phân phối cho trước. Kỹ thuật mẫu mô phỏng này được coi như là kỹ thuật Monte Carlo được sử dụng để giải quyết các bài toán trong lý thuyết xếp hàng, các bài toán cung ứng vật tư và các vấn đề liên quan đến xấp xỉ nghiệm phương trình vi phân, tích phân. CHƯƠNG I: TẠO SỐ GIẢ NGẪU NHIÊN GIỚI THIỆU Có rất nhiều phương pháp đáng tin cậy để sinh các số ngẫu nhiên cho việc mô phỏng ngẫu nhiên thông qua các bộ sinh số ngẫu nhiên với cơ sở toán học vững chắc. Chúng ta sẽ xem xét một số phương pháp tạo số ngẫu nhiên quan trọng. Một phương pháp chấp nhận được để tạo số giả ngẫu nhiên phải đạt được các yêu cầu sau: Các số được tạo ra phải tuân theo phân phối đều, bởi vì thực sự các sự kiện ngẫu nhiên đều tuân theo phân phối này. Vì vậy, bất cứ một sự mô phỏng các sự kiện ngẫu nhiên nào cũng tuân theo quy luật này hay ít nhất là xấp xỉ. Các số được tạo ra cần phải độc lập, nghĩa là giá trị của một số trong dãy số ngẫu nhiên không ảnh hưởng đến giá trị của số kế tiếp. Dãy số ngẫu nhiên được tạo ra cần phải tái tạo lại được. Điều này cho phép lặp lại thí nghiệm mô phỏng. Dãy số không được lặp lại đối với bất cứ chiều dài nào. Theo lý thuyết thì không thể có, nhưng vì mục đích thực tế thì khả năng lặp lại của một chu kỳ dài là phù hợp. Chu kỳ lặp lại của một bộ số ngẫu nhiên được gọi là giai đoạn của nó. Việc tạo các số ngẫu nhiên cần phải nhanh chóng vì trong các nghiên cứu mô phỏng, đòi hỏi cần có nhiều số ngẫu nhiên, nếu việc tạo các số diễn ra chậm thì có thể mất nhiều thời gian và tăng giá thành các nghiên cứu mô phỏng. Trong việc taọ số ngẫu nhiên nên sử dụng càng ít bộ nhớ càng tốt. Mô hình mô phỏng thường đòi hỏi bộ nhớ lớn, do bộ nhớ thường có hạn nên việc giảm tối đa việc chiếm dụng bộ nhớ trở nên rất cần thiết trong việc tạo ra số ngẫu nhiên. Chúng ta sẽ tìm hiểu một số phương pháp để tạo số ngẫu nhiên cơ bản. Dựa vào những phương pháp này, chúng ta sẽ tiếp tục trong chương tiếp theo để xem xét những phương pháp tạo những số ngẫu nhiên mà có một phân phối nhất định, như phân phối số mũ, phân phối chuẩn,... THUẬT TOÁN TẠO RA CÁC SỐ GIẢ NGẪU NHIÊN Phương pháp nửa bình phương Kỹ thuật nửa bình phương do John von Neuman phát triển vào những năm 40. Bắt đầu từ số đầu tiên cho trước, ta bình phương nó lên và số giữa của số bình phương này được dùng làm số thứ hai của dãy số. Kế tiếp, bình phương số thứ hai và lấy số giữa của số bình phương này làm số thứ ba cho dãy số. Quá trình cứ lặp lại tiếp tục như vậy. Ví dụ 1: Giả sử số đầu x0 = 25, khi đó các số ngẫu nhiên có 2 chữ số gồm (25)2 = 0625 x1 = 62. (62)2 = 3844 x2 = 84. (84)2 = 7056 x3 = 05. (05)2 = 0025 x4 = 02. (02)2 = 0004 x5 = 00. (00)2 = 0000 x6 = 00. Ví dụ 2: Giả sử số đầu x0 = 3187, khi đó các số ngẫu nhiên có 4 chữ số gồm (3187)2 = 10156969 x1 = 1569. (1569)2 = 02461761 x2 = 4617. (4617)2 = 21316689 x3 = 3166. (3166)2 = 10023556 x4 = 0235. (0235)2 = 00055225 x5 = 0552. (0552)2 = 00304704 x6 = 3047. (3047)2 = 09284209 x7 = 2842. Phương pháp nửa bình phương có một số tính chất sau: + Các dãy số được tạo ra có chu kỳ ngắn. + Bất kỳ lúc nào số 0 đều tạo ra các số bằng 0. (trường hợp ví dụ 1) Phương pháp đồng dư bậc hai Phương pháp này gần như tương đương với phương pháp nửa bình phương nhưng có chu kỳ dài hơn. Mối quan hệ phép đệ quy cho phương pháp này được xác định bởi: xn+1 = (xn(xn + 1)) mod m, với n ³ 0, xo mod 4 =2, m= 2k Ví dụ: Với x0 = 2, m = 16 và tạo dãy số ngẫu nhiên sử dụng phương pháp đồng dư bậc hai. x0 = 2 x1 = (x0(x0 + 1)) mod 16 = (2(2 + 1)) mod 16 = 6 x2 = (x1(x1 + 1)) mod 16 = (6(6 + 1)) mod 16 = 10 x3 = (x2(x2 + 1)) mod 16 = (10(10 + 1)) mod 16 = 14 x4 = (x3(x3 + 1)) mod 16 = (14(14 + 1)) mod 10 = 2 x5 = (x4(x4 + 1)) mod 16 = (2(2 + 1)) mod 10 = 6 x6 = (x5(x5 + 1)) mod 16 = (6(6 + 1)) mod 10 = 10 x7 = (x6(x6 + 1)) mod 16 = (10(10 + 1)) mod 10 = 14 x8 = (x7(x7 + 1)) mod 16 = (14(14 + 1)) mod 10 = 2 Dùng phần mềm R để tạo ra 50 số ngẫu nhiên theo phương pháp này ta có câu lệnh như sau: > x<-1 > for(j in 1:50){ + x[0]<-2 + x[j+1]<-(x[j]*(x[j]+1))%%16 + } > print(x) Ta có kết quả như sau: [1] 1 2 6 10 14 2 6 10 14 2 6 10 14 2 6 10 14 2 6 10 14 2 6 10 14 [26] 2 6 10 14 2 6 10 14 2 6 10 14 2 6 10 14 2 6 10 14 2 6 10 14 2 [51] 6 Phương pháp đồng dư bậc hai được sử dụng khi m là lũy thừa của 2, và có chu kỳ dài hơn phương pháp nửa bình phương. Phương pháp đồng dư tuyến tính Phương pháp đồng dư tuyến tính (Linear Congruential Generators – LCG) là phương pháp được sử dụng thông dụng nhất, được đưa ra đầu tiên bởi Lehmer. Trạng thái tại bước thứ n là một số nguyên xn và hàm chuyển T được định nghĩa như sau: xn = (a xn-1 +c ) mod m, n ≥ 0 trong đó: x0 là giá trị khởi đầu cho trước (0xom) a là hằng số nhân (0 a m). c là gia số (0cm). m là modul (m > 0). Chú ý : 1. Nếu a=1: phương pháp được gọi là phương pháp cộng. 2. Nếu c=0: phương pháp được gọi là phương pháp nhân (multiplicative congruential random number generator). 3. Nếu c0, phương pháp được gọi là phương pháp đồng dư hỗn tạp (mixed congruential random number generator). 4. Các LCG nhân (c=0) nhanh hơn các LCG hỗn tạp (c0) do chúng có ít phép toán cộng hơn. 5. Trong thực tế phương pháp nhân được dùng nhiều hơn phương pháp cộng. Bởi vì theo phương pháp này xi+1 được xác định bởi xi. Do (m+1) giá trị xo,x1,.., xm không thể phân biệt, nên có ít nhất một giá trị xuất hiện 2 lần, ví dụ như xi và xi+k Khi đó xi+k,…, xi+k-1 được lặp lại như xi+k,…, xi+2k-1 và như vậy dãy số xi tuần hoàn với chu kỳ k<=m. Toàn bộ chu kì m luôn có thể đạt được với a=c=1. Bên cạnh đó, sự lựa chọn các tham số a, c, m, xo rất quan trọng đối với chất lượng của bộ sinh. Nếu chúng không được chọn chính xác, bộ sinh có thể sẽ không có chu kỳ lớn nhất, hay các số được sinh ra có thể không thể hiện tính ngẫu nhiên tốt hay thậm chí bộ sinh có thể không thực hiện hiệu quả. Đối với bộ số nhân lớn nhất là m-1 và nếu khi 0 xảy ra thì nó sẽ lặp lại không xác định. 6. Thông thường, ta nên chọn m để làm cho toán tử modul có hiệu lực và sau đó chọn a và c để làm cho chu kỳ càng dài càng tốt. 7. Một chu kỳ đầy đủ (có độ dài m) có thể đạt được khi một số của điều kiện được thỏa mãn như trong định lý sau. Định lý : Một bộ sinh đệ quy có chu kỳ đầy đủ m khi và chỉ khi nó thỏa các điều kiện sau: (i). USCLN (c, m) = 1 (nghĩa là c và m luôn có ước số chung bằng 1). (ii). a º 1 mod p đối với mỗi ước nguyên tố p của m (nghĩa là mỗi ước số chung của m cũng là ước số chung của a-1 ). (iii). a º mod 4 nếu 4 chia hết cho m (nghĩa là, nếu m có bậc 4 thì 4 cũng là ước số của a - 1) . Định nghĩa: Nếu m là nguyên tố thì a là số nguyên thủy đầu tiên của modul m nếu và chỉ nếu an mod m 1 với n=1, 2, 3, …, m-2. Chú ý: 1. Nếu m là số nguyên tố thì chu kỳ đủ đạt được chỉ khi a = 1. 2. Ngay cả khi bộ sinh là chu kỳ đầy đủ vẫn không chắc chắn rằng các số được tạo ra là số ngẫu nhiên. Chẳng hạn, nếu a = 1, m = 1 và c = 3 thì các điều kiện trên đều thỏa mãn, nhưng với x0 = 0 toàn bộ dãy số được tạo ra là 4, 7, 10, 2, 5, 8, 0, 3, 6, 9, 1, 4, 7, ... chúng hầu như không phải là số ngẫu nhiên. 3. Việc lựa chọn hằng số nhân a ảnh hưởng đến độ lớn của chu kỳ và tính ngẫu nhiên của chuỗi được sinh ra. 4. Khi m= 2n và c>0: chu kỳ tối đa là m có thể đạt được khi và chỉ khi a mod 4 1 và c là số lẻ (thường được chọn bằng 1). Ví dụ, xét bộ sinh LCG (a, 1, 16, x0): chu kỳ tối đa là 16 có thể đạt được nếu và chỉ nếu a=1, 5, 9 hay 13. Khi a=3, hay 11 thì chu kỳ là 8; khi a=7 thì chu kỳ là 4; và khi a=5 thì chu kỳ là 2. Chẳng hạn chuỗi các số nguyên giả ngẫu nhiên sinh ra với LCG(5,1,16,1) là 1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 7, 4, 5, 10, 3, 0, 1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 5. Khi m=2n và c=0: chu kỳ tối đa là m/4 đạt được nếu và chỉ nếu a mod 8 1 hay a mod 8 5 (thường được chọn) và giá trị khởi đầu là số lẻ. Ví dụ, với bộ sinh LCG(a, 0, 16, x0), chu kỳ tối đa là 4 đạt được nếu và chỉ nếu a=3, 5, 11 hay 13. 6. Khi m là số nguyên tố và a>1 (không quan tâm đến c = 0 hay không): chu kỳ tối đa là m-1 đạt được khi và chỉ khi a là số nguyên thủy đầu tiên của modul m. Như vậy, tham số quan trọng nhất của một LCG là modul m. Kích thước của nó ràng buộc chu kỳ (m thường được chọn là số nguyên tố hoặc là lũy thừa của 2). Đối với các bộ sinh đồng dư tuyến tính với modul là số nguyên tố, việc sử dụng gia số c≠0 không tăng chu kỳ ngoại trừ khi a = 1. Thông thường, a phải lớn hơn 1 để chuỗi sinh ra có tính ngẫu nhiên. Ví dụ 1: Xét bộ sinh LCG (a, 0, 13, 1), xét về tính ngẫu nhiên của chuỗi được sinh ra, a=6 hoặc a=11 tốt hơn a=2 hay a=7 mặc dù chúng sinh ra chu kì đầy đủ. Người ta thường mong muốn các bộ sinh có chu kỳ đầy đủ hơn là các bộ sinh có chu kỳ ngắn. a Chuỗi kết quả {xn} Chu kỳ 0 0, 0,… 1 1 1, 1,.. 1 2 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1,… 12 3 1, 3, 9, 1 3 4 1, 4, 3, 12, 9, 10, 1,… 6 5 1, 5, 12, 8, 1 4 6 1, 6, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1,.. 12 7 1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1,… 12 8 1, 8, 12, 5, 1,.. 4 9 1, 9, 3, 1,… 3 10 1, 10, 9, 12, 3, 4, 1,.. 6 11 1, 11, 4, 5, 3, 7, 12, 2, 9, 8, 10, 6, 1 12 12 1, 12, 1,… 2 Đối với chu kỳ đầy đủ, các sự lựa chọn khác nhau của giá trị khởi đầu chỉ nhằm để chuyển sang điểm khởi đầu trong chuỗi đã xác định bởi a, c, m. Chẳng hạn như LCG(6, 0, 13, x0) là bộ sinh chu kỳ đầy đủ. Nếu giá trị khởi đầu xo =1, ta có chuỗi kết quả là 1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1,… Các giá trị khởi đầu giữa 1 và 12 không ảnh hưởng đến tính ngẫu nhiên của chuỗi mà chỉ chuyển điểm khởi đầu của chuỗi. Tuy nhiên nếu bộ sinh không phải có chu kỳ đầy đủ thì các giá trị khởi đầu khác nhau sẽ sinh ra các chuỗi kết quả khác nhau với các chu kỳ khác nhau. Ví dụ 2: Nếu một LCG không phải là bộ sinh chu kỳ đầy đủ, thì các giá trị khởi đầu xo có thể cho ra các chuỗi khác nhau và độ dài chu kỳ khác nhau. Chẳng hạn với LCG(3, 0, 16, xo) xo Chuỗi kết quả {xn} Chu kỳ 1, 3, 9 hoặc 11 …1, 3, 9, 11, 1,.. 4 5, 7, 13 hoặc 15 …5, 15, 13, 7, 5,… 4 2 hoặc 6 …2, 6, 2,… 2 4 hoặc 12 …4, 12, 4,… 2 10 hoặc 14 …10, 14,… 2 0 0, 0,… 1 8 8, 8,… 1 Phương pháp đồng dư cộng Phương pháp đồng dư cộng (Additive Congruential Generators) cũng tương tự phương pháp đồng dư tuyến tính, tuy nhiên ở đây phép toán xor trong công thức được thay thế bằng phép toán cộng: Xj=(Xj-1 +…+ Xj-n) mod m, Phương pháp này nhanh vì không cần phép nhân nào cả. Ngay cả khi chỉ dùng phép cộng số nguyên thông thường, vẫn có thể tạo được các số ngẫu nhiên tốt Ví dụ: x1 = 1, x2 = 2, x3 = 4, x4 = 8, x5 = 6 . x6 = (x5 + x1) mod 10 = (6+1) mod 10 = 7. x7 = (x6 + x2) mod 10 = (7+2) mod 10 = 9. x8 = (x7 + x3) mod 10 = (9+4) mod 10 = 3. x9 = (x8 + x4) mod 10 = (8+8) mod 10 = 1. x10 = (x9 + x5) mod 10 = (1+6) mod 10 = 7. x11 = (x10 + x6) mod 10 = (7+7) mod 10 = 4. x12 = (x11 + x7) mod 10 = (4+9) mod 10 = 3. x13 = (x12 + x8) mod 10 = (3+3) mod 10 = 6. x14 = (x13 + x9) mod 10 = (6+1) mod 10 = 7. x15 = (x14 + x10) mod 10 = (7+7) mod 10 = 4. Dùng phần mềm R ta có thể tạo 200 số ngẫu nhiên ta dùng câu lệnh như sau: > x<-1 > for(j in 6:200){ + x[1]<-1 + x[2]<-2 + x[3]<-4 + x[4]<-8 + x[5]<-6 + x[j]<-(x[j-1]+x[j-5])%%10 + } > print(x) Từ đó ta có kết quả như sau: [1] 1 2 4 8 6 7 9 3 1 7 4 3 6 7 4 8 1 7 4 8 6 7 4 8 6 2 9 3 1 7 9 8 [33] 1 2 9 8 6 7 9 8 6 2 9 8 6 2 4 3 1 7 9 3 6 7 4 3 6 2 9 3 6 2 4 3 [65] 6 2 4 8 1 7 9 3 1 2 9 8 1 2 4 3 1 2 4 8 1 2 4 8 6 7 9 3 1 7 4 3 [97] 6 7 4 8 1 7 4 8 6 7 4 8 6 2 9 3 1 7 9 8 1 2 9 8 6 7 9 8 6 2 9 8 [129] 6 2 4 3 1 7 9 3 6 7 4 3 6 2 9 3 6 2 4 3 6 2 4 8 1 7 9 3 1 2 9 8 [161] 1 2 4 3 1 2 4 8 1 2 4 8 6 7 9 3 1 7 4 3 6 7 4 8 1 7 4 8 6 7 4 8 [193] 6 2 9 3 1 7 9 8 CHƯƠNG II: TẠO BIẾN NGẪU NHIÊN 2.1 GIỚI THIỆU Trong chương này, ta bàn luận về kỹ thuật để phát sinh những số ngẫu nhiên với một phân phối đặc biệt. Những số ngẫu nhiên sau một phân phối đặc biệt được gọi random variates hoặc stochastic variates (những biến ngẫu nhiên). Biến ngẫu nhiên là một thuật ngữ được dùng trong toán học và thống kê. Trong một phép thử ngẫu nhiên (random experiment), đầu ra (outcome) của nó có thể là giá trị số hoặc không phải. Ví dụ phép thử ngẫu nhiên là tung một đồng xu lên và xét mặt nào của đồng xu ở phía trên, thì kết quả đầu ra có thể là {sấp, ngửa} (đầu ra không phải là số). Ví dụ phép thử ngẫu nhiên là tung con xúc sắc và xem mặt nằm phía trên là có mấy chấm, thì kết quả đầu ra có thể là {1,2,3,4,5,6} (đầu ra là số). Tuy nhiên, trong các ứng dụng của thống kê, người ta muốn mỗi đầu ra đều gắn với một đại lượng đo đạc được, hay còn gọi là thuộc tính có giá trị là số. Để thực hiện điều này, người ta định ra biến ngẫu nhiên để ánh xạ mỗi đầu ra của một phép thử ngẫu nhiên với một giá trị số. Biến ngẫu nhiên là một hàm toán học với đặc điểm: nó gán một giá trị bằng số cho kết quả (đầu ra) của một phép thử ngẫu nhiên (thực nghiệm). với ζ là đại diện cho đầu ra của một thực nghiệm, x là một số thực, X là hàm ánh xạ (hay là biến ngẫu nhiên). Vì thế, người ta còn gọi X là biến ngẫu nhiên giá trị thực (real-valued random variable). Có nhiều kỹ thuật để sinh những biến ngẫu nhiên. Phương pháp phép biến nghịch đảo là một trong số kỹ thuật thường sử dụng nhất. Ngoài ra có một số phương pháp để tạo biến ngẫu nhiên từ những phân phối lý thuyết liên tục và riêng biệt được xác định. CÁC PHƯƠNG PHÁP ĐỂ TẠO BIỄN NGẪU NHIÊN Phương pháp phép biến nghịch đảo Phương pháp này có thể áp dụng cho những trường hợp khi hàm mật độ tích lũy có thể đảo ngược phân tích. Giả thiết rằng ta muốn sinh những biến ngẫu nhiên từ một hàm mật độ xác suất (bdf) f(x). Giả sử F(x) là hàm mật độ tích lũy của nó. Chú ý F(x) được định nghĩa trong [0,1]. Xét thuộc tính này của hàm mật độ tích lũy để thu được máy phát những biến ngẫu nhiên đơn giản sau. Trước hết, sinh một số ngẫu nhiên r nào đó rồi thiết lập cho F(x), đó là F(x)=r. Số lượng x thu được bằng cách nghịch đảo F, đó là , ở đây chỉ phép biến đổi nghịch đảo của F. Trong khi một ví dụ, giả sử ta giả thiết muốn tạo biến ngẫu nhiên với mật độ xác suất tuân theo hàm f(x) = 2x, 0 <=x<= 1. Đồ thị biểu diễn hàm mật độ xác suất này trong hình 2.1a. Đầu tiên ta tính toán hàm mật độ F(x) tích lũy. Ta có Giả sử r là một số ngẫu nhiên. Khi đó, ta có r=x2 hoặc 0 1 x 1 f(x) 2 F(x) r 0 x 1 Hình 2.1a pdf f(x) Hình 2.1b Nghịch đảo của F(x) Nghịch đảo của đồ thị trong hình 2.1a sẽ thu được đồ thị trong hình 2.1b. Lấy mẫu từ những phân phối xác suất liên tục Chúng ta sẽ tìm hiểu cách sử dụng phương pháp biến nghịch đảo để phát sinh những biến ngẫu nhiên từ một phân phối đều, một phân phối mũ, và một phân phối Erlang. Ta cũng mô tả hai kỹ thuật để sinh những biến ngẫu nhiên từ phân phối chuẩn. Lấy mẫu từ phân phối đều Hàm mật độ xác xuất của phân phối đều được định nghĩa như sau: Và đồ thị biểu diễn: Hình 2.2 Phân phối đều Hàm mật độ tích luỹ Kỳ vọng và phương sai được xác định như sau: Phương pháp phép biến nghịch đảo để sinh những biến ngẫu nhiên: hoặc Lấy mẫu từ phân phối mũ Hàm mật độ xác suất phân phối mũ được định nghĩa như sau: F(x) = ae-ax, a > 0, x >= 0. Hàm mật độ tích lũy: Kỳ vọng và phương sai được xác định theo: Phương pháp phép biến nghịch đảo để sinh những biến ngẫu nhiên như sau: r=F(x)=1-e-ax hoặc 1-r =e-ax hoặc Từ phân phối 1 - F(x) không xác định trong [ 0,1], chúng ta có thể sử dụng thủ tục rút gọn sau: r=e-ax vì vậy Lấy mẫu từ một phân phối Erlang Một phân phối mũ có thể không đại diện một trạng thái trong thực tế. Chẳng hạn, thời gian thực hiện của một chương trình máy tính, hoặc thời gian mà nó dùng để sản xuất một thiết bị, có thể không phân phối mũ. Nó có thể được xác định, tuy nhiên, trong khi một số phân phối mũ cung cấp những vị trí liên tiếp. Nếu trung bình của tất cả dịch vụ riêng lẻ cũng như thế, thì toàn bộ thời gian dịch vụ đi theo một phân phối Erlang, như được đưa ra ở hình 3.3. Hình 2.3 Phân phối Erlang Phân phối Erlang là cuộn của k phân phối mũ có cùng tính chất 1/a. Một phân phối Erlang gồm có k phân phối mũ được tham chiếu tới như Ek. Kỳ vọng và phương sai của một biến ngẫu nhiên x được xác định theo phân phối Erlang: và Những biến ngẫu nhiên Erlang có thể được sinh ra bởi quá trình sinh đơn giản ngẫu nhiên trên về phân phối Erlang nào đó đặt cơ sở. Quá trình này có thể được hoàn thành bởi việc lấy tổng của k biến ngẫu nhiên phân phối mũ, x1, x2,..., xk với cùng điều kiện 1/a. Chúng ta có Lấy mẫu từ một phân phối chuẩn Một biến ngẫu nhiên X với hàm mật độ xác xuất Trong đó, >0 được xác định để có một phân phối chuẩn với những tham số và . Phương sai và kỳ vọng của X tương ứng là và . Nếu = 0 và = 1 thì phân phối chuẩn được xác định như sự phân bố bình thường chuẩn và hàm mật độ xác xuất của nó là Nếu một biến ngẫu nhiên X theo một phân phối chuẩn với trung bình và phương sai , thì là biến ngẫu nhiên Z được định nghĩa như sau: theo phân phối bình thường chuẩn. Để sinh những biến ngẫu nhiên từ một phân phối chuẩn với những tham số và , ta sử dụng định lý giới hạn trung tâm. Đặc biệt định lý giới hạn trung tâm phát biểu tóm tắt là nếu x1, x2,..., xn là n biến ngẫu nhiên độc lập, từng biến có cùng phân phối xác suất với E(Xi) = và Var(Xi) = , thì tổng = X1 + X2 +...+ Xn tiếp cận một phân phối chuẩn trong khi n lớn. Kỳ vọng và phương sai của phân phối chuẩn này: Thủ tục sinh những biến ngẫu nhiên bình thường yêu cầu k số ngẫu nhiên r1, r2,...,rk. Khi mỗi ri là một số ngẫu nhiên phân tán không xác định trong [0, 1], ta có: Sử dụng định lý giới hạn trung tâm, ta có tổng åri của k số ngẫu nhiên tiếp cận phân phối chuẩn là : hoặc (3.1) Bây giờ, ta xem xét phân phối chuẩn với những tham số và từ đó muốn sinh những biến ngẫu nhiên bình thường. Giả sử x là một biến ngẫu nhiên bình thường như vậy. Thì: (3.2) Cân bằng (3.1) và (3.2) ta có hoặc Phương trình này cung cấp cho ta một công thức đơn giản để sinh những biến ngẫu nhiên bình thường với trị một trung bình và độ lệch chuẩn . Giá trị k phải rất lớn, từ sự lớn hơn nó làm độ chính xác tốt hơn. Thông thường, phải cân bằng sự chính xác để mang lại hiệu quả. Giá trị nhỏ nhất cần thiết k = 10. Một cách tiếp cận thay thế để phát sinh những biến ngẫu nhiên bình thường (được biết như cách tiếp cận trực tiếp) sau đây. Giả sử r1 và r2 là hai số ngẫu nhiên độc lập phân bố không xác định. Thì là hai biến ngẫu nhiên phân phối chuẩn bình thường. Phương pháp này sinh những kết quả và tốc độ của những sự tính toán so sánh là tốt với cách tiếp cận giới hạn trung tâm để những hàm chương trình con đạt hiệu quả đặc biệt. Lấy mẫu từ những phân phối xác suất riêng biệt Trong phần này, ta sử dụng phương pháp phép biến đổi nghịch đảo để phát sinh những biến ngẫu nhiên từ một phân phối theo cấp số nhân. Đồng thời, mô tả một kỹ thuật lấy mẫu từ phân phối nhị thức, và một kỹ thuật lấy mẫu từ phân phối Poisson. Lấy mẫu từ phân phối theo cấp số nhân Xem xét một dãy những thử nghiệm độc lập nối tiếp nhau, kết quả của mỗi thử nghiệm hoặc là thất bại hoặc thành công. Giả sử p và q là xác suất thành công và thất bại tương ứng. Chúng ta có p + q = 1. Biến ngẫu nhiên xác định số lần thất bại liên tiếp xuất hiện trước khi thành công xuất hiện theo phân phối cấp số nhân. Hàm mật độ xác xuất của phân phối cấp số nhân là p(n) = pqn, n = 0,1,2,..., và mật độ xác xuất tích lũy của nó là Phương sai và kỳ vọng của biến ngẫu nhiên theo phân phối theo cấp số nhân là: Sinh những biến ngẫu nhiên hình học sử dụng phương pháp phép biến đổi nghịch đảo có thể được hình thành như sau. Từ biểu thức p = 1 - q, chúng ta có F(n) = 1 - qn+1. Từ biểu thức này chúng ta thu được 1 - F(n) = qn+1. Chúng ta quan sát 1 - F(n) biến đổi giữa 0 và 1. Bởi vậy, giả sử r la một biến ngẫu nhiên ta có r=qn+1 hoặc log(r)=(n+1)log(q) hoặc Cách khác, từ biểu thức (1-F(n))/q=qn và (1-F(n))/q biến đổi trong khoảng 0 và 1 r=qn hoặc Lấy mẫu từ một phân phối nhị thức Xét một thử nghiệm độc lập nối tiếp nhau (những thử nghiệm Bernoulli). Giả sử p xác suất của sự thành công và q = 1 - p xác suất của sự thất bại. Giả sử x một biến ngẫu nhiên chỉ số lượng phép thử thành công trong n những thử nghiệm. Thì, biến ngẫu nhiên này theo phân phối nhị thức. Hàm mật độ xác suất của x là: Kỳ vọng và phương sai được xác định E(X)=np Var(X)=npq Chúng ta có thể sinh những biến ngẫu nhiên từ một phân phối nhị thức với n và p đã cho như sau. Sinh n số ngẫu nhiên, sau đó đặt một biến k0 = 0. Cho mỗi số ngẫu nhiên ri, i = 1, 2,..., n, kiểm tra được thực hiện và biến ki được tăng lên như sau: Số lượng cuối cùng kn là biến ngẫu nhiên nhị thức. Phương pháp này sinh những biến ngẫu nhiên được biết như phương pháp loại trừ. Phương pháp này được bàn luận chi tiết bên dưới trong mục 6. Lấy mẫu từ phân phối Poisson Mô hình biến cố phân phối Poisson của một sự kiện đặc biệt trong một thời gian. Giả sử l là số lượng biến cố trung bình trong thời gian một đơn vị. Số lượng biến cố x trong một đơn vị thời gian có hàm mật độ xác suất sau: p(n)=e-l(ln/n!), n=0,1,2,… Nó có thể được biểu diễn qua thời gian giữa hai biến cố liên tiếp của sự kiện phân tán lũy thừa với trung bình 1/l, là f(t) =lelt. Một phương pháp để sinh những biến ngẫu nhiên Poisson theo phương thức lũy thừa trong những khoảng thời gian phân tán t1, t2, t3,... với một kỳ vọng bằng 1/l. Những khoảng này được tích lũy cho đến khi chúng lớn hơn 1 đơn vị chu kỳ thời gian. Như là: Biến ngẫu nhiên n đơn giản là số lượng sự kiện xuất hiện trong thời gian một đơn vị chu trình. Bây giờ, từ , n có thể thu được từ cộng thêm những số ngẫu nhiên cho đến khi tổng n +1 lớn hơn số lượng el. Điều đó, n được sinh ra từ biểu thức: Lấy mẫu từ phân phối xác suất thực nghiệm Phân phối xác suất thực nghiệm có thể thường xuyên không được xấp xỉ thỏa mãn bởi một trong những phân phối lý thuyết phổ biến. Trong trường hợp đó, nó bắt buộc sinh những biến ngẫu nhiên theo phân phối xác suất thực nghiệm đặc biệt này. Ở đây, ta đưa ra cách thức có thể lấy mẫu từ phân phối thực nghiệm riêng biệt hoặc một phân phối thực nghiệm liên tục. Lấy mẫu từ phân phối xác suất riêng biệt Giả sử x là biến ngẫu nhiên riêng biệt, và p(x = i) = pi, ở đây pi được tính toán từ dữ liệu thực nghiệm. Giả sử p(X ¬ i) = Pi là xác suất tích lũy. Những biến ngẫu nhiên từ phân phối xác suất này có thể dễ dàng được sinh như sau. Bây giờ giả sử r là một số ngẫu nhiên. Ta giả thiết r rơi giữa P2 và P3 (như hình 2.4). Biến ngẫu nhiên x = 3. Nói chung, nếu Pi - 1 < r < Pi thì x = i. Phương pháp này dựa vào việc pi = Pi - Pi-1 và từ r là một số ngẫu nhiên, nó sẽ rơi vào trong khoảng (Pi, Pi - 1) pi% thời gian. 1 . . . . P3 P2 P1 0 r 1 2 3 …… n x Hình 2.4: Lấy mẫu từ phân phối xác suất thực nghiệm riêng biệt. Trong một ví dụ, giả sử chúng ta xem xét vấn đề newsboy nổi tiếng. Giả sử X là số lượng tờ báo được bán bởi một newsboy mỗi ngày. Từ dữ liệu lịch sử chúng ta có phân phối sau cho X. X 1 2 3 4 5 F (X) 0.20 0.20 0.30 0.15 0.15 Phân phối xác suất tích luỹ X 1 2 3 4 5 f(X) 0.20 0.40 0.70 0.85 1 Sinh biến ngẫu nhiên có thể được tổng kết như sau: 1. Lấy mẫu số ngẫu nhiên r. 2. Định vị khoảng mà r rơi vào đó để xác định biến ngẫu nhiên x. • Nếu 0.85 < r <= 1.00 thì x = 5 • Nếu 0.70 < R <= 0.85 thì x = 4 • Nếu 0.40 < R <= 0.70 thì x = 3 • Nếu 0.20 < R <= 0.40 thì x = 2 • Trường hợp khác thì x = 1 Lấy mẫu từ phân phối xác suất liên tục Chúng ta giả thiết quan sát thực nghiệm của một biến ngẫu nhiên x có thể được tổng kết trong biểu đồ hình 2.5. Từ biểu đồ này, tập hợp những giá trị (xi, f(xi)) có thể thu được như sau: f(x2) x2 f(x3) x3 f(x4) x4 f(x5) x5 f(x6) x6 f(x7) x7 f(x1) x1 Hình 2.5: Biểu đồ biến ngẫu nhiên x Ở đây xi là điểm thứ i khoảng trung điểm của dãy, và f(xi) là chiều cao của hình chữ nhật thứ i. Sử dụng tập hợp những giá trị này chúng ta có thể xây dựng phân phối xác suất tích lũy xấp xỉ được đưa ra trong hình 2.6, ở đây . Phân phối tích luỹ được giả thiết để là tăng đều trong mỗi khoảng [F(xi - 1), F(xi)]. Hình 2.6 Phân phối tích luỹ Bây giờ, giả sử r là một số ngẫu nhiên và F(xi - 1)< r < F(xi), sử dụng đường nội suy, biến ngẫu nhiên x có thể thu được như sau: . Ở đây, xi là cực trị bên phải tại vị trí thứ i x 0 xn x4 x3 x2 x1 f(xn) f(x4) f(x3) f(x2) f(x1) f(x ) Hình 2.7 Hàm mật độ xác suất “Discretizing” 1 cf(x) a b Hình 2.8 Normalized Cách tiếp cận này có thể được sử dụng để sinh biến ngẫu nhiên từ phân phối xác suất liên tục f(x). Trước hết, thu được một tập hợp những giá trị (xi, f(xi)) như trong hình 2.7. Tập hợp giá trị này được sử dụng để thay cho hàm mật độ xác suất chính xác. (Nó được biết đến như hàm mật độ xác suất “Discretizing”). Sử dụng tập hợp giá trị này ta có thể tiếp tục xây dựng phân phối xác suất tích lũy và sau đó thu được những biến ngẫu nhiên như mô tả ở trên. Sự chính xác của cách tiếp cận này phụ thuộc vào cách thức chọn những điểm xi liên tiếp nhau: Phương pháp loại trừ (Rejection) Kỹ thuật loại trừ có thể sử dụng để phát sinh những biến ngẫu nhiên, nếu f(x) được giới hạn và x có một miền giá trị hữu hạn, ta nói a ≤ x ≤ b. Những bước sau có liên quan với nhau: • Chuẩn hóa miền giá trị của f(x) bởi một hệ số thang độ như vậy là cf(x) ≤ 1, a≤x≤b. (hình 2.8) • Xác định x như một hàm tuyến tính của r, như x = a + (b - a)r, r là một số ngẫu nhiên. • Sinh những cặp những số ngẫu nhiên (r1, r2). • Chấp nhận cặp và sử dụng x = a + (b - a)r1 như một biến ngẫu nhiên bất cứ khi nào mà cặp thỏa mãn mối quan hệ r2 ≤ cf(a + (b - a)r1), như những cặp (x,r2) dưới đường cong trong hình 2.8. Ý tưởng đằng sau cách tiếp cận này là xác suất xuất hiện r2 ít hơn hoặc bằng cf(x) như p[r2 ≤ cf(x)] = cf(x). Vậy nếu x được chọn ngẫu nhiên từ vùng (a,b) và sau đó loại bỏ r2 > cf(x), hàm mật độ xác suất của việc chấp nhận x’s sẽ chính xác. Chúng ta trình bày phương pháp loại trừ bởi việc đưa ra hai ví dụ khác nhau. Ví dụ đầu tiên giải quyết biến ngẫu nhiên tổng quát, và ví dụ thứ hai giải quyết vấn đề phép lấy tích phân bằng số. Ví dụ 1: Sử dụng phương pháp loại trừ để sinh những biến ngẫu nhiên với hàm mật độ xác suất f(x) = 2x, 0 ≤ x ≤ 1. Thủ tục này có thể là thủ tục được hoàn thành đang sử dụng sau đây: 1. Chọn c để df(x) = 1, là c = 1/2. 2. Sinh ra r1, và đặt x = r1. 3. Sinh r2. Nếu là r2< cf(r1) = (1/2)2r1= r1 thì chấp nhận r2, ngược lại trở lại bước 2. Ví dụ 2: Sử dụng phương pháp loại trừ để tính toán vùng của góc phần tư đầu tiên trong một vòng tròn đơn vị. Trước hết chúng ta chú ý rằng bất kỳ cặp số đồng dạng (r1, r2) nào được xác định trên khoảng đơn vị tương ứng tới bằng điểm bên trong hình vuông. Một cặp (r1,r2) trên đường tròn nếu r12+ r22 = 1. Phép lấy tích phân bằng số có thể được hình thành bởi việc thực hiện lặp lại nhiều lần hai bước sau đây: 1. Sinh một cặp số ngẫu nhiên (r1, r2). 2. Nếu r2 < f(r1), ở đây thì r2 ở dưới (hoặc trên) đường cong và từ đây cặp (r1,r2) được chấp nhận. Ngược lại, nó được loại bỏ. Diện tích dưới đường cong có thể thu được theo tỷ lệ Trong đó, s là diện tích dưới đường cong, NC là tổng số cặp chấp nhận, NT là tổng các cặp được sinh ra. Phương pháp loại trừ không mang lại hiệu quả cao khi c(b - a) trở thành rất lớn. Phương pháp của phối hợp có thể được sử dụng, bằng cách phân phối bị gãy trong những mảnh và những mảnh được lấy mẫu tỷ lệ với số lượng từng vùng phân phối chứa đựng. Quá trình này đồng nhất với phương pháp loại trừ cho mỗi mảnh của phân phối, cộng một mẫu dữ liệu thật. Phương pháp Monte Carlo Phương pháp Monte Carlo gồm có nhánh toán học thực nghiệm quan tâm đến những thí nghiệm về số ngẫu nhiên. Phương pháp Monte Carlo là những vấn đề thông thường liên quan đến lý thuyết lợi tức (interest). Không giống những kỹ thuật mô hình hóa trực tiếp, phương pháp Monte Carlo chưa được quan tâm với lối đi của thời gian. Mỗi tính toán Monte Carlo dẫn tới những kết quả định lượng có thể được xem như đánh giá giá trị của một tích phân bội. Phương pháp loại trừ trước đó được trình diễn để tính toán nguyên hàm là một ví dụ của Monte Carlo, nó được biết như hit-or-miss Monte Carlo. Một phương pháp thay thế để tính toán một nguyên hàm là phương pháp Monte Carlo thô (crude). Chúng ta hãy giả thiết rằng ta muốn tính toán một kích thước nguyên Giả sử là những số ngẫu nhiên giữa 0 và 1. thì những lượng fi=f(zi) độc lập ngẫu nhiên là những biến ngẫu nhiên với thời gian đợi q. Bởi vậy, là hàm đánh giá q, sự mâu thuẫn của nó có thể được đánh giá bằng sử dụng biểu thức Như vậy, sai số hiệu dụng của là . Kỹ thuật ước lượng ở trên việc dựa vào ý tưởng sau: Tổng quát, nếu x là một biến ngẫu nhiên có giá trị trong [0,1] và f(x) là một hàm của biến ngẫu nhiên này, thì Trong đó, g(x) là hàm mật độ của X. Giả thiết x là phân tán không xác định có giá trị trong (0,1), như g(x) = 1, ta có Như vậy, là một ước lượng không chệch của E(f(X)). Kỹ thuật này hiệu quả hơn kỹ thuật được đề cập trong mục trước. TÀI LIỆU THAM KHẢO [1] Trần Lộc Hùng, Bài giảng mô phỏng ngẫu nhiên. [2] Trần Lộc Hùng, Cơ sở mô phỏng ngẫu nhiên, nhà xuất bản giáo dục-1997. [3] Đào Hữu Hồ, Xác suất thống kê [4] Cao Hào Thi, Biến ngẫu nhiên và phân phối xác suất, Chương 5 [5] [6] [7]