金融工学でのモンテカルロ法(22/22)：準Monte Carlo法 - 「大人の教養・知識・気付き」を伸ばすブログ

　金融工学におけるシミュレーションについて学んでいく。テキストとして以下を使う。今回は順番を変えて先にP.153-165までを取り扱う。

モンテカルロ法の金融工学への応用 (シリーズ現代金融工学)

作者:祥二, 湯前,輝好, 鈴木
朝倉書店

Amazon

8.　準モンテカルロ法

　モンテカルロ法は

問題に沿った（同時）分布に従う（多変量）乱数列の生成
その乱数列を使った計算

の2つの部分に分けて考えられる。乱数列の生成は更に

一様分布に従う乱数列 $\{u_1,u_2,\cdots,u_n\}$ の生成
それを元にした必要な同時分布に従う乱数列 $\{\boldsymbol{x}_1,\boldsymbol{x}_2,\cdots,\boldsymbol{x}_n\}$ の生成

に分けられる。

8.　準モンテカルロ法

8.1　準Monte Carlo法

　準Monte Carlo法はlow-discrepancy列を用いて $k$ 次元の超立方体 $[0,1]^{k}$ での積分を計算する手法である。もし解こうとする問題が超立方体 $[0,1]^{k}$ での積分で表現できる場合、準Monte Carlo法を適用できる。通常のMonte Carlo法において点列（擬似乱数列）をlow-discrepancy列に取り換えればよい。
　
　Monte Carlo法と準Monte Carlo法では様々な性質が異なる：

相違点	Monte Carlo法	準Monte Carlo法
(1) 用いる点列の性質	擬似乱数列	low-discrepancy列
(2) 基盤となる定理	大数の法則・中心極限定理	Koksma-Hlawkaの不等式
(3) 誤差のオーダー	$O(N^{-1/2})$	$N^{-1}(\log{N})^k$
(4) 誤差の上限	存在するとは限らない。	存在する。

準Monte Carlo法の方が誤差のオーダーが低いため、より少ない試行回数で正しい値に近い計算結果が得られる可能性がある。

8.2　van der Corput列

　low-discrepancy列の1つであるvan der Corput列を用いた準Monte Carlo法を考える。そのためにvan der Corput列を定義する。
　その準備として $b$ 進法で表した際の10進法整数を小数点で対称に折り返したradical-inverse functionを定義する：

　 $10$ 進法の整数 $n\geq0$ を $b\geq2$ で表したときの $b^j$ 桁目の数字を $a_j(n)$ 、すなわち
$\begin{aligned} n=\displaystyle{\sum_{j=0}^{\infty}a_j(n)b^{j}} \end{aligned}$
とする。このとき
$\begin{aligned} \Phi_{b}(n)=\displaystyle{\sum_{j=0}^{\infty}a_j(n)b^{-j-1}} \end{aligned}$
を基数 $b$ のradical-inverse functionという。

$n\geq0$ のすべての整数 $n$ で $\Phi_{b}(n)\in[0,1)$ が成り立つ。
　これを基にvan der Corput列を定義する：

　ある整数 $b\geq2$ について
$\begin{aligned} x_n=\Phi_{b}(n),\ n=0,1,\cdots \end{aligned}$
で得られる点列 $\{x_0,x_1,\cdots\}$ を基数 $b$ のvan der Corput列という。

　例として、1次元の積分

$\begin{aligned} \int_{0}^{1}f(u)du \end{aligned}$

を計算する。
　これを、van der Corput列 $\{x_i\}$ の最初の $N$ 個からなる点集合を用いて

$\begin{aligned} \displaystyle{\int_{0}^{1}f(u)du}\approx \displaystyle{\frac{1}{N}}\displaystyle{\sum_{i=0}^{N-1}f(x_i)} \end{aligned}$

で近似する。
　 $N=2^k$ まで取ると、数値積分の典型的な手法である台形則での離散点に一致する。

8.3　Low-discrepancy列

　Low-discrepancy列を説明する。その前にまずdiscrepancyを考える。
discrepancyとは生成した各点の散らばり具合を表す概念である。

8.3.1　一次元のdiscrepancy

　まず1次元で有限な場合を考える。線分 $[0,1]$ 上に $N$ 個の点からなる点集合 $P=\{x_1,x_2,\cdots,x_n\}$ を取る。この線分の上で $y$ を $0$ から $1$ まで動かしたときに $B(y)=[0,y)$ に入る $x_n$ の個数を $A(B;P)$ と書くことにする。このとき

$z$ を $B=[0,y)$ に入る点の比率
$\begin{aligned}z=\displaystyle{\frac{A(B;P)}{N}}\end{aligned}$
とする。
$(y,z)$ の軌跡 $f$ を平面にプロットすることで階段状のグラフを得る。
この平面に傾きが $1$ の直線 $g:z=y$ を書き加える。
この会談と直線の2つの線の食い違いの度合いを点集合 $P$ のdiscrepancyとする。

