金融工学におけるシミュレーションについて学んでいく。テキストとして以下を使う。今回は順番を変えて先にP.153-165までを取り扱う。
- 問題に沿った(同時)分布に従う(多変量)乱数列の生成
- その乱数列を使った計算
の2つの部分に分けて考えられる。乱数列の生成は更に
- 一様分布に従う乱数列
の生成
- それを元にした必要な同時分布に従う乱数列
の生成
に分けられる。
8. 準モンテカルロ法
8.1 準Monte Carlo法
準Monte Carlo法はlow-discrepancy列を用いて次元の超立方体
での積分を計算する手法である。もし解こうとする問題が超立方体
での積分で表現できる場合、準Monte Carlo法を適用できる。通常のMonte Carlo法において点列(擬似乱数列)をlow-discrepancy列に取り換えればよい。
Monte Carlo法と準Monte Carlo法では様々な性質が異なる:
相違点 |
Monte Carlo法 |
準Monte Carlo法 |
(1) 用いる点列の性質 | 擬似乱数列 | low-discrepancy列 |
(2) 基盤となる定理 | 大数の法則・中心極限定理 | Koksma-Hlawkaの不等式 |
(3) 誤差のオーダー | ||
(4) 誤差の上限 | 存在するとは限らない。 | 存在する。 |
準Monte Carlo法の方が誤差のオーダーが低いため、より少ない試行回数で正しい値に近い計算結果が得られる可能性がある。
8.2 van der Corput列
low-discrepancy列の1つであるvan der Corput列を用いた準Monte Carlo法を考える。そのためにvan der Corput列を定義する。
その準備として進法で表した際の10進法整数を小数点で対称に折り返したradical-inverse functionを定義する:
進法の整数
を
で表したときの
桁目の数字を
、すなわち
とする。このとき
を基数
のradical-inverse functionという。
のすべての整数
で
が成り立つ。
これを基にvan der Corput列を定義する:
ある整数
について
で得られる点列を基数
のvan der Corput列という。
例として、1次元の積分
を計算する。
これを、van der Corput列の最初の
個からなる点集合を用いて
で近似する。
まで取ると、数値積分の典型的な手法である台形則での離散点に一致する。
8.3 Low-discrepancy列
Low-discrepancy列を説明する。その前にまずdiscrepancyを考える。
discrepancyとは生成した各点の散らばり具合を表す概念である。
8.3.1 一次元のdiscrepancy
まず1次元で有限な場合を考える。線分上に
個の点からなる点集合
を取る。この線分の上で
を
から
まで動かしたときに
に入る
の個数を
と書くことにする。このとき
を
に入る点の比率
とする。の軌跡
を平面にプロットすることで階段状のグラフを得る。
- この平面に傾きが
の直線
を書き加える。
- この会談と直線の2つの線の食い違いの度合いを点集合
のdiscrepancyとする。
食い違いの度合いは以下のstar discrepancyにて測る:
点集合
において
これを基にlow-discrepancy列を以下で定義する:
以上のすべての
について
を満たす点集合をlow-discrepancy列という。
このlow-discrepancy列を使った準Monte Carlo法での誤差を評価する。
が成立する。
すなわち準Monte Carlo法の結果と真の解の差は点列のstar discrepancyを用いてで押さえられる。
8.3.2 多次元のdiscrepancy
次元のdiscrepancyを定義すべく、まずは前提事項を導入する。
を
の中の点集合とし、
を
の中の点とする。また
とし、に入る
の個数を
とする。このとき、
を点集合のstar discrepancyという。
点列において
の最初の
個を取った点集合
のstar discrepancyを
と書く。更に多次元のlow-discrepancy列は1次元と同様に定義される:
以上のすべての
について
を満たす点集合をlow-discrepancy列という。
の準Monte Carlo法に関する誤差は次のKoksma-Hlawkaの不等式に基づき評価できる:
が成立する。
low-discrepancy列では、に対して
が十分に小さければ、準Monte Carlo法では試行回数
を増やすとほぼ
のオーダーで誤差が小さくなる。また通常のMonte Carlo法ではその根拠となる中心極限定理が確率収束であることから誤差は上限を持たない一方で、準Monte Carlo法ではKolksma-Hlawkaの不等式により確定的な上限が存在する。
8.3.3 さまざまな多次元low-discrepancy列
多次元のlow-discrepancy列にはさまざまなものがある。
- Halton列
互いに素な個の基数
に対してradical-inverse function
を用いて
で表される点列をHalton列である。
- Sobol'列
基数のvan der Corput列の2進法での表現において
桁目の数字に着目すれば
- Faure列
Faure列は次元の問題に対して
以上の素数
を基数として用いるlow-discrepancy列である。
- 最初の次元
について基数
のvan der Corput列、すなわち
となるを用いて
とおく。 - 残りの次元
については
- これらをまとめてFaure列を得る。
8.4 準Monte Carlo法での正規分布
low-discrepancy列はで一様に分布する確率変数の期待値計算に用いられる点列であるしたがって準Monte Carlo法で相関のある多次元正規分布に従う確率変数を扱うためにはCholesky分解と逆関数法を用いて
で一様に分布する確率変数の問題に変換する。
逆関数法とCholesky分解を順番に用いることでで一様に分布する確率ベクトル
から、多次元標準正規分布に従う確率ベクトル
を介して一般の多次元正規分布に従う確率ベクトル
が得られる。これを
から
に逆に辿ると、一般の多次元正規分布による期待値計算が
で一様に分布する確率変数による期待値計算に置き換えられる。したがって一般の多次元正規分布を扱う問題が準Monte Carlo法に置き換えられる。
次元のlow-discrepancy列
を生成する。
から逆関数法で
次元標準正規分布に従う点列
を生成する。
- 求めたい
次元正規分布の分散共分散行列
をCholesky分解して正則行列
を求める。
- 点列
を
で求める。
このを用いることで、一般の多次元正規分布を扱った問題を準Monte Carlo法で解くことが出来る。