「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。

MENU

金融工学でのモンテカルロ法(X/N):準Monte Carlo法

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

 モンテカルロ法

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

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

  1. 一様分布に従う乱数列\{u_1,u_2,\cdots,u_n\}の生成
  2. それを元にした必要な同時分布に従う乱数列\{\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\geq0b\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\}を取る。この線分の上でy0から1まで動かしたときにB(y)=[0,y)に入るx_nの個数をA(B;P)と書くことにする。このとき

  • zB=[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}桁の数字01

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

  • Faure列

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

  1. 最初の次元\{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}
    とおく。
  2. 残りの次元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}
とおく。

  1. これらをまとめて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法に置き換えられる。

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

このYを用いることで、一般の多次元正規分布を扱った問題を準Monte Carlo法で解くことが出来る。

*1:ここで有界変動とは、実区間[a,b]\subset\mathbb{R}上で定義された実関数fの全変動

\begin{aligned}V_{a}^{b}(f)=\sup_{P\in\mathcal{P}}\sum_{i=0}^{n_{P}-1}|f(x_{i+1})-f(x_i)|\end{aligned}
のうち有界であるようなものを言う。

プライバシーポリシー お問い合わせ