VEGASアルゴリズム

G.ピーター・ルページ[ ^{1] [2] [3]}によるVEGASアルゴリズムは、既知または近似の確率分布関数を使用して、最終的な積分に最も大きく貢献する積分関数の領域に探索を集中させることにより、モンテカルロシミュレーションの誤差を減らす方法です。

VEGAS アルゴリズムは、重要度サンプリングに基づいています。関数によって記述される確率分布から点をサンプリングし、積分に最も大きく寄与する領域に点が集中するようにします。GNU Scientific Library (GSL) は、VEGAS ルーチンを提供します。 ${\displaystyle |f|,}$

一般に、ある体積上のモンテカルロ積分を関数によって記述される確率分布に従って分布する点からサンプリングすると、推定値が得られる。${\displaystyle f}$${\displaystyle \オメガ}$${\displaystyle g,}$${\displaystyle \mathrm {E} _{g}(f;N),}$

${\displaystyle \mathrm {E} _{g}(f;N)={1 \over N}\sum _{i}^{N}{f(x_{i})}/g(x_{i}).}$

新しい推定値の 分散は

${\displaystyle \mathrm {Var} _{g}(f;N)=\mathrm {Var} (f/g;N)}$

ここで、元の推定値の分散は、${\displaystyle \mathrm {Var} (f;N)}$${\displaystyle \mathrm {Var} (f;N)=\mathrm {E} (f^{2};N)-(\mathrm {E} (f;N))^{2}.}$

確率分布を として選択すると、分散が消え、推定値の誤差がゼロになることが示されます。実際には、任意の関数の正確な分布 g からサンプリングすることは不可能であるため、重要度サンプリング アルゴリズムは、目的の分布への効率的な近似値を生成することを目的としています。 ${\displaystyle g=|f|/\textstyle \int _{\Omega }|f(x)|dx}$${\displaystyle \mathrm {Var} _{g}(f;N)}$

VEGAS アルゴリズムは、関数 f をヒストグラム化しながら積分領域を何回か通過することで、正確な分布を近似します。各ヒストグラムは、次の通過のサンプリング分布を定義するために使用されます。この手順は、漸近的に目的の分布に収束します。次元dと同様にヒストグラム ビンの数が増えるのを避けるために、確率分布は分離可能な関数で近似されます。したがって、必要なビンの数はKdのみです。これは、積分関数の座標軸への投影から関数のピークを特定することと同じです。VEGAS の効率は、この仮定の妥当性に依存します。積分関数のピークが適切に特定されている場合に最も効率的です。積分関数を近似的に分離可能な形式で書き直すことができれば、VEGAS による積分の効率が向上します。 ${\displaystyle K^{d}}$${\displaystyle g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\cdots }$

• ラスベガスアルゴリズム
• モンテカルロ積分
• 重要度サンプリング