rand () % 6이 편향된 이유는 무엇입니까?

rand () % 6이 편향된 이유는 무엇입니까?

---

std :: rand 사용 방법을 읽을 때 cppreference.com 에서이 코드를 찾았습니다.

int x = 7;
while(x > 6) 
    x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

오른쪽의 표현에 문제가 있습니까? 그것을 시도하고 완벽하게 작동합니다.

---

두 가지 문제가 있습니다 rand() % 6( 두 문제에 1+영향을주지 않음).

첫째, 여러 답변에서 지적했듯이의 하위 비트 rand()가 적절하게 균일하지 않으면 나머지 연산자의 결과도 균일하지 않습니다.

둘째,에서 생성 된 고유 값의 수가 rand()6의 배수가 아니면 나머지는 높은 값보다 더 낮은 값을 생성합니다. rand()완벽하게 분포 된 값을 반환 하더라도 마찬가지 입니다.

극단적 인 예로서 rand()범위에서 균일하게 분포 된 값 을 생성하는 척 하십시오 [0..6]. 해당 값의 나머지를 살펴보면 rand()범위의 값을 반환 할 때 [0..5]나머지는 범위 에 균일하게 분포 된 결과를 생성합니다 [0..5]. rand()6을 rand() % 6반환 하면 0을 반환 한 것처럼 0 rand()을 반환합니다. 따라서 다른 값보다 두 배 많은 0이있는 분포를 얻습니다.

두 번째는 것입니다 실제 와 문제 rand() % 6.

