準モンテカルロ法

数値解析において、準モンテカルロ法は、分散の低減を実現するために、低乖離数列（準ランダム列またはサブランダム列とも呼ばれる）を使用して数値積分やその他の問題を解く方法です。これは、疑似乱数列に基づく通常のモンテカルロ法またはモンテカルロ積分とは対照的です。

モンテカルロ法と準モンテカルロ法は同じように述べられます。問題は、関数fの積分を、点x ₁、...、x _Nの集合で評価された関数の平均として近似することです。

${\displaystyle \int _{[0,1]^{s}}f(u)\,{\rm {d}}u\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).}$

s次元単位立方体上で積分しているので、各x _{i は}s要素のベクトルです。準モンテカルロ法とモンテカルロ法の違いは、 x _iの選択方法です。準モンテカルロ法では、ハルトン数列、ソボル数列、フォーレ数列などの低乖離数列を使用しますが、モンテカルロ法では擬似乱数列を使用します。低乖離数列を使用する利点は、収束速度が速いことです。準モンテカルロ法の収束速度は O(1/ N ) に近いのに対し、モンテカルロ法の収束速度は O( N ^−0.5 ) です。^[1]

準モンテカルロ法は、近年、数理ファイナンスや計算ファイナンスの分野で人気が高まっています。^[1]これらの分野では、閾値ε内で積分を評価する必要がある高次元の数値積分が頻繁に発生します。そのため、モンテカルロ法や準モンテカルロ法は、このような状況で有益です。

準モンテカルロ法の近似誤差は、集合x ₁ , ..., x _Nの差異に比例する項によって制限される。具体的には、コクスマ・フラウカ不等式は、誤差が

${\displaystyle \varepsilon =\left|\int _{[0,1]^{s}}f(u)\,{\rm {d}}u-{\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i})\right|}$

境界は

${\displaystyle |\varepsilon |\leq V(f)D_{N},}$

ここで、V ( f ) は関数fのハーディ・クラウス変分である（詳細な定義については、Morokoff and Caflisch (1995) ^{[2]を参照）。D} _{N は}集合 ( x ₁ ,..., x _N )のいわゆるスター・ディスクレパンシーであり、次のように定義される。

