モンテカルロ法
(グランドカノニカルモンテカルロ法 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/10 06:36 UTC 版)
計算理論
計算理論の分野において、モンテカルロ法とは誤答する確率の上界が与えられる乱択アルゴリズム（ランダム・アルゴリズム）と定義される[1]。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。一般にモンテカルロ法は独立な乱択を用いて繰り返し、実行時間を犠牲にすれば誤答する確率をいくらでも小さくすることができる。またモンテカルロ法の中でも任意の入力に対して最大時間計算量の上界が入力サイズの多項式で与えられるものを効率的モンテカルロ法という[2]。
なお、これとは対照的に理論上必ずしも終了するとは限らないが、もし答えが得られれば必ず正しい乱択アルゴリズムをラスベガス法と呼ぶ。
計算複雑性理論では、確率的チューリング機械によるモデル化によってモンテカルロ法を用いて解決できる問題のクラスをいくつか定義している。代表的なところでは RPやBPP、PP などがある。これらのクラスと P や NP との関連性を解明していくことによって、モンテカルロ法のようにランダム性を含むアルゴリズムによって解ける問題の範囲が拡大しているのか（P ≠ BPP なのか）、それとも単に決定的アルゴリズムで解ける問題の多項式時間の次数を減らしているだけなのか（P=BPP なのか）は計算複雑性理論における主要課題の1つである。現在、NP ⊂ PP 、RP ⊆ NPであることはわかっているが BPP と NPとの関係はわかっていない。
準モンテカルロ法
一様乱数ではなく、超一様分布列を使用する方法を準モンテカルロ法という[3]。たとえばモンテカルロ数値積分法で、乱数の代わりに準乱数を用いれば収束の加速が期待できる。ただし、分布の一様性の高い数列としての準乱数は、モンテカルロ数値積分には適切であっても、それ以外の用途に用いた場合には、本来の答えと異なる結果を生じる可能性がある。
以下は超一様分布列の例である。
数値積分
数値解析の分野においてはモンテカルロ法はよく確率を近似的に求める手法として使われる。n 回シミュレーションを行い、ある事象が m 回起これば、その事象の起こる確率は当然ながら m/n で近似される。試行回数が少なければ近似は荒く、試行回数が多ければよい近似となる。
また、この確率を利用すれば、積分（面積）の近似解を求めることが可能となる。領域 R の面積 S は、領域 R を含む面積 T の領域内でランダムに点を打ち、領域 R の中に入る確率 p をモンテカルロ法で求めれば、S = pT で近似される。
n 重積分
- P.J. Davis and P.Rabinowitz、森正武（訳）：「計算機による数値積分法」、日本コンピュータ協会（1981年2月15日）。
- Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized algorithms. Cambridge University Press. ISBN 0-521-47465-5. MR 1344451. Zbl 0849.68039
- Jan van Leeuwen 編：「コンピュータ基礎理論ハンドブックⅠ：アルゴリズムと複雑さ」、廣瀬 健、野崎昭弘、小林孝次郎 監訳、丸善、1994年、ISBN 4-621-03921-0
- 電気学会 GA・ニューロを用いた学習法とその応用調査専門委員会 編：『学習とそのアルゴリズム』、森北出版、2002年、ISBN 4-627-82751-2
- 杉原正顕、室田一雄：「数値計算法の数理」、岩波書店 2003年、ISBN 978-4-00-005518-5
- 伏見正則 、逆瀬川浩孝（監訳)：「モンテカルロ法ハンドブック」、朝倉出版、ISBN 978-4-254-28005-0（2014年8月25日）。原著はDirk P.Kroese, Thomas Taimre, Zdravko I.Botev：Handbook of Monte Carlo Methods, John Wiley & Sons, Inc.，ISBN 978-0-47017793-8（2011年1月28日）。
- 鈴木航介、合田隆「準モンテカルロ法の最前線」『日本応用数理学会論文誌』第30巻第4号、日本応用数理学会、2020年、320-374頁、doi:10.11540/jsiamt.30.4_320、 ISSN 2424-0982。
- Müller, Fabio; Christiansen, Henrik; Schnabel, Stefan; Janke, Wolfhard (2023-07). “Fast, Hierarchical, and Adaptive Algorithm for Metropolis Monte Carlo Simulations of Long-Range Interacting Systems”. Phys. Rev. X (American Physical Society) 13 (3): 031006. doi:10.1103/PhysRevX.13.031006.
- K.K. Sabelfeld: Monte Carlo Methods: In Boundary Value Problems, Springer-Verlag, ISBN 978-3-642-75979-6 (1991).
- 鈴木航介、合田隆：「重点解説 モンテカルロ法と準モンテカルロ法」、サイエンス社（SGC 197）、ISBN 978-4-7819-1623-1 (2025年1月25日)。
関連項目
- グランドカノニカルモンテカルロ法のページへのリンク
