Trình tạo số ngẫu nhiên. Trình tạo số ngẫu nhiên trực tuyến

Tất nhiên, bất cứ ai cố gắng tạo ra các số ngẫu nhiên bằng phương pháp số học đều đang sống trong tội lỗi.
- John von Neumann

Trình tạo trình tự

Trình tạo chuỗi

Trình kiểm tra hạn ngạch

Lỗi

Một thư viện đã được viết cho API này từ năm các lớp trong Java, trong đó tất cả các phương thức được mô tả ở trên được gọi ở dạng đơn giản và dễ hiểu.
// tung xúc xắc IntegerGenerator ig = new IntegerGenerator(); ig.generate(1, 6, 2); // xáo trộn các thẻ SequenceGenerator sg = new SequenceGenerator(); sg.generate(1, 52); // mật khẩu mới StringGenerator strg = new StringGenerator(); strg.generate(12, 1, true, true, true, true); // còn lại bao nhiêu bit QuotaChecker qc = new QuotaChecker(); qc.quota();

Đó dường như là tất cả. Trên github bạn có thể tải mã nguồn và lib với tên gốc tổ chức ngẫu nhiên(6 kilobyte).

Những con số đi cùng chúng ta khắp mọi nơi - số nhà và căn hộ, số điện thoại, ô tô, hộ chiếu, thẻ nhựa, ngày tháng, mật khẩu email. Chúng tôi tự mình chọn một số tổ hợp số, nhưng hầu hết chúng tôi có được một cách tình cờ. Không hề nhận ra điều đó, chúng ta sử dụng những con số được tạo ngẫu nhiên mỗi ngày. Nếu chúng tôi đưa ra mã PIN, thì mã thẻ tín dụng hoặc thẻ lương duy nhất sẽ được tạo bởi các hệ thống đáng tin cậy loại trừ quyền truy cập vào mật khẩu. Trình tạo số ngẫu nhiên cung cấp bảo mật trong các lĩnh vực yêu cầu tốc độ xử lý, bảo mật và tính độc lập của dữ liệu.

Quá trình tạo số giả ngẫu nhiên tuân theo một số luật nhất định và đã được sử dụng từ lâu, chẳng hạn như trong xổ số. Trong thời gian gần đây, việc quay số được thực hiện bằng máy xổ số hoặc lô. Hiện nay ở nhiều quốc gia, số trúng xổ số của bang được xác định chính xác bằng một tập hợp các số ngẫu nhiên được tạo ra.

Ưu điểm của phương pháp

Vì vậy, bộ tạo số ngẫu nhiên là một cơ chế hiện đại độc lập để xác định ngẫu nhiên các tổ hợp số. Sự độc đáo và hoàn hảo của phương pháp này nằm ở chỗ không thể có sự can thiệp từ bên ngoài vào quá trình này. Trình tạo là một tập hợp các chương trình được xây dựng, chẳng hạn như trên điốt nhiễu. Thiết bị tạo ra một luồng nhiễu ngẫu nhiên, các giá trị hiện tại được chuyển đổi thành số và dạng kết hợp.

Việc tạo số mang lại kết quả tức thì - phải mất vài giây để tạo kết hợp. Nếu nói về xổ số, người tham gia có thể biết ngay số vé có khớp với số trúng thưởng hay không. Điều này cho phép các cuộc vẽ được tổ chức thường xuyên như người tham gia muốn. Nhưng ưu điểm chính của phương pháp này là không thể đoán trước và không thể tính toán thuật toán chọn số.

Cách tạo số giả ngẫu nhiên

Trên thực tế, các số ngẫu nhiên không phải ngẫu nhiên - chuỗi bắt đầu từ một số nhất định và được tạo bằng thuật toán. Trình tạo số giả ngẫu nhiên (PRNG hoặc PRNG - trình tạo số giả ngẫu nhiên) là một thuật toán tạo ra một chuỗi các số dường như không liên quan, thường tuân theo phân phối đồng đều. Trong khoa học máy tính, số giả ngẫu nhiên được sử dụng trong nhiều ứng dụng: mật mã, mô hình mô phỏng, phương pháp Monte Carlo, v.v. Chất lượng của kết quả phụ thuộc vào đặc tính của PRNG.

