马尔可夫链蒙特卡洛

马尔可夫链蒙特卡洛（英語：Markov chain Monte Carlo，MCMC）方法（含随机游走蒙特卡洛方法）是一组用马氏链从随机分布取样的算法，之前步骤的作为底本。步数越多，结果越好。

建立一个具有期望属性的马氏链并非难事，难的是如何决定通过多少步可以达到在许可误差内的稳定分布。一个好的马氏链具有快速混合——从开始阶段迅速获得的一个稳定状态——请参考马氏链最大时间。

因于初始样本，最常见的MCMC取样只能近似得到分布。复杂的MCMC改进算法如过往耦合，但是会消耗更多的计算资源和时间。

典型用法是模拟一个随机行走的行人来进行路径优化等。每一步都算作是一个状态。而统计经过次数最多的地方将在下一步中更有可能为目的地。马氏蒙特卡洛方法是一种结合了蒙特卡罗法的解决方案。但不同于以往的蒙特卡洛integration是统计独立的，MCMC中的是统计相关的。

本方法的相关应用包括：贝叶斯统计、计算物理、计算生物以及计算语言学，此外还有Gill先生的一些著作。

Jeff Gill. Bayesian methods: a social and behavioral sciences approach Second Edition. London: Chapman and Hall/CRC. 2008 [2012-02-07]. ISBN 1-58488-562-9. （原始内容存档于2009-05-23）.  引文格式1维护：冗余文本 (link) </ref> and Robert & Casella.[1]

随机游走算法

马氏链性质决定了下一个方位取决于当前状态和随机变量。这样的性质决定了最终所有的空间将被覆盖但是却需要花费较长时间。下面给出MCMC方法：

• Metropolis–Hastings算法：给出预见密度和回绝按照给出方向前进的方法。
• 吉布斯采样：取目标区域所有的条件分布样本。
• 平滑取样
• 多重实验Metropolis：Metropolis–Hastings算法的改良版本。

基本原理

设非周期正常返的马尔可夫链的平稳分布为${\displaystyle \pi }$，${\displaystyle S}$为马尔可夫链的状态，对于任意${\displaystyle S}$上有界函数${\displaystyle h}$有： ${\displaystyle P(\lim _{n\rightarrow \inf }{\frac {1}{n}}\sum _{k=0}^{n}h(X_{k})=\sum _{x\in S}\pi (x)h(x))=1}$，也就是说，该马尔可夫链在取的变量${\displaystyle X_{k}}$在${\displaystyle n}$比较大时会趋向于服从概率分布${\displaystyle \pi }$。

在设计一个马尔可夫链满足细致平衡的条件下，对马尔科夫链的模拟就可以看作对概率分布${\displaystyle \pi }$的采样。[2]

基本步骤

MCMC方法是使用马尔科夫链的蒙特卡洛积分，其基本思想是：构造一条Markov链使其平稳分布为待估参数的后验分布${\displaystyle \pi (x)}$，通过这条马尔科夫链产生后验分布的样本，并基于马尔科夫链达到平稳分布时的样本（有效样本）进行蒙特卡罗积分。设${\displaystyle n}$为产生的总样本数，${\displaystyle m}$为Markov链达到平稳时的样本数则MCMC方法的基本思路可概括为：

• 构造Markov链。构造一条Markov链，给定马尔科夫链状态转移矩阵${\displaystyle Q}$，使其收敛到平稳分布${\displaystyle \pi (x)}$；
• 产生样本：从初始状态${\displaystyle x_{0}\sim p_{0}}$出发，利用从条件概率分布${\displaystyle Q(x|x_{t})}$生成样本，并通过转移条件判断是否转移，通过${\displaystyle m}$次更新达到平稳，此后生成的即为${\displaystyle \pi (x)}$的样本，我们记为${\displaystyle x^{(1)},\cdots ,x^{(n)}}$；
• 蒙特卡罗积分。任一函数${\displaystyle f(x)}$的期望估计为：${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}f(x^{(i)})}$

在采用MCMC方法时马尔科夫链转移核的构造至关重要，不同的转移核构造方法将产生不同的MCMC方法，目前常用的MCMC方法主要有两种Gibbs抽样和Metropolis-Hastings算法。

抽样算法

l Gibbs '抽样'

Gibbs抽样是现实中最简单应用最广泛的MCMC方法，由Geman最初命名提出其基础思路如下：

给定任意的初始向量；

从中抽取样本

从中抽取样本

…

从中抽取样本

…

从中抽取样本

至此，完成的转移。经过n次迭代，可得后验样本。根据后验样本可计算后验分布的各阶矩，进行相应的统计推断。

• Metropolis-Hastings '算法'

Metropolis-Hastings算法是较早出现且比较一般化的MCMC方法，最初由Metropolis等人在1953年提出之后由Hastings对其加以推广形成了，Metropolis-Hastings方法。该方法的基本思路是：选择一转移函数和初始值，若第次迭代开始时的参数值为

，则第次迭代过程为：

• 从中抽取一个备选值

• 计算接受概率

• 以概率，置，以概率，置；
• 重复i –iii 次，则可得后验样本。根据后验样本可计算后验分布的各阶矩，进行相应的统计推断。

参见

• 贝叶斯推理
• 圖模式
• 马尔可夫链
• 马尔可夫逻辑网络

注释

1. Christian P Robert & Casella G. Monte Carlo statistical methods Second Edition. New York: Springer. 2004 [2012-02-07]. ISBN 0-387-21239-6. （原始内容存档于2010-01-12）.  引文格式1维护：冗余文本 (link)
2. 李东风. 统计计算. 2022-08-29 （中文）. 

参考文献

• 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. ISBN 978-0470177945
• 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." [1].
• Bolstad, William M.（2010）Understanding Computational Bayesian Statistics, John Wiley ISBN 0-470-04609-8

延展阅读

• Diaconis, Persi, "The Markov chain Monte Carlo revolution", Bull. Amer. Math. Soc.（2009）
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP, Section 15.8. Markov Chain Monte Carlo, Numerical Recipes: The Art of Scientific Computing 3rd, New York: Cambridge University Press, 2007 [2012-02-07], ISBN 978-0-521-88068-8, （原始内容存档于2011-08-11） 
• Richey, Matthew, "The Evolution of Markov Chain Monte Carlo Methods", The American Mathematical Monthly, May 2010, 383-413

外部链接

• MCMC sampling and other methods in a basic overview, by Alexander Mantzaris
• Visual demonstration of MCMC sampling methods (Java applet) （页面存档备份，存于互联网档案馆）, by Laird Breyer
• A Toy Example of MCMC sampling, by Zhiyuan Weng
• MCL - a cluster algorithm for graphs （页面存档备份，存于互联网档案馆）, by Stijn van Dongen