저불일치 수열

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

저불일치 수열은 주어진 수열이 얼마나 균일하게 분포되어 있는지를 나타내는 척도로, 몬테카를로 방법의 정확도 향상에 기여한다. 하랄트 니더라이터의 표기법을 사용하여 정의되며, 별-저불일치도와 저불일치도 간에는 관계가 성립한다. 불일치도가 낮을수록 데이터가 고르게 분포되어 몬테카를로 방법의 정확도를 높일 수 있다. 준난수 생성에 활용되며, 반데르코르푸트 수열, 홀턴 수열, 소볼 수열 등이 있다. 콕스마-흐와프카 부등식은 준 몬테카를로 방법에서 오차 범위를 결정하는 데 사용되며, 어르도스-투란-콕스마 부등식은 불일치도의 상한을 제공한다. 저불일치 수열의 불일치도 하한에 대한 추측이 존재하며, 이는 준난수 연구의 중요한 미해결 문제이다.

더 읽어볼만한 페이지

난수 - 주사위
주사위는 다양한 게임, 교육, 점술 등에 사용되는 도구로, 정육면체 외에도 다양한 형태가 존재하며, 플라스틱 사출 성형으로 제작되고 무게 중심과 눈의 배치를 통해 공정성을 유지한다.
난수 - 비결정론
비결정론은 미래가 미리 정해져 있지 않다고 보며, 우연의 개념을 중요하게 생각하고, 확률 과정, 양자역학, 진화 생물학 등 다양한 분야에서 논의된다.
난수 발생기 - 신뢰 플랫폼 모듈
신뢰 플랫폼 모듈(TPM)은 신뢰 컴퓨팅 그룹(TCG)에서 구상한 보안 장치로, 하드웨어 난수 생성, 암호 키 안전 생성, 원격 증명, 바인딩, 밀봉된 저장소 등의 기능을 제공하여 플랫폼 무결성 보장, 디스크 암호화, 디지털 권한 관리(DRM) 등 다양한 분야에 활용되며 여러 유형으로 구현되고 있다.
난수 발생기 - /dev/random
/dev/random은 리눅스 커널에서 제공하는 난수 장치 파일로, 안전한 난수 생성을 위해 사용되며, 엔트로피 풀이 비어있을 경우 블로킹되는 특징을 가진다.
수열 - 코시 열
코시 열은 무한수열에서 항들이 뒤로 갈수록 서로 가까워지는 수열로, 수렴열은 항상 코시 열이지만 그 역은 성립하지 않을 수 있으며, 실수의 완비성 정의 및 무한급수 수렴성 판정에 중요한 역할을 하는 개념이다.
수열 - 실베스터 수열
실베스터 수열은 각 항이 이전 항들의 곱에 1을 더한 값으로 정의되는 정수 수열로서, 재귀적으로 정의되며 이중 지수 함수적으로 증가하고, 이집트 분수 및 탐욕 알고리즘과 관련이 있으며, 역수 합은 1로 수렴한다.

저불일치 수열
개요
유형	수열
분야	수학, 컴퓨터 과학
정의
설명	단위 초입방체(unit hypercube)에서 점들의 분포가 균일한 수열
성질
주요 특징	낮은 불일치도
활용	수치 해석, 몬테카를로 방법
예시
대표적인 수열	할톤 수열 소볼 수열 파울 수열 니더라이터 수열 코코렌 수열
응용
사용 분야	수치 적분 전역 최적화 준 몬테카를로 방법
관련 개념
관련 용어	불일치도

2. 정의

집합 $P = \{x_1, \dots, x_N \}$ 의 ''저불일치도''는 니더라이터의 표기법을 사용하여 다음과 같이 정의된다.

: $D_N(P) = \sup_{B\in J}\left| \frac{A(B;P)}{N} - \lambda_s(B) \right|$

여기서 $\lambda_s$ 는 $s$ 차원 르베그 측도이고,

$A(B;P)$ 는 $P$ 에 속하는 점들 중 $B$ 에 속하는 점의 개수이며,

$J$ 는 다음과 같은 형태의 $s$ 차원 구간 또는 상자들의 집합이다.

: $\prod_{i=1}^s [a_i, b_i) = \{ \mathbf{x} \in \mathbf{R}^s : a_i \le x_i < b_i \} \,$

여기서 $0 \le a_i < b_i \le 1$ 이다.

