Czytałem o RNG na Wikipedii i $RANDOM
funkcjonowaniu na TLDP, ale tak naprawdę nie wyjaśnia tego wyniku:
$ 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
Dlaczego wartości powyżej około 2x są bardziej skłonne do 0, 1, 2 niż 3, 4, 5, ale kiedy zmieniam maksymalny moduł, są one prawie równomiernie rozłożone na wszystkie 10 wartości?
$ 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
zmienna nie używa dobrego PRNG wewnętrznie.Odpowiedzi:
Aby rozwinąć temat błędu modulo, twoja formuła jest następująca:
I w tej formule
$RANDOM
jest wartością losową z zakresu 0–32767.Pomaga wizualizować, w jaki sposób mapuje się na możliwe wartości:
Tak więc w twoim wzorze prawdopodobieństwo dla 0, 1, 2 jest dwa razy większe niż 4, 5. I prawdopodobieństwo 3 jest również nieco wyższe niż 4, 5. Stąd twój wynik z 0, 1, 2 jako zwycięzcami i 4, 5 jako przegranymi.
Po zmianie na
9*3600
, okazuje się, że:Prawdopodobieństwo 1-8 ma takie samo prawdopodobieństwo, ale dla wartości 0 nadal występuje niewielki błąd, a zatem 0 wciąż było zwycięzcą w teście z iteracjami 100 000.
Aby naprawić błąd modulo, powinieneś najpierw uprościć formułę (jeśli chcesz tylko 0-5, to modulo to 6, a nie 3600 lub nawet bardziej szalona liczba, bez sensu). Samo to uproszczenie znacznie zmniejszy twoje uprzedzenie (32766 map do 0, 32767 do 1, dając niewielkie odchylenie do tych dwóch liczb).
Aby całkowicie pozbyć się uprzedzeń, musisz ponownie wykonać rzut (np.), Gdy
$RANDOM
jest niższy niż32768 % 6
(wyeliminuj stany, które nie odwzorowują idealnie dostępnego zakresu losowego).Wynik testu:
Alternatywą byłoby użycie innego losowego źródła, które nie ma zauważalnego odchylenia (rzędy wielkości większe niż tylko 32768 możliwych wartości). Ale wdrożenie logiki ponownego rzutu i tak nie zaszkodzi (nawet jeśli prawdopodobnie nigdy nie nastąpi).
źródło
To jest tendencyjność modulo. Jeśli
RANDOM
jest dobrze skonstruowany, każda wartość od 0 do 32767 jest generowana z jednakowym prawdopodobieństwem. Kiedy używasz modulo, zmieniasz prawdopodobieństwa: prawdopodobieństwa wszystkich wartości powyżej modułu są dodawane do wartości, na które mapują.W twoim przykładzie 6 × 3600 to około dwie trzecie zakresu wartości. Prawdopodobieństwa górnej trzeciej są zatem dodawane do prawdopodobieństwa dolnej trzeciej, co oznacza, że wartości od 0 do 2 (w przybliżeniu) są dwa razy bardziej prawdopodobne niż wartości od 3 do 5. 9 × 3600 to prawie 32767, więc odchylenie modulo jest znacznie mniejsze i wpływa tylko na wartości od 32400 do 32767.
Aby odpowiedzieć na twoje główne pytanie, przynajmniej w Bash losowa sekwencja jest w pełni przewidywalna, jeśli znasz ziarno. Zobacz
intrand32
wvariables.c
.źródło