소볼 수열

소볼 시퀀스(베이스 2에서 LP_τ 시퀀스 또는 (t, s) 시퀀스라고도 함)는 준랜덤 저점 시퀀스의 예다.그것들은 러시아의 수학자 일리아 M에 의해 처음 소개되었다. Sobol (Илья Меерович Соболь) in 1967.^[1]

이러한 시퀀스는 2의 베이스를 사용하여 장치 간격의 균일한 파티션을 연속적으로 미세하게 구성한 다음 각 차원의 좌표를 다시 정렬한다.

s차원 단위 하이퍼큐브에서의 양호한 분포

Let I^s = [0,1]^s s차원 단위 하이퍼큐브로서, I에^s 대한 실제 통합 가능한 함수 f.소볼의 원래 동기는 I에^s sequence_n x를 구성해서 그렇게 하도록 하는 것이었다.

${\displaystyle \lim _{n\to \flat }{1}{n1}\sum _{i=1}^{nf(x_{i})=\int _{I^{s}f}$

가능한 한 빨리 수렴할 수 있을 거야

합이 적분 쪽으로 수렴되기 위해서는 x 점이_n 홀을 최소화해야^s 한다는 것은 다소 분명하다.또^s 다른 좋은 특성은 내 저차원 얼굴에 x의_n 투영도 매우 적은 구멍을 남긴다는 것이다.따라서 낮은 차원에서는 많은 점들이 같은 위치에 있기 때문에 적분 추정에 사용할 수 없기 때문에 I의^s 균일한 충전은 적합하지 않다.

이러한 좋은 분포는 base에서 (t,m,s)-nets와 (t,s)-sequence라고 불린다.이들을 소개하려면 먼저 기초 s-간격(s-interval)을 base b에서 폼의 I^s 하위 집합으로 정의하십시오.

${\displaystyle \prod_{j=1}^{s}\왼쪽[{\frac {a_{j}{b^{d_{j}}}},{\frac {a_{j}+1}{b^{d_}}}}}\right),}$

여기서 a와_j d는_j 음이 아닌 정수이며, {1, ...,s}의 모든 j에 < ${\$

Given 2 integers ${\displaystyle 0\leq t\leq m}$, a (t,m,s)-net in base b is a sequence x_n of b^m points of I^s such that ${\displaystyle \operatorname {Card} P\cap \{x_{1},...,x_{b^{m}}\}=b^{t}}$ for all elementary interval P in base b of hypervolume λ(P) = b^t−m.

Given a non-negative integer t, a (t,s)-sequence in base b is an infinite sequence of points x_n such that for all integers ${\displaystyle k\geq 0,m\geq t}$, the sequence ${\displaystyle \{x_{kb^{m}},...,x_{(k+1)b^{m}-1}\}}$ is a (t,m,s)-net in base b.

소볼은 기사에서 π-meses와_τ LP_τ 시퀀스를 각각 베이스 2에서 그물(t,m,s) 순서와 (t,s) 순서에 대해 설명했다.베이스 b(Nederreiter sequence라고도 함)에서 (t,m,s)-네트와 (t,s)시퀀스라는 용어는 1988년 하랄드 니더레이터에 의해 만들어졌다.^[2]소볼 시퀀스라는 용어는 영어권 후기 신문에 할튼, 파우어, 그리고 다른 낮은 점수의 시퀀스와 비교해서 소개되었다.

빠른 알고리즘

보다 효율적인 그레이 코드 구현은 안토노프와 살레프가 제안했다.^[3]

소볼 숫자의 생성에 대해서는, ${\displaystyle \mathrm{n번째}}$ 점 추첨을 위해 n이 아닌$$ 그레이 코드${\displaystyle }$G(${\displaystyle n}$)${\displaystyle }$= n${\displaystyle n}$ n${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ {\$displaystyle G(n)=n\n$\oplus $\lfloor n/2\rfloor }$을(으)의 사용으로 분명히 도움을 받는다.

이미 모든 Sobol 시퀀스를 n - 1까지 끌어오고 필요한 모든 치수에 대한_n−1,j 값 x를 메모리에 저장했다고 가정합시다.회색 코드 G(n)는 앞의 G(n - 1)의 그것과 단 하나의 차이로 다르므로, k-th, 비트(n - 1의 가장 오른쪽 0비트)라고 말하면, 모든 x를_n−1 x에서 x로_n 전파하기 위해 각 차원에 대한 단일 XOR 연산만 하면 된다.

${\displaystyle x_{n,i}=x_{n-1,i}\oplus v_{k,i}.}$

추가 균일성 속성

소볼은 재산 A와 A'로 알려진 추가적인 균일성 조건을 도입했다.^[4]

정의

길이 2의^d d-차원 시퀀스 중 (임의적인 부분집합이 아닌) 이진 세그먼트에 대해 각각의 길이 확장을 따라 단위 하이퍼큐브를 반으로 세분화하여 발생하는 2개의^d 하이퍼큐브 각각에 정확히 1개의 추첨이 있는 경우 낮은 점수의 시퀀스는 속성 A를 만족시킨다고 한다.

정의

길이 4의^d d-차원 시퀀스 중 (임의의 부분집합이 아닌) 이진 세그먼트에 대해 각각의 길이 확장을 따라 단위 하이퍼큐브를 4개의 동일한 부분으로 세분화함으로써 발생하는 4개의^d 하이퍼큐브 각각에 정확히 1개의 추첨이 있는 경우 낮은 점수의 순서는 속성 A'를 만족한다고 한다.

특성 A와 A'를 보증하는 수학적 조건이 있다.

정리.

d차원 Sobol 시퀀스는 속성 A ifff를 소유한다.

${\displaystyle \det(\mathbf {V}_{d})\equiv 1(\mod 2)}$

여기서 V는^d d × d 이진 행렬로 정의된다.

${\displaystyle \mathbf {V} _{d}:={\begin{pmatrix}{v_{1,1,1}}&{v_{2,1,1}}&{\dots }&{v_{d,1,1}}\\{v_{1,2,1}}&{v_{2,2,1}}&{\dots }&{v_{d,2,1}}\\{\vdots }&{\vdots }&{\ddots }&{\vdots }\\{v_{1,d,1}}&{v_{2,d,1}}&{\dots }&{v_{d,d,1}}\end{pmatrix}},}$

v-방향_k,j,mk,j 번호 v = (0_k,j,1k,j,2.₂vv...)의 이진 지점 뒤의 m-th 자리 표시

정리.

d차원 Sobol 시퀀스는 속성 A' ifff를 소유하고 있다.

${\displaystyle \det(\mathbf {U} _{d}\equiv 1\mod 2,}$

여기서 U는^d 다음에 의해 정의된 2d × 2d 이진 행렬이다.

${\displaystyle \mathbf{U}_{d}:={\begin{pmatrix}{v_{1,1,1}}&{v_{1,1,2}}&{v_{2,1,1}}&{v_{2,1,2}}&{\dots}&,{v_{d,1,1}}&{v_{d,1,2}}\\{v_{1,2,1}}&{v_{1,2,2}}&{v_{2,2,1}}&{v_{2,2,2}}&{\dots}&,{v_{d,2,1}}&{v_{d,2,2}}\\{\vdots}&,{\vdots}&,{\vdots}&,{\vdots}&,{\ddots}&,{\vdots}&,{\vdo.이익}\\{v_{1,2d,1}}&{v_{1,2d,2}}&{v_{2,2d,1}}&{v_{2,2d,2}}&{\dots}&,{v_{d,2d,1}&{v_{d,2d,2}}\end{pmatrix},}$

v-방향_k,j,mk,j 번호 v = (0_k,j,1k,j,2.₂vv...)의 이진 지점 뒤의 m-th 자리 표시

속성 A와 A'에 대한 테스트는 독립적이다.따라서 속성 A와 A' 또는 그 중 하나만 만족하는 소볼 시퀀스를 구성할 수 있다.

Sobol 번호 초기화

Sobol 시퀀스를 구성하려면 일련의 방향 번호_i,j v를 선택해야 한다.초기 방향 번호의 선택에는 약간의 자유가 있다.^{[note 1]}따라서 선택된 치수에 대해 소볼 시퀀스의 다른 실현을 받을 수 있다.초기 숫자를 잘못 선택하면 연산에 사용될 때 Sobol 시퀀스의 효율성이 상당히 감소할 수 있다.

거의 틀림없이 초기화 숫자에 대한 가장 쉬운 선택은 l-th 좌측 비트를 설정하고 다른 모든 비트를 0으로 설정하는 것이다. 즉, 모든 k와_k,j j에 대해 m = 1이다.이러한 초기화를 보통 단위 초기화라고 한다.그러나 그러한 순서는 저차원에 대해서도 속성 A와 A'에 대한 시험을 통과하지 못하므로 이 초기화는 좋지 않다.

구현 및 가용성

여러 명의 저자가 서로 다른 차원의 양호한 초기화 번호를 제공한다.예를 들어, 소볼은 51까지 치수에 대한 초기화 번호를 제공한다.^[5]브래틀리와 폭스가 동일한 초기화 번호 집합을 사용한다.^[6]

높은 차원에 대한 초기화 번호는 Joe와 Kuo에서 사용할 수 있다.^[7]피터 야켈은 그의 저서 "금융의 몬테 카를로 방법"에서 32까지 초기화 숫자를 제시한다.^[8]

다른 구현은 소프트웨어의 수치적 레시피 컬렉션에서 C, Fortran 77 또는 Fortran 90 루틴으로 이용할 수 있다.^[9]Joe와 Kuo 초기화 번호에 근거한 최대 1111차원의 무료/오픈 소스 구현은 C로,^[10] Python과^[11][12] Julia에서는 최대 21201차원의 구현을 이용할 수 있다.^[13]C++, Fortran 90, Matlab 및 Python에 대해 최대 1111차원의 다른 자유/오픈 소스 구현이 가능하다.^[14]

마지막으로 상용 소볼 시퀀스 생성기는 예를 들어 NAG 라이브러리 내에서 사용할 수 있다.^[15]영국-러시아 해양개발청(BRODA)에서 버전을 구할 수 있다.^[16][17] MATLAB는 또한 통계 도구 상자의 일부로 구현을^[18] 포함하고 있다.

참고 항목

• 점유가 적은 시퀀스
• 준몬테카를로법

메모들

참조

외부 링크

• ACM의 수집 알고리즘 (알고리즘 647, 659, 738 참조)
• Sobol 시퀀스 생성기 프로그래밍 코드 모음
• Sobol 시퀀스의 Freeware C++ 생성기