Nguồn phát sinh có thể là nhiễu vật lý từ bức xạ vũ trụ đến nhiễu trong điện trở, nhưng những thiết bị như vậy hầu như không bao giờ được sử dụng trong các ứng dụng an ninh mạng. Các ứng dụng mật mã sử dụng các thuật toán đặc biệt để tạo ra các chuỗi không thể ngẫu nhiên về mặt thống kê. Tuy nhiên, một thuật toán được chọn đúng có thể tạo ra chuỗi số vượt qua hầu hết các bài kiểm tra tính ngẫu nhiên. Khoảng thời gian lặp lại trong các chuỗi như vậy lớn hơn khoảng thời gian làm việc để lấy số.

Nhiều bộ xử lý hiện đại chứa PRNG, chẳng hạn như RdRand. Thay vào đó, các tập hợp số ngẫu nhiên được tạo và xuất bản trong sổ ghi chép một lần (từ điển). Nguồn số trong trường hợp này bị hạn chế và không cung cấp bảo mật mạng hoàn chỉnh.

Lịch sử của PRNG

Nguyên mẫu của máy tạo số ngẫu nhiên có thể coi là trò chơi board game Senet, phổ biến ở Ai Cập cổ đại vào năm 3500 trước Công nguyên. Theo điều kiện, có hai người chơi tham gia, nước đi được xác định bằng cách ném bốn cây gậy dẹt màu đen và trắng - chúng là một loại PRNG thời bấy giờ. Các gậy được ném cùng lúc và điểm được tính: nếu một người ngã bên trắng thì được 1 điểm và một nước đi phụ, hai gậy trắng - hai điểm, v.v. Người chơi ném bốn cây gậy có mặt đen sẽ nhận được kết quả tối đa là năm điểm.

Ngày nay, máy tạo ERNIE đã được sử dụng nhiều năm ở Anh để rút thăm trúng thưởng. Có hai phương pháp chính để tạo số trúng thưởng: đồng dư tuyến tính và đồng dư cộng tính. Những phương pháp này và các phương pháp khác đều dựa trên nguyên tắc lựa chọn ngẫu nhiên và được cung cấp bởi phần mềm tạo ra các con số vô tận, không thể đoán được trình tự của chúng.

PRNG hoạt động liên tục, ví dụ như trong các máy đánh bạc. Theo luật pháp Mỹ, đây là điều kiện bắt buộc mà tất cả các nhà cung cấp phần mềm phải tuân thủ.

v.v. và được chủ tài khoản sử dụng để thu hút khán giả mới vào cộng đồng.

Kết quả của những lần rút thăm như vậy thường phụ thuộc vào sự may mắn của người dùng, vì người nhận giải thưởng được xác định ngẫu nhiên.

Để đưa ra quyết định này, các nhà tổ chức xổ số hầu như luôn sử dụng trình tạo số ngẫu nhiên trực tuyến hoặc cài đặt sẵn được phân phát miễn phí.

Sự lựa chọn

Thông thường, việc lựa chọn một máy phát điện như vậy có thể khó khăn vì chức năng của chúng khá khác nhau - đối với một số thì nó bị hạn chế đáng kể, đối với một số khác thì nó khá rộng.

Một số lượng khá lớn các dịch vụ như vậy đang được triển khai, nhưng khó khăn là chúng khác nhau về phạm vi.

Ví dụ: nhiều ứng dụng bị ràng buộc bởi chức năng của chúng với một mạng xã hội cụ thể (ví dụ: nhiều ứng dụng tạo chỉ hoạt động với các liên kết từ mạng xã hội này).

Các trình tạo đơn giản nhất chỉ cần xác định ngẫu nhiên một số trong một phạm vi nhất định.

Điều này thuận tiện vì nó không liên kết kết quả với một bài đăng cụ thể, có nghĩa là nó có thể được sử dụng để rút thăm trúng thưởng bên ngoài mạng xã hội và trong nhiều tình huống khác.

Về cơ bản chúng không có công dụng nào khác.

