Warum erhalte ich bei Verwendung von $ RANDOM ungleichmäßig verteilte Ergebnisse?

Ich habe in Wikipedia über RNGs gelesen und arbeite$RANDOM mit TLDP, aber das erklärt dieses Ergebnis nicht wirklich:

$ 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

Warum sind die Werte über etwa 2x eher geneigt, 0, 1, 2 als 3, 4, 5 zu sein, aber wenn ich das maximale Modulo ändere, sind sie über alle 10 Werte fast gleich verteilt?

$ 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

Um das Thema Modulo Bias zu erweitern, lautet Ihre Formel:

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

Und in dieser Formel $RANDOMist ein zufälliger Wert im Bereich von 0 bis 32767.

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

Es hilft zu visualisieren, wie dies auf mögliche Werte abgebildet wird:

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

In Ihrer Formel ist die Wahrscheinlichkeit für 0, 1, 2 also doppelt so hoch wie für 4, 5. Und die Wahrscheinlichkeit für 3 ist auch etwas höher als für 4, 5. Daher Ihr Ergebnis mit 0, 1, 2 als Gewinner und 4, 5 als Verlierer.

Beim Wechsel zu 9*3600stellt sich heraus:

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 haben die gleiche Wahrscheinlichkeit, aber es gibt immer noch eine leichte Verzerrung für 0 und daher war 0 mit 100'000 Iterationen immer noch der Gewinner in Ihrem Test.

Um die Modulo-Verzerrung zu beheben, sollten Sie zuerst die Formel vereinfachen (wenn Sie nur 0-5 wollen, dann ist das Modulo 6, nicht 3600 oder sogar eine verrückte Zahl, das macht keinen Sinn). Diese Vereinfachung allein wird Ihre Vorurteile um ein Vielfaches reduzieren (32766 Maps auf 0, 32767 auf 1, was diesen beiden Zahlen eine winzige Vorurteile verleiht).

Um die Verzerrung insgesamt zu beseitigen, müssen Sie (zum Beispiel) neu würfeln, wenn $RANDOMniedriger ist als 32768 % 6(entfernen Sie die Zustände, die dem verfügbaren zufälligen Bereich nicht perfekt zugeordnet sind).

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

Testergebnis:

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

Die Alternative wäre die Verwendung einer anderen Zufallsquelle ohne erkennbare Verzerrung (Größenordnungen größer als nur 32768 mögliche Werte). Aber die Implementierung einer Re-Roll-Logik schadet trotzdem nicht (auch wenn es wahrscheinlich nie passiert).

Dies ist Modulo-Bias. WennRANDOM gut konstruiert, wird jeder Wert zwischen 0 und 32767 mit gleicher Wahrscheinlichkeit erzeugt. Wenn Sie modulo verwenden, ändern Sie die Wahrscheinlichkeiten: Die Wahrscheinlichkeiten aller Werte über dem modulo werden zu den Werten hinzugefügt, denen sie zugeordnet sind.

In Ihrem Beispiel entspricht 6 × 3600 ungefähr zwei Dritteln des Wertebereichs. Die Wahrscheinlichkeiten des oberen Drittels werden daher zu denen des unteren Drittels addiert, was bedeutet, dass Werte von 0 bis 2 (ungefähr) doppelt so wahrscheinlich wie Werte von 3 bis 5 erzeugt werden. 9 × 3600 ist also fast 32767 Die Modulo-Vorspannung ist viel kleiner und betrifft nur Werte von 32400 bis 32767.

Um Ihre Hauptfrage zu beantworten, ist zumindest in Bash die zufällige Reihenfolge vollständig vorhersehbar, wenn Sie den Samen kennen. Sehen Sie intrand32in variables.c.