Dlaczego otrzymuję nierównomiernie rozłożone wyniki przy użyciu $ RANDOM?

Czytałem o RNG na Wikipedii i $RANDOMfunkcjonowaniu 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

Aby rozwinąć temat błędu modulo, twoja formuła jest następująca:

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

I w tej formule $RANDOMjest wartością losową z zakresu 0–32767.

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

Pomaga wizualizować, w jaki sposób mapuje się na możliwe wartości:

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

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:

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

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 $RANDOMjest niższy niż 32768 % 6(wyeliminuj stany, które nie odwzorowują idealnie dostępnego zakresu losowego).

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

Wynik testu:

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

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).

To jest tendencyjność modulo. Jeśli RANDOMjest 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 intrand32w variables.c.