''별-저불일치도'' $D^*_N(P)$ 는 유사하게 정의되지만, 상한은 다음과 같은 형태의 직사각형 상자들의 집합 $J^*$ 에 대해 취해진다.

: $\prod_{i=1}^s [0, u_i)$

여기서 $u_i$ 는 반열린 구간 [0, 1)에 속한다.

이 두 값은 다음 관계를 갖는다.

: $D^*_N \le D_N \le 2^s D^*_N . \,$

''참고'': 이러한 정의에서, 저불일치도는 균일 집합의 최악의 경우 또는 최대 점 밀도 편차를 나타낸다. 그러나 다른 오차 척도 또한 의미가 있으며, 이는 다른 정의와 변동 척도로 이어진다. 예를 들어, $L^2$ -저불일치도 또는 수정된 중심 $L^2$ -저불일치도 역시 균일 점 집합의 품질을 비교하는 데 광범위하게 사용된다. 이 두 척도는 큰 $N$ 과 $s$ 에 대해 계산하기가 훨씬 쉽다.

2. 1. 불일치도 (Discrepancy)

불일치도는 주어진 수열이 얼마나 균일하게 분포되어 있는지를 나타내는 척도이다. 낮은 불일치도를 갖는 수열은 특정 영역에 데이터가 몰리지 않고 고르게 분포되어, 몬테카를로 방법의 정확도를 향상시킨다.

집합

P = \{x_1, \dots, x_N \}

의 ''저불일치도''는 니더라이터의 표기법을 사용하여 다음과 같이 정의된다.

:

D_N(P) = \sup_{B\in J}\left|  \frac{A(B;P)}{N} - \lambda_s(B)  \right|

여기서

\lambda_s

는

s

차원 르베그 측도이고,

A(B;P)

는

P

에 속하는 점들 중

B

에 속하는 점의 개수이며,

J

는 다음과 같은 형태의

s

차원 구간 또는 상자들의 집합이다.

:

\prod_{i=1}^s [a_i, b_i) = \{ \mathbf{x} \in \mathbf{R}^s : a_i \le x_i < b_i \} \,

여기서

0 \le a_i < b_i \le 1

이다.

''별-저불일치도''

D^*_N(P)

는 유사하게 정의되지만, 상한은 다음과 같은 형태의 직사각형 상자들의 집합

J^*

에 대해 취해진다.

:

\prod_{i=1}^s [0, u_i)

여기서

u_i

는 반열린 구간 [0, 1)에 속한다.

이 두 값은 다음 관계를 갖는다.

:

D^*_N \le D_N \le 2^s D^*_N . \,

저불일치도는 균일 집합의 최악의 경우 또는 최대 점 밀도 편차를 나타낸다.

L^2

-저불일치도 또는 수정된 중심

L^2

-저불일치도 역시 균일 점 집합의 품질을 비교하는 데 사용된다.

3. 장점

난수를 이용한 몬테카를로 방법은 데이터포인트가 불균일하게 분포하여 정확도에 문제가 생기는 경우가 있지만, 준난수는 이러한 문제를 해결할 수 있다. 준난수를 사용하면 기존의 결과를 유지하면서 데이터포인트를 추가할 수 있어, 데이터포인트의 수가 늘어나도 효율적인 계산이 가능하다. 이는 준몬테카를로 방법에 유용하게 활용된다.

4. 생성 방법

임의의 숫자 분포는 균등 분포에 매핑될 수 있으며, 준임의 숫자도 동일한 방식으로 매핑되므로, 이 문서에서는 다차원 균등 분포에서 준임의 숫자를 생성하는 방법에 대해서만 다룬다.

다음과 같은 수열의 구성이 알려져 있다.

: $D_N^{*}(x_1,\ldots,x_N)\leq C\frac{(\ln N)^{s}}{N}.$

여기서 $C$ 는 수열에 따라 달라지는 상수이다. 추측 2 이후, 이러한 수열은 가능한 최상의 수렴 차수를 갖는 것으로 여겨진다. 다음 예는 반데르코르푸트 수열, 할턴 수열 및 소볼' 수열이다. 한 가지 일반적인 제한 사항은 구성 방법이 일반적으로 수렴 차수만을 보장할 수 있다는 것이다. 실제로, 낮은 불일치는 $N$ 이 충분히 클 때만 달성될 수 있으며, 큰 $s$ 의 경우 이 최소 $N$ 은 매우 클 수 있다. 즉, 예를 들어 $s=20$ 개의 변수와 낮은 불일치 수열 생성기에서 생성된 $N=1000$ 개의 점을 사용하여 몬테카를로 분석을 실행하면 정확성 향상이 매우 미미할 수 있다.

