Почему я получаю неравномерно распределенные результаты при использовании $ RANDOM?

Я читал о ГСЧ в Википедии и о $RANDOMфункционировании в TLDP, но на самом деле это не объясняет этот результат:

$ 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

Почему значения выше примерно в 2 раза более склонны быть 0, 1, 2, чем 3, 4, 5, но когда я изменяю max по модулю, они почти одинаково распределены по всем 10 значениям?

$ 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

Чтобы расширить тему смещения по модулю, ваша формула:

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

И в этой формуле $RANDOMесть случайное значение в диапазоне 0-32767.

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

Это помогает визуализировать, как это сопоставляется с возможными значениями:

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

Таким образом, в вашей формуле вероятность 0, 1, 2 в два раза выше, чем 4, 5. И вероятность 3 немного выше, чем 4, 5. Отсюда ваш результат с 0, 1, 2 в качестве победителей и 4, 5 в качестве проигравших.

При изменении на 9*3600это получается как:

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 имеют такую ​​же вероятность, но все еще есть небольшое смещение для 0, и, следовательно, 0 по-прежнему был победителем в вашем тесте с 100 000 итераций.

Чтобы исправить смещение по модулю, вы должны сначала упростить формулу (если вы хотите только 0-5, то по модулю 6, а не 3600 или даже более безумное число, в этом нет никакого смысла). Одно только это упрощение значительно уменьшит ваше смещение (32766 карт до 0, 32767 до 1, что дает небольшое смещение к этим двум числам).

Чтобы полностью избавиться от смещения, вам необходимо перебросить (например), когда $RANDOMоно ниже, чем 32768 % 6(исключить состояния, которые не отображаются идеально на доступный случайный диапазон).

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

Результат испытаний:

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

Альтернативой будет использование другого случайного источника, который не имеет заметного смещения (на порядки больше, чем 32768 возможных значений). Но реализация логики перекатывания в любом случае не повредит (даже если это, вероятно, никогда не осуществится).

Это смещение по модулю. Если RANDOMправильно построено, каждое значение между 0 и 32767 произведено с равной вероятностью. Когда вы используете модуль по модулю, вы изменяете вероятности: вероятности всех значений над модулем добавляются к значениям, на которые они отображаются.

В вашем примере 6 × 3600 составляет примерно две трети диапазона значений. Следовательно, вероятности верхней трети добавляются к вероятностям нижней трети, что означает, что значения от 0 до 2 (приблизительно) в два раза больше вероятности, чем значения от 3 до 5. 9 × 3600 - это почти 32767, поэтому Смещение по модулю намного меньше и влияет только на значения от 32400 до 32767.

Чтобы ответить на ваш главный вопрос, по крайней мере в Bash случайная последовательность полностью предсказуема, если вы знаете начальное число. Смотрите intrand32в variables.c.