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

14

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
cprn
źródło
9
Zwykle odpowiedzią na to jest przewijanie (odrzuć otrzymany numer i wybranie innego), jeśli jesteś pomiędzy maksymalną wartością RANDOM a najwyższą możliwą wartością, która może równomiernie podzielić się na twoje modulo. To nie jest zwykłe RANDOM, to zwykłe używanie modulo do ograniczania domeny RNG we wszystkich językach / narzędziach itp. wdrażanie RNG tego typu.
Charles Duffy
7
Zobacz moją 2013 artykuł na źródło tego błędu, jeśli chcesz jakieś ładne wykresy jak źle robi: ericlippert.com/2013/12/16/...
Eric Lippert
1
„Generowanie liczb losowych jest zbyt ważne, aby pozostawić je przypadkowi”. - Robert Coveyou. Do Twojej wiadomości: większość programów nie jest w stanie wygenerować naprawdę przypadkowych liczb
jesse_b
@Eric Lippert dziękuję, chętnie to przeczytam!
cprn
1
Zauważ, że nawet jeśli widzisz problemy z powodu błędu modulo, $RANDOMzmienna nie używa dobrego PRNG wewnętrznie.
las

Odpowiedzi:

36

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

frostschutz
źródło
Twoja odpowiedź jest w dużej mierze poprawna, z wyjątkiem: „musisz przerzucić, gdy $ RANDOM jest niższy niż 32768% 6” powinien faktycznie być „równy lub większy niż floor ((RANDMAX + 1) / 6) * 6” (tj. 32766 ) i napraw poniżej powiązany kod powłoki.
Nayuki,
@Nayuki, jeśli możesz wskazać konkretny błąd (dotyczy danego kontekstu), chętnie go poprawię. Moje rozwiązanie jest tylko przykładem, są na to różne sposoby. Możesz usunąć odchylenie z zakresu początkowego lub końcowego, lub gdzieś pośrodku, to nie ma znaczenia. Możesz to lepiej obliczyć (i nie robić modulo w każdej iteracji). Możesz obsłużyć specjalne przypadki, takie jak dowolne wartości modułów i wartości randmax, a także obsłużyć RANDMAX = INTMAX, gdzie RANDMAX + 1 nie istnieje, ale tutaj nie było to najważniejsze.
frostschutz
Twoja odpowiedź jest znacznie gorsza niż Twój post. Przede wszystkim wskazałem konkretnie, które z twoich zdań jest błędne pod względem faktycznym. Zauważ, że „32768% 6” == 2, więc chcesz przewijać za każdym razem, gdy $ RANDOM <2? Jeśli chodzi o stronniczość na początku / na końcu / w środku zakresu, cały post dotyczy usuwania uprzedzeń na końcu zakresu, a moja odpowiedź dotyczy dokładnie tego. Po trzecie, mówisz o obsłudze RANDMAX = INTMAX, ale w swojej odpowiedzi wielokrotnie wspominałeś o wartości 32768 (= 32767 + 1), co oznacza, że ​​czujesz się komfortowo przy obliczaniu RANDMAX + 1.
Nayuki,
1
@Nayuki mój kod usuwa 0 i 1, twój usuwa 32766 i 32767 i chciałbym, abyś rozwinął: jaką to robi różnicę? Jestem tylko człowiekiem, popełniam błędy, ale wszystko, co do tej pory powiedziałeś, to „to źle” bez wyjaśnienia lub wyjaśnienia, dlaczego. Dziękuję Ci.
frostschutz
1
Nieważne, rozgryzłem to. Przepraszam za fałszywy alarm.
Nayuki,
23

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.

Stephen Kitt
źródło