== 무리수 기반 방법 ==

모든 무리수 $\alpha$ 에 대해

: $s_n = \{s_0 + n\alpha\}$

는 좋은 준난수가 된다.

이것은 a가 1이고 m이 1인 선형 합동 생성기의 특별한 경우이다.

: $r_i = (a r_{i-1} + c) \bmod m$

위 식에서 c가 황금비의 소수부일 때 성능이 아주 좋다고 알려져 있으나, 백은비를 사용할 수도 있다. 다차원에서는 소수의 제곱근(의 소수부)를 사용할 수 있다.^[3]

임의의 무리수 $\alpha$ 에 대해, 수열

: $s_n = \{s_0 + n\alpha\}$

은 불일치가 $1/N$ 으로 수렴한다. 이 수열은 다음과 같이 재귀적으로 정의할 수 있다.

: $s_{n+1} = (s_n + \alpha)\bmod 1 \;.$

적절한 $\alpha$ 값은 독립적인 균등 확률 변수의 수열보다 낮은 불일치를 제공한다.

불일치는 $\alpha$ 의 근사 지수에 의해 제한될 수 있다. 만약 근사 지수가 $\mu$ 이면, 모든 $\varepsilon>0$ 에 대해 다음의 경계가 성립한다.^[3]

: $D_N((s_n)) = O_\varepsilon (N^{-1/(\mu-1)+\varepsilon}).$

투에-지겔-로스 정리에 따르면, 임의의 무리수 대수적 수의 근사 지수는 2이므로, 위에서 $N^{-1+\varepsilon}$ 의 경계를 제공한다.

위의 재귀 관계는 다음과 같은 품질이 낮은 의사 난수 생성기인 선형 합동 생성기에서 사용되는 재귀 관계와 유사하다:^[4]

: $r_i = (a r_{i-1} + c) \bmod m$

낮은 불일치 가산 재귀에서, ''a''와 ''m''은 1로 선택된다. 그러나, 이것은 독립적인 난수를 생성하지 않으므로, 독립성을 요구하는 목적에는 사용해서는 안 된다.

가장 낮은 불일치를 갖는 $c$ 의 값은 황금비의 소수 부분이다:^[5]

: $c = \frac{\sqrt{5}-1}{2} = \varphi - 1 \approx 0.618034.$

거의 그만큼 좋은 또 다른 값은 은비의 소수 부분이며, 이는 2의 제곱근의 소수 부분이다.

: $c = \sqrt{2}-1 \approx 0.414214. \,$

2차원 이상에서는 각 차원마다 별도의 준난수가 필요하다. 사용되는 편리한 값 집합은 2부터 시작하는 소수의 제곱근이며, 모두 1을 모듈로로 한다.

: $c = \sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{7}, \sqrt{11}, \ldots \,$

그러나 일반화된 황금비를 기반으로 한 값 집합이 더 균등하게 분포된 점을 생성하는 것으로 나타났다. ^[6]

== 판 데르 코르퓃 수열 (Van der Corput sequence) ==

요하네스 판데르코르퓟이 만든 판데르코르퓃 수열(Van der Corput sequence)은 주어진 진법에서 숫자를 뒤집는 방식으로 생성되는 기본적인 준난수 수열이다.

다음과 같이 정의한다.

: $n=\sum_{k=0}^{L-1}d_k(n)b^k$

이는 양의 정수 $n \geq 1$ 에 대한 $b$ 진법 표현이며, $0 \leq d_k(n) < b$ 이다. 다음을 설정한다.

: $g_b(n)=\sum_{k=0}^{L-1}d_k(n)b^{-k-1}.$

그러면 $b$ 에만 의존하는 상수 $C$ 가 존재하여 $(g_b(n))_{n \geq 1}$ 은 다음을 만족한다.

: $D^*_N(g_b(1),\dots,g_b(N))\leq C\frac{\log N}{N},$

여기서 $D^*_N$ 는 '''스타 불일치도'''이다.

== 홀턴 수열 (Halton sequence) ==

요하네스 판데르코르퓟이 만든 판데르코퓟 수열을 다차원으로 확장한 수열이 홀턴 수열이다.

임의의 차원 ''s''에 대해, 1보다 큰 임의의 상호 소수 정수 ''b''₁, ..., ''b''_''s''를 정의한다.

