Sobol Sequence
Monte Carlo 방법에서는 표본을 반복해서 생성하고, 그 표본으로부터 기대값이나 옵션 가격을 근사한다. 이때 흔히 생성되는 표본을 난수라고 부르지만, 컴퓨터가 만들어 내는 수는 실제로는 알고리즘과 초기 seed에 의해 결정되는 의사난수(pseudorandom number) 이다.
의사난수는 무작위처럼 보이도록 만들어진다. 그러나 옵션 가격을 Monte Carlo 방법으로 평가할 때 중요한 것은 생성된 표본이 확률공간 전체를 얼마나 고르게 반영하는지이다.
같은 개수의 표본을 사용하더라도 어떤 영역에는 점이 몰리고 다른 영역에는 점이 거의 없다면, 시뮬레이션은 일부 시나리오를 반복해서 반영하고 다른 시나리오는 충분히 반영하지 못할 수 있다. 이러한 문제를 줄이기 위해 등장한 것이 준난수(quasi-random number) 이다.
\[\text{Monte Carlo의 의사난수} \longrightarrow \text{준난수} \longrightarrow \text{반데르코르퓌 수열} \longrightarrow \text{할튼 수열} \longrightarrow \text{소볼 수열}\]이 글에서는 위 흐름을 그대로 따라가면서, 발표자료에 등장한 수식과 계산 원리를 자세히 정리한다.
1. Monte Carlo에서 생성되는 값은 정말 난수인가
Monte Carlo 시뮬레이션에서는 어떤 확률분포를 따르는 표본을 여러 번 생성한다. 예를 들어 옵션 가격을 계산할 때는 미래의 주가 경로를 여러 개 만들고, 각 경로에서 발생하는 옵션의 payoff를 계산한 뒤 그 평균을 사용한다.
이 과정에서 생성되는 표본값을 보통 난수라고 부른다. 그러나 컴퓨터에서 생성되는 난수는 대부분 다음 두 요소에 의해 결정된다.
- 난수를 생성하는 알고리즘
- 알고리즘을 시작시키는 초기값인 seed
같은 알고리즘에 같은 seed를 넣으면 동일한 수열이 다시 생성된다. 따라서 컴퓨터가 생성하는 난수는 완전히 우연하게 발생하는 수가 아니라, 정해진 계산 규칙에 따라 생성되면서도 겉으로는 무작위처럼 보이는 수이다.
이를 의사난수라고 한다.
\[\text{의사난수} = \text{알고리즘} + \text{초기 seed}\]Monte Carlo 방법에서는 이러한 의사난수를 사용해 여러 시나리오를 만든다. 다만 문제는 의사난수가 무작위성을 잘 흉내 내더라도, 유한한 개수의 표본이 공간 전체를 고르게 덮는다는 보장은 없다는 점이다.
2. 옵션 가격 계산에서는 왜 표본의 배치가 중요한가
옵션 가격을 Monte Carlo 방법으로 평가할 때는 여러 표본 또는 여러 가격 경로를 생성한다. 이 표본들은 가능한 미래 상황을 나타낸다.
예를 들어 한 개의 표본이 특정한 미래 주가를 의미한다고 생각해 보자. 표본을 많이 생성할수록 더 많은 미래 상황을 고려할 수 있다. 하지만 표본이 특정 영역에 집중되어 있다면 실제로는 비슷한 상황만 반복해서 계산하게 된다.
다음 두 경우를 비교해 보자.
- 표본이 무작위로 생성되어 특정 영역에 우연히 몰리는 경우
- 표본이 전체 영역에 비교적 고르게 퍼지는 경우
두 번째 경우가 같은 수의 표본으로 더 다양한 시나리오를 반영할 가능성이 높다.
왼쪽의 Random 점들은 전체적으로는 사각형 안에 퍼져 있지만, 자세히 보면 점이 밀집된 부분과 비교적 비어 있는 부분이 존재한다.
반면 오른쪽의 Quasi-random 점들은 점과 점 사이의 간격이 더 규칙적으로 유지되며 사각형 전체를 비교적 고르게 채운다.
준난수는 엄밀한 의미에서 무작위인 수가 아니다. 정해진 규칙에 따라 생성되는 결정론적 수열이다. 하지만 점들이 $[0,1]$ 구간 또는 $[0,1]^d$ 공간을 고르게 채우도록 설계된다.
옵션 가격 계산에서는 준난수를 사용함으로써 시뮬레이션 경로가 다양한 시나리오를 더 고르게 반영하도록 만들 수 있다.
이번 글에서 다룰 대표적인 준난수열은 다음 세 가지이다.
\[\text{반데르코르퓌 수열} \quad \text{할튼 수열} \quad \text{소볼 수열}\]3. 반데르코르퓌 수열
반데르코르퓌 수열은 1차원 구간 $[0,1]$을 고르게 채우기 위한 가장 기본적인 준난수열이다.
핵심 아이디어는 정수 $n$을 어떤 진법으로 나타낸 뒤, 그 자릿수의 순서를 뒤집어 소수점 아래에 배치하는 것이다.
정수의 자릿수를 단순히 뒤집는 것처럼 보이지만, 이 과정은 새로 생성되는 값들이 기존 값 사이의 빈 공간을 차례로 채우도록 만든다.
반데르코르퓌 수열 생성 과정 반데르코르퓌 수열은 정수 $n$을 $b$진수로 표현한 뒤, 자릿수의 순서를 뒤집어 $[0,1]$ 구간의 소수로 변환하는 방식으로 생성한다.
1. 정수 $n$을 $b$진수로 표현한다.
기수(base)를 $b$라고 하자. 정수 $n$을 $b$진수로 표현하면
\[n=(\cdots d_3d_2d_1d_0)_b\]이다. 이를 각 자릿수의 합으로 나타내면
\[n=d_0b^0+d_1b^1+d_2b^2+\cdots+d_mb^m\]이다. 여기서 $d_i$는 $b$진수의 각 자릿수이며
\[d_i\in\{0,1,\ldots,b-1\}\]을 만족한다.
2. 자릿수의 순서를 뒤집어 소수점 아래에 배치한다.
정수 부분의 자릿수를 역순으로 배열하면
\[(\cdots d_3d_2d_1d_0)_b\quad\longrightarrow\quad(0.d_0d_1d_2d_3\cdots)_b\]가 된다. 즉, 가장 오른쪽에 있던 자릿수 $d_0$이 소수점 아래 첫 번째 자리로 이동하고, $d_1$은 두 번째 자리, $d_2$는 세 번째 자리로 이동한다.
3. 뒤집힌 $b$진 소수를 수치로 계산한다.
이렇게 얻은 반데르코르퓌 수열의 $n$번째 값은
\[h(n,b)=\sum_{i=0}^{m}d_ib^{-(i+1)}\]로 정의된다. 각 항을 풀어 쓰면
\[h(n,b)=\frac{d_0}{b}+\frac{d_1}{b^2}+\frac{d_2}{b^3}+\cdots+\frac{d_m}{b^{m+1}}\]이다. 따라서 각 자릿수는
\[d_0\longrightarrow\frac{d_0}{b},\qquad d_1\longrightarrow\frac{d_1}{b^2},\qquad d_2\longrightarrow\frac{d_2}{b^3}\]와 같이 변환된다.
정리하면 반데르코르퓌 수열은 정수 $n$을 $b$진수로 변환하고, 그 자릿수를 뒤집어 소수점 아래에 배치한 뒤, 이를 다시 수치로 계산하여 생성한다.
예제: 기수 $3$인 반데르코르퓌 수열의 $19$번째 값
정수 $19$를 기수 $3$으로 나타내 보자.
\[19=2\cdot3^2+0\cdot3^1+1\cdot3^0\]따라서
\[19=(201)_3\]이다.
반데르코르퓌 수열은 $3$진수의 자릿수를 뒤집어 소수점 아래에 배치하므로
\[(201)_3\quad\longrightarrow\quad(0.102)_3\]가 된다.
이제 $(0.102)_3$을 십진수 값으로 계산하면
\[h(19,3)=\frac{1}{3}+\frac{0}{3^2}+\frac{2}{3^3}\]이고,
\[h(19,3)=\frac{1}{3}+\frac{2}{27}=\frac{9}{27}+\frac{2}{27}=\frac{11}{27}\]이다.
따라서
\[\boxed{h(19,3)=\frac{11}{27}\approx0.4074074}\]를 얻는다.
출처 : Van der Corput sequence - Rosetta Code
그림의 위쪽 초록색 점들은 반데르코르퓌 수열의 값을 나타내고, 아래쪽 파란색 점들은 의사난수를 나타낸다.
의사난수는 점 사이의 간격이 불규칙하며 특정 구간에 점이 몰릴 수 있다. 반면 반데르코르퓌 수열은 기존 점 사이의 빈 구간을 반복적으로 나누어 채우기 때문에 전체 구간에 더 균등하게 퍼진 형태를 보인다.
반데르코르퓌 수열은 기본적으로 1차원 수열이다. 실제 옵션 가격 계산에서는 여러 개의 난수가 동시에 필요할 수 있으므로 이를 다차원으로 확장할 방법이 필요하다.
이 확장으로 등장하는 것이 할튼 수열이다.
4. 할튼 수열
할튼 수열은 반데르코르퓌 수열을 여러 차원에 결합한 다차원 저불일치 수열이다.
$d$차원 할튼 수열을 만들 때는 각 차원마다 서로 다른 소수를 기수로 사용한다.
예를 들어 2차원 할튼 수열에서는 보통 다음과 같이 구성한다.
\[\mathbf{x}_n = \left( h(n,2), h(n,3) \right)\]첫 번째 좌표는 기수 $2$의 반데르코르퓌 수열을 사용하고, 두 번째 좌표는 기수 $3$의 반데르코르퓌 수열을 사용한다.
3차원이라면 서로 다른 소수 $2,3,5$를 사용하여
\[\mathbf{x}_n = \left( h(n,2), h(n,3), h(n,5) \right)\]로 만든다.
일반적인 $d$차원 할튼 수열은 서로 다른 소수
\[p_1,p_2,\ldots,p_d\]를 이용하여
\[\mathbf{x}_n = \left( h(n,p_1), h(n,p_2), \ldots, h(n,p_d) \right)\]로 구성한다.
출처 : Uniform sequence (left) and Halton sequence (right) of length N = 256
왼쪽의 일반 난수는 사각형 전체에 퍼져 있지만 점이 가까이 모이는 부분과 넓은 빈 공간이 존재한다.
오른쪽의 할튼 수열은 점들이 일정한 방향성을 가지면서도 전체 영역을 비교적 고르게 채운다. 각 차원에서 서로 다른 기수를 사용하기 때문에 두 좌표가 같은 방식으로 반복되는 것을 피하고, 2차원 공간에 점을 분산시킬 수 있다.
할튼 수열은 낮은 차원에서는 전체 공간을 비교적 고르게 채운다. 그러나 차원이 높아지면 큰 소수를 기수로 사용하는 차원이 등장한다.
자료에서는 이러한 상황에서 특정 차원 쌍 사이에 규칙적인 패턴 또는 상관관계가 나타날 수 있음을 보여 준다.
출처 : Problems with correlation in two-dimensional Halton sequences
그림을 보면 작은 소수를 사용하는 차원 조합에서는 점들이 비교적 고르게 분포하지만, 큰 소수를 사용하는 일부 차원 조합에서는 점들이 대각선 모양의 띠를 형성한다.
점들이 사각형 전체를 자유롭게 채우지 않고 몇 개의 선을 따라 배열되면, 해당 차원들이 표현해야 하는 다양한 조합을 충분히 반영하지 못할 수 있다.
\[\text{단순한 자릿수 반사 방식} \longrightarrow \text{차원이 커질수록 패턴이 망가질 수 있음}\]이러한 문제에 대한 대안으로 제시되는 수열이 소볼 수열이다.
5. 소볼 수열의 기본 아이디어
소볼 수열은 이진수 구조를 기반으로 하며, 각 차원에 적절한 방향수(direction numbers) 를 설정한 뒤 XOR 연산으로 좌표를 생성한다.
정의를 정리하면 다음과 같다.
소볼 수열은 이진수 기반의 방향수와 XOR 연산을 이용하여 고차원 공간에 점들을 균등하게 배치하도록 생성한 저불일치 준난수열이다.
소볼 수열의 한 좌표는 다음과 같은 형태로 표현된다.
\[x_n = a_1v_1 \oplus a_2v_2 \oplus \cdots\]여기서
- $a_i$는 정수 $n$의 이진수 자릿수
- $v_i$는 방향수
- $\oplus$는 XOR 연산
이다.
이 식을 이해하려면 다음 네 가지가 필요하다.
- 정수의 이진수 표현
- XOR 연산
- 방향수
- 방향수를 생성하는 원시다항식
6. 정수를 이진수로 표현하기
6.1 이진 전개
정수 $n$은 이진수로 다음과 같이 표현할 수 있다.
\[n = \sum_{i=0}^{I} a_i(n)2^i, \qquad n\ge0\]여기서
\[a_i(n)\in\{0,1\}\]은 정수 $n$의 $i$번째 이진수 계수이다.
이진수의 각 자릿수는 $0$ 또는 $1$이므로, $a_i(n)$은 해당 위치의 $2^i$가 정수 $n$을 구성하는 데 포함되는지를 나타낸다.
6.2 가장 큰 지수 $I$
기수 $p$로 정수 $n$을 표현할 때 가장 큰 지수를 $I$라고 하면
\[p^I\le n<p^{I+1}\]이다.
양변에 로그를 적용하면
\[I \le \frac{\ln n}{\ln p} < I+1\]이므로
\[I = \left\lfloor \frac{\ln n}{\ln p} \right\rfloor\]이다.
소볼 수열은 이진수 기반이므로 $p=2$를 사용한다.
\[I = \left\lfloor \log_2n \right\rfloor\]예를 들어 정수 $13$을 이진수로 나타내면
\[13 = 1\cdot2^3 + 1\cdot2^2 + 0\cdot2^1 + 1\cdot2^0\]이다.
따라서
\[13=(1101)_2\]이다.
가장 큰 지수는 $3$이므로
\[I=3\]이다.
로그를 사용해도
\[\log_2 13 \approx3.70\]이고,
\[\lfloor3.70\rfloor=3\]이므로 같은 결과가 나온다.
즉, $n=13$의 이진수 계수는 오른쪽부터
\[a_0=1,\qquad a_1=0,\qquad a_2=1,\qquad a_3=1\]이다.
소볼 수열에서는 이 계수들 중 값이 $1$인 위치에 대응하는 방향수만 XOR 연산에 참여한다.
7. XOR 연산
7.1 OR 연산과 XOR 연산의 차이
OR 연산은 두 비트 중 하나 이상이 $1$이면 결과를 $1$로 만드는 포괄적 논리합(inclusive OR) 이다.
| 첫 번째 비트 | 두 번째 비트 | OR |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
예를 들어
\[0101\ \mathrm{OR}\ 0011 = 0111\]이다.
반면, XOR 연산은 두 비트 중 오직 한쪽만 $1$인 경우에만 결과를 $1$로 만드는 배타적 논리합(exclusive OR) 이다.
| 첫 번째 비트 | 두 번째 비트 | XOR |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
따라서
\[0101\oplus0011 = 0110\]이다.
각 자릿수별로 보면
\[0\oplus0=0,\qquad 1\oplus0=1,\qquad 0\oplus1=1,\qquad 1\oplus1=0.\]마지막 자리에서는 두 수가 모두 $1$이므로 XOR 결과는 $0$이 된다.
7.2 소볼 수열에서 XOR가 사용되는 방식
소볼 수열에서는 정수 $n$의 이진수 계수가 $1$인 위치에 대응하는 방향수만 선택하여 XOR한다. 이때 이진수의 자릿수는 $2^0$부터 시작하지만 방향수의 번호는 $v_1$부터 시작하므로, $2^i$ 자리의 계수 $a_i$는 방향수 $v_{i+1}$에 대응한다.
예를 들어
\[n=(1101)_2=1\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0\]이면
\[a_0=1,\qquad a_1=0,\qquad a_2=1,\qquad a_3=1\]이다. 따라서 $a_0$, $a_2$, $a_3$에 대응하는 방향수 $v_1$, $v_3$, $v_4$만 선택되고, $a_1=0$에 대응하는 $v_2$는 계산에서 제외된다. 그러므로
\[x_n=v_1\oplus v_3\oplus v_4\]로 계산된다.
8. 방향수
방향수 $v_i$는 소볼 수열에서 각 점의 좌표를 만들 때 사용하는 기본 단위이다.
발표자료에서는 방향수를 다음과 같이 정의한다.
\[v_i = \frac{q_i}{2^i}\]여기서 정수 $q_i$는 다음 조건을 만족한다.
\[0<q_i<2^i\]그리고
\[q_i\text{는 홀수}\]이다.
$2^i$로 나누는 이유는 정수 $q_i$를 $[0,1]$ 구간에서 사용할 수 있는 이진소수로 변환하기 위해서이다.
예제: 방향수 $v_i$ 계산
방향수는 정수 $q_i$를 $2^i$로 나누어 계산한다.
\[v_i=\frac{q_i}{2^i}\]먼저 $q_1=1$이면
\[v_1=\frac{q_1}{2^1}=\frac{1}{2}=0.1_2\]이다.
다음으로 $q_2=3$이면
\[v_2=\frac{q_2}{2^2}=\frac{3}{4}=0.11_2\]이다.
마찬가지로 $q_3=5$이면
\[v_3=\frac{q_3}{2^3}=\frac{5}{8}=0.101_2\]이다.
따라서 처음 세 방향수는
\[v_1=0.1_2,\qquad v_2=0.11_2,\qquad v_3=0.101_2\]로 나타낼 수 있다.
방향수는 소볼 수열의 좌표를 생성할 때 XOR 연산에 사용되는 기본값이다. 각 방향수가 어떤 이진 비트 구조를 가지는지에 따라 소볼 점이 이동하는 방향과 공간을 채우는 방식이 결정된다.
9. 원시다항식과 방향수의 생성
앞에서 설명하였듯이 각 차원에서 소볼 점들이 공간을 고르게 채우도록 방향을 조절하는 방향수를 생성하기 위해, 계수가 이진수로 이루어진 $d$차 원시다항식을 사용한다.
\[P(x) = x^d + \alpha_1x^{d-1} + \cdots + \alpha_{d-1}x + 1\]여기서
\[\alpha_k\in\{0,1\}\]이다.
발표자료에서는 이를 원시다항식이라고 부르며, 원시다항식이 소볼 수열의 방향수를 생성하는 재귀 규칙을 결정한다고 설명한다.
각 차원마다 사용하는 다항식과 초기 방향수가 달라질 수 있는데 이 차이가 각 차원의 점 배치가 서로 동일한 패턴을 반복하지 않도록 만든다.
방향수 생성을 위한 초기값 조건
$d$차 원시다항식을 사용하는 경우, 방향수의 분자가 되는 처음 $d$개의 값
\[q_1,q_2,\ldots,q_d\]는 재귀식을 적용하기 전에 미리 주어져야 한다.
각 초기값 $q_i$는 다음 두 조건을 만족해야 한다.
\[0<q_i<2^i\]그리고 $q_i$는 홀수여야 한다.
따라서 $q_i$는
\[q_i\in\{1,3,5,\ldots,2^i-1\}\]중 하나로 선택된다.
예를 들어 $i=3$이면
\[0<q_3<2^3=8\]이고 $q_3$는 홀수여야 하므로
\[q_3\in\{1,3,5,7\}\]중 하나를 초기값으로 선택할 수 있다.
이 초기값들은 이후의 방향수들을 재귀적으로 생성하는 출발점이며, 초기값을 어떻게 선택하는지에 따라 소볼 수열의 점들이 공간에 배치되는 패턴이 달라진다.
초기값 $q_1,\ldots,q_d$가 주어졌다면, 이후의 값 $q_{d+1},q_{d+2},\ldots$는 원시다항식의 계수 $\alpha_k$를 이용하여 재귀적으로 생성한다.
$q_i$의 재귀 생성
$d$차 원시다항식
\[P(x)=x^d+\alpha_1x^{d-1}+\cdots+\alpha_{d-1}x+1\]이 주어졌을 때, 이후의 $q_i$는 다음과 같이 계산한다.
\[q_i=2\alpha_1q_{i-1}\oplus2^2\alpha_2q_{i-2}\oplus\cdots\oplus2^{d-1}\alpha_{d-1}q_{i-d+1}\oplus2^dq_{i-d}\oplus q_{i-d}\]여기서 $\alpha_k\in{0,1}$이므로, $\alpha_k=1$인 항만 실제 XOR 연산에 포함되고 $\alpha_k=0$인 항은 제외된다.
이 식에 나타나는 $2^kq$는 일반적인 곱셈으로 계산할 수도 있지만, 이진수 관점에서는 $q$의 비트를 왼쪽으로 $k$자리 이동시키는 연산으로 이해할 수 있다.
예를 들어 $q=(101)_2$라면
\[2q=(1010)_2\]가 되어 비트가 왼쪽으로 한 자리 이동하고,
\[2^2q=(10100)_2\]가 되어 비트가 왼쪽으로 두 자리 이동한다.
따라서 $q_i$의 재귀식은 기존의 $q_{i-1},q_{i-2},\ldots,q_{i-d}$를 필요한 만큼 왼쪽으로 이동시킨 뒤, 그 결과들을 XOR하여 새로운 $q_i$를 만드는 과정이다.
방향수는 방향수의 분자 $q_i$를 $2^i$로 나눈 값으로 정의된다.
\[v_i=\frac{q_i}{2^i}\]따라서 $q_i$의 재귀식을 $v_i$의 형태로 바꾸면 방향수 자체를 직접 생성하는 재귀식을 얻을 수 있다.
$v_i$의 재귀 생성
방향수 $v_i$는 기존 방향수들을 XOR하여 다음과 같이 생성한다.
\[v_i=\alpha_1v_{i-1}\oplus\alpha_2v_{i-2}\oplus\cdots\oplus\alpha_{d-1}v_{i-d+1}\oplus v_{i-d}\oplus\frac{v_{i-d}}{2^d}\]이 식에서도 $\alpha_k=1$인 항만 XOR 연산에 포함된다. 마지막 항 $\frac{v_{i-d}}{2^d}$는 $v_{i-d}$의 이진소수 비트를 오른쪽으로 $d$자리 이동시킨 값에 해당한다.
$q_i$의 재귀식은 정수 형태의 방향수 분자를 생성하는 식이고, $v_i$의 재귀식은 이를 $[0,1]$ 구간의 이진소수 형태로 나타낸 식이다. 두 식은 같은 생성 과정을 각각 정수 표현과 이진소수 표현으로 나타낸 것이다.
방향수 생성 과정
- 차수 $d$의 원시다항식을 선택한다.
- 조건을 만족하는 초기값 $q_1,\ldots,q_d$를 정한다.
- 원시다항식의 계수 $\alpha_k$를 재귀식에 대입하여 $q_{d+1},q_{d+2},\ldots$를 계산한다.
- 각 $q_i$를 $2^i$로 나누어 방향수 $v_i=\frac{q_i}{2^i}$를 구한다.
- 생성된 방향수들을 소볼 수열의 XOR 연산에 사용한다.
10. 소볼 수열을 직접 계산하는 알고리즘
정수 $n$을 이진수로 나타내면
\[n = a_0(n)2^0 + a_1(n)2^1 +\cdots+ a_I(n)2^I\]이다.
이때 소볼 수열의 값은 $a_i(n)=1$인 위치의 방향수를 XOR하여 구한다.
인덱스를 방향수 번호에 맞추어 쓰면
\[x_n = a_0(n)v_1 \oplus a_1(n)v_2 \oplus \cdots \oplus a_I(n)v_{I+1}\]이다.
여기서 $a_i(n)=0$이면 해당 방향수는 사용하지 않고, $a_i(n)=1$이면 해당 방향수를 XOR한다.
직접 계산 절차
- 계산하려는 인덱스 $n$을 이진수로 변환한다.
- 이진수에서 $1$인 비트의 위치를 찾는다.
- 각 위치에 대응하는 방향수를 선택한다.
- 선택된 방향수들의 이진소수 표현을 XOR한다.
- 최종 이진소수를 십진수로 변환한다.
예제: 4차 원시다항식으로 $q_5$와 $v_5$ 구하기
다음 4차 원시다항식을 사용하여 새로운 방향수의 분자 $q_5$와 방향수 $v_5$를 계산해 보자.
\[P(x)=x^4+x^3+x^2+x+1\]이 다항식의 차수는
\[d=4\]이고, 각 항의 계수는
\[\alpha_1=\alpha_2=\alpha_3=1\]이다.
초기값은 다음과 같이 주어진다.
\[q_1=1,\qquad q_2=3,\qquad q_3=5,\qquad q_4=11\]$d=4$이고 모든 계수 $\alpha_1,\alpha_2,\alpha_3$가 $1$이므로, $q_i$의 재귀식은
\[q_i=2q_{i-1}\oplus4q_{i-2}\oplus8q_{i-3}\oplus16q_{i-4}\oplus q_{i-4}\]가 된다.
이제 $i=5$를 대입하면
\[q_5=2q_4\oplus4q_3\oplus8q_2\oplus16q_1\oplus q_1\]이다.
주어진 초기값을 대입하면
\[q_5=2(11)\oplus4(5)\oplus8(3)\oplus16(1)\oplus1=22\oplus20\oplus24\oplus16\oplus1\]을 얻는다.
각 값을 동일한 길이의 이진수로 나타내면
\[22=(10110)_2,\qquad20=(10100)_2,\qquad24=(11000)_2,\qquad16=(10000)_2,\qquad1=(00001)_2\]이다.
이 값들을 차례로 XOR하면
\[10110\oplus10100=00010\] \[00010\oplus11000=11010\] \[11010\oplus10000=01010\] \[01010\oplus00001=01011\]이므로
\[q_5=(01011)_2=11\]을 얻는다.
마지막으로 방향수는 $v_i=\frac{q_i}{2^i}$로 정의되므로
\[v_5=\frac{q_5}{2^5}=\frac{11}{32}=0.01011_2\]이다.
따라서 이 예제에서 새롭게 생성된 방향수의 분자와 방향수는
\[\boxed{q_5=11,\qquad v_5=\frac{11}{32}}\]이다. 같은 재귀 과정을 반복하면 $q_6,q_7,\ldots$와 이에 대응하는 방향수 $v_6,v_7,\ldots$를 필요한 만큼 계속 생성할 수 있다.
11. Gray Code가 필요한 이유
소볼 수열의 직접 계산식은 정확하지만, 새로운 점을 만들 때마다 정수 $n$의 이진수 표현을 다시 확인하고 여러 방향수를 XOR해야 할 수 있다.
일반 이진수에서는 연속된 정수로 넘어갈 때 여러 비트가 동시에 바뀌는 경우가 있다.
예를 들어
\[0111 \longrightarrow 1000\]에서는 네 개의 비트가 모두 바뀐다.
이 경우 이전 소볼 값에서 다음 값을 만들 때 여러 방향수를 동시에 반영해야 한다.
연속적인 점을 빠르게 생성해야 하는 상황에서는 이러한 방식이 비효율적일 수 있다.
11.1 Gray Code
Gray code는 연속된 두 수가 오직 한 비트만 다르도록 만든 이진 표현 방식이다.
정수 $j$의 Gray code는
\[G(j) = j \oplus \left\lfloor \frac{j}{2} \right\rfloor\]로 정의된다.
$\lfloor x\rfloor$는 $x$보다 작거나 같은 가장 큰 정수이다.
| 구분 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 십진수 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 이진수 | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| Gray code | 000 | 001 | 011 | 010 | 110 | 111 | 101 | 100 |
발표자료의 3비트 Gray Code 예시
표를 보면 일반 이진수에서는
\[011\longrightarrow100\]처럼 여러 비트가 바뀌지만, Gray code에서는 인접한 두 값 사이에서 한 비트만 변한다.
예를 들어
\[010\longrightarrow110\]에서는 첫 번째 비트 하나만 바뀐다.
예제: 정수 $2$의 Gray code 계산
정수 $j$의 Gray code는 다음 식으로 정의된다.
\[G(j)=j\oplus\left\lfloor\frac{j}{2}\right\rfloor\]여기서 $j=2$를 대입하면
\[G(2)=2\oplus\left\lfloor\frac{2}{2}\right\rfloor=2\oplus1\]이다.
이제 두 정수를 같은 자릿수의 이진수로 나타내면
\[2=(10)_2,\qquad1=(01)_2\]이다.
각 비트에 XOR 연산을 적용하면
\[(10)_2\oplus(01)_2=(11)_2\]이므로
\[\boxed{G(2)=(11)_2=3}\]을 얻는다.
따라서 정수 $2$의 일반 이진수 표현은 $(10)_2$이지만, 이에 대응하는 Gray code는 $(11)_2$이다.
12. Gray Code를 이용한 소볼 수열의 순차 생성
12.1 한 개의 방향수만 바꾸기
Gray code에서는 연속된 두 수가 한 비트만 다르다. 따라서 이전 소볼 값에서 방향수 하나만 XOR하면 다음 값을 얻을 수 있다.
발표자료의 순차 생성식은
\[\boxed{ x_{n+1} = x_n \oplus v_c }\]이다.
여기서
- $x_n$: 현재 소볼 수열 값
- $x_{n+1}$: 다음 소볼 수열 값
- $v_c$: $c$번째 방향수
- $c$: 정수 $n$의 이진수 표현에서 오른쪽부터 처음으로 $0$이 나타나는 위치
이다.
12.2 $c$의 의미
정수 $n$의 이진수 표현을 오른쪽부터 확인한다.
처음 발견되는 $0$의 위치를 $c$라고 한다. 가장 오른쪽 자리를 첫 번째 위치로 센다.
예를 들어
\[n=10\]이면
\[10_{10}=(1010)_2\]이다.
오른쪽부터 보면 첫 번째 비트가 바로 $0$이다. 따라서
\[c=1\]이다.
그러므로
\[x_{11} = x_{10} \oplus v_1\]로 계산한다.
| 현재 $n$ | $n$의 이진수 | 오른쪽부터 처음인 $0$ | 다음 값을 만들 때 사용하는 방향수 |
|---|---|---|---|
| 0 | 0000 | 1번째 | $v_1$ |
| 1 | 0001 | 2번째 | $v_2$ |
| 2 | 0010 | 1번째 | $v_1$ |
| 3 | 0011 | 3번째 | $v_3$ |
처음 몇 단계는 다음과 같이 해석된다. 따라서 순차적으로
\[x_1=x_0\oplus v_1\] \[x_2=x_1\oplus v_2\] \[x_3=x_2\oplus v_1\] \[x_4=x_3\oplus v_3\]와 같이 계산한다.
이 방식의 장점은 매 단계에서 방향수 하나만 XOR하면 된다는 것이다.
13. 1차원 소볼 수열 출력 예
발표자료의 4차 다항식 예제에서는 초기 방향수 분자
\[q_1=1,\qquad q_2=3,\qquad q_3=5,\qquad q_4=11\]을 사용하고, 시작값을 $0.5$로 두어 다음과 같은 값을 제시한다.
| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $x_n$ | 0.5000 | 0.0000 | 0.7500 | 0.2500 | 0.8750 | 0.3750 | 0.6250 | 0.1250 | 0.5625 | 0.0625 | 0.8125 |
표에 제시된 값은 다음과 같다.
| $n$ | $x_n$ |
|---|---|
| 0 | 0.5000 |
| 1 | 0.0000 |
| 2 | 0.7500 |
| 3 | 0.2500 |
| 4 | 0.8750 |
| 5 | 0.3750 |
| 6 | 0.6250 |
| 7 | 0.1250 |
| 8 | 0.5625 |
| 9 | 0.0625 |
| 10 | 0.8125 |
값의 순서를 보면 단순히 왼쪽에서 오른쪽으로 증가하지 않는다.
처음에는
\[0.5,\quad0\]을 방문하고, 다음에는
\[0.75,\quad0.25\]를 방문한다.
그다음에는
\[0.875,\quad0.375,\quad0.625,\quad0.125\]와 같이 기존 점 사이의 빈 구간을 채운다.
즉, 소볼 수열은 수의 크기 순서대로 움직이는 수열이 아니라 $[0,1]$ 구간의 서로 다른 영역을 차례로 방문하도록 구성된 수열이다.
14. 예제: $P(x)=x^3+x+1$일 때 23번째 소볼 값
예제: $x_{23}$ 계산
다음 원시다항식과 초기값이 주어졌다고 하자.
\[P(x)=x^3+x+1\] \[m_1=1,\qquad m_2=3,\qquad m_3=7\]앞에서는 방향수의 분자를 $q_i$로 표기했지만, 이 예제에서는 발표자료의 표기에 맞추어 $m_i$를 사용한다.
1. 방향수 분자의 재귀식
주어진 다항식에서
\[d=3,\qquad \alpha_1=0,\qquad \alpha_2=1\]이므로 방향수 분자의 재귀식은
\[m_i=4m_{i-2}\oplus8m_{i-3}\oplus m_{i-3}\]이다.
2. $m_4$ 계산
재귀식에 $i=4$를 대입하면
\[m_4=4m_2\oplus8m_1\oplus m_1=4(3)\oplus8(1)\oplus1=12\oplus8\oplus1\]이다.
각 값을 같은 길이의 이진수로 나타내면
\[12=(1100)_2,\qquad8=(1000)_2,\qquad1=(0001)_2\]이고, 차례로 XOR하면
\[1100\oplus1000=0100,\qquad0100\oplus0001=0101\]이다. 따라서
\[m_4=(0101)_2=5\]를 얻는다.
3. $m_5$ 계산
재귀식에 $i=5$를 대입하면
\[m_5=4m_3\oplus8m_2\oplus m_2=4(7)\oplus8(3)\oplus3=28\oplus24\oplus3\]이다.
각 값을 이진수로 나타내면
\[28=(11100)_2,\qquad24=(11000)_2,\qquad3=(00011)_2\]이고, 차례로 XOR하면
\[11100\oplus11000=00100,\qquad00100\oplus00011=00111\]이다. 따라서
\[m_5=(00111)_2=7\]을 얻는다.
4. 필요한 방향수 계산
방향수는
\[v_i=\frac{m_i}{2^i}\]로 정의되므로
\[v_1=\frac12,\qquad v_2=\frac34,\qquad v_3=\frac78,\qquad v_4=\frac5{16},\qquad v_5=\frac7{32}\]이다.
5. 정수 $23$의 Gray code 계산
정수 $23$은
\[23=(10111)_2\]이고,
\[\left\lfloor\frac{23}{2}\right\rfloor=11=(01011)_2\]이다. 따라서
\[G(23)=23\oplus\left\lfloor\frac{23}{2}\right\rfloor=(10111)_2\oplus(01011)_2=(11100)_2\]이다.
Gray code $(11100)_2$에서 값이 $1$인 비트는 세 번째, 네 번째, 다섯 번째 비트이므로
\[x_{23}=v_3\oplus v_4\oplus v_5\]로 계산한다.
6. 방향수의 XOR 계산
XOR 연산을 위해 세 방향수의 분모를 $32$로 통일하면
\[v_3=\frac78=\frac{28}{32}=0.11100_2,\qquad v_4=\frac5{16}=\frac{10}{32}=0.01010_2,\qquad v_5=\frac7{32}=0.00111_2\]이다.
이를 차례로 XOR하면
\[0.11100_2\oplus0.01010_2=0.10110_2\] \[0.10110_2\oplus0.00111_2=0.10001_2\]이므로
\[x_{23}=0.10001_2\]이다.
이를 십진수로 변환하면
\[x_{23}=\frac12+\frac1{32}=\frac{16}{32}+\frac1{32}=\frac{17}{32}\]이다. 따라서 최종적으로
\[\boxed{x_{23}=\frac{17}{32}=0.53125}\]를 얻는다.
15. 소볼 수열의 전체 생성 알고리즘
소볼 수열의 생성 과정은 크게 두 단계로 나눌 수 있다.
첫 번째 단계에서는 원시다항식과 초기값을 이용하여 각 차원에 필요한 방향수를 생성한다. 두 번째 단계에서는 정수 $n$의 Gray code와 생성된 방향수를 결합하여 소볼 값을 계산한다.
15.1 방향수 생성
1단계: 방향수 준비
먼저 각 차원에서 사용할 $d$차 원시다항식을 정한다.
\[P(x)=x^d+\alpha_1x^{d-1}+\cdots+\alpha_{d-1}x+1\]다음으로 재귀식의 출발점이 되는 초기값
\[q_1,q_2,\ldots,q_d\]를 정한다.
각 초기값은
\[0<q_i<2^i\]를 만족하는 홀수여야 한다.
이후 원시다항식의 계수 $\alpha_k$를 이용한 재귀식으로
\[q_{d+1},q_{d+2},\ldots\]를 필요한 만큼 생성한다.
마지막으로 각 $q_i$를
\[v_i=\frac{q_i}{2^i}\]로 변환하면 소볼 수열 계산에 사용되는 방향수 $v_i$를 얻는다.
방향수 생성은 소볼 값을 계산하기 전에 수행하는 준비 단계이다. 이 단계 자체는 Gray code 알고리즘이 아니라, 이후 Gray code와 결합할 방향수를 만드는 과정이다.
15.2 특정한 $n$번째 소볼 값의 직접 계산
특정한 $n$번째 값 $x_n$을 바로 계산하려면 정수 $n$의 Gray code를 사용한다.
2단계: Gray code를 이용한 직접 계산
먼저 정수 $n$의 Gray code를 계산한다.
\[G(n)=n\oplus\left\lfloor\frac{n}{2}\right\rfloor\]Gray code를 이진수로 나타내고, 값이 $1$인 비트의 위치를 찾는다.
Gray code의 $i$번째 비트가 $1$이면 그 위치에 대응하는 방향수 $v_i$를 선택하고, 비트가 $0$이면 해당 방향수를 사용하지 않는다.
선택된 방향수를 모두 XOR하면 $n$번째 소볼 값을 얻는다.
\[x_n=g_1v_1\oplus g_2v_2\oplus\cdots\]여기서 $g_i\in{0,1}$는 $G(n)$의 $i$번째 이진수 계수이다.
예를 들어
\[G(n)=(10110)_2\]이라면 값이 $1$인 첫 번째, 세 번째, 네 번째 비트에 대응하는 방향수만 선택하므로
\[x_n=v_1\oplus v_3\oplus v_4\]와 같이 계산한다.
이 방식은 특정한 $n$번째 값을 이전 값 없이 바로 계산할 때 사용하는 Gray code 기반 직접 계산법이다.
15.3 연속된 소볼 값의 순차 생성
소볼 값을 $x_0,x_1,x_2,\ldots$의 순서로 연속해서 생성할 때는 매번 Gray code 전체를 다시 계산할 필요가 없다.
Gray code에서는 인접한 두 값이 오직 한 비트만 다르기 때문이다.
3단계: Gray code를 이용한 순차 계산
현재 인덱스 $n$을 이진수로 나타낸다.
오른쪽부터 처음으로 $0$이 나타나는 비트의 위치를 $c$라고 한다.
그러면 다음 소볼 값은 현재 값에 $c$번째 방향수 하나만 XOR하여 계산할 수 있다.
\[x_{n+1}=x_n\oplus v_c\]
예를 들어
\[n=10=(1010)_2\]이면 오른쪽에서 첫 번째 비트가 $0$이므로
\[c=1\]이다. 따라서
\[x_{11}=x_{10}\oplus v_1\]로 계산한다.
이 방식은 Gray code에서 연속된 두 값 사이에 하나의 비트만 변한다는 성질을 이용한다. 따라서 이전 소볼 값이 주어져 있다면 방향수 하나만 XOR하여 다음 값을 빠르게 생성할 수 있다.
15.4 두 계산 방식의 차이
| 구분 | 직접 계산 | 순차 계산 |
|---|---|---|
| 목적 | 특정한 $x_n$을 바로 계산 | $x_n$에서 $x_{n+1}$을 계산 |
| 사용하는 정보 | $n$의 전체 Gray code | $n$의 오른쪽부터 첫 번째 $0$ 위치 |
| 계산식 | $x_n=g_1v_1\oplus g_2v_2\oplus\cdots$ | $x_{n+1}=x_n\oplus v_c$ |
| 특징 | 이전 소볼 값이 필요 없음 | 방향수 하나만 XOR하므로 효율적 |
방향수 생성은 소볼 수열을 만들기 위한 사전 준비 단계이고, 특정한 값을 구할 때는 Gray code의 $1$인 비트에 대응하는 방향수들을 XOR한다. 연속된 값을 생성할 때는 Gray code의 한 비트만 변한다는 성질을 이용하여 $x_{n+1}=x_n\oplus v_c$로 계산한다.
Monte Carlo 방법에서 생성되는 표본은 알고리즘과 seed에 의해 만들어지는 의사난수이다. 의사난수는 무작위성을 잘 모방하지만, 유한한 표본이 공간 전체를 고르게 덮는다는 보장은 없다.
옵션 가격 계산에서는 표본이 다양한 시나리오를 고르게 반영하는 것이 중요하다. 이 목적을 위해 결정론적으로 공간을 채우는 준난수가 사용된다.
반데르코르퓌 수열은 정수의 진법 자릿수를 뒤집어 $[0,1]$ 구간을 채운다.
\[h(n,b) = \sum_{i=0}^{m}d_i b^{-(i+1)}\]할튼 수열은 서로 다른 소수를 기수로 하는 반데르코르퓌 수열을 각 차원에 배치한다.
\[\mathbf{x}_n = \left( h(n,p_1),\ldots,h(n,p_d) \right)\]하지만 차원이 높아지면 특정 차원 사이에서 규칙적인 패턴이 나타날 수 있다.
소볼 수열은 이진수, 방향수, 원시다항식, XOR 연산을 사용하여 고차원 공간에 점을 배치한다.
\[x_n = a_0(n)v_1 \oplus a_1(n)v_2 \oplus \cdots\]방향수는
\[v_i=\frac{q_i}{2^i}\]로 정의되고, $q_i$는 다항식에 의해 정해진 재귀식으로 생성된다.
연속된 값을 생성할 때는 Gray code를 이용하여
\[x_{n+1}=x_n\oplus v_c\]로 계산한다.