통계적 무작위성

Statistical randomness

숫자 시퀀스는 인지할 수 있는 패턴이나 규칙성이 없을 때 통계적으로 랜덤하다고 한다. 이상적인 주사위 굴림의 결과나 or의 숫자와 같은 시퀀스는 통계적 랜덤성을 나타낸다.[1]

통계적 무작위성은 반드시 "진정한" 무작위성, 즉 객관적 예측 불가능성을 의미하지는 않는다. 유사성은 통계와 같은 많은 용도에 충분하므로 통계적 무작위라는 명칭이다.

전지구적 무작위성과 국부적 무작위성은 다르다. 무작위성에 대한 대부분의 철학적인 개념은 글로벌하다. 왜냐하면 그들은 "장기적으로" 특정한 하위 순서가 무작위로 보이지 않을지라도 순서는 정말로 무작위로 보인다는 생각에 바탕을 두고 있기 때문이다. 예를 들어, 충분한 길이의 "진정한" 무작위 순서에서, 전체 순서는 무작위일 수 있지만, 숫자만 반복하는 긴 순서가 있을 가능성이 있다. 국부 무작위성은 랜덤 분포를 근사하게 추정하는 최소 시퀀스 길이가 있을 수 있다는 생각을 말한다. "진정한" 무작위 프로세스에 의해 생성된 숫자도 같은 숫자의 긴 스트레칭은 표본의 "국소 무작위성"을 감소시킬 것이다(예를 들어, 1만 개의 숫자의 시퀀스에 대해 국소적으로만 무작위적일 수 있고, 1,000개 미만의 시퀀스를 추출하는 것은 전혀 무작위로 나타나지 않을 수 있다).

패턴을 보여주는 순서는 따라서 통계적으로 무작위가 아닌 것으로 증명되지 않는다. 램지 이론의 원리에 따르면, 충분히 큰 물체는 반드시 주어진 하부 구조("완전한 무질서는 불가능하다")를 포함해야 한다.

도박에 관한 법률은 슬롯머신에 통계적 무작위성의 일정한 기준을 부과한다.

테스트

주요기사 : 랜덤성 검정

무작위 숫자에 대한 첫 번째 테스트는 M.G. Kendall과 Bernard Babington Smith에 의해 1938년 영국 왕립통계학회지에 발표되었다.[2] 그것들은 Pearson의 카이-제곱 검정과 같은 통계적 도구를 기반으로 만들어졌는데, 이는 실험 현상이 이론적 확률과 일치하는지 여부를 구별하기 위해 개발되었다. Pearson은 원래 W.F.R. Weldon의 여러 주사위 실험에서 "랜덤" 행동을 보이지 않는다는 것을 보여줌으로써 그의 테스트를 개발했다.

Kendall과 Smith의 원래 네 가지 테스트는 가설 검정이었는데, 이는 주어진 무작위 시퀀스의 각 숫자가 발생할 확률이 같으며, 데이터의 다양한 다른 패턴도 장비적으로 분포되어야 한다는 생각을 귀무 가설로 삼았다.

  • 주파수 테스트는 0, 1, 2, 3의 숫자가 대략 같은지 확인하는 것이 매우 기본적이었다.
  • 직렬 테스트는 동일한 작업을 수행했지만 한 번에 두 자릿수의 시퀀스(00, 01, 02 등)에 대해 관찰된 주파수와 가상의 예측을 비교한 결과 동일한 분포를 보였다.
  • 포커 테스트는 게임 포커에서 손을 기준으로 한 번에 5개의 숫자(AAAAA, AAAAB, AAABB 등)의 특정 시퀀스를 테스트했다.
  • 간격 테스트는 0 사이의 거리를 조사했다(00은 0, 030은 1,02250은 3 등).

주어진 시퀀스가 주어진 유의성 정도(일반적으로 5%) 내에서 이러한 모든 시험을 통과할 수 있다면, 그것은 그들의 말로 "거의 무작위"로 판정되었다. Kendall과 Smith는 "로컬 무작위성"을 "진정한 무작위성"과 구별했는데, 이는 진정한 무작위성"으로 생성된 많은 시퀀스가 "로컬 무작위성"을 특정 정도까지 표시하지 않을 수 있다는 것이다. 매우 큰 시퀀스는 한 자릿수의 많은 행을 포함할 수 있다. 이는 전체 시퀀스의 규모에 "랜덤"이 될 수 있지만, 더 작은 블록에서는 "랜덤"이 아닐 것이며(그들의 시험을 통과하지 못할 것이며), 다수의 통계적 적용에 무용지물이 될 것이다.