Khuyên bảo! Khi chọn máy phát điện phù hợp nhất, điều quan trọng là phải xem xét nó sẽ được sử dụng vào mục đích gì.

Thông số kỹ thuật

Để có quá trình nhanh nhất trong việc chọn dịch vụ trực tuyến tối ưu để tạo số ngẫu nhiên, bảng bên dưới hiển thị các đặc tính kỹ thuật và chức năng chính của các ứng dụng đó.

Tất cả các ứng dụng được thảo luận trong bảng sẽ được mô tả chi tiết hơn dưới đây.

RandStuff

Bạn có thể sử dụng ứng dụng này trực tuyến bằng cách nhấp vào liên kết đến trang web chính thức của nó http://randstuff.ru/number/.

Đây là một trình tạo số ngẫu nhiên đơn giản, đặc trưng bởi hoạt động nhanh chóng và ổn định.

Nó được triển khai thành công cả ở định dạng của một ứng dụng độc lập riêng biệt trên trang web chính thức và dưới dạng ứng dụng ở định dạng .

Điểm đặc biệt của dịch vụ này là nó có thể chọn một số ngẫu nhiên từ một phạm vi được chỉ định và từ danh sách các số cụ thể có thể được chỉ định trên trang web.

• Công việc ổn định và nhanh chóng;
• Thiếu kết nối trực tiếp với mạng xã hội;
• Bạn có thể chọn một hoặc nhiều số;
• Bạn chỉ có thể chọn trong số các số được chỉ định.

Đánh giá của người dùng về ứng dụng này như sau: “Chúng tôi xác định người chiến thắng trong nhóm VKontakte thông qua dịch vụ này. Cảm ơn bạn”, “Bạn là người tuyệt vời nhất”, “Tôi chỉ sử dụng dịch vụ này.”

Bắt thăm

Ứng dụng này là một trình tạo chức năng đơn giản, được triển khai trên trang web chính thức dưới dạng ứng dụng VKontakte.

Ngoài ra còn có một tiện ích tạo để chèn vào trang web của bạn.

Sự khác biệt chính so với ứng dụng được mô tả trước đó là điều này cho phép bạn vô hiệu hóa tính năng lặp lại kết quả.

Lưu ý rằng lý tưởng nhất là đường cong mật độ phân bố số ngẫu nhiên sẽ trông như trong Hình 2. 22.3. Đó là, lý tưởng nhất là mỗi khoảng chứa cùng một số điểm: N Tôi = N/k , Ở đâu N tổng số điểm, k số khoảng, Tôi= 1, , k .

Cần nhớ rằng việc tạo số ngẫu nhiên tùy ý bao gồm hai giai đoạn:

• tạo số ngẫu nhiên được chuẩn hóa (nghĩa là phân bố đồng đều từ 0 đến 1);
• chuyển đổi số ngẫu nhiên chuẩn hóa r Tôiđến số ngẫu nhiên x Tôi, được phân phối theo luật phân phối (tùy ý) do người dùng yêu cầu hoặc trong khoảng thời gian được yêu cầu.

Trình tạo số ngẫu nhiên theo phương pháp lấy số được chia thành:

• thuộc vật chất;
• dạng bảng;
• thuật toán.

RNG vật lý

Một ví dụ về RNG vật lý có thể là: một đồng xu (“ngửa” 1, “sấp” 0); xúc xắc; một cái trống có mũi tên chia thành các ô có số; bộ tạo tiếng ồn phần cứng (HS), sử dụng một thiết bị nhiệt gây ồn, chẳng hạn như bóng bán dẫn (Hình 22.422.5).

RNG dạng bảng

RNG dạng bảng sử dụng các bảng được biên dịch đặc biệt chứa các số không tương quan đã được xác minh, tức là không phụ thuộc lẫn nhau, các số làm nguồn của các số ngẫu nhiên. Trong bảng Hình 22.1 cho thấy một phần nhỏ của bảng như vậy. Bằng cách duyệt bảng từ trái sang phải từ trên xuống dưới, bạn có thể thu được các số ngẫu nhiên phân bố đều từ 0 đến 1 với số chữ số thập phân cần thiết (trong ví dụ của chúng tôi, chúng tôi sử dụng ba chữ số thập phân cho mỗi số). Vì các số trong bảng không phụ thuộc vào nhau nên bảng có thể được duyệt theo nhiều cách khác nhau, chẳng hạn như từ trên xuống dưới hoặc từ phải sang trái hoặc bạn có thể chọn các số ở vị trí chẵn.

