Mengapa saya mendapatkan hasil yang tidak merata saat menggunakan $ RANDOM?

14

Saya membaca tentang RNG di Wikipedia dan $RANDOMberfungsi di TLDP tetapi tidak benar-benar menjelaskan hasil ini:

$ max=$((6*3600))
$ for f in {1..100000}; do echo $(($RANDOM%max/3600)); done | sort | uniq -c
  21787 0
  22114 1
  21933 2
  12157 3
  10938 4
  11071 5

Mengapa nilai-nilai di atas sekitar 2x lebih cenderung menjadi 0, 1, 2 dari 3, 4, 5 tetapi ketika saya mengubah modulo max mereka hampir sama tersebar di semua 10 nilai?

$ max=$((9*3600))
$ for f in {1..100000}; do echo $(($RANDOM%max/3600)); done | sort | uniq -c
  11940 0
  11199 1
  10898 2
  10945 3
  11239 4
  10928 5
  10875 6
  10759 7
  11217 8
cprn
sumber
9
Jawaban yang biasa untuk ini adalah untuk reroll (membuang nomor yang Anda terima dan memilih yang lain) jika Anda berada di antara nilai maksimum untuk RANDOM dan nilai tertinggi yang mungkin dapat dibagi secara merata ke dalam modulo Anda. Itu tidak biasa-ke-RANDOM, itu biasa-menggunakan-modulo-untuk-membatasi-RNG-domain di semua bahasa / alat / dll. mengimplementasikan RNG dari tipe itu.
Charles Duffy
7
Lihat artikel saya di 2013 tentang sumber bias ini jika Anda menginginkan grafik yang bagus tentang seberapa buruknya: ericlippert.com/2013/12/16/…
Eric Lippert
1
"Generasi bilangan acak terlalu penting untuk dibiarkan kebetulan." - Robert Coveyou. FYI: sebagian besar program tidak dapat menghasilkan angka acak
jesse_b
@Eric Lippert terima kasih, saya akan membacanya dengan senang hati!
cprn
1
Perhatikan bahwa, meskipun Anda melihat masalah karena bias modulo, $RANDOMvariabel tidak menggunakan PRNG yang baik secara internal.
hutan

Jawaban:

36

Untuk memperluas topik bias modulo, rumus Anda adalah:

max=$((6*3600))
$(($RANDOM%max/3600))

Dan dalam rumus ini, $RANDOMadalah nilai acak di kisaran 0-32767.

   RANDOM Each time this parameter is referenced, a random integer between
          0 and 32767 is generated.

Ini membantu untuk memvisualisasikan bagaimana ini memetakan ke nilai yang mungkin:

0 = 0-3599
1 = 3600-7199
2 = 7200-10799
3 = 10800-14399
4 = 14400-17999
5 = 18000-21599
0 = 21600-25199
1 = 25200-28799
2 = 28800-32399
3 = 32400-32767

Jadi dalam rumus Anda, probabilitas untuk 0, 1, 2 adalah dua kali lipat dari 4, 5. Dan probabilitas 3 sedikit lebih tinggi dari 4, 5 juga. Maka hasil Anda dengan 0, 1, 2 sebagai pemenang dan 4, 5 sebagai pecundang.

Saat berubah menjadi 9*3600, itu berubah menjadi:

0 = 0-3599
1 = 3600-7199
2 = 7200-10799
3 = 10800-14399
4 = 14400-17999
5 = 18000-21599
6 = 21600-25199
7 = 25200-28799
8 = 28800-32399
0 = 32400-32767

1-8 memiliki probabilitas yang sama, tetapi masih ada sedikit bias untuk 0, dan karenanya 0 masih menjadi pemenang dalam pengujian Anda dengan 100'000 iterasi.

Untuk memperbaiki bias modulo, Anda harus terlebih dahulu menyederhanakan formula (jika Anda hanya ingin 0-5 maka modulo adalah 6, bukan 3600 atau bahkan angka lebih gila, tidak masuk akal dalam hal itu). Penyederhanaan ini saja akan mengurangi bias Anda banyak (32766 peta ke 0, 32767 ke 1 memberikan bias kecil untuk dua angka).

