박스-뮬러 변환

Box-Muller 변환의 시각화 - 원으로 그려진 단위 사각형(u1, u2)의 색상은 십자형으로 그려진 2D 가우스(z0, z1)에 매핑된다.여백의 그림은 z0과 z1의 확률분포함수다.z0과 z1은 제한되지 않는다는 점에 유의하십시오. 그림으로 표시된 점의 선택으로 인해 [-2.5,2.5]에 있는 것으로 나타난다.SVG 파일에서 점 위에 마우스를 올려 놓으면 해당 점과 해당 점을 강조 표시하십시오.

George Edward Pelham Box와 Mervin Edgar Muller에 의한 Box-Muller 변환은 균일하게 분포된 무작위 숫자의 출처가 주어진 독립적이고 표준적이며 정규 분포를 따르는 (기대 0, 단위 분산) 난수 쌍을 생성하기 위한 난수 샘플방식이다.^[1]그 방법은 사실 1934년 레이먼드 E. A. C. 페일리와 노르베르트 비너에 의해 처음으로 명시적으로 언급되었다.^[2]null

Box-Muller 변환은 일반적으로 두 가지 형태로 표현된다.Box와 Muller가 제공한 기본 형식은 [0, 1] 간격의 균일한 분포에서 두 개의 표본을 추출하여 두 개의 표준, 정규 분포 표본에 매핑한다.극성 형태는 다른 간격에서 두 개의 표본을 채취하여 사인 또는 코사인 함수를 사용하지 않고 정규 분포 표본 2개에 매핑한다.null

Box-Muller 변환은 역변환 샘플링 방법에 대한 보다 계산적으로 효율적인 대안으로 개발되었다.^[3]지구라트 알고리즘은 스칼라 프로세서(예: 구형 CPU)에 대해 보다 효율적인 방법을 제공하는 반면, 박스-뮬러 변환은 벡터 유닛(예: GPU 또는 최신 CPU)이 있는 프로세서에서는 우수하다.^[4]null

기본형식

U와₁ U가₂ 단위 간격(0, 1)의 균일한 분포에서 선택한 독립적인 표본이라고 가정합시다.내버려두다