Ưu điểm của phương pháp này là nó tạo ra các số thực sự ngẫu nhiên vì bảng chứa các số không tương quan đã được xác minh. Nhược điểm của phương pháp: lưu trữ số lượng lớn chữ số đòi hỏi nhiều bộ nhớ; Có những khó khăn lớn trong việc tạo và kiểm tra loại bảng này; việc lặp lại khi sử dụng bảng không còn đảm bảo tính ngẫu nhiên của chuỗi số và do đó độ tin cậy của kết quả.

Có một bảng chứa 500 số được xác minh hoàn toàn ngẫu nhiên (lấy từ cuốn sách của I. G. Venetsky, V. I. Venetskaya “Các khái niệm và công thức toán học và thống kê cơ bản trong phân tích kinh tế”).

RNG thuật toán

Các số được tạo bởi các RNG này luôn là giả ngẫu nhiên (hoặc bán ngẫu nhiên), nghĩa là mỗi số tiếp theo được tạo phụ thuộc vào số trước đó:

r Tôi + 1 = f(r Tôi) .

Các chuỗi được tạo thành từ các số như vậy tạo thành các vòng lặp, nghĩa là nhất thiết phải có một chu trình lặp lại vô số lần. Chu kỳ lặp đi lặp lại được gọi là thời kỳ.

Ưu điểm của những RNG này là tốc độ của chúng; máy phát điện hầu như không cần tài nguyên bộ nhớ và nhỏ gọn. Nhược điểm: các số không thể được gọi hoàn toàn là ngẫu nhiên, vì có sự phụ thuộc giữa chúng, cũng như sự hiện diện của các dấu chấm trong chuỗi các số gần như ngẫu nhiên.

Hãy xem xét một số phương pháp thuật toán để thu được RNG:

• phương pháp bình phương trung vị;
• phương pháp sản phẩm trung gian;
• phương pháp khuấy;
• phương pháp đồng nhất tuyến tính.

Phương pháp trung bình

Có một số có bốn chữ số R 0 . Số này được bình phương và nhập vào R 1 . Tiếp theo từ R 1 là số ngẫu nhiên mới ở giữa (bốn chữ số ở giữa) và được ghi vào R 0 . Sau đó, quy trình được lặp lại (xem Hình 22.6). Lưu ý rằng trên thực tế, là một số ngẫu nhiên bạn cần lấy không ghij, MỘT 0.ghij với số 0 và dấu thập phân được thêm vào bên trái. Thực tế này được phản ánh như trong hình. 22.6 và trong các hình tương tự tiếp theo.

Nhược điểm của phương pháp: 1) nếu tại một số lần lặp lại số R 0 trở thành bằng 0, khi đó bộ tạo sẽ suy biến, vì vậy việc lựa chọn đúng giá trị ban đầu là rất quan trọng R 0 ; 2) trình tạo sẽ lặp lại trình tự thông qua M N các bước (tốt nhất), ở đâu N số chữ số R 0 , M cơ sở của hệ thống số.

Ví dụ trong hình. 22,6: nếu số R Số 0 sẽ được biểu diễn trong hệ số nhị phân, khi đó dãy số giả ngẫu nhiên sẽ được lặp lại theo 2 4 = 16 bước. Lưu ý rằng việc lặp lại trình tự có thể xảy ra sớm hơn nếu số bắt đầu được chọn không đúng.

Phương pháp được mô tả ở trên do John von Neumann đề xuất và có từ năm 1946. Vì phương pháp này tỏ ra không đáng tin cậy nên nó nhanh chóng bị bỏ rơi.

Phương pháp sản phẩm trung gian

Con số R 0 nhân với R 1, từ kết quả thu được R 2 phần giữa được trích xuất R 2 * (đây là một số ngẫu nhiên khác) và nhân với R 1 . Tất cả các số ngẫu nhiên tiếp theo được tính bằng sơ đồ này (xem Hình 22.7).

