Saya membaca tentang RNG di Wikipedia dan $RANDOM
berfungsi 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
$RANDOM
variabel tidak menggunakan PRNG yang baik secara internal.Jawaban:
Untuk memperluas topik bias modulo, rumus Anda adalah:
Dan dalam rumus ini,
$RANDOM
adalah nilai acak di kisaran 0-32767.Ini membantu untuk memvisualisasikan bagaimana ini memetakan ke nilai yang mungkin:
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: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
$RANDOM
lebih rendah dari32768 % 6
(menghilangkan negara-negara yang tidak memetakan sempurna untuk rentang acak yang tersedia).Hasil tes:
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).
sumber
Ini bias modulo. Jika
RANDOM
dibangun 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
intrand32
divariables.c
.sumber