食い違いの度合いは以下のstar discrepancyにて測る：

　点集合 $P=\{x_1,x_2,\cdots,x_N\}$ において
$\begin{aligned} D_N^{*}(P)=\displaystyle{\sup_{y\in[0,1]}\left|\displaystyle{\frac{A(B;P)}{N}}-y\right|} \end{aligned}$

　これを基にlow-discrepancy列を以下で定義する：

　 $2$ 以上のすべての $N$ について
$\begin{aligned} D_N^{*}(S)\leq c\displaystyle{\frac{\log{N}}{N}},\ c\in\mathbb{R} \end{aligned}$
を満たす点集合 $P=\{x_1,x_2,\cdots,x_N\}$ をlow-discrepancy列という。

　このlow-discrepancy列を使った準Monte Carlo法での誤差を評価する。

　関数 $f$ が $[0,1]$ で有界変動 $V_f$ *1を持てば
$\begin{aligned} \displaystyle{\left|\int_{0}^{1}f(x)dx - \frac{1}{N}\sum_{n=1}^{N}f(x_n)\right|}\leq V_f D_N^{*}(S) \end{aligned}$
が成立する。

すなわち準Monte Carlo法の結果と真の解の差は点列のstar discrepancyを用いて $V_f D_N^{*}(S)$ で押さえられる。

8.3.2　多次元のdiscrepancy

　 $k\geq1$ 次元のdiscrepancyを定義すべく、まずは前提事項を導入する。
　 $P=\{\boldsymbol{x}_n=(x_n^{(1)},\cdots,x_n^{(k)}),\ n=0,1,\cdots,N-1\}$ を $[0,1]^{k}$ の中の点集合とし、 $\boldsymbol{y}=(y^{(1)},\cdots,y^{(k)})$ を $[0,1]^{k}$ の中の点とする。また

$\begin{aligned} J(\boldsymbol{y})=[0,y^{(1)})\times\cdots\times[0,y^{(k)})\subset[0,1]^k \end{aligned}$

とし、 $J(\boldsymbol{y})$ に入る $\boldsymbol{x}_n\in P$ の個数を $A(J;P)$ とする。このとき、

$\begin{aligned} D_N^{*}(P)=\displaystyle{\sup_{\boldsymbol{y}\in[0,1]^{k}}\left|\displaystyle{\frac{A(J;P)}{N}-\prod_{i=1}^{k}y^{(i)}}\right|} \end{aligned}$
を点集合 $P$ のstar discrepancyという。

　点列 $S$ において $S$ の最初の $N$ 個を取った点集合 $P$ のstar discrepancyを $D_N^{*}(S)$ と書く。更に多次元のlow-discrepancy列は1次元と同様に定義される：

　 $2$ 以上のすべての $N$ について
$\begin{aligned} D_N^{*}(S)\leq c\displaystyle{\frac{\log{N}}{N}},\ c\in\mathbb{R} \end{aligned}$
を満たす点集合 $P=\{x_1,x_2,\cdots,x_N\}$ をlow-discrepancy列という。

　 $k\geq1$ の準Monte Carlo法に関する誤差は次のKoksma-Hlawkaの不等式に基づき評価できる：

　 $f$ が $[0,1]^{k}$ でHardy-Krauseの意味での有界変動 $V_{f}$ を持てば
$\begin{aligned} \left|\displaystyle{\int_{0}^{1}\cdots\int_{0}^{1}f(\boldsymbol{x})d\boldsymbol{x}}-\displaystyle{\frac{1}{N}\sum_{n=1}^{N}f(\boldsymbol{x}_n)} \right|\leq V_{f} D_N^{*}(S) \end{aligned}$
が成立する。

　low-discrepancy列では、 $N$ に対して $(\log N)^{k}$ が十分に小さければ、準Monte Carlo法では試行回数 $N$ を増やすとほぼ $O(N^{-1})$ のオーダーで誤差が小さくなる。また通常のMonte Carlo法ではその根拠となる中心極限定理が確率収束であることから誤差は上限を持たない一方で、準Monte Carlo法ではKolksma-Hlawkaの不等式により確定的な上限が存在する。

8.3.3　さまざまな多次元low-discrepancy列

　多次元のlow-discrepancy列にはさまざまなものがある。

Halton列

　互いに素な $k$ 個の基数 $b_1, b_2,\cdots,b_k$ に対してradical-inverse function $\Phi_b(n)$ を用いて

