マルコフ連鎖モンテカルロ法（マルコフれんさモンテカルロほう、、通称MCMC）とは、求める確率分布を均衡分布として持つマルコフ連鎖を作成することによって確率分布のサンプリングを行う種々のアルゴリズムの総称である。具体的には、同時事後分布に従う乱数を継時的に生成する。代表的なMCMCとしてメトロポリス・ヘイスティングス法やギブスサンプリングがある。
MCMCで充分に多くの回数の試行を行った後のマルコフ連鎖の状態は求める目標分布の標本として用いられる。試行の回数を増やすとともにサンプルの品質も向上する。
求められる特性を持つマルコフ連鎖を作成することは通常難しくない。問題は許容できる誤差内で定常分布に収束する試行の回数を決めることである。適切な連鎖なら任意の位置から始めても定常分布に速く達し、これを高速混合（rapid mixing）とよぶ。
典型的なMCMCは常にある程度の初期値の影響が残るため目標分布しか近似することができない。CFTP法（）などの、より洗練されたMCMCベースのアルゴリズムは完全標本を作成することができるが、より多くの計算と（期待値では有限だが）限界のない実行時間を要する。
このアルゴリズムの最も一般的な応用は多重積分を数値的に計算することである。ランダムに歩き回る粒子の集団を想定し、粒子が点を通過するたびに、その点の被積分関数の値を積分に加算する。粒子は次に積分への貢献が高い所を探して複数の仮の動作をする。このような方法はランダムウォーク法とよばれ、これは乱数的なシミュレーションつまりモンテカルロ法の一種である。従来のモンテカルロ法で用いられる被積分関数のランダムな標本が独立であるのに対して、MCMCで用いられる標本は相関がある。被積分関数を均衡分布に持つようなマルコフ連鎖を作成する必要があるが、多くの場合において容易に行うことができる。
多重積分はベイズ統計学、計算物理学、計算生物学などにしばしば現れるため、そのような分野でMCMCが広く使われている。例としては や を参照。
生成された乱数列はトレースプロット（英: trace plots）の形で可視化できる。
ランダムウォーク法 マルコフ連鎖モンテカルロ法 (MCMC) では、均衡分布の近辺を小さなステップで無作為に動き回る粒子を想定したアルゴリズムが多い。これをランダムウォーク（酔歩）という。この方法は実装や解析が容易だが、粒子はしばしば折り返して既に調べた空間を調べ始めてしまうため、粒子が全空間を調べるのに長い時間がかかってしまう。以下にランダムウォークを用いたMCMCのいくつかを並べる：
メトロポリス・ヘイスティングス法：提案密度（）によって新しい候補を提案し、提案された候補を棄却もしくは採択する手続き用いてマルコフ連鎖を生成する。下記の様々な手法を特別な方法として含む、最も一般的なMCMCである。 ギブスサンプリング：対象となる確率分布の条件付き分布を用いて状態を更新するMCMCである。必要となる全ての条件付分布からの乱数が正確に生成できることを必要とする。必ず提案が採択されるメトロポリス・ヘイスティングス法と捉えることもできる。他の多くの手法で必要となる、調整パラメータを基本的に必要としないことも、この手法がよく用いられる理由の一つである。 スライスサンプリング：密度関数の曲線下の領域を一様にサンプルすることによって、対象となる確率分布を生成することができるという原理に基づく。この手法では垂直方向への一様なサンプリングと、現在の垂直位置の水平方向への、密度関数の「スライス」のサンプリングが交互に行われる。 ：M-H アルゴリズムの変種で各点において複数の試行を行う。一般的にこの手法は一回ごとの歩幅を大きめにとることができ、高次元にまつわる問題の解消に役立つ。
散漫な動きの回避 マルコフ連鎖モンテカルロ法の効率を下げる要因の一つは、マルコフ連鎖が近い状態を行きつ戻りつする散漫 (diffusive) な動きである。散漫な動きを防ぐ工夫を持つアルゴリズムが様々提案されている。これらのアルゴリズムは実装が難しくなるが、より高速な収束を得られる可能性がある。つまり、少ない試行から正確な結果を得られるということである。
SOR法 – モンテカルロ法を応用したSOR法はギブスサンプリングの一種とみなすことができ、散漫な動きを避けることがある。 ハイブリッドモンテカルロ法（HMC法）– ハミルトニアン・モンテカルロ法とも。補助の運動量ベクトルを導入しポテンシャルが対象となる確率分布の負の対数密度関数となるハミルトニアンを構築する。標準的な方法では，ハミルトニアン方程式を近似的に解く確定的動きと、運動量ベクトルを更新する確率的動きによって候補を生成する。確定的な動きのおかげでHMC法でのマルコフ連鎖は標本空間をより大きなステップで移動し、相関が弱く、目標の分布により素早く収束することが期待される。 NUTS法 – ベイズ統計学で広く用いられる、統計モデリングプラットフォームである Stan では、HMC法の変法である NUTS法（No-U-Turn Sampler）が採用されている。 スライスサンプリングの一部は散漫な動きを回避する。
次元の変化 はメトロポリス・ヘイスティングス法の拡張で、次元の異なる空間からの候補を許容する。この手法は1995年にブリストル大学のピーター・グリーン（Peter Green）によって考案された。次元の変化する MCMC は分布が大正準集団である問題（箱の中の分子の数が変動する場合など）を解くのに統計力学の分野で長い間使われている。
脚注
参考文献
関連文献 和文献 福島孝治, 「マルコフ連鎖モンテカルロ法の実践」, 2005年度東京工業大学大学院総合理工研究科知能システム科学特別講義資料 C.M. ビショップ：「パターン認識と機械学習下: ベイズ理論による統計的予測」、シュプリンガー・ジャパン株式会社 (2008年). Olle Häggström(著)、野間口謙太郎(訳)：「やさしいMCMC入門：有限マルコフ連鎖とアルゴリズム」、共立出版、ISBN 978-4-320-11314-5 (2017年5月10日). 洋文献 Christophe Andrieu et al: An Introduction to MCMC for Machine Learning, 2003 Bernd A. Berg: Markov Chain Monte Carlo Simulations and Their Statistical Analysis. Singapore, World Scientific 2004. George Casella and Edward I. George: "Explaining the Gibbs sampler". The American Statistician, 46:167-174, (1992). (Basic summary and many references.) A.E. Gelfand and A.F.M. Smith: "Sampling-Based Approaches to Calculating Marginal Densities". J. American Statistical Association, 85:398-409, (1990). Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin: Bayesian Data Analysis. London: Chapman and Hall. First edition, (1995). (See Chapter 11.) S. Geman and D. Geman: "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images". IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721-741, (1984). Radford M. Neal: Probabilistic Inference Using Markov Chain Monte Carlo Methods, (1993). Gilks W.R., Richardson S. and Spiegelhalter D.J. : Markov Chain Monte Carlo in Practice, Chapman & Hall/CRC (1996). C.P. Robert and G. Casella: "Monte Carlo Statistical Methods" (second edition), New York: Springer-Verlag (2004). R. Y. Rubinstein and D. P. Kroese: Simulation and the Monte Carlo Method (second edition), New York: John Wiley & Sons (2007). R. L. Smith: "Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions", Operations Research, Vol.32, pp.1296-1308 (1984). Asmussen and Glynn: Stochastic Simulation: Algorithms and Analysis, Springer. Series: Stochastic Modelling and Applied Probability, Vol. 57 (2007). P. Atzberger: An Introduction to Monte-Carlo Methods. A. Mantzaris: MCMC sampling and other methods in a basic overview.
関連項目 ベイズ推定 逐次モンテカルロ法 焼きなまし法 魔方陣、ラテン方陣 メトロポリス法 メトロポリス・ヘイスティングス法 量子モンテカルロ法 パラレルテンパリング レプリカ交換法