Untuk menghilangkan bias sama sekali, Anda perlu memutar ulang, (misalnya) ketika $RANDOMlebih rendah dari 32768 % 6(menghilangkan negara-negara yang tidak memetakan sempurna untuk rentang acak yang tersedia).

max=6
for f in {1..100000}
do
    r=$RANDOM
    while [ $r -lt $((32768 % $max)) ]; do r=$RANDOM; done
    echo $(($r%max))
done | sort | uniq -c | sort -n

Hasil tes:

  16425 5
  16515 1
  16720 0
  16769 2
  16776 4
  16795 3

Alternatifnya akan menggunakan sumber acak berbeda yang tidak memiliki bias yang nyata (urutan besarnya lebih besar dari hanya 32.768 nilai yang mungkin). Tetapi menerapkan logika re-roll toh tidak ada salahnya (bahkan jika itu sepertinya tidak pernah terjadi).

frostschutz
sumber
Jawaban Anda sebagian besar benar, kecuali: "Anda harus memutar ulang ketika $ RANDOM lebih rendah dari 32768% 6" sebenarnya harus "sama dengan atau lebih besar dari lantai ((RANDMAX + 1) / 6) * 6" (yaitu 32766 ), dan perbaiki kode shell terkait di bawahnya.
Nayuki
@Nayuki jika Anda bisa menunjukkan kesalahan tertentu (yang berlaku dalam konteks yang diberikan) Saya akan dengan senang hati memperbaikinya. Solusi saya hanyalah sebuah contoh, ada berbagai cara untuk melakukannya. Anda dapat menghapus bias dari rentang awal, atau kisaran akhir, atau di suatu tempat di tengah, tidak ada bedanya. Anda dapat menghitungnya lebih baik (dan tidak melakukan modulo di setiap iterasi). Anda dapat menangani kasus-kasus khusus seperti modulos arbitrer dan nilai-nilai randmax, juga menangani RANDMAX = INTMAX di mana RANDMAX + 1 tidak ada, tetapi itu bukan fokus di sini.
frostschutz
Balasan Anda jauh lebih buruk daripada posting Anda. Pertama-tama, saya secara khusus menunjukkan frasa mana yang salah. Perhatikan bahwa "32768% 6" == 2, jadi Anda ingin menjalankan ulang setiap kali $ ACAK <2? Mengenai bias pada awal / akhir / midde rentang, seluruh posting Anda adalah tentang menghapus bias pada akhir rentang, dan tanggapan saya juga melayani hal itu. Ketiga, Anda berbicara tentang menangani RANDMAX = INTMAX, tetapi dalam jawaban Anda Anda menyebutkan nilai 32768 (= 32767 +1) berkali-kali, yang menyiratkan Anda merasa nyaman dengan komputasi RANDMAX + 1.
Nayuki
1
@Nayuki kode saya menghapus 0 dan 1, milik Anda menghapus 32766 dan 32767 dan saya ingin Anda menjelaskan: apa bedanya? Saya hanya manusia, saya membuat kesalahan, tetapi yang Anda katakan sejauh ini adalah "itu salah" tanpa menjelaskan atau menunjukkan alasannya. Terima kasih.
frostschutz
1
Sudahlah, cari tahu. Maaf tentang alarm salah.
Nayuki
23

Ini bias modulo. Jika RANDOMdibangun dengan baik, setiap nilai antara 0 dan 32767 diproduksi dengan probabilitas yang sama. Saat Anda menggunakan modulo, Anda mengubah probabilitas: probabilitas semua nilai di atas modulo ditambahkan ke nilai yang dipetakan.

Dalam contoh Anda, 6 × 3600 adalah sekitar dua pertiga dari rentang nilai. Oleh karena itu probabilitas dari sepertiga atas ditambahkan ke orang-orang dari sepertiga bawah, yang berarti bahwa nilai dari 0 hingga 2 (kira-kira) dua kali lebih mungkin untuk dihasilkan sebagai nilai dari 3 sampai 5. 9 × 3600 hampir 32767, sehingga modulo bias jauh lebih kecil dan hanya memengaruhi nilai dari 32400 hingga 32767.

Untuk menjawab pertanyaan utama Anda, setidaknya di Bash urutan acak sepenuhnya dapat diprediksi jika Anda mengetahui seed. Lihat intrand32di variables.c.

Stephen Kitt
sumber