무작위 숫자 집합이 점점 더 흔해짐에 따라, 더 많은 정밀도 검사를 사용하게 되었다. 일부 현대적 테스트는 무작위 숫자를 3차원 평면에 점으로 표시하며, 이 점은 숨겨진 패턴을 찾기 위해 회전할 수 있다. 1995년 통계학자 조지 마르사글리아는 다이하드 테스트로 알려진 일련의 테스트를 만들었는데, 그는 이 테스트를 50억 개의 유사함수의 CD-ROM과 함께 배포한다. 2015년 용게왕은 통계적 거리 기반 랜덤성 테스트를 위해 자바 소프트웨어 패키지를 배포했다.

유사수 생성기는 "정확한 무작위" 프로세스가 아니라 결정론적 알고리즘에 의해 생성되기 때문에 "랜덤성"에 대한 배타적인 검증으로서 시험이 필요하다. 난수 생성의 역사를 통해, 시험 중 "난수"로 보이는 많은 수의 출처는 나중에 특정 유형의 시험을 받을 때 매우 난수성이 없는 것으로 밝혀졌다. 유사 난수 개념은 유사 난수 생성기가 여전히 많은 애플리케이션("비난수"로 알려진 애플리케이션)에서 광범위하게 사용되지만, 대부분의 애플리케이션에 "충분히 양호하다"는 점에서 이러한 문제들 중 일부를 회피하기 위해 개발되었다.

기타 테스트:

  • 모노비트 테스트는 무작위 번호 생성기의 각 출력 비트를 코인 플립 테스트로 처리하고 관찰된 헤드와 꼬리의 수가 예상 주파수 50%에 가까운지 여부를 결정한다. 코인 플립 트레일에 있는 헤드의 수는 이항 분포를 형성한다.
  • Wald-Wolfowitz는 무작위 비트 시퀀스의 예상 주파수와 관측된 주파수를 비교하면서 0비트와 1비트 사이의 비트 전환 횟수를 테스트한다.
  • 정보 엔트로피
  • 자기 상관 검정
  • 콜모고로프-스미르노프 시험
  • 통계적 거리 기반 랜덤성 검정. 융게 왕은 NIST SP800-22 시험 표준이 무작위 생성기의 일부 취약성을 탐지하기에 충분하지 않다는 것을 보여주었고 통계적 거리 기반 무작위 시험을 제안했다.
  • 스펙트럼 밀도 추정[6] - "랜덤" 신호에서 푸리에 변환을 수행하면 비 무작위 반복 추세를 감지하기 위해 주기 함수의 합으로 변환된다.
  • 마우러의 유니버설 통계 시험
  • 다이하르트 테스트

참고 항목

참조

  1. ^ Pi는 좋은 무작위 번호 생성기처럼 보이지만 항상 최고인 것은 아니다, Chad Boutin, Purdue University
  2. ^ Kendall, M.G.; Smith, B. Babington (1938). "Randomness and Random Sampling Numbers". Journal of the Royal Statistical Society. 101 (1): 147–166. doi:10.2307/2980655. JSTOR 2980655.
  3. ^ 왕융게. 가성분 생성을 위한 통계적 시험 기법. http://webpages.uncc.edu/yonwang/liltest/
  4. ^ 용게 왕: (시료도) 무작위 생성기의 LIL 테스트와 일부 실험 결과의 설계에 관하여. PDF
  5. ^ Wang, Yongge; Nicol, Tony (2015). "Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL". Computers and Security. 53: 44–64. doi:10.1016/j.cose.2015.05.005.
  6. ^ Knuth, Donald (1998). The Art of Computer Programming Vol. 2 : Seminumerical Algorithms. Addison Wesley. pp. 93–118. ISBN 978-0-201-89684-8.

외부 링크