ĐẠ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....................................................................................................................................1
CHƯƠNG I: TẠO SỐ GIẢ NGẪU NHIÊN.............................................................................2
GIỚI THIỆU.........................................................................................................................2
THUẬT TOÁN TẠO RA CÁC SỐ GIẢ NGẪU NHIÊN...................................................2
Phương pháp nửa bình phương..........................................................................................2
Phương pháp đồng dư bậc hai............................................................................................3
Phương pháp đồng dư tuyến tính.......................................................................................4
Phương pháp đồng dư cộng................................................................................................7
CHƯƠNG II: TẠO BIẾN NGẪU NHIÊN................................................................................8
2.1 GIỚI THIỆU................................................................................................................8
2.2 CÁC PHƯƠNG PHÁP ĐỂ TẠO BIỄN NGẪU NHIÊN................................................8
2.2.1 Phương pháp phép biến nghịch đảo..........................................................................8
2.2.2Lấy mẫu từ những phân phối xác suất liên tục..........................................................9
2.2.3 Lấy mẫu từ những phân phối xác suất riêng biệt...................................................12
2.2.4 Lấy mẫu từ phân phối xác suất thực nghiệm ........................................................14
2.2.5 Phương pháp loại trừ (Rejection)...........................................................................17

2.2.6 Phương pháp Monte Carlo.....................................................................................18
TÀI LIỆU THAM KHẢO.......................................................................................................20
Tiếu luận môn học: Mô phỏng ngẫu nhiên
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.
Nguyễn Thị Liệu - Cao học KHMT 2008-2010 1
Tiếu luận môn học: Mô phỏng ngẫu nhiê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:

1. 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ỉ.
2. 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.
3. 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.
4. 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ó.
5. 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.
6. 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 x
0
= 25, khi đó các số ngẫu nhiên có 2 chữ số gồm
(25)
2
= 0625
⇒
x
1
= 62.
(62)
2
= 3844
⇒
x
2
= 84.
Nguyễn Thị Liệu - Cao học KHMT 2008-2010 2
Tiếu luận môn học: Mô phỏng ngẫu nhiên
(84)
2
= 7056
⇒
x
3
= 05.
(05)
2
= 0025
⇒

x
4
= 02.
(02)
2
= 0004
⇒
x
5
= 00.
(00)
2
= 0000
⇒
x
6
= 00.
Ví dụ 2:
Giả sử số đầu x
0
= 3187, khi đó các số ngẫu nhiên có 4 chữ số gồm
(3187)
2
= 10156969
⇒
x
1
= 1569.
(1569)
2

= 02461761
⇒
x
2
= 4617.
(4617)
2
= 21316689
⇒
x
3
= 3166.
(3166)
2
= 10023556
⇒
x
4
= 0235.
(0235)
2
= 00055225
⇒
x
5
= 0552.
(0552)
2
= 00304704
⇒

x
6
= 3047.
(3047)
2
= 09284209
⇒
x
7
= 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:
x
n+1
= (x
n
(x
n
+ 1)) mod m, với n
≥
0, x
o
mod 4 =2, m= 2
k
Ví dụ:

Với x
0
= 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.
x
0
= 2
x
1
= (x
0
(x
0
+ 1)) mod 16 = (2(2 + 1)) mod 16 = 6
x
2
= (x
1
(x
1
+ 1)) mod 16 = (6(6 + 1)) mod 16 = 10
x
3
= (x
2
(x
2
+ 1)) mod 16 = (10(10 + 1)) mod 16 = 14
x
4
= (x

3
(x
3
+ 1)) mod 16 = (14(14 + 1)) mod 10 = 2
x
5
= (x
4
(x
4
+ 1)) mod 16 = (2(2 + 1)) mod 10 = 6
x
6
= (x
5
(x
5
+ 1)) mod 16 = (6(6 + 1)) mod 10 = 10
x
7
= (x
6
(x
6
+ 1)) mod 16 = (10(10 + 1)) mod 10 = 14
x
8
= (x
7
(x

7
+ 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
Nguyễn Thị Liệu - Cao học KHMT 2008-2010 3
Tiếu luận môn học: Mô phỏng ngẫu nhiên
+ }
> 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 x
n
và hàm chuyển T được định nghĩa như sau:
x
n
= (a x
n-1
+c ) mod m, n ≥ 0
trong đó: x

0
là giá trị khởi đầu cho trước (0
≤
x
o
≤
m)
a là hằng số nhân (0
≤
a
≤
m).
c là gia số (0
≤
c
≤
m).
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 c
≠
0, 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 (c
≠
0) 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 x
i+1
được xác định bởi x
i
.

Do (m+1) giá trị x
o
,x
1
,.., x
m
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ư x
i
và x
i+k
Khi đó x
i+k
,…, x
i+k-1
được lặp lại như x
i+k
,…, x
i+2k-1
và như vậy dãy số x
i
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, x
o
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.
Nguyễn Thị Liệu - Cao học KHMT 2008-2010 4
Tiếu luận môn học: Mô phỏng ngẫu nhiên
Đị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 a
n
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 x
0
= 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= 2
n
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, x
0
): 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=2
n
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, x
0
), 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.
Nguyễn Thị Liệu - Cao học KHMT 2008-2010 5
Tiếu luận môn học: Mô phỏng ngẫu nhiên
Đố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, x
0
) là bộ sinh chu kỳ đầy đủ. Nếu giá trị khởi đầu x
o
=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 x
o
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, x
o

)
x
o
Chuỗi kết quả {x
n
} 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
Nguyễn Thị Liệu - Cao học KHMT 2008-2010 6
a Chuỗi kết quả {x
n
} 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