의사 난수 샘플링

Pseudo-random number sampling

의사 난수 샘플링 또는 불균일한 의사 난수 변동 생성은 주어진 확률 분포에 따라 분포되는 의사 난수를 생성하는 수치 관행이다.

불균일한 분포를 샘플링하는 방법은 일반적으로 균등하게 분포된 숫자 X를 생성하는 의사 난수 발생기의 가용성에 기초합니다.연산 알고리즘은 단일 랜덤 변수 X 또는 종종 그러한 변수 몇 개를 새로운 랜덤 변수 Y로 조작하여 이들 값이 필요한 분포를 갖도록 하기 위해 사용됩니다.

역사적으로 의사 난수 표본 추출의 기본 방법은 맨해튼 [citation needed]프로젝트의 몬테카를로 시뮬레이션을 위해 개발되었으며, 1950년대 [1]초에 John von Neumann에 의해 처음 발표되었다.

유한 이산 분포

확률질량함수 f가 0이 아닌 값을 취하는 한정된 수의 지수를 갖는 이산 확률 분포의 경우, 기본 샘플링 알고리즘은 간단하다.간격 [0, 1)은 n개의 간격 [0, f(1)], [f(1)], f(1) + f(2), ...로 나뉩니다.구간 i의 폭은 확률 f(i)와 같습니다.균등하게 분포된 의사 난수 X를 그려, 대응하는 구간의 지수 i를 검색한다.이렇게 결정되면 분포 f(i)를 갖게 됩니다.

누적 분포 함수를 사용하여 이 아이디어를 공식화하는 것이 더 쉬워집니다.

F(0) = 0으로 설정하면 편리합니다.n개의 간격은 단순하게 [F(0), F(1)], [F(1), F(2), ..., [F(n - 1), F(n)]입니다.그런 다음 주요 계산 작업은 F(i - 1) x X < F(i)에 대한 i를 결정하는 것이다.

이것은, 다른 알고리즘으로 실행할 수 있습니다.

  • 선형 검색, 계산 시간 선형(n).
  • 바이너리 검색, 계산 시간은 로그 n으로 갑니다.
  • 인덱스 검색([2]컷포인트 [3]방식이라고도 함)
  • 에일리어스 방식, 계산 시간은 일정하며, 미리 계산된 테이블을 사용합니다.
  • 일정 시간이 [4]소요되는 다른 방법이 있습니다.

연속 전달

독립 샘플을 생성하는 일반적인 방법:

상관된 샘플을 생성하는 일반적인 방법(흔히 비정상적인 모양 또는 고차원 분포에 필요함):

정규 분포를 생성하는 경우:

포아송 분포를 생성하는 경우:

소프트웨어 라이브러리

GNU Scientific Library에는 20개 이상의 다른 배포에서 샘플링하기 위한 루틴이 포함된 "랜덤 번호 배포"라는 섹션이 있습니다.

각주

  1. ^ 폰 노이만, 존(1951년)."다양한 기법 사용된 접합부 랜덤 Digits에"(PDF).하우스 홀더, A.S.;포사이스, G.E.;Germond, H.H.(eds.)에서.몬테카를로 콘텐츠.전미 표준 응용 수학 시리즈의.Vol12.미국 정부 인쇄국..를 대신하여 서명함. 36–38.누가 난수를 생산하는 산술적 방법이라고 생각하는 사람 물론, 죄의 상태에 있다.원본의 출판물 또한 온라인은 하급의 검사합니다.
  2. ^ 리플리(1987년)[page needed]
  3. ^ 피시맨(1996년)[page needed]
  4. ^ 피시맨(1996년)[page needed]

문학.