下一状态的可能位置]]
梅特罗波利斯-黑斯廷斯算法（）是统计学与统计物理中的一种马尔科夫蒙特卡洛（MCMC）方法，用于在难以直接采样时从某一概率分布中抽取随机样本序列。得到的序列可用于估计该概率分布或计算积分（如期望值）等。梅特罗波利斯－黑斯廷斯或其他MCMC算法一般用于从多变量（尤其是高维）分布中采样。对于单变量分布而言，常会使用自适应判别采样（adaptive rejection sampling）等其他能抽取独立样本的方法，而不会出现MCMC中样本自相关的问题。

该算法的名称源于美国物理学家尼古拉斯·梅特罗波利斯与加拿大统计学家W·K·黑斯廷斯。

算法
假设P(x)为目标概率分布。梅特罗波利斯－黑斯廷斯算法的过程为：

初始化

选定初始状态x_0；

令t=0；

迭代过程

生成：从某一容易抽样的分布Q(x' | x_t)中随机生成候选状态x'；

计算：计算是否采纳候选状态的概率A(x' | x) = \min\left(1,\frac{P(x')}{P(x)}\frac{Q(x | x')}{Q(x' | x)}\right)；

接受或拒绝

从[0,1]的均匀分布中生成随机数u；

如u \le A(x' | x)，则接受该状态，并令x_{t+1} = x'；

如u > A(x' | x)，则拒绝该状态，并令x_{t+1} = x_{t}（复制原状态）；

增量：令t=t+1；

注释
参考文献

Bernd A. Berg. Markov Chain Monte Carlo Simulations and Their Statistical Analysis. Singapore, World Scientific, 2004.
Siddhartha Chib and Edward Greenberg: "Understanding the Metropolis–Hastings Algorithm". American Statistician, 49(4), 327–335, 1995
[http://www.tandfonline.com/doi/abs/10.1080/03610918.2013.777455#.VOk8J1PF9_c David D. L. Minh and Do Le Minh. "Understanding the Hastings Algorithm." Communications in Statistics - Simulation and Computation, 44:2 332-349, 2015]
Bolstad, William M. (2010) Understanding Computational Bayesian Statistics, John Wiley & Sons

梅特罗波利斯-黑斯廷斯算法

初始化