☰

$RANDOM을 사용할 때 결과가 고르지 않게 분포되는 이유는 무엇입니까?

tag-icon • tag-icon random
$RANDOM을 사용할 때 결과가 고르지 않게 분포되는 이유는 무엇입니까?

온라인에서 RNG에 대해 읽었습니다.위키피디아그리고 $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

위의 값은 3, 4, 5보다 확률이 약 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

답변1

모듈러 편차 주제를 확장하려면 공식은 다음과 같습니다.

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은 여전히 ​​약간 편향되어 있으므로 100,000번의 테스트 반복에서 0이 여전히 승자입니다.

모듈로 편향을 수정하려면 먼저 공식을 단순화해야 합니다(0-5만 원하는 경우 모듈로는 3600이나 이해가 되지 않는 더 미친 숫자가 아닌 6이 됩니다). 이 단순화만으로도 편향이 크게 줄어듭니다(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개의 가능한 값보다 큰 크기 차수) 다양한 무작위 소스를 사용하는 것입니다. 그러나 어쨌든 리롤링 로직을 구현하는 것은 나쁠 것이 없습니다(구현되지 않더라도).

답변2

이것은 모듈러 편차입니다. 올바르게 구성 되면 RANDOM0에서 32767 사이의 모든 값이 동일한 확률로 생성됩니다. 모듈러스를 사용하면 확률이 변경됩니다. 모듈러스 위의 모든 값에는 매핑되는 값에 확률이 추가됩니다.

귀하의 예에서 6×3600은 값 범위의 약 2/3입니다. 따라서 상위 1/3의 확률은 하위 1/3의 확률에 추가됩니다. 즉, 0에서 2 사이의 값은 3에서 5 사이의 값보다 (대략) 두 배 더 높습니다. 9×3600은 32767에 가깝기 때문에 모듈러 편차가 훨씬 작아서 32400과 32767 사이의 값에만 영향을 미칩니다.

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

관련 정보