$\begin{aligned} \boldsymbol{x}_n=(\Phi_{b_1}(n),\Phi_{b_2}(n),\cdots,\Phi_{b_k}(n)) \end{aligned}$

で表される点列をHalton列である。

Sobol'列

　基数 $2$ のvan der Corput列の2進法での表現において $2^{-j}$ 桁目の数字に着目すれば

$\begin{aligned} \{0,\cdots,0,1,\cdots,1\} \end{aligned}$

を繰り返す。ここで $\{x_0,x_1,\cdots\}$ を前から順に $2^{j}$ 個ずつのまとまりに分けて、そのまとまりにおいて $2^{-j}$ 桁の数字 $0$ と $1$ を

$\begin{aligned} \{1,\cdots,1,0,\cdots,0\} \end{aligned}$

と入れ替えても全体としてlow-discrepancy列であることには変わらない。このように互いに異なるlow-discrepancy列を $k$ 個束ねて $k$ 次元のベクトルの列にしたものをSobol'列である。

Faure列

　Faure列は $k$ 次元の問題に対して $k$ 以上の素数 $p$ を基数として用いるlow-discrepancy列である。

最初の次元 $\{x^{(1)}(n)\}$ について基数 $p$ のvan der Corput列、すなわち
$\begin{aligned} n=\displaystyle{\sum_{j=0}^{\infty}a_j^{(1)}(n)p^{j},\ n=0,1,\cdots}\end{aligned}$
となる $a_j^{(1)}(n)$ を用いて
$\begin{aligned} x^{(1)}(n)=\displaystyle{\sum_{j=0}^{\infty}a_j^{(1)}(n)p^{-j-1}},\ n=0,1,\cdots\end{aligned}$
とおく。
残りの次元 $x^{(l)}(n),2\leq l\leq k$ については

$\begin{aligned}\begin{bmatrix}a_0^{(l)}(n)\\a_1^{(l)}(n)\\a_2^{(l)}(n)\\ \vdots\end{bmatrix}=\begin{bmatrix} { }_{0}C_{0}&{ }_{1}C_{0}&{ }_{2}C_{0}&\cdots\\ {} &{ }_{1}C_{1}&{ }_{2}C_{1}&\cdots\\ {}&{}&{ }_{2}C_{2}&\cdots\\ {}&{}&{}&\ddots \end{bmatrix}^{l-1}= \begin{bmatrix}a_0^{(l)}(n)\\a_1^{(l)}(n)\\a_2^{(l)}(n)\\ \vdots\end{bmatrix}(mod\ p) \end{aligned}$

となる $a_j^{(j)}(n)$ を用いて

$\begin{aligned}x^{(l)}(n)=\displaystyle{\sum_{j=0}^{\infty}a_j^{(l)}(n)p^{-j-1}}\end{aligned}$

とおく。

これらをまとめてFaure列を得る。

8.4　準Monte Carlo法での正規分布

　low-discrepancy列は $\bar{I}^{k}=[0,1]^{k}$ で一様に分布する確率変数の期待値計算に用いられる点列であるしたがって準Monte Carlo法で相関のある多次元正規分布に従う確率変数を扱うためにはCholesky分解と逆関数法を用いて $\bar{I}^{k}$ で一様に分布する確率変数の問題に変換する。
　逆関数法とCholesky分解を順番に用いることで $\bar{I}^{k}$ で一様に分布する確率ベクトル $\boldsymbol{X}$ から、多次元標準正規分布に従う確率ベクトル $\boldsymbol{Y}$ を介して一般の多次元正規分布に従う確率ベクトル $\boldsymbol{Z}$ が得られる。これを $\boldsymbol{Z}$ から $\boldsymbol{X}$ に逆に辿ると、一般の多次元正規分布による期待値計算が $\bar{I}^{k}$ で一様に分布する確率変数による期待値計算に置き換えられる。したがって一般の多次元正規分布を扱う問題が準Monte Carlo法に置き換えられる。

$k$ 次元のlow-discrepancy列 $\{\boldsymbol{u}_n\}=\{u_n^{(1)},\cdots,u_n^{(k)}\}$ を生成する。
$\{\boldsymbol{u}_n\}$ から逆関数法で $k$ 次元標準正規分布に従う点列 $\{\boldsymbol{x}_n\}=\{x_n^{(1)},\cdots,x_n^{(k)}\}$ を生成する。
求めたい $k$ 次元正規分布の分散共分散行列 $\boldsymbol{\Sigma}$ をCholesky分解して正則行列 $\boldsymbol{C}$ を求める。
点列 $\{\boldsymbol{y}_n\}=\{y_n^{()},\cdots,y_n^{(k)}\}$ を
$\begin{aligned}\boldsymbol{y}_n=\boldsymbol{C}\boldsymbol{x}_n\end{aligned}$
で求める。