무작위성을 테스트하는 방법(해당 사례 - 셔플링)
https://stackoverflow.com/questions/56411
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
우선, 이 질문은 다음에서 발췌되었습니다. 이것 질문.나는 이 부분이 더 긴 질문의 하위 부분보다 더 크다고 생각하기 때문에 그렇게 했습니다.기분이 상했다면 용서해주세요.
무작위성을 생성하는 알고리즘이 있다고 가정합니다.이제 어떻게 테스트하나요?또는 좀 더 직접적으로 말하자면, 카드 한 벌을 섞는 알고리즘이 있다고 가정합니다. 이것이 완벽하게 무작위인 알고리즘인지 어떻게 테스트합니까?
문제에 대한 이론을 추가하려면 52 장에서 카드 한 장을 뒤섞을 수 있습니다!(52 계승) 다른 방식.카드 한 벌을 가져와 손으로 섞은 다음 모든 카드의 순서를 적습니다.당신이 정확히 그 셔플을 얻었을 확률은 얼마입니까?답변:1/52!.
섞은 후에 A, K, Q, J를 얻을 확률은 얼마나 됩니까?각 슈트를 순서대로?1/52로 답변해주세요!
따라서 한 번만 섞고 결과를 보면 셔플링 알고리즘의 무작위성에 대한 정보가 전혀 제공되지 않습니다.두 번이면 더 많은 정보가 있고, 세 번이면 더 많은 정보가 있습니다...
무작위성에 대한 셔플링 알고리즘을 블랙박스 테스트하려면 어떻게 해야 합니까?
해결책
통계.RNG 테스트를 위한 사실상의 표준은 다음과 같습니다. 다이하드 스위트 (원래는 다음에서 사용 가능합니다. http://stat.fsu.edu/pub/diehard).대안적으로, 엔트 프로그램 해석하기는 더 간단하지만 덜 포괄적인 테스트를 제공합니다.
셔플링 알고리즘은 다음과 같은 잘 알려진 알고리즘을 사용합니다. 피셔-예이츠 (일명 "Knuth Shuffle").기본 RNG가 균일하게 무작위인 한 셔플은 균일하게 무작위로 수행됩니다.Java를 사용하는 경우 이 알고리즘은 표준 라이브러리에서 사용할 수 있습니다(참조: 컬렉션.셔플).
아마도 대부분의 애플리케이션에서는 문제가 되지 않을 것입니다. 그러나 대부분의 RNG는 52카드 데크의 가능한 모든 순열을 생성할 만큼 충분한 자유도를 제공하지 않는다는 점에 유의하십시오. 여기).
다른 팁
수행할 수 있는 간단한 검사는 다음과 같습니다.생성된 난수를 사용하여 Pi를 추정합니다.무작위성의 증거는 아니지만 열악한 RNG는 일반적으로 잘 수행되지 않습니다(~3.14가 아닌 2.5 또는 3.8과 같은 값을 반환합니다).
이상적으로 이는 무작위성을 확인하기 위해 실행하는 많은 테스트 중 하나일 뿐입니다.
또 확인할 수 있는 부분은 표준 편차 출력의.0..n 범위의 균일하게 분포된 값 모집단에 대한 예상 표준 편차는 n/sqrt(12)에 접근합니다.
/**
* This is a rudimentary check to ensure that the output of a given RNG
* is approximately uniformly distributed. If the RNG output is not
* uniformly distributed, this method will return a poor estimate for the
* value of pi.
* @param rng The RNG to test.
* @param iterations The number of random points to generate for use in the
* calculation. This value needs to be sufficiently large in order to
* produce a reasonably accurate result (assuming the RNG is uniform).
* Less than 10,000 is not particularly useful. 100,000 should be sufficient.
* @return An approximation of pi generated using the provided RNG.
*/
public static double calculateMonteCarloValueForPi(Random rng,
int iterations)
{
// Assumes a quadrant of a circle of radius 1, bounded by a box with
// sides of length 1. The area of the square is therefore 1 square unit
// and the area of the quadrant is (pi * r^2) / 4.
int totalInsideQuadrant = 0;
// Generate the specified number of random points and count how many fall
// within the quadrant and how many do not. We expect the number of points
// in the quadrant (expressed as a fraction of the total number of points)
// to be pi/4. Therefore pi = 4 * ratio.
for (int i = 0; i < iterations; i++)
{
double x = rng.nextDouble();
double y = rng.nextDouble();
if (isInQuadrant(x, y))
{
++totalInsideQuadrant;
}
}
// From these figures we can deduce an approximate value for Pi.
return 4 * ((double) totalInsideQuadrant / iterations);
}
/**
* Uses Pythagoras' theorem to determine whether the specified coordinates
* fall within the area of the quadrant of a circle of radius 1 that is
* centered on the origin.
* @param x The x-coordinate of the point (must be between 0 and 1).
* @param y The y-coordinate of the point (must be between 0 and 1).
* @return True if the point is within the quadrant, false otherwise.
*/
private static boolean isInQuadrant(double x, double y)
{
double distance = Math.sqrt((x * x) + (y * y));
return distance <= 1;
}
첫째, 당신이 지적한 것처럼 특정 유한 출력이 "정말로 무작위"인지 확실히 아는 것은 불가능합니다. 어떤 출력이든 가능.
수행할 수 있는 작업은 일련의 출력을 취하고 이 시퀀스의 다양한 측정값을 가능성이 더 높은 항목과 비교하여 확인하는 것입니다.생성 알고리즘이 제대로 작동하고 있다는 일종의 신뢰도 점수를 도출할 수 있습니다.
예를 들어, 10개의 서로 다른 셔플의 출력을 확인할 수 있습니다.각 카드에 0부터 51까지의 숫자를 할당하고 셔플 전체에서 위치 6에 있는 카드의 평균을 구합니다.수렴 평균은 25.5이므로 여기서 값이 1인 것을 보면 놀랄 것입니다.중심 극한 정리를 사용하여 주어진 위치에 대해 각 평균이 얼마나 가능성이 있는지 추정할 수 있습니다.
하지만 여기서 멈춰서는 안 됩니다!왜냐하면 이 알고리즘은 각 위치에서 정확한 평균 25.5를 제공하도록 설계된 두 개의 셔플만 번갈아 사용하는 시스템에 의해 속일 수 있기 때문입니다.어떻게 하면 더 잘할 수 있을까요?
우리는 다양한 셔플에 걸쳐 각 위치에서 균일한 분포(특정 카드에 대해 동일한 가능성)를 기대합니다.그래서 10 개의 셔플 중에서, 우리는 선택이 '균일 해 보이는지'확인하려고 노력할 수 있습니다. 이것은 기본적으로 원래 문제의 감소 된 버전 일뿐입니다.표준편차가 합리적인지, 최소값이 합리적인지, 최대값도 합리적인지 확인할 수 있습니다.가장 가까운 두 카드(할당된 숫자 기준)와 같은 다른 값도 의미가 있는지 확인할 수도 있습니다.
그러나 충분한 통계가 주어지면 특정 셔플이 어떤 이유로든 거의 발생하지 않을 것이기 때문에 이 광고처럼 다양한 측정값을 무한정 추가할 수도 없습니다(예:이것은 카드 X, Y, Z가 순서대로 나타나는 셔플 중 하나입니다.따라서 가장 큰 질문은 다음과 같습니다.취해야 할 올바른 측정 세트는 무엇입니까?여기서 나는 최선의 대답을 모른다는 것을 인정해야 합니다.그러나 특정 응용 프로그램을 염두에 두고 있다면 테스트할 좋은 속성/측정 세트를 선택하고 이를 사용하여 작업할 수 있습니다. 이것이 암호 전문가가 작업을 처리하는 방식인 것 같습니다.
무작위성을 테스트하는 데에는 많은 이론이 있습니다.카드 셔플링 알고리즘에 대한 매우 간단한 테스트의 경우 많은 셔플을 수행한 다음 각 카드가 어떤 위치에서든 나올 확률이 균일하다는 카이 제곱 테스트를 실행할 수 있습니다.하지만 이는 연속된 카드가 서로 연관되어 있지 않다는 것을 테스트하지 않으므로 그에 대한 테스트도 수행하고 싶을 것입니다.
Knuth의 컴퓨터 프로그래밍 기술 2권에서는 섹션 3.3.2(경험적 테스트) 및 3.3.4(스펙트럼 테스트)에서 사용할 수 있는 여러 테스트와 그 뒤에 있는 이론을 제공합니다.
많이 섞은 다음 결과를 기록합니다(내가 이것을 올바르게 읽었다면)."난수 생성기"에 대한 비교를 본 기억이 납니다.그들은 그것을 계속해서 테스트한 다음 결과를 그래프로 표시합니다.
그것이 정말로 무작위라면 그래프는 대부분 짝수일 것입니다.
무작위성을 테스트하는 유일한 방법은 테스트 중인 데이터에 대한 예측 모델을 구축하고 해당 모델을 사용하여 미래 데이터를 예측하고 예측의 불확실성 또는 엔트로피를 보여주는 프로그램을 작성하는 것입니다. 최대값을 향하는 경향이 있습니다(예:시간 경과에 따른 균일 분포).물론 모델이 필요한 모든 컨텍스트를 캡처했는지 여부는 항상 불확실합니다.모델이 주어지면 첫 번째 모델에는 무작위로 보이는 무작위가 아닌 데이터를 생성하는 두 번째 모델을 구축하는 것이 항상 가능합니다.그러나 명왕성의 궤도가 셔플링 알고리즘의 결과에 미미한 영향을 미친다는 점을 인정하는 한, 그 결과가 허용 가능한 무작위라는 점을 스스로 만족시킬 수 있어야 합니다.
물론 이렇게 하면 모델을 사용할 수도 있습니다. 생성적으로, 실제로 원하는 데이터를 생성합니다.그렇게 하면 다시 원점으로 돌아가게 됩니다.
나는 귀하의 질문을 완전히 따르지 않습니다.당신은 말한다
무작위성을 생성하는 알고리즘이 있다고 가정합니다.이제 어떻게 테스트하나요?
무슨 뜻이에요?무작위성을 생성할 수 있다고 가정한다면 이를 테스트할 필요가 없습니다.
좋은 난수 생성기가 있으면 난수 순열을 만드는 것이 쉽습니다(예:카드를 1-52로 부르세요.52개의 난수를 생성하여 각 숫자를 카드에 순서대로 할당한 다음 52개의 난수에 따라 정렬합니다.순열을 생성하여 좋은 RNG의 무작위성을 파괴하지 않을 것입니다.
어려운 질문은 RNG를 신뢰할 수 있는지 여부입니다. 여기 특정 맥락에서 해당 문제를 논의하는 사람들에 대한 샘플 링크.
테스트 52!가능성은 당연히 불가능하다.대신 3, 5, 10과 같이 더 적은 수의 카드를 섞어 보세요.그런 다음 수십억 번의 셔플을 테스트하고 히스토그램과 카이제곱 통계 테스트를 사용하여 각 순열이 "짝수" 번 나타나는지 증명할 수 있습니다.
지금까지는 코드가 없으므로 다음에서 테스트 부분을 복사하여 붙여넣습니다. 내 대답 원래 질문에.
// ...
int main() {
typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map;
Map freqs;
Deck d;
const size_t ntests = 100000;
// compute frequencies of events: card at position
for (size_t i = 0; i < ntests; ++i) {
d.shuffle();
size_t pos = 0;
for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos)
++freqs[std::make_pair(pos, *j)];
}
// if Deck.shuffle() is correct then all frequencies must be similar
for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)
std::cout << "pos=" << j->first.first << " card=" << j->first.second
<< " freq=" << j->second << std::endl;
}
이 코드는 기본 의사 난수 생성기의 무작위성을 테스트하지 않습니다.PRNG 무작위성을 테스트하는 것은 과학의 전체 분야입니다.
빠른 테스트를 위해 언제든지 압축해 볼 수 있습니다.압축되지 않으면 다른 테스트로 이동할 수 있습니다.
나는 더 열심히 노력했지만 셔플 작업을 거부합니다.모든 테스트가 실패합니다.또한 정말 지루합니다. 원하는 값의 범위나 그와 유사한 것을 지정할 수 없습니다.
스스로 생각해 보면 다음과 같습니다.
설정(의사 코드)
// A card has a Number 0-51 and a position 0-51
int[][] StatMatrix = new int[52][52]; // Assume all are set to 0 as starting values
ShuffleCards();
ForEach (card in Cards) {
StatMatrix[Card.Position][Card.Number]++;
}
이는 카드가 특정 위치에 도달한 횟수를 나타내는 52x52 행렬을 제공합니다.이것을 여러 번 반복합니다(나는 1000부터 시작하겠지만 나보다 통계에 능숙한 사람들은 더 나은 숫자를 줄 수도 있습니다).
매트릭스 분석
완벽한 무작위성을 갖고 무한 횟수로 셔플을 수행하면 각 카드와 각 위치에 대해 카드가 해당 위치에 있는 횟수는 다른 카드와 동일합니다.같은 말을 다른 방식으로 말하면 다음과 같습니다.
statMatrix[position][card] / numberOfShuffle = 1/52.
그래서 나는 우리가 그 숫자로부터 얼마나 멀리 떨어져 있는지 계산할 것입니다.