Z_{0}=R\cos(\Teta )={\sqrt {-2\ln U_{1}}\cos(2\PI U_{2})\,

그리고

Z_{1}=R\sin(\Teta )={\sqrt {-2\ln U_{1}}\sin(2\PI U_{2}).\,

그러면 Z와₀ Z는₁ 표준 정규 분포를 갖는 독립 랜덤 변수다.null

파생은^[5] 2차원 카르테시안 시스템의 속성에 기초하는데, 여기서 X 좌표와 Y 좌표는 두 개의 독립적이고 정규적으로 분포된 랜덤 변수에 의해 설명되며, 해당 극좌표에서² R과 ((위 그림)에 대한 랜덤 변수도 독립적이어서 다음과 같이 표현할 수 있다.

R^{2}=-2\cdot \ln U_{1}\,

그리고

\theta =2\pi U_{2}.\,

R은² 표준 이바리산 정규 변수(X, Y)의 정규 제곱이기 때문에 자유도가 2인 카이-제곱 분포를 가진다.자유도 2도의 특수한 경우, 카이-제곱 분포는 지수 분포와 일치하며, 위의 R에² 대한 방정식은 필요한 지수 변동을 생성하는 간단한 방법이다.null

극형

u와 v는 마찬가지로 균일하게 분포된 s = R² 값을 생성하는 데 사용된다.그런 다음 사인 및 코사인 정의는 삼각함수의 사용을 피하기 위해 Box-Muller 변환의 기본 형식에 적용된다.

극형은 처음에 J. 벨에^[6] 의해 제안되었다가 R. Knop에 의해 수정되었다.^[7]극지방법의 여러 가지 다른 버전이 설명되어 왔지만, R. Knop의 버전은 수치적 레시피에 포함되어 있기 때문에 부분적으로 가장 널리 사용되고 있기 때문에 여기에서 설명될 것이다.null

u와 v가 주어진 경우, 닫힌 간격[-1, +1]에서 독립적이고 균일하게 분포된 s = R² = u² + v를² 설정한다. s = 0 또는 s ≥ 1인 경우 u와 v를 버리고 다른 쌍(u, v)을 시도한다.u와 v는 균일하게 분포되어 있고 단위 원 내의 점만 인정되었기 때문에 s의 값은 개방 간격(0, 1)에서도 균일하게 분포될 것이다.후자는 구간(0, 1)에서 s에 대한 누적분포함수를 계산하면 알 수 있다. $\scriptstyle \pi$ $\scriptstyle {\sqrt {s}}$ ${\$ 을(를) $\scriptstyle {\sqrt {s}}$ by ${\$ 로 나눈 원의 영역이다 $\scriptstyle \pi$ 여기서 확률밀도함수는 간격(0, 1)에 상수 값 1을 갖는다는 것을 알 수 있다.마찬가지로 θ을 $\scriptstyle 2\pi$ 으로 나눈 각도 $\scriptstyle 2\pi$ θ은 [ $0,$ 1) $구간$ 에 균일하게 분포하며 $\scriptstyle 2\pi$ s에 독립적이다.

이제 기본 형태로₁ U와 $\scriptstyle \theta /(2\pi )$ / $\scriptstyle \theta /(2\pi )$ ( $\scriptstyle \theta /(2\pi )$ 2 $\scriptstyle \theta /(2\pi )$ )의 $\scriptstyle \theta /(2\pi )$ 값과 s의 값을 U의₂ 값과 $\scriptstyle \theta /(2\pi )$ \ $displaystyle$ \ $scriptstyle$ \theta /( $2\pi )}$ 로 식별한다.As shown in the figure, the values of $\scriptstyle \cos \theta =\cos 2\pi U_{2}$ and $\scriptstyle \sin \theta =\sin 2\pi U_{2}$ in the basic form can be replaced with the ratios ${\displaystyle \scriptst$ $yle \cos \theta =u/{\sqrt{s}}$ 와 $\scriptstyle\cos \theta = u/R = u/\sqrt{s}$ $\scriptstyle \sin \theta =v/R=v/{\sqrt {s}}$ $theta$ = $v/R=v/{\$ sqrt ${s},$ /{\sqrt{s}.삼각함수를 직접 계산하는 것을 피할 수 있는 것이 장점이다.이것은 삼각함수가 각각의 삼각함수를 대체하는 단일분할보다 계산에 더 비쌀 때 유용하다.null

기본 형태가 두 가지 표준적인 정상 이탈을 낳는 것처럼, 이 대체적인 계산도 마찬가지다.null

z_{0}={\sqrt {-2\ln U_{1}}}\cos(2\pi U_{2})={\sqrt {-2\ln s}}\left({\frac {u}{\sqrt {s}}}\right)=u\cdot {\sqrt {\frac {-2\ln s}{s}}}

그리고

z_{1}={\sqrt {-2\ln U_{1}}}\sin(2\pi U_{2})={\sqrt {-2\ln s}}\left({\frac {v}{\sqrt {s}}}\right)=v\cdot {\sqrt {\frac {-2\ln s}{s}}}.

두 형태 대비

극지방법은 거부표본의 일종이라는 점에서 기본방법과 다르다.생성된 일부 난수는 삭제하지만, 계산이 간단하고(난수 발생기가 상대적으로 빠를 경우) 수적으로 강력하기 때문에 기본 방법보다 더 빠를 수 있다.^[8]값비싼 삼각함수의 사용을 피하면 기본 형태보다 속도가 향상된다.^[6]1 - $π$ /4 ≈ 21.46%의 균일하게 분포된 난수 쌍, 즉 4/102 - 1 ≈ 27.32%의 균일하게 분포된 난수 쌍이 생성되어 출력 $난수$ 당 1.2732개의 입력 난수 쌍이 필요하다.null

기본형식은 정상변동별로 2개의 곱, 1/2 로그, 1/2제곱근, 1개의 삼각함수를 필요로 한다.^[9]일부 프로세서에서는 단일 명령을 사용하여 동일한 인수의 코사인(cosine)과 사인(sine)을 병렬로 계산할 수 있다.특히 인텔 기반 기계의 경우 fsincos 조립기 명령이나 expi 명령어(일반적으로 C에서 내장 함수로 사용 가능)를 사용하여 복잡한 것을 계산할 수 있다.

\displaystyle \exp(iz)=e^{iz}=\cos z+i\sin z,\,}

현실과 상상의 부분만 분리하면 돼null

참고: 복합 극성 형태를 명시적으로 계산하려면 일반 양식에서 다음 대체품을 사용하십시오.

$r={\sqrt {-2\ln(u_{1})}}$ = $r={\sqrt {-2\ln(u_{1})}}$ - $r={\sqrt {-2\ln(u_{1})}}$ $r={\sqrt {-2\ln(u_{1})}}$ $r={\sqrt {-2\ln(u_{1})}}$ ( $r={\sqrt {-2\ln(u_{1})}}$ 1 ) $r={\sqrt {-2\ln(u_{1})}}$ {\ $displaystyle r={\sqrt$ {- $2\ln(u_{1}}}}},$ $z=2\pi u_{2}.$ = $z=2\pi u_{2}.$ u $z=2\pi u_{2}.$ . $z=2\pi u_{2}.$ {\ $displaystyle z=2\pi u_{2}.}$ 그러면 $z=2\pi u_{2}.$

re^{iz}={\sqrt{-2\ln(u_{1}})}e^{i2\pi u_{2}}={\sqrt{-2\ln(u_{1}}}}}}}}}}}}}\좌측[2\cos(2\pi u_{2}}\n}오른쪽).

