Tiểu luận Thuộc tính của chuỗi ngẫu nhiên

Phần 1. Mở đầu Trong hoạt động cuộc sống, nghiên cứu và học tập, chúng ta rất cần đến sự ngẫu nhiên của các đại lượng. Như chúng ta đã biết, có nhiều ứng dụng phải sử dụng số ngẫu nhiên. Một trong số đó là trong thuật toán mật mã, với mục đích chính là mã hóa một thông điệp để chỉ có người nhận mới được dùng chúng. Muốn vậy chúng ta phải làm cho thông điệp có vẻ như ngẫu nhiên bằng cách dùng một chuỗi giả ngẫu nhiên để mã hóa và cũng với chuỗi đó người nhận có thể giải mã được. Một lĩnh vực khác cũng được sử dụng rộng rãi các số ngẫu nhiên là mô phỏng. Một mô phỏng đặc trưng bao gồm một chương trình mô tả một số khía cạnh của thế giới thực. Các số ngẫu nhiên lại thích hợp làm dữ liệu nhập cho các chương trình như vậy. Ngay cả khi không cần các số ngẫu nhiên, mô phỏng vẫn cần các số tùy ý dùng làm dữ liệu nhập. Nhiều ứng dụng khi phân tích một số lượng lớn dữ liệu, đôi khi chỉ cần xử lý trên một tập con nhỏ của nó, khi đó chỉ cần lựa chọn theo kiểu thử ngẫu nhiên. Có nhiều phương pháp để sinh số ngẫu nhiên. Tiểu luận này sẽ đưa ra hai phương pháp có bản đó là phương pháp đồng dư tuyến tính và đồng dư cộng. Không thể dùng máy vi tính để sinh được chuỗi số ngẫu nhiên thực sự, chúng ta chỉ hy vọng tạo ra các chuỗi có nhiều thuộc tính giống như chuỗi số ngẫu nhiên. Các số này được gọi là các số giả ngẫu nhiên. Có nhiều phương pháp để kiểm tra xem một chuỗi giả ngẫu nhiên có một số thuộc tính của chuỗi ngẫu nhiên hay không. Tiểu luận sẽ trình bày một phương pháp kiểm tra cơ bản đó là phương pháp khi bình phương. Nội dung tiểu luận gồm ba phần: Phần 1: Đưa ra một số khái niệm về số ngẫu nhiên và số giả ngẫu nhiên. Phần 2: Giới thiệu ra hai phương pháp cơ bản để tạo số ngẫu nhiên: đó là phương pháp đồng dư tuyến tính và phương pháp đồng dư cộng. Phần 3: Trình bày một phương pháp khi bình phương nhằm kiểm tra tính ngẫu nhiên của chuỗi được sinh ra. Tiểu luận nhằm mục đích là giới thiệu các thuật toán và những kỹ thuật để dùng máy vi tính tạo số ngẫu nhiên và kiểm tra tính ngẫu nhiên của số được tạo. Để cài đặt cho những thuật toán trong tiểu luận này, chúng tôi sử dụng ngôn ngữ lập trình Pascal. Phần 2. Nội dung I/ Số ngẫu nhiên và số giả ngẫu nhiên Thông thường người ta dùng thuật ngữ ngẫu nhiên khi muốn nói đến một sự tùy ý. Một người yêu cầu một số ngẫu nhiên, nghĩa là không quan tâm đến giá trị của số đó. Tuy nhiên, số ngẫu nhiên là một khái niệm toán học được định nghĩa là mọi số đều có khả năng xuất hiện tương đương nhau. Để đáp ứng được định nghĩa số ngẫu nhiên trên, chúng ta phải giới hạn các số được dùng vào một phạm vi nhất định. 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 đó. Trong hầu hết các trường hợp ta không phải chỉ cần một số ngẫu nhiên, mà cần đến dãy số ngẫu nhiên. Khi đó cần phải chứng minh nhiều mặt về các thuộc tính của dãy số ngẫu nhiên. Ví dụ trong một chuỗi dài các số ngẫu nhiên của một phạm vi nhỏ, chúng ta có thể muốn biết số lần xuất hiện của các giá trị trong chuỗi. Không có cách nào để tạo ra các số ngẫu nhiên thực sự từ một máy vi tính. Bởi vì khi ta viết chương trình tạo số ngẫu nhiên thì các số mà chương trình tạo ra chắc chắn có thể suy luận được. Cách tốt nhất mà chúng ta hy vọng là viết các chương trình để tạo ra các chuỗi số có được nhiều thuộc tính giống như các số ngẫu nhiên. Các số này thường được gọi là các số giả ngẫu nhiên. Chúng không thật sự ngẫu nhiên nhưng chúng có thể hữu dụng như sự xấp xỉ của các số ngẫu nhiên. Tiểu luận này trình bày phương pháp tạo số ngẫu nhiên trên máy vi tính nên ở một mức độ nào đó, từ nay ta thống nhất số giả ngẫu nhiên với số ngẫu nhiên. Có nhiều phương pháp để sinh những chuỗi số như vậy. Chẳng hạn phương pháp đồng dư tuyến tính, phương pháp đồng dư cộng, phương pháp đồng dư toàn phương... Các phương pháp này phải đáp ứng được các yêu cầu sau: -Những số được sinh ra phải phân bố đều và độc lập về mặt thống kê. Giá trị của một số trong một chuỗi ngẫu nhiên không liên quan đến giá trị của số kế tiếp. Chuỗi phải không được lặp lại đối với bất kỳ độ dài nào. -Tốc độ sinh số ngẫu nhiên phải nhanh. Bởi vì trong quá trình một mô phỏng thực hiện thường yêu cầu một số lượng lớn các số ngẫu nhiên. Nếu công cụ sinh chậm thì chi phí thực hiện mô phỏng sẽ cao. -Thuật toán để sinh số ngẫu nhiên sử dụng càng ít bộ nhớ càng tốt. Bởi vì chương trình mô phỏng thường yêu cầu bộ nhớ lớn nhưng bộ nhớ thường bị giới hạn. Trong một số trường hợp, một số thuộc tính của các số ngẫu nhiên thì quan trọng trong khi các thuộc tính còn lại thì không cần thiết. Trong trường hợp đó, cần tạo ra các số gần ngẫu nhiên, chúng chắc chắn có các thuộc tính mong muốn nhưng chưa chắc có các thuộc tính khác. Trong một số ứng dụng, các số gần ngẫu nhiên có thể là thích hợp hơn các số giả ngẫu nhiên. Có nhiều phương pháp để kiểm tra xem một chuỗi giả ngẫu nhiên có một số thuộc tính của chuỗi ngẫu nhiên hay không. Chẳng hạn phương pháp kiểm tra số ngẫu nhiên theo luật phân phối đều, phân phối chuẩn, phân phối mũ.. Trong phần tiếp theo ta sẽ xem xét cụ thể hai phương pháp sinh số ngẫu nhiên và một phương pháp kiểm tra tính ngẫu nhiên của chuỗi được sinh. II/ Các phương pháp tạo số ngẫu nhiên Nhiều công trình nghiên cứu nhằm đưa ra các thuật toán sinh chuỗi số giả ngẫu nhiên. Thuật toán không chỉ khó trong kỹ thuật mà còn khó trong tốc độ sinh số ngẫu nhiên, độ dài vòng lặp, và tính chính xác của chương trình. Phần này giới thiệu hai phương pháp thông dụng là phương pháp đồng dư tuyến tính và phương pháp đồng dư cộng. 1/ Phương pháp đồng dư tuyến tính. Phương pháp đồng dư tuyến tính được D. Lehner đề xuất vào năm 1951. Đây là phương pháp nổi tiếng và rất thường được sử dụng để tạo số ngẫu nhiên. Phương pháp này được đặc trưng bởi công thức đệ quy sinh số thứ n+1 dựa trên số thứ n như sau: an+1=(b*an + c) mod m (n³0). Giá trị khởi đầu là hằng số a0, hằng số b là một số nhân, hằng số c là số gia và m là số chia (modulus). Sự lựa chọn những giá trị của những hằng số này có ảnh hưởng đến độ dài chu kỳ của chuỗi số ngẫu nhiên được sinh ra. Ta thấy, trong phương pháp này những số kế tiếp trong chuỗi được sinh ra bởi mối quan hệ đệ quy. Để tạo một số ngẫu nhiên mới, ta dùng số trước đó nhân với b, cộng thêm c, chia cho m và lấy phần dư. Như vậy số nhận được luôn nằm trong đoạn từ 0 đến m-1 Ví dụ 1: Cho b=2, c=3, m=10 và a0=0 thì ta có a0=0 a1=(2*0+3) mod 10=3 a2=(2*3+3) mod 10=9 a3=(2*9+3) mod 10=1 a4=(2*1+3) mod 10=5 a5=(2*5+3) mod 10=3 a6=(2*3+3) mod 10=9 a7=(2*9+3) mod 10=1 a8=(2*1+3) mod 10=5 Ví dụ 2: Cho b=2, c=0, m=10 và a0=1 thì ta có a0=1 a1=(2*1) mod 10=2 a2=(2*2) mod 10=4 a3=(2*4) mod 10=8 a4=(2*8) mod 10=6 a5=(2*6) mod 10=2 a6=(2*2) mod 10=4 a7=(2*4) mod 10=8 a8=(2*8) mod 10=6 Trong ví dụ 2 minh họa trường hợp trong đó c=0. Thuật toán này được gọi là phương pháp đồng dư nhân. Nếu cạ0 thuật toán được gọi là phương pháp đồng dư hỗn hợp. Cả hai ví dụ minh họa khả năng lặp lại của bất kỳ của chuỗi được sinh bởi lược đồ này. Thuật toán trên rất thích hợp khi sử dụng trong máy vi tính để tạo số ngẫu nhiên vì nó dễ cài đặt. Dưới đây là đoạn chương trình tạo ra N số ngẫu nhiên cho mảng A. Program tao_mang_ngau_nhien; type mmc=array[1..1000] of word; Var a:mmc; c,m,i:word; Begin c:=3; m:=10 a[0]:=0; for i:=1 to 100 do a[i]:=(a[i-1]*b+c) mod m; end. Để có được số ngẫu nhiên tốt, phải có cách chọn các hằng số a0, b và m. Nhiều tài liệu đã cung cấp một số hướng dẫn trong việc chọn các hằng số này. Trước hết m nên lớn, vì chu kỳ sẽ luôn luôn nhỏ hơn m nên khi m lớn thì sự lặp lại của các số sẽ ít hơn. m có thể là giá trị tối đa của một kiểu nguyên nhưng cũng không cần phải hoàn toàn lớn như vậy nếu không tiện. Thông thường, chọn m là lũy thừa của 10 hoặc 2 là thuận lợi trong việc tính toán đồng dư. Thứ hai là chọn b và c: Một chuỗi được sinh ra bởi sơ đồ đồng dư tuyến tính có chu kỳ m nếu và chỉ nếu: c là nguyên tố cùng nhau với m. b-1 là bội số của mọi số nguyên tố chia cho m. b-1 là bội của 4 nếu m là bội của 4. Những ràng buộc này dẫn đến những giá trị số nhân có dạng b=zp+1, trong đó z là cơ số được dùng trong biểu diễn số của máy tính, k là số lượng bít tối đa của kiểu nguyên, m=zk và zÊp<k. Như đối với sự lựa chọn của c, b phải thỏa mãn yêu cầu là nguyên tố cùng nhau với m. Theo tài liệu Algorithms, b nên là một hằng số tùy ý, không theo một mẫu riêng nào cả, ngoại trừ nó nên kết thúc bởi ....x21, với x chẵn. b không nên quá lớn hoặc quá nhỏ. Một sự lựa chọn an toàn là dùng một số ít hơn m một chữ số. Điều này giúp tránh được một số sự cố có thể xảy ra mà các phân tích toán học còn để hở. Thứ ba là chọn x0. Nếu chu kỳ của chuỗi là m, sự lựa chọn x0 là không quan trọng, vì toàn bộ chuỗi sẽ được sinh ra. Tuy nhiên cần chú ý khi chọn x0=0 và sử dụng phương pháp đồng dư nhân sẽ dẫn đến một chuỗi thoái hóa. Các quy luật nêu trên được phát triển bởi D. E. Knuth. Knuth chứng minh rằng các sự lựa chọn này làm cho phương pháp đồng dư tuyến tính tạo ra các số ngẫu nhiên tốt, thỏa mãn được nhiều kiểm tra thống kê phức tạp. Một tình huống xấu nhất là chuỗi số được sinh ra có chu kỳ nhỏ so với miền xác định của nó. Ví dụ như với b=19, m=381, a0=0 sẽ tạo ra chuỗi không ngẫu nhiên 0, 1, 20, 0, 1, 20,... trong khoảng từ 0 đến 380. Không phải dễ để nhận ra được các tình huống như trên. Vì vậy tốt nhất nên theo các chỉ dẫn của Knuth đưa ra để tránh được những trường hợp “xấu” mà ông đã tìm được. Khi các giá trị khởi động khác nhau thì tạo thành các chuỗi ngẫu nhiên khác nhau. Thường thì không cần phải lưu trữ cả chuỗi như chương trình nêu trên. Ngược lại, chúng ta chỉ cần lưu lại trong một biến toàn cục a, khởi động với một giá trị nào đó, rồi cập nhật bằng phép tính a:=(a*b+1) mod m. Trong Pascal, chúng ta còn một bước nữa mới có thể thực hiện được, bởi vì chúng ta không được phép bỏ qua tình trạng tràn số. Tràn số là một trường hợp lỗi mà có thể tạo ra các kết quả không dự đoán được. Giả sử máy tính có kiểu nguyên 32 bít và ta chọn m=100000000, b=31415821, a=1234567. Tất cả các giá trị này đều nhỏ hơn giá trị tối đa của kiểu số nguyên, nhưng phép toán nhân đã làm cho nó tràn a*b+1. Kết quả được tạo ra sẽ không có quan hệ với tính toán của chúng ta. Vì ta chỉ quan tâm đến 8 ký số sau cùng nên có một kỹ thuật để loại bỏ sự tràn là phân nhỏ phép nhân ra làm nhiều phần. Để nhân p và q, ta viết p=104p1+p0 q=104q1+q0. Do đó phép nhân được viết: p*q= (104p1+p0)*(104q1+q0)=104p1q1+104(p1q0+p0q1)+p0q0 Chúng ta chỉ muốn 8 ký số cho kết quả, vì thế có thể bỏ qua số hạng đầu tiên (104p1q1) và bỏ qua bốn ký số đầu tiên của số hạng thứ hai 104(p1q0+p0q1). Ta có chương trình như dưới đây Procedure tao_chuoi_ngau_nhien; const m=100000000; m1=10000;b=3141581; var i,a,N:integer; Function nhan(p,q:integer):integer; var p1,p0,q1,q0:integer; Begin p1:=p div m1; p0:=p mod m1; q1:=q div m1; q0:=q mod m1; nhan:=(((p0q1+p1q0) mod m1)*m1+p0q0) mod m; End; Function randomint:integer; Begin a:=(nhan(a,b)+1) mod m; randomint:=a; End; BEGIN readln(N,a); for i:=1 to N do write(random); Readln; END. Hàm nhan() trong chương trình này tính (p*q mod m) không bị tràn khi mà m nhỏ hơn 1/2 giá trị số nguyên tối đa. Khi chạy chương trình với dữ liệu nhập N=10 và q=124567 chương trình sẽ tạo được 10 số như sau: 35884508, 80001069, 63512650, 43635651, 1034472, 87181513, 6917174, 209855, 67115956, 59939877. Trong các số này, có sự không ngẫu nhiên: ví dụ, các ký số hàng đơn vị xoay vòng qua các ký số từ 0 đến 9. Dễ dàng chứng minh được điều này là do từ công thức. Nói chung các ký số bên phải không thật sự ngẫu nhiên. Đây là hạn chế cơ bản của phương pháp đồng dư tuyến tính để tạo số ngẫu nhiên. Để tạo một số nguyên ngẫu nhiên trong giới hạn [0,r-1], ta có thể thay hàm random() ở chương trình trên bởi hàm dưới đây: Function badrandom(r:integer):integer; begin a:=(nhan(b,a)+1) mod m badrandom:= a mod r end; Hàm này được đánh giá là không “tốt” vì các ký số không ngẫu nhiên bên phải là các ký số được sử dụng, nên chuỗi kết quả chỉ có được ít thuộc tính mong muốn. Vấn đề này có thể dễ dàng khắc phục bằng cách dùng các ký số bên trái thay thế. Hàm được viết lại là: Function newrandom(r:integer):integer; begin a:=(nhan(b,a)+1) mod m newrandom:= a*r div m end; Hàm trên cho ta một số nguyên ngẫu nhiên giữa 0 và r-1. Tuy nhiên tình huống tràn vẫn còn có thể xảy ra. Ta cải tiến lại hàm này như sau: Function randomint(r:integer):integer; Begin a:=(nhan(a,b)+1) mod m; randomint:=((a div m1)*r) div m1; End; Để tạo số thực ngẫu nhiên giữa 0 và 1, ta xem các số tạo như trên là phân thập phân với chấm thập phân ở bên trái. Điều này có thể cài được dễ dàng bằng cách trả về giá trị thực a/m thay vì số nguyên a. Hàm tạo số thực ngẫu nhiên giữa 0 và 1 được viết. Function randomreal:real; Begin a:=(nhan(a,b)+1) mod m; randomreal:=a/m; End; Khi đó người sử dụng có thể nhận được một số nguyên trong giới hạn [0,r) bằng cách đơn giản nhân giá trị này với r và cắt lấy phần nguyên của kết quả. Hay có thể nói một số thực ngẫu nhiên giữa 0 và 1 mới chính là số cần thiết. 2/ Phương pháp đồng dư cộng. Một phương pháp khác để tạo các số ngẫu nhiên là dựa trên “các thanh ghi dịch chuyển hồi tiếp tuyến tính” được sử dụng trên các máy mã hóa trước đây. ý tưởng bắt đầu với một thanh ghi chứa một mẫu tùy ý, sau đó chuyển sang phải một bước, bỏ vào các vị trí trống bên trái bằng một bít được xác định bằng cách XOR của hai bít phải nhất của thanh ghi đó. Một thanh ghi dịch chuyển hồi tiếp tuyến tính 4 bít Ví dụ: Nếu thanh ghi được khởi tạo là 1111 thì sau dịch chuyển, nội dung là 0111 (1 XOR 1=0), tiếp theo sẽ là 0011, 0001, 1000, 0100, 0010, 1001, 1100,0110, 1011, 0101, 1010, 1101, 1110, 1111. Khi chúng ta nhận lại mẫu khởi tạo, tiến trình hiển nhiên đã lặp lại. Chú ý rằng tất cả các mẫu bít có thể có đều xuất hiện: giá trị khởi đầu lặp lại sau 15 bước. Tuy nhiên, nếu ta thay đổi các vị trí các bít lấy ra dùng để tính giá trị cho hồi tiếp bên trái thì sẽ được một chuỗi hoàn toàn khác. Ví dụ, ta lấy bít 0 và 2 thay vì 0 và 1 như trên (thứ tự tính từ phải sang trái) thì chúng ta nhận được chuỗi 1111, 0111, 0011, 1001, 1100, 1110, 1111, không phải chu kỳ đầy đủ như trước. Thông thường với thanh ghi n bít, chúng ta có thể sắp xếp để chiều dài vòng lặp là 2n-1. Vì vậy, với giá trị n đủ lớn, các thanh ghi n bít tạo được chuỗi ngẫu nhiên khá tốt. Thông thường, chúng ta thường lấy n=31 hay n=63. Cũng như phương pháp đồng dư tuyến tính, các đặc tính toán học của các thanh ghi này đã được nghiên cứu nhằm đưa ra nhiều phương án lựa chọn vị trí lấy ra các bít để tính giá trị bít bên phải để tạo được tất cả các mẫu. Ví dụ với n=31, các vị trí rút ra có thể là 0 và một trong các vị trí: 4, 7, 8, 14, 19, 25, 26, hay 29. Một cách thực hiện khác là có thể tính toán một lần một một số nguyên thay vì mỗi lần một bít với phương pháp đệ quy như trên. Trong ví dụ trên nếu sử dụng phép toán XOR bit cho hai số kế tiếp, chúng ta tạo được một số sẽ xuất hiện tại ba vị trí sau đó trong danh sách. Điều này giúp ta có được một phương pháp tạo số ngẫu nhiên có thể dễ dàng áp dụng cho máy vi tính. Dùng thanh ghi dịch chuyển hồi tiếp với hai bít lấy ra tính toán là bít thứ b và thứ c, cũng giống như dùng công thức đệ quy sau: a[k]:=(a[k-b]+a[k-c]) mod m Để thích hợp với phương pháp thanh ghi dịch chuyển, phép toán cộng trong công thức này nên được thay thế bằng phép toán XOR trên bít. Tuy nhiên, điều này chứng tỏ rằng có thể tạo được các số ngẫu nhiên tốt ngay cả khi chỉ dùng phép cộng số nguyên thông thường mà thôi. Phương pháp này gọi là đồng dư cộng (additive congruential) Bít phải nhất của các số trong phương pháp này cũng giống như các bít trong thanh ghi dịch chuyển hồi tiếp tương ứng. Do đó số bước đạt được trước khi bắt đầu lặp lại, ít nhất cũng bằng chiều dài của chu kỳ lặp. Với phương pháp này các số ngẫu nhiên được tạo ra vượt qua được các kiểm tra thống kê. Để cài đặt chương trình tạo số ngẫu nhiên theo phương pháp đồng dư cộng, chúng ta cần giữ một bảng gồm c phần tử, luôn chứa c số được tạo ra gần nhất. Việc tính toán được tiếp tục bằng cách thay thế một trong các số trong bảng bằng tổng của hai số khác trong bảng. Khởi đầu, bảng nên gồm các số không lớn quá và cũng không nhỏ quá. Một cách đơn giản là dùng phương pháp đồng dư tuyến tính để sinh ra bảng này. Knuth khuyên nên chọn b=31, c=55. Khi đó chúng ta cần phải giữ lại 55 số được tạo gần nhất. Cấu trúc dữ liệu thích hợp là dùng hàng đợi, nhưng bởi vì kích thước của bảng cố định nên chúng ta chỉ dùng một mảng kích thước đó, với chỉ số xoay vòng như sau: Procedure randominit(s:integer); begin a[0]:=s;j:=0; repeat j:=j+1; a[j]:=(nhan(b,a[j-1])+1) mod m; until j=54; end; Function randomint(r:integer):integer; begin j:=(j+1) mod 55; a[j]:=a[(j+23) mod 55] + a[(j+54) mod 55]) mod m; randomint:=((a[j] div m1)*r) div m1; end; Biến toàn cục a được thay bằng một mảng và một con trỏ chỉ số j trên mảng. Dung lượng lớn của mảng a là một khuyết điểm của phương pháp này trong một số ứng dụng. Nhưng nó cũng chính là một ưu điểm, bởi vì nó làm cho chu kỳ lặp rất dài, ít nhất 255-1 ngay cả khi m nhỏ. Hàm randomint trả về một số nguyên giữa 0 và r-1. Và dĩ nhiên, chúng ta cũng có thể dễ dàng thay đổi như phần trước để trả về một số thực ngẫu nhiên giữa 0 và 1 bằng cách a[j]/m. Hàm randomint() được viết lại randomreal() như sau: Function randomreal:real; begin j:=(j+1) mod 55; a[j]:=a[(j+23) mod 55] + a[(j+54) mod 55]) mod m; randomreal:=a[j]/m; end; Ví dụ: Cho m=10, và mở rộng chuỗi 1, 2, 4, 8, 6 được sinh trong ví dụ trước. a1 = 1 a2 = 2 a3 = 4 a4 = 8 a5 = 6 a6 = (a5 + a1) mod 10 = (6+1) mod 10 =7 a7 = (a6 + a2) mod 10 = (7+2) mod 10 =9 a8 = (a7 + a3) mod 10 = (9+4) mod 10 =3 a9 = (a8 + a4) mod 10 = (3+8) mod 10 =1 a10 = (a9 +a5) mod 10 = (1+6) mod 10 =7 a11 = (a10 + a6) mod 10 = (7+7) mod 10 =4 a12 = (a11 + a7) mod 10 = (4+9) mod 10 =3 a13 = (a12 + a8) mod 10 = (3+3) mod 10 =6 a14 = (a13 + a9) mod 10 = (6+1) mod 10 =7 a15 = (a14 + a10) mod 10 = (7+7) mod 10 =4 a16 = (a15 + a11) mod 10 = (4+4) mod 10 =8 a17 = (a16 + a12) mod 10 = (8+3) mod 10 =1 a18 = (a17 + a13) mod 10 = (1+6) mod 10 =7 a19 = (a18 + a14) mod 10 = (7+7) mod 10 =4 a20 = (a19 + a15) mod 10 = (4+4) mod 10 =8 III/ Kiểm tra tính ngẫu nhiên bằng phương pháp “Khi bình phương”. Thường có thể dễ dàng nhận ra một chuỗi là không ngẫu nhiên, nhưng thật khó chứng minh rằng một chuỗi là ngẫu nhiên. Như đã đề cập trước đây, không có một chuỗi nào được tạo bằng máy vi tính có thể thực sự ngẫu nhiên, nhưng chúng ta có thể có được một chuỗi thể hiện nhiều đặc tính của các số ngẫu nhiên. Thực tế, thường không thể xác định chính xác thuộc tính nào của số ngẫu nhiên là quan trọng đối với một trình ứng dụng đặc biệt. Hơn nữa, lúc nào cũng nên nghĩ đến việc thực hiện một vài kiểu kiểm tra trên phương pháp tạo số ngẫu nhiên, để đảm bảo rằng không có trường hợp suy thoái xảy ra. Các phương pháp tạo số ngẫu nhiên có thể rất tốt nhưng cũng có khi rất xấu. Nhiều kiểm tra được triển khai để xác định một chuỗi có được nhiều thuộc tính của chuỗi ngẫu nhiên thực sự hay không. Hầu hết các kiểm tra này đều có cơ sở trong toán học. Trong số đó kiểm tra “khi-bình phương” là một kiểm tra thống kê cơ bản, dễ cài đặt và hữu dụng trong nhiều ứng dụng. ý tưởng của phương pháp khi bình phương là xem xét các số tạo ra có phân bố một cách hợp lý hay không. Nếu chúng ta tạo ra N số dương có giá trị nhỏ hơn r thì chúng ta mong muốn nhận được khoảng N/r số cho mỗi giá trị. Nhưng số lần xuất hiện của tất cả các giá trị cũng không được bằng nhau, vì nếu số lần xuất hiện của tất cả các giá trị bằng nhau thì không còn là ngẫu nhiên nữa. Điều này dẫn đến việc cần tính toán xem một chuỗi các số có được phân bố giống như một chuỗi ngẫu nhiên hay không bằng cách tính tổng số của bình phương số lần xuất hiện của mỗi giá trị, chia cho tần số mong muốn (N/r), rồi trừ bớt chiều dài chuỗi (N). Ta có chương trình kiểm tra tính ngẫu nhiên của chuỗi được sinh ra như sau: Function khi_binh_phuong(N,r,s:integer):real; var i,t:integer; f:array[0..rmax] of integer; begin raninit(s); for i:=0 to rmax do f[i]:=0; for i:=1 to n do begin t:=randomint(r); f[t]:=f[t]+1; end; t:=0; for i:=0 to r-1 do t:=t+f[i]*f[i]; Khi_binh_phuong:=((r*t/N)-N); end; Giá trị của hàm là giá trị thống kê khi bình phương và cũng có thể biểu diễn kết quả của công thức toán học sau: Với 0<i<r. Nếu giá trị thống kê khi bình phương “gần” với r thì các số đó là ngẫu nhiên, ngược lại, nếu nó “xa” r thì chúng không ngẫu nhiên. Đối với phương pháp kiểm tra đơn giản mà chúng ta đang thực hiện, giá trị thống kê chỉ nên lệch một khoảng 2 so với r. Điều này chỉ đúng nếu N lớn hơn 10r. Để đảm bảo chuỗi tạo ra là ngẫu nhiên, nên thực hiện kiểm tra nhiều lần. Phương pháp kiểm tra này cài đặt đơn giản nên thích hợp cho việc tích hợp nó vào bên trong mỗi chương trình tạo số ngẫu nhiên, nhằm đảm bảo rằng không có điều gì ngoài dự tính có thể gây ra các vấn đề nghiêm trọng. Tất cả các thuật toán “tốt” mà chúng ta đã thảo luận đều vượt qua được kiểm tra này. Sử dụng phương pháp tạo nêu trên cho 1000 số có giá trị nhỏ hơn 100, chúng ta có giá trị thống kê khi bình phương là 100.8 đối với phương pháp đồng dư tuyến tính và 105.4 đối với phương pháp đồng dư cộng. Cả hai phương pháp đều đạt trong vùng lệch 20 so với 100 (tức là trong [80,120]). Phần 3. Kết luận Như chúng ta đã biết, có nhiều phương pháp tạo số ngẫu nhiên. Tiểu luận đã trình bày kỹ thuật tạo số ngẫu nhiên bằng máy vi tính với hai phương pháp thông dụng là phương pháp đồng dư tuyến tính và phương pháp cộng. Có hai cách để lập trình sinh ra chuỗi ngẫu nhiên. Người ta thường tạo một hàm, khởi động nó, rồi gọi lặp lại nhiều lần, mỗi lần trả về một số ngẫu nhiên. Một cách khác là chỉ gọi một lần, và nó tạo ra dãy các số ngẫu nhiên cho trình ứng dụng. Trong cả hai trường hợp trên, người ta đều mong muốn nhận được các chuỗi giống nhau trong các lời gọi kế tiếp (để tìm lỗi hay so sánh các chương trình khác nhau trên cùng dữ liệu nhập) và tạo được một chuỗi tùy ý. Tất cả các điểm nêu trên đòi hỏi phải dùng đến trạng thái được giữ lại giữa các lời gọi của hàm tạo số ngẫu nhiên. Điều này có thể không thuận lợi trong một số môi trường lập trình. Phương pháp cộng bất lợi vì có một trạng thái khá lớn (mảng giữ các số nguyên vừa tạo) nhưng lại có một thuận lợi là có một chu kỳ dài, mà có thể không cần phải khởi tạo. Cho dù công cụ tạo số ngẫu nhiên tốt đến bao nhiêu đi nữa vẫn có thể sinh ra chuỗi không ngẫu nhiên hoặc không có nhiều thuộc tính ngẫu nhiên mong muốn. Vì vậy, cần phải xem xét cẩn thận các công cụ tạo số ngẫu nhiên bằng cách thực hiện nhiều loại kiểm tra thống kê, nếu không thì thì khó đảm bảo một phương pháp tạo số ngẫu nhiên là tốt. Tiểu luận đã trình bày được một phương pháp kiểm tra tính ngẫu nhiên của chuỗi được sinh ra, đó là phương pháp “khi bình phương”. Đây là một phương pháp kiểm tra khá chặt chẽ và dễ cài đặt. Ngoài ra, để có được công cụ tạo số ngẫu nhiên tốt thì cần phải dựa trên các phân tích toán học và nhiều kinh nghiệm thực tế. Một phương pháp được đề xuất nhằm tránh các sai lệch xảy ra trong thao tác tạo số ngẫu nhiên là kết hợp các phương pháp với nhau. Chẳng hạn dùng phương pháp đồng dư tuyến tính để tạo mảng ban đầu cho phương pháp đồng dư cộng. Lời kết: Để hoàn thành được đề tài này, ngoài sự nỗ lực và cố gắng của bản thân, tác giả đã nhận được sự giúp đỡ qúy báu của Quý Thầy, PGS.TS. Trần Lộc Hùng. Là một học viên chuyên ngành Tin học và dù rất tâm đắc với đề tài đang nghiên cứu nhưng với thời gian có hạn và khối lượng kiến thức của bản thân còn ít ỏi nên chắc chắn tiểu luận không tránh khỏi những hạn chế trong việc tiếp cận, nghiên cứu và trình bày. Tác giả xin kính trọng cảm ơn sự giúp đỡ quý báu của Quý Thầy và mong được đón nhận từ Quý Thầy sự góp ý để giúp tác giả có được hiểu biết đúng hơn đối với vấn đề đang nghiên cứu đồng thời mong được sự lượng thứ cho những sơ suất trong tiểu luận này. tài liệu tham khảo [1] Phạm Văn Khánh Lý thuyết mô phỏng đại lượng ngẫu nhiên và quá trình ngẫu nhiên [2] Robert Sedgewick Algorithms Addison-Wesley Publishing 2nd Edition [3] Các tài liệu về sinh số ngẫu nhiên: Generation of random numbers Mục lục Nội dung Trang Mở đầu ......................................................................................................................... .......................... 1 Nội dung ......................................................................................................................... ...................... 2 1-Số ngẫu nhiên và số giả ngẫu nhiên .......................................................................... 2 2-Các phương pháp tạo số ngẫu nhiên .......................................................................... 3 Phương pháp đồng dư tuyến tính .................................................................................. 3 Phương pháp đồng dư cộng ............................................................................................... 7 3-Kiểm tra tính ngẫu nhiên bằng phương pháp “khi bình phương” ...... 10 Kết luận ......................................................................................................................... .......................... 13 Tài liệu tham khảo ........................................................................................................................... 14 Kỷ thuật đồng dư cộng as hạt giống của nó, một chuỗi n số x1,x2,...,xn. Chuổi số này có thể được sinh ra từ mọt số kỷ thuật khác. ứng dụng của thuật toán này sẽ sinh ra một sự mở rộng thành chuổi xn+1, xn+2... Lớp của thuật toán này là xj=(xj-1+xj-n) mod m Thuận lợi chính của kỹ thuật này là tốc độ; không có sự nhân là cần thiết. Nó có thể dẫn đến chu kỳ lơn hơn m. Như Knuth đã đề cập, thuyết hành vi của kỹ thuật này là không được hiểu giống như hành vi của kỹ thuật đồng dư hỗn hợp. Do đó, việc xác nhận tính hợp lệ của bất kỳ chuỗi số được sinh bởi kỹ thuật này là cần thiết. Dễ thấy rằng việc làm cho gần đúng thuộc tính “mỗi số có khả năng xuất hiện như nhau” trong một chuỗi dài vẫn chưa đủ. Ví dụ, mỗi số trong đoạn [1,100] xuất hiện một lần trong chuỗi (1,2,...,100), nhưng chuỗi này không chắc là hữu dụng như một chuỗi gần tương đương chuỗi ngẫu nhiên. Trong thực tế, trong một chuỗi ngẫu nhiên gồm 100 số thuộc miền xác định [1,100] sẽ có một vài số sẽ xuất hiện hơn một lần và một vài số khác thì không có trong chuỗi. Nếu không đạt được điều này trong một chuỗi giả ngẫu nhiên thì nghĩa là đã có sai sót trong việc tạo chuỗi. Nhiều phương pháp kiểm tra dựa trên các nhận xét như vậy đã được áp dụng cho các phương pháp tạo chuỗi ngẫu nhiên nhằm kiểm tra xem một chuỗi số giả ngẫu nhiên có một số thuộc tính của chuỗi ngẫu nhiên hay không. Chúng ta cũng sẽ xem xét một trong các kiểm tra quan trọng nhất, đó là kiểm tra ‘khi bình phương” Chúng ta sẽ bàn kỹ về các số ngẫu nhiên phân phối đều, với các giá trị xem như tương đương nhau. Cũng tương tự cho các số ngẫu nhiên tuân theo các phân phối không đồng đều, với một số giá trị có nhiều hơn một số khác. Các số giả ngẫu nhiên với phương pháp phân phối không đồng đều thường bao gồm bởi thực hiện vài phân phối kiểu đồng đều tạo thành. Như chúng ta sẽ thấy, khó mà thuyết phục rằng các số ngẫu nhiên chúng ta tạo có tất cả các thuộc tính của số ngẫu nhiên. Đây cũng là một vấn đề quan trọng đối với các phương pháp phân phối khác. Trong nhiều mô phỏng những sự kiện xảy ra để xuất hiện ở ngẫu nhiên hoặc bao hàm thuộc tính mà giá trị phải được ấn định một ít ngẫu nhiên. Xảy ra này bởi vì hầu hết mô phỏng là dựa trên kiến thức được mô tả như mối quan hệ chung chung hoặc có liên quan đến lịch sử. Ví dụ, trong nhiều trường hợp khoảng thời gian của một sự kiện được kiết để rơi với một phạm vi náo đó. Mô phỏng của một sự kiện yêu cầu một giá trị đặc biệt được ấn định. Giả sử mô phỏng của một hệ thống máy tính general-purpose. Một sự kiện mà phải được mô hình là phục hồi của một bản ghi từ một thiết bị lưu trữ truy xuất trực tiếp. Khoảng thời gian của sự kiện này có thể được xác định dể rơi với một khoảng thời gian nào đó; giá trị thực sự, tuy nhiên, bị ảnh hưởng bởi những biến tình cờ, chẳng hạn vị trí của bản ghi liên quan với đầu đọc khi yêu cầu được thực hiện. Một ví dụ khác trong đó sự xuất hiện tình cờ to play a part là trong lan rộng sử dụng của sự quyết định logic trong mô phỏng. Ví dụ, mục đích rằng trong hoạt động hệ thống, một đường dẫn được cho được biết để đưa ra tỷ lệ nào đó của thời gian. Mô phỏng của một hệ thống yêu cầu một phương thức để chọn đường dẫn này trên những cái khác vì vậy hành vi của mô phỏng tương tự như của những hệ thống thực tế. Vì hầu hết trường hợp sự quyết định này là bất khả quyết, sự lựa chọn thông thường dựa trên mối quan hệ xác suất. Đối với những lý do này và khác, một đòi hỏi của hầu hết bất kỳ mô hình mô phỏng là một số phương tiện thuận lợi để sinh số ngẫu nhiên. Nó phải có khả năng để ấn định một giá trị cụ thể để có vẻ như những sự kiện ngẫu nhiên trên những hệ thống mô phỏng đã cho. Trong ví dụ trước của mô phỏng của hệ thống máy tính, nó phải được ấn định một giá trị cụ thể cho thời gian yêu cầu để tìm lại được một bản ghi từ một thiết bị lưu trữ truy xuất trực tiếp mỗi khi một yêu cầu tái tạo được nhận. Trong trường hợp của một khối quyết định nó phải là trược tiếp ... Số ngẫu nhiên là sự say mê và then chốt của mô phỏng. Tiêu biểu, tất cả tính chất ngẫu nhiên được yêu cầu bởi mô hình được mô phỏng bởi bộ số ngẫu nhiên cái mà dữ liệu ra của nó được giả sử là một chuỗi của sự độc lập và phân phối tương tự nhau U(0,1) nhưng giá trị ngẫu nhiên (nghĩa là những giá trị ngẫu nhiên liên tục phân bố đồng đều trên khoảng (0,1)). Những giá trị ngẫu nhiên này được biến đổi khi cần thiết để mô phỏng những giá trị khác nhau từ những phân bố xác suất khác nhau, chẳng hạn lũy thừa, Poisson, nhị thức, hình học, rời rạc đều,...cũng như Sinh biến ngẫu nhiên. 1/ Giới thiệu: Trong chương 4 sinh số ngẫu nhiên được thảo luận. Trong chương này, vì số ngẫu nhiên luôn luôn có nghĩa biến ngẫu nhiên đồng đều, biểu thị bởi RN(0,1), cái mà hàm phân phối của nó là FU(u)= (1) Do đó những số ngẫu nhiên là luôn luôn phân phối đều trên khoảng đơn vị (0,1). Sự sinh số ngẫu nhiên là một chủ đề quan trọng trong its own right. Ngược lại, sinh biến ngẫu nhiên luôn luôn liên quan với sự sinh ra những biến mà xác suất phân phối của nó là khác nhau mà của đồng đều trên khoảng (0,1). Vấn đề cơ bản là vì thế để sinh một biến ngẫu nhiên, X, mà hàm phân phối của nó là: F(x)=Pr(XÊx) (-Ơ<x<+Ơ) (2) được giả sử là hoàn toàn được biết, và khác với (1) Hầu hết các hệ thống máy tính lớn chứa những thư viện với sự thực hiện của những bộ sinh đối với những phân phối tầm thường hơn. Bộ sinh cũng biến thiên trong nhiều package thống kê và mô phỏng hiện tại cho máy tính cá nhân. Sự lựa chọn một bộ sinh thường có nhiều để làm với những thuộc tính của sự phân phối để được sử dụng, như với những thuộc tính của bản thân bộ sinh. Trong sự mô tả của những bộ sinh đã cho cụ thể dưới đây, nhấn mạnh vì vậy được cho để sự nằm dưới đặc điểm của phân phối được xem xét và trong mỗi quan hệ giữa phân phối khác nhau. Thông tin này sẽ là hữu ích trong sự giúp đỡ sự hiểu của những thuộctính của bộ sinh. Mục đích là để cho phép một sự lựa chọn được thực hiện, và thuật toán sẽ là không cần thiế để xem xét nhiều như là sự thực hiện một hộp đen. Thêm vào đó, nguyên lý chung và phương thức chung của sinh biến ngẫu nhiên được mo tả cái mà có thể sẽ reader để xây dựng bộ sinh cho phân phối không chuẩn. Bộ sinh biến ngẫu nhiên lúc nào cũng vậy sử dụng như điểm bắt đầu của chúng một bộ sinh số ngẫu nhiên cái mà làm ra RN(0,1) với phân phối đã cho bởi (1). Kỷ thuật là để biến đổi hoặc thực hiện một hoặc nhiều biến ngẫu nhiên đồng đều trong một số cách hiệu quả để thu được một biến với phân phối mong muốn (2). Trong chương này nó sẽ được giả sử rằng nguồn gốc của số ngẫu nhiên là có sẵn. Thêm vào đó, để là đồng đều, các số ngẫu nhiên cũng phải là độc lập lẫn nhau. Một vấn đề đầy ý nghĩa được thảo luận trong chương 4 là xây dựnh bộ sinh mà sản sinh ra số ngẫu nhiên mà có thể an toàn được xem xét như là độc lập. Nó được giả sử trong tiếp theo mà một bộ sinh như vậy đã có sẵn. Trong những cái dưới đây, nó được giả sử rằng một chuỗi số được sinh ra bởi một bộ sinh {U1, U2,} chạy nhập nhằng từ một chuỗi của biến phân phối độc lập RN(0,1) 1/Tính chính xác: Điề này liên quan với phân phối của những biến được sinh ra bởi bộ sinh. Bộ sinh được gọi là chính xác nếu phân phối của những biến được sinh có dạng chính xác mong muốn. Trong những ứng dụng nào đó trong đó phân phối chính xác là không critical, một phương thức có thể được chấp nhận cái mà có thể là tốt như những nhân tố khác được liên quan, nhưng ...... Nguyên tắc sinh Như đã đề cập trong 5.1, từ bây giờ trên nó được giả sử rằng một bộ sinh số số giả ngẫu nhiên là có sẵn mà sinh ra một chuỗi của những biến độc lập, với sự hiểu rằng mỗi lần hàm này được gọi, một biến RN(0,1) được trả về mà độc lập với tất cả các biến được sinh bởi lần gọi trước của hàm này. Khi X là một biến ngẫu nhiên phân phối liên tục, phân phối có thể được định nghĩa bằng hàm mật độ f(x). Hàm mật độ cho phép xác suất mà X nằm giữa hai giá trị đã cho a và b (a<b) được ước lượng là: Pr(aÊXÊb)= Từ sự định nghĩa của nó, (2), nó sẽ được xem rằng hàm phân bố trong trường hợp này có thể được ước lượng từ hàm mật độ là tích phân F(x)= Hàm phân phối là vì vậy tăng nghiêm ngặt và liên tục (hinhg 5.1). Trong trường hợp này, đối với bất kỳ 0<u<1, phương trình F(x)=u có thể được giải quyết để đưa ra một x duy nhất. Nếu (và đây là điều kiện tới hạn) nghịch đảo của hàm phân phối có thể được biểu diễn trong một dạng đơn giản, phương pháp này có thể được chứng tỏ (bao hàm) bằng cách viết phương trình trong một dạng tương đương x=F-1(u); vì vậy x được biểu diễn hàm hiện của u. Hàm F-1 này dược gọi là nghịch đảo của F. This yields phương pháp thuận lợi tiếp theo đối với sinh biến với hàm phân phối đã cho F... Phương pháp biến đổi nghịch đảo (trường hợp liên tục) Cho U=RN(0,1) Trả về X=F-1(U) Để chỉ ra rằng nó làm việc, tất cả những cái đòi hỏi đó là để xác minh rằng hàm phân phối của X quả thực là F (nghĩa là Pr(XÊx)=F(x)). Bây giờ Pr(XÊx)=Pr[F-1(U) Êx)]=Pr[UÊF(x)] Nhưng xác suất bên phải là hàm phân phối của một biến ngẫu nhiên đồng đều ước lượng tại giá trị F(x), và từ (1) đây là bằng với F(x), như đã quy định. Ví dụ được biết nhiều nhất và hữu dụng nhất là khi X là một biến ngẫu nhiên phân phối lũy thữa với a>0. hàm phân phối của nó là F(x)= (3) Giải u=F(x) đối với x trong trường hợp này nghiệm (yields) là x=F-1(u)=-a ln (1-u) (4) Mọt biến ngẫu nhiên vơi hàm phân phối (3) vì thế thu được bởi sử dụng công thức (4) để tính X, với u được sinh ra như một biến U(0,1) Phương pháp biến đổi nghịch đảo (trường hợp rời rạc) Cho U=RN(0,1) Cho i=1 While F(xi)<U do i:=i+1; Return X:=xi Bởi vì phương thức sử dụng một tìm kiếm tuyến tính, nó có thể không hiệu quả nếu n là lớn. Phương pháp hiệu quả hơn được mô tả như sau: Nếu một bảng các giá trị xi với sự tương ững những giá trị F(xi) được lưu, phương pháp cũng được gọi là table-lookup method. Phương pháp thực hiện thông qua bảng so sánh U với mỗi F(xi), và trả về, như X, xi đầu tiên được bắt gặp for which F(xi)³U.