:x(n)=(g_b₁(n),...,g_{b_s}(n)).

그러면 수열 {''x''(''n'')}_''n''≥1이 다음을 만족하는 ''s''차원 수열이 되도록 하는 상수 ''C''가 존재한다. 이때 ''C''는 오직 ''b''₁, ..., ''b''_''s''에만 의존한다.

:D^*_N(x(1),...,x(N))≤C'{(log N)^s/N}.

== 소볼 수열 (Sobol sequence) ==

소볼 수열은 러시아에서 만들어진 저불일치 수열이다.

안토노프-살레예프 변형 소볼 수열은 ''w''개의 특수한 이진 분수 ''V''_''i'', ''i'' = 1, 2, …, ''w''(방향수) 집합으로부터 길이가 ''w''인 이진 분수 형태로 0과 1 사이의 숫자를 직접 생성한다. ''i''의 그레이 코드 ''G''(''i'')의 비트는 방향수를 선택하는 데 사용된다. 소볼 수열 값 ''s''_''i''를 얻으려면 ''i''의 그레이 코드의 이진 값과 적절한 방향수의 배타적 논리합을 취한다. 필요한 차원의 수는 ''V''_''i''의 선택에 영향을 미친다.

== 기타 생성 방법 ==

판데르코르퓃 수열(Van der Corput sequence)과 홀턴 수열(Halton sequence) 외에도 다양한 준난수 생성 방법이 존재한다. 네덜란드의 요하네스 판데르코르퓃이 만든 판데르코퓟 수열, 영국의 J. H. Halton이 만든 홀턴 수열, 러시아에서 만들어진 소볼 수열 등이 있다.

== 라틴 하이퍼큐브 샘플링 (Latin Hypercube Sampling) ==

다차원 공간에서 균일한 표본 추출을 위해 사용되는 방법이다.

4. 1. 무리수 기반 방법

모든 무리수

\alpha

에 대해

:

s_n = \{s_0 + n\alpha\}

는 좋은 준난수가 된다.

이것은 a가 1이고 m이 1인 선형 합동 생성기의 특별한 경우이다.

:

r_i = (a r_{i-1} + c) \bmod m

위 식에서 c가 황금비의 소수부일 때 성능이 아주 좋다고 알려져 있으나, 백은비를 사용할 수도 있다. 다차원에서는 소수의 제곱근(의 소수부)를 사용할 수 있다.^[3]

임의의 무리수

\alpha

에 대해, 수열

:

s_n = \{s_0 + n\alpha\}

은 불일치가

1/N

으로 수렴한다. 이 수열은 다음과 같이 재귀적으로 정의할 수 있다.

:

s_{n+1} = (s_n + \alpha)\bmod 1 \;.

적절한

\alpha

값은 독립적인 균등 확률 변수의 수열보다 낮은 불일치를 제공한다.

불일치는

\alpha

의 근사 지수에 의해 제한될 수 있다. 만약 근사 지수가

\mu

이면, 모든

\varepsilon>0

에 대해 다음의 경계가 성립한다:^[3]

:

D_N((s_n)) = O_\varepsilon (N^{-1/(\mu-1)+\varepsilon}).

투에-지겔-로스 정리에 따르면, 임의의 무리수 대수적 수의 근사 지수는 2이므로, 위에서

N^{-1+\varepsilon}

의 경계를 제공한다.

위의 재귀 관계는 다음과 같은 품질이 낮은 의사 난수 생성기인 선형 합동 생성기에서 사용되는 재귀 관계와 유사하다:^[4]

:

r_i = (a r_{i-1} + c) \bmod m

낮은 불일치 가산 재귀에서, ''a''와 ''m''은 1로 선택된다. 그러나, 이것은 독립적인 난수를 생성하지 않으므로, 독립성을 요구하는 목적에는 사용해서는 안 된다.

가장 낮은 불일치를 갖는

c

의 값은 황금비의 소수 부분이다:^[5]

:

c = \frac{\sqrt{5}-1}{2} = \varphi - 1 \approx 0.618034.

거의 그만큼 좋은 또 다른 값은 은비의 소수 부분이며, 이는 2의 제곱근의 소수 부분이다.

:

c = \sqrt{2}-1 \approx 0.414214. \,

2차원 이상에서는 각 차원마다 별도의 준난수가 필요하다. 사용되는 편리한 값 집합은 2부터 시작하는 소수의 제곱근이며, 모두 1을 모듈로로 한다.

:

