Tiểu luận cơ sở mô phỏng 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 c