Kualitas generator kongruensial linier untuk angka acak

Saya sedang melakukan beberapa simulasi persamaan Langevin, untuk berbagai kekuatan eksternal. Diberitahu bahwa C's rand()from stdlib.hdapat memperkenalkan bias pada hasil saya, saya menggunakan Twister Mersenne.

Namun demikian, saya ingin tahu (dan melihat) persis apa jenis kesalahan yang dapat diperkenalkan oleh generator kongruensi linear dalam simulasi saya. Ini adalah hal-hal yang telah saya coba:

• Menghasilkan tuple 3D tebaran untuk mencoba melihat hyperplanes. Saya tidak bisa melihat apa-apa.
• Melakukan FFT dari vektor besar angka acak. Ini hampir sama untuk Twister dan Mersenne rand().
• Memeriksa prinsip ekuipartisi untuk partikel dalam gerakan Brown. Kedua integrator setuju dengan nilai yang diharapkan dari dengan jumlah digit signifikan yang sama.$\langle \text{KE}\rangle=\frac{1}{2}k_BT$
• Melihat seberapa baik mereka nampan di sejumlah nampan yang bukan kekuatan dua. Keduanya memberikan hasil kualitatif yang sama, tidak ada yang lebih baik.
• Melihat jalur Brown untuk melihat perbedaan yang jelas dari . Sekali lagi, tidak ada keberuntungan.$\langle x\rangle = 0$
• Distribusi titik dalam lingkaran. Diisi, dan hanya di perimeter. Di antara mereka semua dan di antara tetangga terdekat (jawaban Shor, di bawah dalam komentar). Tersedia di intisari ini , jalankan saja dengan Julia 0.5.0 setelah menginstal pustaka yang diperlukan (lihat intisari untuk instruksinya).

Saya ingin menekankan bahwa saya mencari bias yang diperkenalkan dalam konteks simulasi fisik. Sebagai contoh, saya telah melihat betapa rand()gagalnya tes dieharder gagal sementara Mersenne Twister tidak, tetapi untuk saat itu tidak terlalu berarti bagi saya.

Apakah Anda memiliki contoh fisik, konkret, tentang bagaimana generator bilangan acak yang buruk merusak simulasi Montecarlo?

Catatan: Saya telah melihat bagaimana sukanya PRNG RANDUbisa mengerikan. Saya tertarik pada contoh yang tidak jelas, tentang generator yang terlihat tidak bersalah tetapi pada akhirnya menimbulkan bias.

Salah satu referensi menarik yang menggambarkan kegagalan simulasi Monte Carlo dari sistem fisik karena RNG yang tidak memadai (meskipun mereka tidak menggunakan LCG) adalah:

A. Ferrenberg dan DP Landau. Simulasi Monte Carlo: Kesalahan Tersembunyi dari Generator Angka Acak "Bagus". Physical Review Letters 63 (23): 3382-3384, 1992.

Model Ising yang dipelajari oleh Ferrenberg dan Landua adalah tes RNG yang baik karena Anda dapat membandingkan dengan solusi yang tepat (untuk masalah 2-D) dan menemukan kesalahan di dalam digit. Model-model ini harus menunjukkan kesalahan dalam PMMLCG aritmatika 32 bit kuno tanpa terlalu banyak kesulitan.

Referensi lain yang menarik adalah:

H. Bauke dan Stephan Mertens. Koin Acak Pseudo Tampilkan Lebih Banyak Kepala daripada Ekor. arXiv: cond-mat / 0307138 [cond-mat.stat-mech]

Bauke dan Mertens membuat kasus yang kuat terhadap generator register acak gaya biner linier umpan balik linier. Bauke dan Mertens memiliki beberapa makalah lain yang berkaitan dengan ini.

Mungkin sulit untuk menemukan pesawat Marsaglia di sebaran plot 3D. Anda dapat mencoba memutar plot untuk mendapatkan tampilan yang lebih baik dan kadang-kadang mereka akan muncul begitu saja. Anda juga dapat melakukan tes 3D keseragaman statistik - untuk LCG 32 bit yang lebih lama, ini akan gagal pada jumlah sampah yang cukup kecil. mis uji keseragaman dengan kisi-kisi sampah 20x20x20 dalam 3 dimensi cukup untuk mendeteksi kurangnya keseragaman untuk PMMLCG yang banyak digunakan (dan sebelumnya dianggap baik) dengan m = 2 ^ 31-1, a = 7 ^ 5.

Hal ini dimungkinkan untuk menggunakan yang TestU01 Suite tes PRNG untuk mengetahui mana dari tes tersebut randgagal. (Lihat TestU01: AC Library untuk Pengujian Empiris Generator Angka Acak untuk tinjauan umum suite uji.) Itu lebih mudah daripada membuat simulasi Monte Carlo sendiri. Di satu sisi, itu juga pertanyaan tentang kompabilitas perangkat lunak (dan kebenaran perangkat lunak): diberikan PRNG yang tampaknya berfungsi baik pada tes kecil dan sederhana, bagaimana Anda tahu perilaku patologisnya tidak akan dipicu oleh program yang lebih besar?

Ini kodenya:

#include "TestU01.h"

int main() {
  // Same as rand() on my machine
  unif01_Gen* gen = ulcg_CreateLCG(2147483647, 16807, 0, 12345);

  bbattery_SmallCrush(gen);
  bbattery_Crush(gen);

  return 0;
}

Untuk paket SmallCrush , ada 3 tes gagal dari 15 (lihat guidelongtestu01.pdf di TestU01 untuk deskripsi panjang dan semua referensi; ini adalah 15 statistik dari 10 tes).

• $n$ $t$$d^t$$d^t$$I_1,\ldots$$\{I_{j+1}-I_j\}$

• $n$ $t$$[0,1)^t$$d^t$

• $n$$t$$[0,1)$$X$$n$$\mathbb{P}(X<x) = x^t$$n=2\times 10^6$$t=6$$\chi^2$$<10^{-300}$

Dengan asumsi ini semua simulasi Monte Carlo "khas" (meskipun mungkin tidak seperti masalah yang ada dalam pikiran Anda), kesimpulannya adalah bahwa randgagal beberapa subset yang tidak diketahui dari mereka. Saya tidak tahu mengapa subset itu khusus, jadi, tidak mungkin bagi saya untuk mengatakan apakah itu akan bekerja pada masalah Anda sendiri atau tidak.

MaxOft tampaknya sangat mencurigakan, mengingat betapa mudahnya deskripsinya.

Di antara tes di Crush suite, randgagal 51 dari 140 (140 statistik dalam 96 tes). Beberapa tes yang gagal (seperti Fourier3 ) dilakukan pada string bit, jadi mungkin itu mungkin tidak relevan bagi Anda. Tes penasaran lain yang gagal adalah GCD , yang menguji distribusi GCD dari dua bilangan bulat acak. (Sekali lagi, saya tidak tahu mengapa tes khusus ini gagal atau apakah simulasi Anda akan menderita karena ini.)

PS : Namun hal lain yang perlu diperhatikan adalah bahwa rand()sebenarnya lebih lambat daripada beberapa PRNG yang berhasil lulus semua tes SmallCrush , Crush , BigCrush , seperti MRG32k3a (lihat kertas L'Ecuyer & Simard di atas).