c = \sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{7}, \sqrt{11}, \ldots \,

그러나 일반화된 황금비를 기반으로 한 값 집합이 더 균등하게 분포된 점을 생성하는 것으로 나타났다. ^[6]

4. 1. 1. 판 데르 코르퓃 수열 (Van der Corput sequence)

요하네스 판데르코르퓟이 만든 판데르코르퓃 수열(Van der Corput sequence)은 주어진 진법에서 숫자를 뒤집는 방식으로 생성되는 기본적인 준난수 수열이다.

다음과 같이 정의한다.

:

n=\sum_{k=0}^{L-1}d_k(n)b^k

이는 양의 정수

n \geq 1

에 대한

b

진법 표현이며,

0 \leq d_k(n) < b

이다. 다음을 설정한다.

:

g_b(n)=\sum_{k=0}^{L-1}d_k(n)b^{-k-1}.

그러면

b

에만 의존하는 상수

C

가 존재하여

(g_b(n))_{n \geq 1}

은 다음을 만족한다.

:

D^*_N(g_b(1),\dots,g_b(N))\leq C\frac{\log N}{N},

여기서

D^*_N

는 '''스타 불일치도'''이다.

4. 1. 2. 홀턴 수열 (Halton sequence)

요하네스 판데르코르퓟이 만든 판데르코퓟 수열을 다차원으로 확장한 수열이 홀턴 수열이다.

임의의 차원 ''s''에 대해, 1보다 큰 임의의 상호 소수 정수 ''b''₁, ..., ''b''_''s''를 정의한다.

:x(n)=(g_b₁(n),...,g_{b_s}(n)).

그러면 수열 {''x''(''n'')}_''n''≥1이 다음을 만족하는 ''s''차원 수열이 되도록 하는 상수 ''C''가 존재한다. 이때 ''C''는 오직 ''b''₁, ..., ''b''_''s''에만 의존한다.

:D^*_N(x(1),...,x(N))≤C'{(log N)^s/N}.

4. 2. 기타 생성 방법

판데르코퓃 수열(Van der Corput sequence)과 홀턴 수열(Halton sequence) 외에도 다양한 준난수 생성 방법이 존재한다. 네덜란드의 요하네스 판데르코르퓃이 만든 판데르코퓟 수열, 영국의 J. H. Halton이 만든 홀턴 수열, 러시아에서 만들어진 소볼 수열 등이 있다.

4. 2. 1. 소볼 수열 (Sobol sequence)

소볼 수열은 러시아에서 만들어진 저불일치 수열이다.

안토노프-살레예프 변형 소볼 수열은 ''w''개의 특수한 이진 분수 ''V''_''i'', ''i'' = 1, 2, …, ''w''(방향수) 집합으로부터 길이가 ''w''인 이진 분수 형태로 0과 1 사이의 숫자를 직접 생성한다. ''i''의 그레이 코드 ''G''(''i'')의 비트는 방향수를 선택하는 데 사용된다. 소볼 수열 값 ''s''_''i''를 얻으려면 ''i''의 그레이 코드의 이진 값과 적절한 방향수의 배타적 논리합을 취한다. 필요한 차원의 수는 ''V''_''i''의 선택에 영향을 미친다.

4. 2. 2. 라틴 하이퍼큐브 샘플링 (Latin Hypercube Sampling)

다차원 공간에서 균일한 표본 추출을 위해 사용되는 방법이다.

5. 응용 분야

준무작위 수는 관심 영역을 빠르고 균등하게 커버한다는 점에서 순수한 무작위 수보다 유리하다.

두 가지 유용한 응용 분야는 특성 함수를 찾는 것과 노이즈가 적은 결정론적 함수의 도함수를 찾는 것이다. 준무작위 수를 사용하면 고차 모멘트를 매우 빠르게 높은 정확도로 계산할 수 있다.

정렬을 포함하지 않는 응용 분야는 통계 분포의 평균, 표준 편차, 왜도, 첨도를 찾고, 어려운 결정론적 함수의 적분과 전역 최댓값과 최솟값을 찾는 데 사용될 수 있다. 준무작위 수는 또한 뉴턴-랩슨 방법과 같이 국부적으로만 작동하는 결정론적 알고리즘의 시작점을 제공하는 데 사용할 수도 있다.

준무작위 수는 검색 알고리즘과 결합하여 사용할 수도 있다. 검색 알고리즘과 함께 준무작위 수를 사용하여 통계 분포의 최빈값, 중앙값, 신뢰 구간 및 누적 분포와 결정론적 함수의 모든 국소 최솟값 및 모든 해를 찾을 수 있다.