${\displaystyle D_{N}=\sup _{Q\subset [0,1]^{s}}\left|{\frac {{\text{Q内の点の数}{N}}-\operatorname {体積} (Q)\right|,}$

ここで、Qは [0,1] の直方体で、^辺は座標軸に平行です。^[2]この不等式は、準モンテカルロ法による近似値の誤差が であるのに対し、モンテカルロ法の確率誤差は であることを示すために使用できます。したがって、 が十分に大きい場合、準モンテカルロは常にランダムモンテカルロよりも優れたパフォーマンスを発揮します。ただし、 は次元とともに指数関数的に急速に増加するため、不適切に選択されたシーケンスは高次元ではモンテカルロよりもはるかに悪くなる可能性があります。実際には、適切な低乖離シーケンスを選択するか、適切な変換を被積分関数に適用して、準モンテカルロが少なくともモンテカルロと同等（多くの場合、はるかに優れている）のパフォーマンスを発揮するようにすることがほぼ常に可能です。^[1]${\displaystyle |\varepsilon |\leq V(f)D_{N}}$${\displaystyle O\left({\frac {(\log N)^{s}}{N}}\right)}$${\displaystyle O\left({\frac {1}{\sqrt {N}}}\right)}$${\displaystyle N}$${\displaystyle \log(N)^{s}}$

1 次元積分では、関数が滑らかな場合、台形則、シンプソン則、ニュートン・コーツの公式などの求積法が効率的であることが知られています。これらのアプローチは、1 次元積分を複数の次元で繰り返すことで、多次元積分にも使用できます。ただし、関数の評価回数は、 次元数sが増加するにつれて指数関数的に増加します。したがって、多次元積分には、この次元の呪いを克服できる方法を使用する必要があります。標準的なモンテカルロ法は、求積法の実装が困難または高価である場合によく使用されます。^[2]モンテカルロ法と準モンテカルロ法は、次元が 300 以上まで高い場合、正確で比較的高速です。^[3]

Morokoff と Caflisch ^[2]は、モンテ カルロ法と準モンテ カルロ法の積分におけるパフォーマンスを研究しました。この論文では、準モンテ カルロ法のハルトン シーケンス、ソボル シーケンス、フォーレ シーケンスを、疑似ランダム シーケンスを使用した標準モンテ カルロ法と比較しています。その結果、ハルトン シーケンスは 6 次元程度までのパフォーマンスが最も優れ、ソボル シーケンスはそれより高い次元でのパフォーマンスが最も優れ、フォーレ シーケンスは他の 2 つよりパフォーマンスが劣るものの、疑似ランダム シーケンスよりはパフォーマンスが優れていることがわかりました。

しかし、モロコフとカフリッシュ^[2]は、準モンテカルロ法の利点が理論的に期待されるほどではない例を挙げています。それでも、モロコフとカフリッシュが研究した例では、準モンテカルロ法は同じ点数のモンテカルロ法よりも正確な結果をもたらしました。モロコフとカフリッシュは、積分対象が滑らかで、積分の 次元数sが小さい場合、準モンテカルロ法の利点が大きくなると述べています。

ルミューは準モンテカルロ法の欠点について次のように述べている。^[4]

• が より小さくなるためには、が小さく、 が大きくなければなりません (例)。sが大きい場合、 Nの値によっては、低乖離度ジェネレータからの点集合の乖離度が、ランダム集合の乖離度よりも小さくならないことがあります。${\displaystyle O\left({\frac {(\log N)^{s}}{N}}\right)}$${\displaystyle O\left({\frac {1}{\sqrt {N}}}\right)}$${\displaystyle s}$${\displaystyle N}$${\displaystyle N>2^{s}}$
• 実際に発生する多くの関数の場合（たとえば、ガウス変数が使用される場合）。${\displaystyle V(f)=\infty }$
• 誤差の上限（ε ≤ V ( f ) D _N ）しか分かっておらず、およびを計算するのは困難です。${\displaystyle D_{N}^{*}}$${\displaystyle V(f)}$

これらの困難のいくつかを克服するために、ランダム化準モンテカルロ法を使用することができます。

低乖離シーケンスはランダムではなく決定論的であるため、準モンテカルロ法は決定論的アルゴリズムまたは非ランダム化アルゴリズムと見なすことができます。 この場合、誤差の境界（たとえば、ε ≤ V ( f ) D _N）しかなく、誤差を推定するのは困難です。 分散を分析および推定する能力を取り戻すために、この方法をランダム化することができます（一般的な考え方についてはランダム化を参照してください）。 結果として得られる方法は、ランダム化準モンテカルロ法と呼ばれ、標準モンテカルロ法の分散削減手法と見なすこともできます。^[5] いくつかの方法の中で、最も単純な変換手順はランダムシフトによるものです。 { x ₁ ,..., x _N } を低乖離シーケンスからの点集合とします。s次元のランダムベクトルU をサンプリングし、それを { x ₁ , ..., x _N }と混合します。 詳細には、各x _jについて、

${\displaystyle y_{j}=x_{j}+U{\pmod {1}}}$

の代わりにシーケンスを使用します。モンテカルロの複製がR 回ある場合は、各複製で s 次元のランダムベクトル U をサンプルします。ランダム化により、準ランダムシーケンスを使用しながら分散の推定値を得ることができます。純粋な準モンテカルロと比較すると、準ランダムシーケンスのサンプル数はRで割られ、計算コストは​​同等になり、理論的な収束率が低下します。標準モンテカルロと比較すると、分散と計算速度は、Tuffin (2008) ^{[6]の実験結果からわずかに優れています。}${\displaystyle (y_{j})}$${\displaystyle (x_{j})}$

• モンテカルロ法 – 確率的問題解決アルゴリズム
• 金融におけるモンテカルロ法 – 確率的測定法
• 金融における準モンテカルロ法
• 生物学モンテカルロ法 – イオン輸送をシミュレートする方法
• 計算物理学 – コンピュータによる物理的問題の数値シミュレーション
• 低矛盾シーケンス – 数学的シーケンスの種類リダイレクト先の簡単な説明を表示するページ
• 不一致理論 – 分布の不規則性の理論
• マルコフ連鎖モンテカルロ – 複雑な統計分布の計算

• RE Caflisch、モンテカルロ法および準モンテカルロ法、Acta Numerica vol. 7、ケンブリッジ大学出版局、1998 年、1 ～ 49 ページ。
• ヨゼフ・ディックとフリードリヒ・ピリッヒシャマー、「デジタルネットとシーケンス。不一致理論と準モンテカルロ積分」、ケンブリッジ大学出版局、ケンブリッジ、2010年、ISBN 978-0-521-19159-3 
• ギュンター・レオバッハーとフリードリヒ・ピリッヒシャマー、「準モンテカルロ積分とその応用入門」、Compact Textbooks in Mathematics、ビルクハウザー、2014年、ISBN 978-3-319-03424-9 
• Michael Drmota および Robert F. Tichy、「数列、不一致、および応用」、Lecture Notes in Math.、1651、Springer、ベルリン、1997、ISBN 3-540-62606-9 
• William J. Morokoff とRussel E. Caflisch、準ランダムシーケンスとその不一致、SIAM J. Sci. Comput. 15 (1994)、第6号、1251–1279 ( CiteSeer :[2])
• Harald Niederreiter .乱数生成と準モンテカルロ法。工業応用数学協会、1992 年。ISBN 0-89871-295-5 
• Harald G. Niederreiter、準モンテカルロ法と擬似乱数、Bull.アメル。数学。社会84 (1978)、いいえ。 6、957–1041
• Oto Strauch および Štefan Porubský、「Distribution of Sequences: A Sampler」、Peter Lang Publishing House、フランクフルト アム マイン 2005 年、ISBN 3-631-54013-2 

• MCQMC Wikiページには、モンテカルロ法と準モンテカルロ法に関する無料のオンライン資料が多数掲載されています。
• 非常に直感的で包括的な準モンテカルロ法の入門書