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

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

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

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

Amazon

power-of-awareness.com

8.　準Monte Carlo法

8.　準Monte Carlo法

　 $\mathrm{Monte\ Carlo}$ 法は

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

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

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

に分けられる。

8.1　準Monte Carlo法

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

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

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

8.2　van der Corput列

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

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

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

　例として、1次元の積分

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

を計算する。
　これを、 $\mathrm{van}$ $\mathrm{der}$ $\mathrm{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列

　 $\mathrm{Low}$ - $\mathrm{discrepancy}$ 列を説明する。その前にまず $\mathrm{discrepancy}$ を考える。 $\mathrm{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$ の $\mathrm{discrepancy}$ とする。

食い違いの度合いは以下の $\mathrm{star}$ $\mathrm{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}$

　これを基に $\mathrm{low}$ - $\mathrm{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\}$ を $\mathrm{low}$ - $\mathrm{discrepancy}$ 列という。

　この $\mathrm{low}$ - $\mathrm{discrepancy}$ 列を使った準 $\mathrm{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}$
が成立する。

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

8.3.2　多次元のdiscrepancy

　 $k\geq1$ 次元の $\mathrm{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$ の $\mathrm{star}$ $\mathrm{discrepancy}$ という。

　点列 $S$ において $S$ の最初の $N$ 個を取った点集合 $P$ の $\mathrm{star}$ $\mathrm{discrepancy}$ を $D_N^{*}(S)$ と書く。更に多次元の $\mathrm{low}$ - $\mathrm{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\}$ を $\mathrm{low}$ - $\mathrm{discrepancy}$ 列という。

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

　 $f$ が $[0,1]^{k}$ で $\mathrm{Hardy}$ - $\mathrm{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}$
が成立する。

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

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

　多次元の $\mathrm{low}$ - $\mathrm{discrepancy}$ 列にはさまざまなものがある。

$\mathrm{Halton}$ 列

　互いに素な $k$ 個の基数 $b_1, b_2,\cdots,b_k$ に対して $\mathrm{radical}$ - $\mathrm{inverse}$ $\mathrm{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列である。

$\mathrm{Sobol}$ '列

　基数 $2$ の $\mathrm{van}$ $\mathrm{der}$ $\mathrm{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}$

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

$\mathrm{Faure}$ 列

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

最初の次元 $\{x^{(1)}(n)\}$ について基数 $p$ の $\mathrm{van}$ $\mathrm{der}$ $\mathrm{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}$

とおく。

これらをまとめて $\mathrm{Faure}$ 列を得る。

8.4　準Monte Carlo法での正規分布

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

$k$ 次元の $\mathrm{low}$ - $\mathrm{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}$ を $\mathrm{Cholesky}$ 分解して正則行列 $\boldsymbol{C}$ を求める。
点列 $\{\boldsymbol{y}_n\}=\{y_n^{(1)},\cdots,y_n^{(k)}\}$ を
$\begin{aligned}\boldsymbol{y}_n=\boldsymbol{C}\boldsymbol{x}_n\end{aligned}$
で求める。