5. 1. 수치 적분

준 몬테카를로 방법에서 저불일치 수열의 원소를 사용하여 함수의 적분을 계산하면, 콕스마-흐와프카 부등식에 의해 오차는 두 항의 곱으로 제한될 수 있다. 이 중 한 항은 적분 대상 함수에만 의존하며, 다른 하나는 사용된 점 집합, 즉 저불일치 수열의 불일치도에 의존한다.

구체적으로, [0,1] 구간에서 함수 ''f''의 적분은 해당 구간 내의 점 집합

\{x_1, \dots, x_N \}

에서 평가된 함수의 평균으로 근사할 수 있다.

:

\int_0^1 f(u)\,du \approx \frac{1}{N}\,\sum_{i=1}^N f(x_i).

점을

x_i = i/N

로 선택하면 ''직사각형 규칙''이 되고, 무작위(또는 의사 난수)로 분포시키면 몬테카를로 방법이 된다. 저불일치 수열을 사용하면 낮은 불일치도와 함께 점들을 구성할 수 있다.

준무작위 수는 관심 영역을 빠르고 균등하게 다룬다는 점에서 순수한 무작위 수보다 유리하다. 이를 통해 특성 함수를 찾거나, 노이즈가 적은 결정론적 함수의 도함수를 찾는 데 유용하게 활용될 수 있다. 또한, 고차 모멘트를 빠르고 정확하게 계산할 수 있다.

정렬을 포함하지 않는 응용 분야로는 통계 분포의 평균, 표준 편차, 왜도, 첨도를 구하거나, 어려운 결정론적 함수의 적분 및 전역 최댓값과 최솟값을 찾는 것이 있다. 또한, 뉴턴-랩슨 방법과 같이 국부적으로만 작동하는 결정론적 알고리즘의 시작점을 제공하는 데에도 사용될 수 있다.

5. 2. 최적화

준무작위 수는 관심 영역을 빠르고 균등하게 다룬다는 점에서 순수한 무작위 수보다 유리하다. 두 가지 유용한 응용 분야는 특성 함수를 찾는 것과 노이즈가 적은 결정론적 함수의 도함수를 찾는 것이다. 준무작위 수를 사용하면 고차 모멘트를 매우 빠르게 높은 정확도로 계산할 수 있다.

정렬을 포함하지 않는 응용 분야는 통계 분포의 평균, 표준 편차, 왜도, 첨도를 찾고, 어려운 결정론적 함수의 적분과 전역 최댓값과 최솟값을 찾는 데 사용될 수 있다. 준무작위 수는 또한 뉴턴-랩슨 방법과 같이 국부적으로만 작동하는 결정론적 알고리즘의 시작점을 제공하는 데 사용할 수도 있다.

준무작위 수는 검색 알고리즘과 결합하여 사용할 수도 있다. 검색 알고리즘과 함께 준무작위 수를 사용하여 통계 분포의 최빈값, 중앙값, 신뢰 구간 및 누적 분포와 결정론적 함수의 모든 국소 최솟값 및 모든 해를 찾을 수 있다.

5. 3. 금융 모델링

준무작위 수는 관심 영역을 빠르고 균등하게 커버한다는 점에서 순수한 무작위 수보다 유리하다. 특성 함수를 찾거나 노이즈가 적은 결정론적 함수의 도함수를 찾는 데 유용하게 사용될 수 있다. 또한, 준무작위 수를 사용하면 고차 모멘트를 매우 빠르게 높은 정확도로 계산할 수 있다.

정렬을 포함하지 않는 응용 분야로는 통계 분포의 평균, 표준 편차, 왜도, 첨도를 찾는 것, 그리고 어려운 결정론적 함수의 적분과 전역 최댓값과 최솟값을 찾는 것이 있다. 준무작위 수는 뉴턴-랩슨 방법과 같이 국부적으로만 작동하는 결정론적 알고리즘의 시작점을 제공하는 데 사용될 수 있다.

준무작위 수는 검색 알고리즘과 결합하여 통계 분포의 최빈값, 중앙값, 신뢰 구간 및 누적 분포와 결정론적 함수의 모든 국소 최솟값 및 모든 해를 찾는 데 사용될 수 있다.

5. 4. 통계 분석