Phương pháp khuấy

Phương pháp xáo trộn sử dụng các thao tác để dịch chuyển nội dung của ô sang trái và phải theo chu kỳ. Ý tưởng của phương pháp này như sau. Để ô lưu trữ số ban đầu R 0 . Dịch chuyển nội dung ô sang trái theo chu kỳ 1/4 chiều dài ô, ta được số mới R 0 * . Theo cách tương tự, luân chuyển nội dung của ô R 0 ở bên phải bằng 1/4 chiều dài ô, ta được số thứ hai R 0**. Tổng các số R 0* và R 0** đưa ra một số ngẫu nhiên mới R 1 . Hơn nữa R 1 được nhập vào R 0 và toàn bộ chuỗi thao tác được lặp lại (xem Hình 22.8).

Xin lưu ý rằng số có được từ phép tính tổng R 0* và R 0 ** , có thể không vừa hoàn toàn trong ô R 1 . Trong trường hợp này, các chữ số thừa phải được loại bỏ khỏi số kết quả. Hãy để chúng tôi giải thích điều này trong hình. 22.8, trong đó tất cả các ô được biểu thị bằng tám chữ số nhị phân. Cho phép R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , Sau đó R 0 * + R 0 ** = 100110010 2 = 306 10 . Như bạn có thể thấy, số 306 chiếm 9 chữ số (trong hệ thống số nhị phân) và ô R 1 (giống như R 0) có thể chứa tối đa 8 bit. Vì vậy, trước khi nhập giá trị vào R 1, cần phải loại bỏ một bit “phụ”, bit ngoài cùng bên trái khỏi số 306, dẫn đến R 1 sẽ không còn chuyển sang 306 nữa mà chuyển sang 00110010 2 = 50 10 . Cũng lưu ý rằng trong các ngôn ngữ như Pascal, việc “cắt bớt” các bit thừa khi một ô tràn được thực hiện tự động theo loại biến đã chỉ định.

Phương pháp đồng nhất tuyến tính

Phương pháp đồng dư tuyến tính là một trong những phương pháp đơn giản và được sử dụng phổ biến nhất hiện nay để mô phỏng các số ngẫu nhiên. Phương pháp này sử dụng mod( x, y) , trả về số dư khi chia đối số thứ nhất cho đối số thứ hai. Mỗi số ngẫu nhiên tiếp theo được tính dựa trên số ngẫu nhiên trước đó bằng công thức sau:

r Tôi+ 1 = mod( k · r Tôi + b, M) .

Chuỗi số ngẫu nhiên thu được bằng công thức này được gọi là dãy đồng dạng tuyến tính. Nhiều tác giả gọi một chuỗi đồng dư tuyến tính khi b = 0 phương pháp đồng đẳng nhân, và khi b ≠ 0 — phương pháp đồng đẳng hỗn hợp.

Để có máy phát điện chất lượng cao cần lựa chọn hệ số phù hợp. Điều cần thiết là số M khá lớn, vì khoảng thời gian này không thể có nhiều hơn M các phần tử. Mặt khác, phép chia được sử dụng trong phương pháp này là một thao tác khá chậm, vì vậy đối với máy tính nhị phân, lựa chọn hợp lý sẽ là M = 2 N, vì trong trường hợp này, việc tìm phần dư của phép chia được rút gọn bên trong máy tính thành phép toán logic nhị phân “AND”. Việc chọn số nguyên tố lớn nhất cũng là điều bình thường M, dưới 2 N: trong tài liệu chuyên ngành đã chứng minh rằng trong trường hợp này các chữ số bậc thấp của số ngẫu nhiên thu được r Tôi+ 1 hoạt động ngẫu nhiên như những số cũ, điều này có tác động tích cực đến toàn bộ dãy số ngẫu nhiên. Ví dụ, một trong những số Mersenne, bằng 2 31 1, và do đó, M= 2 31 1 .

