查看“梅特罗波利斯－黑斯廷斯算法”的源代码

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

该算法的名称源于美国物理学家[[尼古拉斯·梅特罗波利斯]]<ref name=metropolis>{{cite journal
 |first1=N. |last1=Metropolis 
 |first2=A.W. |last2=Rosenbluth 
 |first3=M.N. |last3=Rosenbluth 
 |first4=A.H. |last4=Teller 
 |first5=E. |last5=Teller 
 |title=Equations of State Calculations by Fast Computing Machines
 |journal=Journal of Chemical Physics
 |volume=21 |issue=6 |pages=1087–1092 |year=1953
 |doi=10.1063/1.1699114
|bibcode = 1953JChPh..21.1087M }}</ref>与加拿大统计学家{{le|W·K·黑斯廷斯|W. K. Hastings}}。<ref name=Hastings>{{cite journal
 |first=W.K. |last=Hastings
 |title=Monte Carlo Sampling Methods Using Markov Chains and Their Applications
 |journal=Biometrika
 |volume=57 |issue=1 |pages=97–109 |year=1970 
 |jstor=2334940 | zbl = 0219.65008 |doi=10.1093/biomet/57.1.97
}}</ref>

== 算法 ==
假设<math>P(x)</math>为目标概率分布。梅特罗波利斯－黑斯廷斯算法的过程为：
# 初始化 
## 选定初始状态<math>x_0</math>；
## 令<math>t=0</math>；
# 迭代过程
## '''生成：''' 从某一容易抽样的分布<math>Q(x' | x_t)</math>中随机生成候选状态<math>x'</math>；{{noteTag|1=该分布称为提议分布（proposal distribution），当其对称时（即满足<math>Q(x'|x)=Q(x|x')</math>），是梅特罗波利斯－黑斯廷斯算法的一类特例，称为梅特罗波利斯算法（Metropolis algorithm）。}}
## '''计算：''' 计算是否采纳候选状态的概率<math display="inline">A(x' | x) = \min\left(1,\frac{P(x')}{P(x)}\frac{Q(x | x')}{Q(x' | x)}\right)</math>；
## '''接受或拒绝''' 
### 从<math>[0,1]</math>的均匀分布中生成随机数<math>u</math>；
### 如<math>u \le A(x' | x)</math>，则接受该状态，并令<math>x_{t+1} = x'</math>；
### 如<math>u >   A(x' | x)</math>，则拒绝该状态，并令<math>x_{t+1} = x_{t}</math>（复制原状态）；
## '''增量：'''令<math display="inline">t=t+1</math>；

== 注释 ==
{{noteFoot}}

== 参考文献 ==
{{reflist}}
* 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 {{ISBN|0-470-04609-0}}

[[Category:蒙地卡羅方法]]