저불일치 수열은 통계 분포의 평균, 표준 편차, 왜도, 첨도를 계산하는 데 유용하게 사용된다. 또한, 결정론적 함수의 적분 및 전역 최댓값과 최솟값을 찾는 데에도 활용될 수 있다.

준무작위 수는 관심 영역을 빠르고 균등하게 탐색한다는 점에서 순수한 무작위 수보다 유리하다. 이러한 특성 덕분에 특성 함수를 찾거나 노이즈가 적은 결정론적 함수의 도함수를 찾는 데 유용하며, 고차 모멘트를 매우 빠르게 높은 정확도로 계산할 수 있게 해준다.

뉴턴-랩슨 방법과 같이 국부적으로만 작동하는 결정론적 알고리즘의 시작점을 제공하는 데에도 사용할 수 있으며, 검색 알고리즘과 결합하여 통계 분포의 최빈값, 중앙값, 신뢰 구간 및 누적 분포를 찾고, 결정론적 함수의 모든 국소 최솟값 및 해를 찾는 데에도 활용할 수 있다.

6. 콕스마-흐와프카 부등식 (Koksma-Hlawka Inequality)

콕스마-흐와프카 부등식(Koksma-Hlawka Inequality)은 준 몬테카를로 방법에서 오차 범위를 결정하는 데 사용되는 중요한 부등식이다. 이 부등식은 함수의 변동(variation)과 점 집합의 불일치도(discrepancy)의 곱으로 오차 상한을 나타낸다.

함수 $f$ 가 유계변동을 가지며, $\overline{I}^s = [0, 1] \times \cdots \times [0, 1]$ ( $s$ 차원 단위 정육면체)에서 하디와 크라우스의 의미로 $V(f)$ 로 표현될 때, 임의의 $x_1, \ldots, x_N$ 에 대해 $I^s = [0, 1)^s = [0, 1) \times \cdots \times [0, 1)$ 에서 다음 부등식이 성립한다.

: $\left| \frac{1}{N} \sum_{i=1}^N f(x_i)$

\int_{\bar I^s} f(u)\,du \right|

\le V(f)\, D_N^* (x_1,\ldots,x_N).

여기서

D_N^* (x_1,\ldots,x_N)

는 점 집합

\{x_1,\ldots,x_N\}

의 불일치도이다.

콕스마–흐와프카 부등식은

I^s

내의 임의의 점 집합

\{x_1,\ldots,x_N\}

와 임의의

\varepsilon>0

에 대해, 유계 변동을 가지며

V(f) = 1

인 함수

f

가 존재하여 다음을 만족한다는 점에서 날카롭다.

:

\left| \frac{1}{N} \sum_{i=1}^N f(x_i)

\int_{\bar I^s} f(u)\,du \right|>D_{N}^{*}(x_1,\ldots,x_N)-\varepsilon.

따라서 수치 적분 규칙의 품질은 불일치도

D^*_N(x_1,\ldots,x_N)

에만 의존한다.

코시-슈바르츠 부등식을 적분 및 합에 적용하고 Hlawka–Zaremba 항등식을 사용하면 콕스마-흐와프카 부등식의

L^2

버전을 얻을 수 있다.

:

\left|\frac{1}{N} \sum_{i=1}^N f(x_i)

\int_{\bar I^s} f(u)\,du\right|\le

\|f\|_d \operatorname{disc}_d (\{t_i\}),

여기서

:

\operatorname{disc}_d(\{t_i\})=\left(\sum_{\emptyset\neq u\subseteq D}\int_{[0,1]^

} \operatorname{disc}(x_u,1)^2 \, dx_u\right)^{1/2}

이고

:

\|f\|_d = \left(\sum_{u\subseteq D}\int_{[0,1]^

}\left|\frac{\partial^

}{\partial x_u} f(x_u,1)\right|^2 dx_u\right)^{1/2}.

L^2

불일치는 주어진 점 집합에 대해 빠르고 명시적인 계산이 가능하기 때문에 실용적으로 매우 중요하다. 이를 통해

L^2

불일치를 기준으로 점 집합 최적화기를 쉽게 만들 수 있다.

7. 어르도스-투란-콕스마 부등식 (Erdős–Turán–Koksma Inequality)

계산적으로 큰 점 집합의 불일치도를 정확히 구하는 것은 어렵다. 어르도스–투란–콕스마 부등식은 상한을 제공한다.

: $x_1,\ldots,x_N$ 을 $I^s$ 의 점들이라고 하고, $H$ 를 임의의 양의 정수라고 하자. 그러면,