극형은 정상변동별로 3/2배수, 1/2로기, 1/2제곱근, 1/2분할이 필요하다.그 효과는 하나의 곱셈과 하나의 삼각함수를 하나의 분할과 조건부 루프로 대체하는 것이다.null

꼬리 자르기

컴퓨터가 균일한 무작위 변수를 생성하기 위해 사용될 경우, 숫자가 0에 얼마나 근접할 수 있는지에 대한 하한이 있기 때문에 필연적으로 일부 부정확할 수 있다.제너레이터가 출력 값당 32비트를 사용하는 경우 생성 가능한 0이 아닌 최소 $2^{-32}$ 는 2 $2^{-32}$ - ${\$ 입니다 $2^{-32}$ $U_{1}$ 1 ${\$ $}}$ 와 $U_{1}$ U $U_{2}$ ${\$ }}가 $U_{2}$ 이와 같을 때 Box-Muller 변환은 $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ = $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ - $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ ( $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ - 32 $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ )와 동일한 랜덤 편차를 생성한다. $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ ( $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ - $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ ) $\delta ={\sqrt {-2\ln(2^{-32})}}\cos(2\pi 2^{-32})\approx 6.660$ $.\$ {\ $displaystyle \delta$ ={\sqrt ${-2\ln(2^{-32})}}}}}}\cos(2\pi$ 2 $^{-32$ $약 6.cos}.$ 이는 알고리즘이 평균으로부터 6.660 표준 편차를 초과하는 랜덤 변수를 생성하지 않는다는 것을 의미한다.This corresponds to a proportion of $2(1-\Phi (\delta ))\simeq 2.738\times 10^{-11}$ lost due to the truncation, where $\Phi (\delta )$ is the standard cumulative normal distribution.64비트의 경우 한계는 $\delta =9.419$ = 9 $\delta =9.419$ ${\displaystyle \delta$ = $9.419}$ 표준 $\delta =9.419$ 편차로 푸시되며 $2(1-\Phi (\delta ))<5\times 10^{-21}$ 이 편차는 $2(1-\Phi (\delta ))<5\times 10^{-21}$ ( $1$ - $2(1-\Phi (\delta ))<5\times 10^{-21}$ ( $2(1-\Phi (\delta ))<5\times 10^{-21}$ ) $2(1-\Phi (\delta ))<5\times 10^{-21}$ < 5 $×$ - $2(1-\Phi (\delta ))<5\times 10^{-21}$ {\ $displaystyle$ 2 $(\delta )<5\$ time $10$ ^{- $21-21}$ 이다 $2(1-\Phi (\delta ))<5\times 10^{-21}$

실행

표준 Box-Muller 변환은 평균 0과 표준 편차 1을 갖는 표준 정규 분포(즉, 표준 정규 편차)로부터 값을 생성한다.아래 표준 C++의 구현은 평균 $[\displaystyle \mu }$ 및 $\mu$ 분산 and $\sigma ^{2}$ ${\$ }}. Z $\sigma ^{2}$ $Z$ 이 $Z$ ( $가$ ) 표준 $X=Z\sigma +\mu$ + $X=Z\sigma +\mu$ ${\displaystystyle X=Z\sigma$ + $}$ 의 정규 분포에서 평균과 함께 정규 분포를 가진다 $X=Z\sigma +\mu$ $\sigma ^{2}$ $[\displaystyle \mu }$ 및 표준 $\mu$ 편차 $\sigma$ deviation {\ $displaystyle \sigma$ $\sigma$ 새 $\sigma$ 무작위 값이 순차 호출에서 로 반환되도록 하기 위해 임의 번호 생성기를 시드했다는 점에 유의하십시오.generateGaussianNoise기능을 하다null

#include <cmath> #include <<limits>> #include <<random>> #include <<utility>>  찌꺼기::짝을 짓다<곱절로 하다, 곱절로 하다> 가우스 노이즈 생성(곱절로 하다 뮤, 곱절로 하다 시그마) {     경구적 곱절로 하다 엡실론 = 찌꺼기::numeric_message<곱절로 하다>::엡실론();     경구적 곱절로 하다 2_pi = 2.0 * M_PI;      //임의 균일 번호 생성기(runif)를 0 ~ 1 범위에서 측정     정태의 찌꺼기::19937년산 rng(찌꺼기::임의_기기{}()); // rd()로 시딩된 표준 메르센_트위스터_엔진     정태의 찌꺼기::균일_real_message<> 런이프(0.0, 1.0);      //임의의 두 숫자를 생성하여 u1이 엡실론보다 큰지 확인하십시오.     곱절로 하다 u1, u2;     하다     {         u1 = 런이프(rng);     }     하는 동안에 (u1 <= 엡실론);     u2 = 런이프(rng);      //z0과 z1을 비교     자동차로 마그 = 시그마 * sqrt(-2.0 * 통나무를 하다(u1));     자동차로 z0  = 마그 * cas(2_pi * u2) + 뮤;     자동차로 z1  = 마그 * 죄를 짓다(2_pi * u2) + 뮤;      돌아오다 찌꺼기::make_make(z0, z1); }

참고 항목

역변환 표본 추출
극좌표 대신 데카르트 좌표를 사용하는 Box-Muller와 유사한 변형인 Marsaglia 극좌표법

참조

Howes, Lee; Thomas, David (2008). GPU Gems 3 - Efficient Random Number Generation and Application Using CUDA. Pearson Education, Inc. ISBN 978-0-321-51526-1.

^ Box, G. E. P.; Muller, Mervin E. (1958). "A Note on the Generation of Random Normal Deviates". The Annals of Mathematical Statistics. 29 (2): 610–611. doi:10.1214/aoms/1177706645. JSTOR 2237361.
^ Raymond E. A. C. Paley와 Norbert Wiener Fourier Transforms in the Complex Domain, New York: American Matheical Society (1934년) §37.
^ Kloeden과 Platen, 확률적 미분 방정식의 수치해결, 페이지 11-12
^ Howes & Thomas 2008.
^ Sheldon Ross, A First Course in Probability, (2002), 페이지 279–281
^ ^a ^b Bell, James R. (1968). "Algorithm 334: Normal random deviates". Communications of the ACM. 11 (7): 498. doi:10.1145/363397.363547.
^ Knop, R. (1969). "Remark on algorithm 334 [G5]: Normal random deviates". Communications of the ACM. 12 (5): 281. doi:10.1145/362946.362996.
^ 에버렛 F.카터 주니어, 무작위 번호의 생성과 적용, 앞 치수(1994), 16권, 1호 & 2호.
^ 2πU의₁ 평가는 2π의 값을 미리 계산하여 반복적으로 사용할 수 있기 때문에 하나의 곱으로 계산된다는 점에 유의한다.

외부 링크

[1] Box, G. E. P.; Muller, Mervin E. (1958). "A Note on the Generation of Random Normal Deviates". The Annals of Mathematical Statistics. 29 (2): 610–611. doi:10.1214/aoms/1177706645. JSTOR 2237361.

[2] Raymond E. A. C. Paley와 Norbert Wiener Fourier Transforms in the Complex Domain, New York: American Matheical Society (1934년) §37.

[3] Kloeden과 Platen, 확률적 미분 방정식의 수치해결, 페이지 11-12

[4] Howes & Thomas 2008.

[5] Sheldon Ross, A First Course in Probability, (2002), 페이지 279–281

[Bell68-6] Bell, James R. (1968). "Algorithm 334: Normal random deviates". Communications of the ACM. 11 (7): 498. doi:10.1145/363397.363547.

[7] Knop, R. (1969). "Remark on algorithm 334 [G5]: Normal random deviates". Communications of the ACM. 12 (5): 281. doi:10.1145/362946.362996.

[Carter-8] 에버렛 F.카터 주니어, 무작위 번호의 생성과 적용, 앞 치수(1994), 16권, 1호 & 2호.

[9] 2πU의₁ 평가는 2π의 값을 미리 계산하여 반복적으로 사용할 수 있기 때문에 하나의 곱으로 계산된다는 점에 유의한다.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search