Menguji algoritma pembangkitan variate acak

Metode apa yang digunakan untuk menguji algoritma pembuatan variate acak?

The Diehard Test Suite adalah sesuatu yang dekat dengan Golden Standard untuk pengujian generator nomor acak. Ini mencakup sejumlah tes di mana generator bilangan acak yang baik harus menghasilkan hasil yang didistribusikan sesuai dengan beberapa distribusi tahu yang hasilnya dapat dibandingkan dengan menggunakan generator yang diuji.

EDIT

Saya harus memperbarui ini karena saya tidak benar: Diehard mungkin masih banyak digunakan, tetapi tidak lagi dipertahankan dan tidak canggih lagi. NIST telah datang dengan serangkaian tes yang ditingkatkan sejak itu.

Hanya untuk menambahkan sedikit pada jawaban klakson, Diehard Test Suite (dikembangkan oleh George Marsaglia) adalah tes standar untuk PRNG.

Ada perpustakaan Diehard C yang bagus yang memberi Anda akses ke tes-tes ini. Selain uji Diehard standar, tes ini juga menyediakan fungsi untuk beberapa tes PRNG lainnya yang melibatkan (antara lain) memeriksa urutan bit. Ada juga kemampuan untuk menguji kecepatan RNG dan menulis tes Anda sendiri.

Ada antarmuka R ke perpustakaan Dieharder, yang disebut RDieHarder :

library(RDieHarder)
dhtest = dieharder(rng="randu", test=10, psamples=100, seed=12345)
print(dhtest)

Diehard Count the 1s Test (byte)

       data:  Created by RNG `randu' with seed=12345, 
              sample of size 100 p-value < 2.2e-16

Ini menunjukkan bahwa generator RANDU RNG gagal dalam uji jarak-minimum / 2dsphere.

Untuk menguji angka-angka yang dihasilkan oleh generator angka acak, tes Diehard adalah pendekatan praktis. Tetapi tes-tes itu tampak agak arbitrer dan satu mungkin dibiarkan bertanya-tanya apakah lebih banyak harus dimasukkan atau jika ada cara untuk benar-benar memeriksa keacakan.

Kandidat terbaik untuk definisi urutan acak tampaknya adalah keacakan Martin-Lof . Gagasan utama untuk keacakan jenis ini, dikembangkan dengan indah di Knuth, bagian 3.5 , adalah untuk menguji keseragaman untuk semua jenis sub-urutan dari urutan angka acak. Mendapatkan bahwa semua jenis definisi urutan benar ternyata menjadi sangat sulit bahkan ketika seseorang menggunakan gagasan komputabilitas.

Tes Diehard hanyalah beberapa kemungkinan langkah yang dapat dipertimbangkan dan kegagalan mereka akan mengecualikan keacakan Martin-Lof.

Anda tidak dapat membuktikan, karena itu tidak mungkin; Anda hanya dapat memeriksa apakah tidak ada autokorelasi memalukan atau gangguan distribusi, dan memang Diehard adalah standar untuk itu. Ini untuk statistik / fisika, kriptografi juga akan memeriksa (antara lain) seberapa sulit untuk menyesuaikan generator dengan data untuk mendapatkan nilai masa depan.

Koreksi kecil pada posting Colin: paket CRAN RDieHarder adalah antarmuka untuk DieHarder , penulisan ulang / perluasan / perbaikan Diehard yang dilakukan oleh Robert G. Brown (yang dengan ramah mendaftarkan saya sebagai penulis pendamping berdasarkan pembungkus RDieHarder saya) dengan kontribusi baru-baru ini oleh David Bauer.

Antara lain, DieHarder termasuk baterai tes NIST yang disebutkan dalam posting Markus serta beberapa yang baru. Ini adalah penelitian yang sedang berlangsung dan telah berlangsung cukup lama. Saya memberi ceramah di useR! 2007 tentang RDieHarder yang bisa Anda dapatkan dari sini .

Jarang berguna untuk menyimpulkan bahwa ada sesuatu yang "acak" dalam abstrak. Lebih sering Anda ingin menguji apakah ia memiliki jenis struktur acak tertentu. Misalnya, Anda mungkin ingin menguji apakah sesuatu memiliki distribusi yang seragam, dengan semua nilai dalam rentang tertentu memiliki kemungkinan yang sama. Atau Anda mungkin ingin menguji apakah sesuatu memiliki distribusi normal, dll. Untuk menguji apakah data memiliki distribusi tertentu, Anda dapat menggunakan uji goodness of fit seperti uji chi square atau tes Kolmogorov-Smirnov.

Ada dua bagian untuk menguji generator nomor acak. Jika Anda hanya ingin menguji generator yang seragam, maka ya, sesuatu seperti test suite DIEHARD adalah ide yang bagus.

Tetapi seringkali Anda perlu menguji transformasi generator yang seragam. Misalnya, Anda dapat menggunakan generator yang seragam untuk membuat nilai yang terdistribusi secara eksponensial atau normal. Anda mungkin memiliki generator seragam berkualitas tinggi - misalnya Anda memiliki implementasi tepercaya dari algoritma terkenal seperti Mersenne Twister - tetapi Anda perlu menguji apakah output yang ditransformasi memiliki distribusi yang tepat. Dalam hal ini Anda perlu melakukan semacam uji goodness of fit seperti Kolmogorov-Smirnov. Tetapi sebagai permulaan, Anda dapat memverifikasi bahwa mean sampel dan varians memiliki nilai yang Anda harapkan.

Kebanyakan orang tidak - dan tidak seharusnya - menulis generator nomor acak seragam mereka sendiri dari awal. Sulit untuk menulis generator yang baik dan mudah menipu diri sendiri dengan berpikir Anda telah menulis yang baik ketika Anda belum. Sebagai contoh, Donald Knuth menceritakan kisah dalam TAOCP volume 2 tentang generator bilangan acak yang ditulisnya yang ternyata mengerikan. Tapi itu biasa bagi orang-orang untuk harus menulis kode mereka sendiri untuk menghasilkan nilai acak dari distribusi baru.

The NIST menerbitkan daftar uji statistik dengan implementasi referensi di C.

Ada juga TestU01 oleh beberapa orang pintar, termasuk peneliti PRNG yang dihormati Pierre L'Ecuyer. Sekali lagi, ada implementasi referensi dalam C.

Seperti yang ditunjukkan oleh komentator lain, ini untuk menguji generasi bit pseudo acak. Jika Anda mengubah bit-bit ini menjadi variabel acak yang berbeda (mis. Transformasi Box-Muller dari seragam ke Normal), Anda akan memerlukan tes tambahan untuk mengonfirmasi kebenaran algoritma transformasi.