이 문제를 피하는 방법은 균일하지 않은 중복을 생성하는 값 을 버리는 것입니다. 보다 작거나 같은 6의 가장 큰 배수를 계산하고 그 배수보다 크거나 같은 값을 반환 RAND_MAX할 때마다 rand()이를 거부하고 필요한만큼 여러 번`rand ()를 다시 호출합니다.

그래서:

int max = 6 * ((RAND_MAX + 1u) / 6)
int value = rand();
while (value >= max)
    value = rand();

이것은 무슨 일이 일어나고 있는지 더 명확하게 보여주기 위해 문제의 코드의 다른 구현입니다.

---

여기에 숨겨진 깊이가 있습니다.

1. 작은의 사용 u에서 RAND_MAX + 1u. 유형으로 RAND_MAX정의되며 int가능한 가장 큰 int. 의 동작은 RAND_MAX + 1될 것입니다 정의되지 않은 사용자가 넘쳐 할 것 같은 경우에 signed유형입니다. 쓰기 1u세력의 변환 입력 RAND_MAX에를 unsigned너무 오버 플로우를 미연에 방지.

2. 의 사용 % 6 캔 (그러나 모든 구현에 std::rand나는 본 적이 없습니다 위 제시된 대안을 넘어 추가 통계에 편차를 소개합니다). % 6위험한 경우는 숫자 생성기가 하위 비트에서 상관 관계 평야를 갖는 경우입니다. 예를 들어, in의 다소 유명한 IBM 구현 (C에서)과 rand같이 상위 및 하위 비트를 "최종 융성". 추가 고려 사항은 6이 매우 작다는 것입니다. RAND_MAX, 따라서가 RAND_MAX6의 배수가 아니면 최소한의 효과 가있을 것입니다.

결론적으로 요즘은 다루기 쉽기 때문에 % 6. 생성기 자체가 도입 한 것 이상의 통계적 이상을 도입 할 가능성은 없습니다. 여전히 의심스러운 경우 생성기를 테스트 하여 사용 사례에 적합한 통계 속성이 있는지 확인하십시오.

---

이 예제 코드 std::rand는 그것이 당신이 그것을 볼 때마다 당신의 눈썹을 올려야하는 레거시화물 컬트 balderdash의 경우를 보여줍니다 .

여기에는 몇 가지 문제가 있습니다.

계약 사람들은 일반적으로 가난한 불운 한 영혼이 더 좋은 모르는 사람들도-가정하고 정확하게 다음에 생각하지 않을 것이다 용어-IS rand로부터 샘플 균일 한 분포를 0에서 정수에, 1, 2, ..., RAND_MAX, 각 호출은 독립적 인 샘플을 생성합니다 .

첫 번째 문제는 가정 된 계약 (각 호출에서 독립적 인 균일 한 무작위 샘플)이 실제로 문서에 나와있는 내용이 아니라는 것입니다. 실제로 구현은 역사적으로 가장 작은 독립 시뮬레이션조차 제공하지 못했습니다. 예를 들어, C99 §7.20.2.1 ' rand기능'은 정교하지 않고 다음과 같이 말합니다.

이 rand함수는 0 ~ RAND_MAX. 범위의 의사 난수 정수 시퀀스를 계산합니다 .

의사 난수는 정수가 아니라 함수 (또는 함수 계열)의 속성 이지만 ISO 관료조차도 언어를 남용하는 것을 막지는 못 하기 때문에 이것은 의미없는 문장 입니다. 결국, 그것에 화를 낼 유일한 독자 rand는 뇌 세포가 썩는다는 두려움 때문에 문서를 읽는 것보다 더 잘 알고 있습니다.

C의 일반적인 역사적 구현은 다음과 같이 작동합니다.

static unsigned int seed = 1;

static void
srand(unsigned int s)
{
    seed = s;
}

static unsigned int
rand(void)
{
    seed = (seed*1103515245 + 12345) % ((unsigned long)RAND_MAX + 1);
    return (int)seed;
}

이는 단일 샘플이 균일 한 임의 시드 (의 특정 값에 따라 다름) 하에서 균일하게 분포 될 수 있지만RAND_MAX 연속 호출에서 짝수와 홀수 정수를 번갈아 가며

int a = rand();
int b = rand();

이 표현식 (a & 1) ^ (b & 1)은 100 % 확률로 1을 산출합니다. 이는 짝수 및 홀수 정수에서 지원되는 모든 분포에 대한 독립적 인 랜덤 샘플 의 경우가 아닙니다 . 따라서, '더 나은 무작위성'이라는 알기 어려운 짐승을 쫓기 위해 하위 비트를 버려야한다는화물 컬트가 등장했습니다. (스포일러 경고 : 이것은 전문 용어가 아닙니다. 이것은 당신이 읽고있는 산문이 그들이 말하는 내용을 모르거나 당신 이 단서가없고 굴욕적 이라고 생각 한다는 신호입니다.)

두 번째 문제는 각 호출이 0, 1, 2,…, RAND_MAX에서 균일 한 무작위 분포 와 독립적으로 샘플링 을 수행 하더라도 의 결과 rand() % 6가 주사위처럼 0, 1, 2, 3, 4, 5에 균일하게 분포되지 않는다는 것입니다. RAND_MAX-1 모듈로 6과 합동 하지 않는 한 롤링 . 간단한 반례 : If RAND_MAX= 6 rand()이면 모든 결과는 1/7 확률이 같지만에서 rand() % 6결과 0은 확률이 2/7이고 다른 모든 결과는 확률이 1/7입니다. .

The right way to do this is with rejection sampling: repeatedly draw an independent uniform random sample s from 0, 1, 2, …, RAND_MAX, and reject (for example) the outcomes 0, 1, 2, …, ((RAND_MAX + 1) % 6) - 1—if you get one of those, start over; otherwise, yield s % 6.

unsigned int s;
while ((s = rand()) < ((unsigned long)RAND_MAX + 1) % 6)
    continue;
return s % 6;

This way, the set of outcomes from rand() that we accept is evenly divisible by 6, and each possible outcome from s % 6 is obtained by the same number of accepted outcomes from rand(), so if rand() is uniformly distributed then so is s. There is no bound on the number of trials, but the expected number is less than 2, and the probability of success grows exponentially with the number of trials.

The choice of which outcomes of rand() you reject is immaterial, provided that you map an equal number of them to each integer below 6. The code at cppreference.com makes a different choice, because of the first problem above—that nothing is guaranteed about the distribution or independence of outputs of rand(), and in practice the low-order bits exhibited patterns that don't ‘look random enough’ (never mind that the next output is a deterministic function of the previous one).

Exercise for the reader: Prove that the code at cppreference.com yields a uniform distribution on die rolls if rand() yields a uniform distribution on 0, 1, 2, …, RAND_MAX.

Exercise for the reader: Why might you prefer one or the other subsets to reject? What computation is needed for each trial in the two cases?

A third problem is that the seed space is so small that even if the seed is uniformly distributed, an adversary armed with knowledge of your program and one outcome but not the seed can readily predict the seed and subsequent outcomes, which makes them seem not so random after all. So don't even think about using this for cryptography.

You can go the fancy overengineered route and C++11's std::uniform_int_distribution class with an appropriate random device and your favorite random engine like the ever-popular Mersenne twister std::mt19937 to play at dice with your four-year-old cousin, but even that is not going to be fit for generating cryptographic key material—and the Mersenne twister is a terrible space hog too with a multi-kilobyte state wreaking havoc on your CPU's cache with an obscene setup time, so it is bad even for, e.g., parallel Monte Carlo simulations with reproducible trees of subcomputations; its popularity likely arises mainly from its catchy name. But you can use it for toy dice rolling like this example!

Another approach is to use a simple cryptographic pseudorandom number generator with a small state, such as a simple fast key erasure PRNG, or just a stream cipher such as AES-CTR or ChaCha20 if you are confident (e.g., in a Monte Carlo simulation for research in the natural sciences) that there are no adverse consequences to predicting past outcomes if the state is ever compromised.

---

I'm not an experienced C++ user by any means, but was interested to see if the other answers regarding std::rand()/((RAND_MAX + 1u)/6) being less biased than 1+std::rand()%6 actually holds true. So I wrote a test program to tabulate the results for both methods (I haven't written C++ in ages, please check it). A link for running the code is found here. It's also reproduced as follows:

// Example program
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <string>

int main()
{
    std::srand(std::time(nullptr)); // use current time as seed for random generator

    // Roll the die 6000000 times using the supposedly unbiased method and keep track of the results

    int results[6] = {0,0,0,0,0,0};

    // roll a 6-sided die 20 times
    for (int n=0; n != 6000000; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

        results[x-1]++;
    }

    for (int n=0; n !=6; n++) {
        std::cout << results[n] << ' ';
    }

    std::cout << "\n";


    // Roll the die 6000000 times using the supposedly biased method and keep track of the results

    int results_bias[6] = {0,0,0,0,0,0};

    // roll a 6-sided die 20 times
    for (int n=0; n != 6000000; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + std::rand()%6;

        results_bias[x-1]++;
    }

    for (int n=0; n !=6; n++) {
        std::cout << results_bias[n] << ' ';
    }
}

I then took the output of this and used the chisq.test function in R to run a Chi-square test to see if the results are significantly different than expected. This stackexchange question goes into more detail of using the chi-square test to test die fairness: How can I test whether a die is fair?. Here are the results for a few runs:

> ?chisq.test
> unbias <- c(100150, 99658, 100319, 99342, 100418, 100113)
> bias <- c(100049, 100040, 100091, 99966, 100188, 99666 )

> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 8.6168, df = 5, p-value = 0.1254

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 1.6034, df = 5, p-value = 0.9008

> unbias <- c(998630, 1001188, 998932, 1001048, 1000968, 999234 )
> bias <- c(1000071, 1000910, 999078, 1000080, 998786, 1001075   )
> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 7.051, df = 5, p-value = 0.2169

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 4.319, df = 5, p-value = 0.5045

> unbias <- c(998630, 999010, 1000736, 999142, 1000631, 1001851)
> bias <- c(999803, 998651, 1000639, 1000735, 1000064,1000108)
> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 7.9592, df = 5, p-value = 0.1585

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 2.8229, df = 5, p-value = 0.7273

In the three runs that I did, the p-value for both methods was always greater than typical alpha values used to test significance (0.05). This means that we wouldn't consider either of them to be biased. Interestingly, the supposedly unbiased method has consistently lower p-values, which indicates that it might actually be more biased. The caveat being that I only did 3 runs.

UPDATE: While I was writing my answer, Konrad Rudolph posted an answer that takes the same approach, but gets a very different result. I don't have the reputation to comment on his answer, so I'm going to address it here. First, the main thing is that the code he uses uses the same seed for the random number generator every time it's run. If you change the seed, you actually get a variety of results. Second, if you don't change the seed, but change the number of trials, you also get a variety of results. Try increasing or decreasing by an order of magnitude to see what I mean. Third, there is some integer truncation or rounding going on where the expected values aren't quite accurate. It probably isn't enough to make a difference, but it's there.

Basically, in summary, he just happened to get the right seed and number of trials that he might be getting a false result.

---

One can think of a random number generator as working on a stream of binary digits. The generator turns the stream into numbers by slicing it up into chunks. If the std:rand function is working with a RAND_MAX of 32767, then it is using 15 bits in each slice.

When one takes the modules of a number between 0 and 32767 inclusive one finds that 5462 '0's and '1's but only 5461 '2's, '3's, '4's, and '5's. Hence the result is biased. The larger the RAND_MAX value is, the less bias there will be, but it is inescapable.

What is not biased is a number in the range [0..(2^n)-1]. You can generate a (theoretically) better number in the range 0..5 by extracting 3 bits, converting them to an integer in the range 0..7 and rejecting 6 and 7.

One hopes that every bit in the bit stream has an equal chance of being a '0' or a '1' irrespective of where it is in the stream or the values of other bits. This is exceptionally difficult in practice. The many different implementations of software PRNGs offer different compromises between speed and quality. A linear congruential generator such as std::rand offers fastest speed for lowest quality. A cryptographic generator offers highest quality for lowest speed.

참고URL : https://stackoverflow.com/questions/49878942/why-is-rand6-biased