Một trong những yêu cầu đối với các chuỗi đồng dạng tuyến tính là độ dài chu kỳ càng dài càng tốt. Độ dài của khoảng thời gian phụ thuộc vào các giá trị M , k Và b. Định lý chúng tôi trình bày dưới đây cho phép chúng tôi xác định liệu có thể đạt được khoảng thời gian có độ dài tối đa cho các giá trị cụ thể hay không M , k Và b .

Định lý. Chuỗi đồng nhất tuyến tính được xác định bởi số M , k , b Và r 0, có một khoảng thời gian dài M nếu và chỉ nếu:

• con số b Và M Tương đối đơn giản;
• k 1 lần P cho mọi số nguyên tố P, đó là số chia M ;
• k 1 là bội số của 4 nếu M bội số của 4.

Cuối cùng, hãy kết thúc bằng một vài ví dụ về việc sử dụng phương pháp đồng dư tuyến tính để tạo số ngẫu nhiên.

Người ta xác định rằng một chuỗi số giả ngẫu nhiên được tạo dựa trên dữ liệu từ ví dụ 1 sẽ được lặp lại mỗi lần. M/4 số. Con số qđược đặt tùy ý trước khi bắt đầu tính toán, tuy nhiên, cần lưu ý rằng chuỗi này tạo ấn tượng là ngẫu nhiên nói chung k(và do đó q). Kết quả có thể được cải thiện phần nào nếu b kỳ quặc và k= 1 + 4 · q trong trường hợp này hàng sẽ được lặp lại mỗi M những con số. Sau một thời gian dài tìm kiếm k các nhà nghiên cứu đã giải quyết các giá trị 69069 và 71365.

Trình tạo số ngẫu nhiên sử dụng dữ liệu từ Ví dụ 2 sẽ tạo ra các số ngẫu nhiên, không lặp lại với chu kỳ 7 triệu.

Phương pháp nhân để tạo số giả ngẫu nhiên được D. H. Lehmer đề xuất vào năm 1949.

Kiểm tra chất lượng máy phát điện

Chất lượng của toàn bộ hệ thống và độ chính xác của kết quả phụ thuộc vào chất lượng của RNG. Do đó, chuỗi ngẫu nhiên do RNG tạo ra phải đáp ứng một số tiêu chí.

Việc kiểm tra được thực hiện có hai loại:

• kiểm tra tính đồng nhất của phân phối;
• kiểm tra tính độc lập thống kê.

Kiểm tra tính đồng nhất của phân phối

1) RNG phải tạo ra các giá trị gần với các giá trị sau của các tham số thống kê đặc trưng của luật ngẫu nhiên thống nhất:

2) Kiểm tra tần số

Kiểm tra tần số cho phép bạn tìm hiểu có bao nhiêu số nằm trong một khoảng (tôi r – σ r ; tôi r + σ r) , tức là (0,5 0,2887; 0,5 + 0,2887) hoặc cuối cùng là (0,2113; 0,7887). Vì 0,7887 0,2113 = 0,5774, chúng tôi kết luận rằng trong một RNG tốt, khoảng 57,7% tổng số ngẫu nhiên được rút sẽ rơi vào khoảng này (xem Hình 22.9).

Cũng cần lưu ý rằng số lượng các số rơi vào khoảng (0; 0,5) phải xấp xỉ bằng số lượng các số rơi vào khoảng (0,5; 1).

3) Kiểm định chi bình phương

Kiểm định chi bình phương (kiểm định χ 2) là một trong những kiểm định thống kê nổi tiếng nhất; nó là phương pháp chính được sử dụng kết hợp với các tiêu chí khác. Kiểm định chi bình phương được Karl Pearson đề xuất vào năm 1900. Công trình đáng chú ý của ông được coi là nền tảng của thống kê toán học hiện đại.

Trong trường hợp của chúng ta, việc kiểm tra bằng tiêu chí chi bình phương sẽ cho phép chúng ta tìm ra thực tế RNG gần với tiêu chuẩn RNG, tức là có đáp ứng yêu cầu phân phối đồng đều hay không.