: $D_{N}^{*}(x_1,\ldots,x_N)\leq\left(\frac{3}{2}\right)^s\left(\frac{2}{H+1}+\sum_{0<\|h\|_{\infty}\leq H}\frac{1}{r(h)}\left|\frac{1}{N}\sum_{n=1}^{N} e^{2\pi i\langle h,x_n\rangle}\right|\right)$

이며, 여기서

: $r(h)=\prod_{i=1}^s\max\{1,|h_i|\}\quad\mbox{for}\quad h=(h_1,\ldots,h_s)\in\Z^s.$ 이다.

8. 주요 추측 (Main Conjectures)

준난수 수열의 불일치도 하한에 대한 추측들이 존재하며, 이는 준난수 연구의 중요한 미해결 문제이다.
추측 1. 차원 $s$ 에만 의존하는 상수 $c_s$ 가 존재하여

: $D_{N}^{*}(x_1,\ldots,x_N)\geq c_s\frac{(\ln N)^{s-1}}{N}$

는 모든 유한 점 집합 ${x_1,\ldots,x_N}$ 에 대해 성립한다.
추측 2. $s$ 에만 의존하는 상수 $c'_s$ 가 존재하여

: $D_{N}^{*}(x_1,\ldots,x_N)\geq c'_s\frac{(\ln N)^{s}}{N}$

는 무한 수열 $x_1,x_2,x_3,\ldots$ 의 무한한 수의 $N$ 에 대해 성립한다.

이러한 추측들은 동등하다. W. M. 슈미트는 $s \leq 2$ 인 경우에 대해 이 추측들을 증명했다. 더 높은 차원에서는 해당 문제는 여전히 미해결 상태이다. 가장 잘 알려진 하한은 마이클 레이시와 그의 협력자들의 연구에 기인한다.

9. 하한 (Lower Bounds)

$s=1$ 인 경우, 임의의 유한 점 집합 $\{x_1, \dots, x_N \}$ 에 대해 다음이 성립한다.

: $D_N^*(x_1,\ldots,x_N)\geq\frac{1}{2N}$

$s=2$ 인 경우, W. M. 슈미트는 임의의 유한 점 집합 $\{x_1, \dots, x_N \}$ 에 대해 다음이 성립함을 증명했다.

: $D_N^*(x_1,\ldots,x_N)\geq C\frac{\log N}{N}$

여기서

: $C=\max_{a\geq3}\frac{1}{16}\frac{a-2}{a\log a}=0.023335\dots.$

임의의 차원 $s > 1$ 에 대해, K. F. 로스는 다음을 증명했다.

: $D_N^*(x_1,\ldots,x_N)\geq\frac{1}{2^{4s}}\frac{1}{((s-1)\log2)^\frac{s-1}{2}}\frac{\log^{\frac{s-1}{2}}N}{N}$

는 임의의 유한 점 집합 $\{x_1, \dots, x_N \}$ 에 대해 성립한다. 요제프 베크(^[1])는 3차원에서 이 결과에 대한 이중 로그 개선을 확립했다. 이것은 D. 빌리크와 M. T. 레이시에 의해 단일 로그의 거듭제곱으로 개선되었다. $s$ > 2에 대한 가장 잘 알려진 경계는 D. 빌리크와 M. T. 레이시와 A. 바가르샤키안(^[2])에 의한 것이다. $\{x_1, \dots, x_N \}$ 에 대해, 다음이 성립하도록 하는 $t=0$ 이 존재한다.

: $D_N^*(x_1,\ldots,x_N)\geq t \frac{\log^{\frac{s-1}{2}+t}N}{N}$

는 임의의 유한 점 집합 $\{x_1, \dots, x_N \}$ 에 대해 성립한다.

10. 같이 보기

참조

_[1] 논문 A two-dimensional van Aardenne-Ehrenfest theorem in irregularities of distribution https://eudml.org/do[...]
_[2] 논문 On the Small Ball Inequality in all dimensions
_[3] 서적
_[4] 서적 The Art of Computer Programming
_[5] 웹사이트 Fibonacci Hashing: The Optimization that the World Forgot https://probablydanc[...] 2018-06-16
_[6] 웹사이트 The Unreasonable Effectiveness of Quasirandom Sequences http://extremelearni[...]
_[7] 서적 Monte Carlo Methods
_[8] 간행물 Poisson Disk Sampling http://devmag.org.za[...] 2008-03
_[9] 논문 Algorithm 659

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com