Kiểm tra chất lượng của PRNGs

Question

Tôi đang chơi xung quanh với PRNG (như Mersenne Twister và rand() chức năng của stdlib) và tôi muốn thử nghiệm tốt sẽ giúp tôi xác định chất lượng dữ liệu ngẫu nhiên do PRNG tạo ra. Tôi đã tính toán giá trị của Pi bằng cách sử dụng các số ngẫu nhiên được tạo ra bởi các PRNG, và tôi thấy rand() và Mersenne Twister rất gần để đưa ra một sự phân biệt (tôi có cần phải xem xét kỹ sau 10 dấu thập phân không?).

Tôi không có nhiều ý tưởng về mô phỏng Monte Carlo; xin vui lòng cho tôi biết về một số thuật toán/ứng dụng (có thể một cái gì đó đơn giản nhưng có thể cung cấp suy luận tốt) sẽ giúp tôi phân biệt chúng về chất lượng.

---

EDIT 1: Tôi không để ý trước đây, nhưng có một sợi tương tự: How to test random numbers?

EDIT 2: tôi không thể để phiên dịch các kết quả của NIST, như đã đề cập trong một trong những ý kiến. Tôi có ý tưởng trực quan này giải thích mẫu (nếu có) từ random.org và sau đó là vì nó đơn giản. Tôi sẽ rất vui mừng nếu ai đó có thể nhận xét về quá trình thử nghiệm của tôi:

1. Tạo N randoms từ [0,1] sử dụng rand() và MT1997
2. nếu (round(genrand_real1()/rand_0_1())) điểm ảnh sau đó màu đỏ, khác màu đen

Vì tôi hiểu rằng đây không phải là giải pháp rất chính xác, nhưng nếu điều này cung cấp một ước tính hợp lý, thì tôi có thể sống với điều này tại thời điểm hiện tại.

Answer 1

Có hai bộ thử nghiệm tiêu chuẩn để thử nghiệm các số ngẫu nhiên.

1. NIST bộ kiểm tra. Họ có một số implementation in C.
2. Diehard Test Suite (do George Marsaglia phát triển). Có C library triển khai các thử nghiệm này.

Có giao diện R cho thư viện Dieharder, được gọi là RDieHarder. Thư viện này cung cấp một giao diện cho cả bộ kiểm tra NIST và Diehard.

Answer 2

Tốt nhất bạn nên xem xét volume 2 of the Knuth's series.

Để đọc ngắn hơn, hãy tìm chương tương ứng của Công thức số.

Nếu bạn chỉ quan tâm đến một loại đường cơ sở cho mô phỏng MC --- máy tạo đồng đẳng tuyến tính tốt nhất là tránh, Mersenne Twister là đủ tốt trong phần lớn các trường hợp.

Answer 3

Có một số bộ kiểm tra thống kê có sẵn.Tôi đã viết, sao chép, và nếu không quy tụ 120 PRNGs và thử nghiệm đều có một loạt các thử nghiệm dãy phòng cho 4 giờ mỗi PRNG mỗi thử nghiệm bộ:

• PractRand (tiêu chuẩn, 1 terabyte) tìm thấy thiên vị trong 78 PRNGs
• TestU01 (BigCrush) tìm thấy thiên vị trong 50 PRNGs
• RaBiGeTe (mở rộng, 512 megabit, x1) tìm thấy thiên vị trong vòng 40 PRNGs
• Dieharder (tùy chọn tùy chỉnh dòng lệnh) được tìm thấy thiên vị trong 25 PRNGs
• Dieharder (-a dòng lệnh tùy chọn) tìm thấy thiên vị trong 13 PRNGs
• NIST STS (mặc định, 64 megabit x128) tìm thấy thiên vị trong 11 PRNGs

Có bao nhiêu trong số đó là trong PRNGs rằng dãy phòng thử nghiệm khác đều bỏ lỡ?

• PractRand (tiêu chuẩn, 1 terabyte) tìm thấy 22 thành kiến ​​riêng biệt, trong nhiều danh mục khác nhau.
• RaBiGeTe (mở rộng, 512 megabit, x1) tìm thấy 5 thành kiến ​​riêng biệt, tất cả trong LCG và LCG kết hợp.
• TestU01 BigCrush tìm thấy 2 thành kiến ​​riêng biệt, cả trong PRNG hỗn độn nhỏ.
  Không có bộ thử nghiệm nào khác tìm thấy bất kỳ thành kiến ​​độc đáo nào.

Tóm lại, chỉ có PractRand, TestU01 và có thể RaBiGeTe đáng sử dụng.

Tiết lộ đầy đủ: Tôi đã viết PractRand, do đó, bộ PRNG hoặc bất kỳ biện pháp phi định tính nào khác đều có thể thiên về lợi ích của nó.

lợi thế khác:

• PractRand và TestU01 có xu hướng dễ nhất để giải thích kết quả của trong quan điểm của tôi.
• PractRand và Dieharder có xu hướng trở thành đơn giản nhất để tự động kiểm tra cho qua giao diện dòng lệnh tôi nghĩ.
• PractRand và RaBiGeTe là những người duy nhất hỗ trợ kiểm tra đa luồng.

nhược điểm khác:

• PractRand cần nhiều bit đầu vào để kiểm tra hơn dãy phòng thử nghiệm khác - có thể là một vấn đề nếu RNG của bạn là rất chậm hoặc bị hạn chế về số lượng dữ liệu sản xuất.
• RaBiGeTe và NIST STS đều có vấn đề về giao diện.
• Dieharder và NIST STS đều có vấn đề về dương tính giả.
• NIST STS có giao diện tồi tệ nhất theo ý kiến ​​của tôi.
• Tôi không thể lấy được Dieharder để biên dịch trên Windows. Tôi quản lý để có được TestU01 để biên dịch trên cửa sổ nhưng nó đã mất một số công việc.
• Phiên bản gần đây của RaBiGeTe là nguồn đóng và chỉ dành cho cửa sổ.

Tập hợp các PRNGs thử nghiệm: Tập PRNG gồm 1 lớn GFRS, 1 LFSR lớn, 4 xorshift loại PRNGs, 2 loại PRNGs xorwow, 3 khác không-khá-LFSR PRNGs. Nó bao gồm 10 mô-đun LCG công suất 2 mô-đun đơn giản (loại bỏ các bit thấp để đạt tới mức chất lượng chấp nhận được), 10 mô-đun không-hoàn-phi-LCG, và 9 máy phát điện kết hợp chủ yếu xung quanh LCG và LCG không hoàn toàn . Nó bao gồm 19 phiên bản CSPRNG giảm sức mạnh, cộng thêm một CSPRNG đầy đủ sức mạnh. Trong số đó, 14 được dựa trên các s-indirection/dynamic s-boxes (ví dụ RC4, ISAAC), bốn là tham số ChaCha/Salsa, và 2 còn lại là các biến thể Trivium. Nó bao gồm 11 PRNG được phân loại rộng rãi như kiểu LFib hoặc tương tự, không tính LFSRs/GFSR. Phần còn lại (khoảng 35) là các PRNG hỗn loạn nhà nước nhỏ, trong đó 10 phép nhân được sử dụng và các số khác được giới hạn trong logic số học và bitwise.

Chỉnh sửa: Ngoài ra còn có bộ kiểm tra trong gjrand, rất tối nghĩa và hơi kỳ quặc nhưng thực sự rất tốt.

Ngoài ra, tất cả các PRNG được kiểm tra đều được bao gồm dưới dạng PRNG không được khuyến nghị trong PractRand.