Sơ đồ tần số thẩm quyền giải quyết RNG được hiển thị trong Hình. 22.10. Vì luật phân phối của RNG tham chiếu là đồng nhất nên xác suất (lý thuyết) P Tôiđưa số vào Tôi khoảng thứ (tổng số khoảng này k) bằng P Tôi = 1/k . Và do đó, trong mỗi k khoảng thời gian sẽ đạt trơn tru Qua P Tôi · N số ( N tổng số số được tạo ra).

RNG thực sự sẽ tạo ra các số được phân bổ (và không nhất thiết phải đồng đều!) k khoảng thời gian và mỗi khoảng thời gian sẽ chứa N Tôi số (tổng cộng N 1 + N 2 + + N k = N ). Làm cách nào chúng tôi có thể xác định RNG đang được thử nghiệm tốt như thế nào và nó gần với RNG tham chiếu đến mức nào? Khá hợp lý khi xem xét sự khác biệt bình phương giữa số lượng kết quả N Tôi và "tham khảo" P Tôi · N . Hãy cộng chúng lại và kết quả là:

χ 2 điểm kinh nghiệm. = ( N 1 P 1 · N) 2 + (N 2 P 2 · N) 2 + + ( N k – P k · N) 2 .

Từ công thức này, ta suy ra rằng sự khác biệt trong mỗi số hạng càng nhỏ (và do đó giá trị χ 2 exp. càng nhỏ), quy luật phân phối các số ngẫu nhiên do RNG thực tạo ra càng mạnh thì có xu hướng đồng nhất.

Trong biểu thức trước, mỗi thuật ngữ được gán cùng trọng số (bằng 1), điều này trên thực tế có thể không đúng; do đó, đối với thống kê chi bình phương, cần phải chuẩn hóa từng Tôi số hạng thứ, chia nó cho P Tôi · N :

Cuối cùng, hãy viết biểu thức thu được gọn gàng hơn và đơn giản hóa nó:

Chúng tôi đã thu được giá trị kiểm tra chi bình phương cho thực nghiệm dữ liệu.

Trong bảng 22,2 được đưa ra lý thuyết giá trị chi bình phương ​​(χ 2 lý thuyết), trong đó ν = N 1 là số bậc tự do, Pđây là mức độ tin cậy do người dùng chỉ định cho biết mức độ RNG phải đáp ứng các yêu cầu phân phối đồng đều hoặc P — là xác suất để giá trị thực nghiệm của χ 2 exp. sẽ nhỏ hơn lý thuyết χ 2 được lập bảng (lý thuyết). hoặc bằng nó.

Được coi là chấp nhận được P từ 10% đến 90%.

Nếu χ 2 điểm kinh nghiệm. nhiều hơn lý thuyết χ 2. (đó là P lớn), thì máy phát điện không thỏa mãn yêu cầu phân bố đồng đều, vì các giá trị quan sát được N Tôiđi quá xa so với lý thuyết P Tôi · N và không thể được coi là ngẫu nhiên. Nói cách khác, khoảng tin cậy lớn như vậy được thiết lập nên các hạn chế về số lượng trở nên rất lỏng lẻo, các yêu cầu về số lượng trở nên yếu đi. Trong trường hợp này, sẽ có sai số tuyệt đối rất lớn.

Ngay cả D. Knuth trong cuốn sách “Nghệ thuật lập trình” cũng lưu ý rằng việc có χ 2 exp. Nói chung, nó cũng không tốt cho những người nhỏ, mặc dù thoạt nhìn điều này có vẻ tuyệt vời nếu xét về tính đồng nhất. Thật vậy, lấy một dãy số 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, 0,7, 0,8, 0,9, 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, chúng rất lý tưởng xét theo quan điểm về tính đồng nhất, và χ 2 điểm kinh nghiệm thực tế sẽ bằng 0, nhưng bạn khó có thể nhận ra chúng là ngẫu nhiên.

Nếu χ 2 điểm kinh nghiệm. nhỏ hơn nhiều so với lý thuyết χ 2. (đó là P nhỏ) thì máy phát điện không thỏa mãn yêu cầu phân bố đồng đều ngẫu nhiên, vì các giá trị quan sát được N Tôi quá gần với lý thuyết P Tôi · N và không thể được coi là ngẫu nhiên.

