유사난수 생성기

유사난수 생성기는 초기 시드(seed)로부터 단위 구간(unit interval)의 균일 분포(uniform distribution)에서 독립적인 추출을 모방하는 길고 재현 가능한 숫자 시퀀스를 생성하는 결정론적 점화식(deterministic recurrence)입니다.

Definition

유사난수 생성기는 상태(state), 상태를 진행시키는 전이 함수(transition function), 그리고 각 상태를 숫자에 매핑하여 균일한 난수와 통계적으로 구별할 수 없도록 의도된 주기적 시퀀스를 생성하는 출력 함수(output function)로 정의되는 알고리즘입니다.

Scope

이 주제는 균일 생성기(선형 합동, 지연-피보나치, 일반화된 피드백 시프트 레지스터, 결합 생성기)의 구성, 주기 길이 및 격자 또는 등분포 거동과 같이 품질을 결정하는 구조적 특성, 그리고 이를 검증하는 데 사용되는 경험적 및 이론적 테스트를 다룹니다. 암호학적으로 안전한 생성기는 대조적인 설계 목표로만 언급됩니다.

Core questions

• 어떤 점화식이 긴 주기와 우수한 고차원 균일성을 제공하는가?
• 생성기의 품질은 격자 구조와 등분포에 의해 어떻게 측정되는가?
• 어떤 경험적 테스트 배터리가 무작위성(randomness)으로부터의 이탈을 감지하는가?
• 주기를 확장하고 통계적 특성을 개선하기 위해 생성기는 어떻게 시드되고 결합되는가?

Key concepts

• 시드 및 상태
• 주기 길이
• 등분포
• 격자 구조
• 스펙트럼 테스트
• 결합 생성기

Key theories

선형 점화식 생성기

선형 합동 및 시프트 레지스터 점화식은 모듈러 산술(modular arithmetic)에 의해 정수 상태를 진행시킵니다. 이들의 주기와 연속적인 출력의 격자 구조는 승수(multiplier)와 모듈러스(modulus)의 정수론적 특성에 의해 결정됩니다.

등분포 및 메르센 트위스터

뒤틀린 일반화된 피드백 시프트 레지스터(twisted generalized feedback shift registers)를 기반으로 하는 생성기는 엄청난 주기를 달성하고 여러 차원에서 증명 가능한 등분포를 제공하여 통계 시뮬레이션의 널리 채택된 기본값이 됩니다.

Clinical relevance

통계 패키지의 기본 생성기는 생성되는 모든 시뮬레이션, 부트스트랩(bootstrap) 및 몬테카를로(Monte Carlo) 결과의 재현성과 유효성을 결정합니다. 주기와 등분포를 이해하는 것은 실무자들이 숨겨진 규칙성으로 인해 고차원 시뮬레이션을 손상시킬 수 있는 생성기를 피하는 데 도움이 됩니다.

History

레머(Lehmer)는 1949년에 선형 합동 방법(linear congruential method)을 제안했습니다. 이후 분석을 통해 잘못 선택된 매개변수의 격자 결함(lattice defects)이 밝혀졌고, 이는 스펙트럼 테스트(spectral test), 결합 생성기(combined generators), 그리고 궁극적으로 1998년 메르센 트위스터(Mersenne Twister)와 같은 장주기 등분포 설계의 동기가 되었습니다.

Key figures

• Donald Knuth
• Pierre L'Ecuyer
• Makoto Matsumoto
• Derrick Henry Lehmer

Seminal works

• knuth1997
• matsumoto1998

Frequently asked questions

어떤 점이 한 유사난수 생성기를 다른 것보다 더 좋게 만드는가?

좋은 생성기는 매우 긴 주기를 가지며, 여러 차원에서도 출력을 균일하게 분포시키고, 표준 통계 테스트 배터리를 통과하며, 빠르고 재현 가능합니다. 좋지 않은 생성기는 짧은 주기를 가지거나 시뮬레이션을 편향시킬 수 있는 가시적인 격자 패턴을 가질 수 있습니다.

시드가 왜 중요한가?

시드는 시작 상태를 고정하므로 전체 시퀀스는 시드에 의해 결정됩니다. 시드를 기록하면 시뮬레이션을 정확하게 재현할 수 있지만, 시드를 부주의하게 선택하면 병렬 실행에서 스트림이 겹치거나 상관 관계를 가질 수 있습니다.