$ RANDOM을 사용할 때 왜 고르지 않은 결과가 나타 납니까? Wikipedia의 RNG 와 TLDP의$RANDOM 기능에

Wikipedia의 RNG 와 TLDP의$RANDOM 기능에 대해 읽었 지만이 결과를 실제로 설명하지는 않습니다.

$ 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 배 이상의 값이 3, 4, 5보다 0, 1, 2 인 경향이 있지만 최대 모듈로를 변경하면 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))

이 공식에서 $RANDOM0-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은 값 범위의 약 2/3입니다. 따라서 상위 3 분의 1의 확률은 하위 3 분의 3의 확률에 더해집니다. 즉, 0에서 2까지의 값은 3에서 5까지의 값에 비해 생성 될 가능성이 두 배가됩니다. 9 × 3600은 거의 32767이므로 모듈로 바이어스는 훨씬 작으며 32400에서 32767 사이의 값에만 영향을줍니다.

주요 질문에 대답하기 위해, 적어도 Bash에서 시드를 알고 있다면 무작위 시퀀스를 완전히 예측할 수 있습니다. 보기 intrand32에서 variables.c.

답변