Nhưng nếu χ 2 exp. nằm trong một khoảng nhất định giữa hai giá trị của lý thuyết χ 2. , tương ứng, ví dụ, P= 25% và P= 50% thì có thể cho rằng các giá trị số ngẫu nhiên do cảm biến tạo ra là hoàn toàn ngẫu nhiên.

Ngoài ra, cần lưu ý rằng tất cả các giá trị P Tôi · N phải đủ lớn, ví dụ lớn hơn 5 (tìm thấy theo kinh nghiệm). Chỉ khi đó (với một mẫu thống kê đủ lớn) thì các điều kiện thí nghiệm mới được coi là thỏa đáng.

Vì vậy, thủ tục xác minh như sau.

Kiểm tra tính độc lập thống kê

1) Kiểm tra tần suất xuất hiện của các số trong dãy

Hãy xem một ví dụ. Số ngẫu nhiên 0,2463389991 bao gồm các chữ số 2463389991, và số 0,5467766618 bao gồm các chữ số 5467766618. Nối các dãy chữ số, chúng ta có: 24633899915467766618.

Rõ ràng là xác suất lý thuyết P Tôi sự mất mát Tôi Chữ số thứ (từ 0 đến 9) bằng 0,1.

2) Kiểm tra sự xuất hiện của dãy số giống nhau

Hãy ký hiệu bằng N L số dãy chữ số giống nhau trên một hàng dài L. Mọi thứ cần phải được kiểm tra L từ 1 đến tôi, Ở đâu tôiđây là số do người dùng chỉ định: số lượng tối đa các chữ số giống nhau trong một chuỗi.

Trong ví dụ “24633899915467766618” đã tìm thấy 2 chuỗi có độ dài 2 (33 và 77), tức là N 2 = 2 và 2 dãy có độ dài 3 (999 và 666), tức là N 3 = 2 .

Xác suất xuất hiện của một chuỗi dài L bằng: P L= 9 10 L (lý thuyết). Nghĩa là, xác suất xuất hiện của một chuỗi dài một ký tự bằng: P 1 = 0,9 (lý thuyết). Xác suất để dãy có hai ký tự xuất hiện là: P 2 = 0,09 (lý thuyết). Xác suất để dãy 3 ký tự xuất hiện là: P 3 = 0,009 (lý thuyết).

Ví dụ: xác suất xuất hiện của một chuỗi dài một ký tự là P L= 0,9, vì chỉ có thể có một ký hiệu trong số 10 ký hiệu và có tổng cộng 9 ký hiệu (không tính số 0). Và xác suất để hai ký hiệu “XX” giống hệt nhau xuất hiện liên tiếp là 0,1 · 0,1 · 9, tức là xác suất 0,1 để ký hiệu “X” xuất hiện ở vị trí đầu tiên được nhân với xác suất 0,1 mà ký hiệu “X” xuất hiện ở vị trí đầu tiên. biểu tượng tương tự sẽ xuất hiện ở vị trí thứ hai “X” và nhân với số kết hợp như vậy 9.

Tần suất xuất hiện của chuỗi được tính bằng công thức chi bình phương mà chúng ta đã thảo luận trước đây bằng cách sử dụng các giá trị P L .

Lưu ý: Máy phát điện có thể được kiểm tra nhiều lần, nhưng các thử nghiệm không hoàn chỉnh và không đảm bảo rằng máy phát điện tạo ra các số ngẫu nhiên. Ví dụ: một trình tạo tạo ra chuỗi 12345678912345 sẽ được coi là lý tưởng trong quá trình thử nghiệm, điều này rõ ràng là không hoàn toàn đúng.

Để kết luận, chúng tôi lưu ý rằng chương thứ ba trong cuốn Nghệ thuật lập trình (Tập 2) của Donald E. Knuth hoàn toàn dành cho việc nghiên cứu các số ngẫu nhiên. Nó xem xét các phương pháp khác nhau để tạo số ngẫu nhiên, kiểm tra thống kê về tính ngẫu nhiên và chuyển đổi số ngẫu nhiên phân bố đồng đều sang các loại biến ngẫu nhiên khác. Hơn hai trăm trang được dành để trình bày tài liệu này.