The Metropolis-Hastings algorithm
Bayesian Statistics Statistics 4224/5224 Spring 2021
March 9, 2021
1
The following notes summarize Sections 11.0, 11.2 and 12.2 of Bayesian Data Analysis, by Andrew Gelman et al.
Markov chain Monte Carlo
Markov chain simulation (also called Markov chain Monte Carlo, or MCMC) is a general method based on drawing values of θ from approximate distributions and then correcting those draws to better approximate the target distribution.
The sampling is done sequentially, with the distribution of the sampled draws depending on the last value drawn; hence, the draws form a Markov chain.
2
Markov chain simulation is used when it is not possible (or not computationally efficient) to sample θ directly from p(θ|y); in- stead we sample iteratively in such a way that at each step of the process we expect to draw from a distribution that becomes closer to p(θ|y).
The key to Markov chain simulation is to create a Markov process whose stationary distribution is the specified p(θ|y) and to run the simulation long enough that the distribution of the current draws is close enough to this stationary distribution.
For any specific p(θ|y), or unnormalized density q(θ|y), a variety of Markov chains with the desired property can be constructed.
3
The Metropolis-Hastings algorithm
The Metropolis-Hastings algorithm is a general term for a family of Markov chain simulation methods that are useful in sampling from Bayesian posterior distributions.
The inputs consist of:
• a starting point θ0, for which p(θ0|y) > 0;
• a jumping proposal distribution J(·|·) such that θ∗ ∼ J(θ∗|θ)
can be easily simulated for any θ such that p(θ|y) > 0;
• the target density p(θ|y), or an unnormalized version q(θ|y). 4
The output is θ1,θ2,…,θT, a partial realization of an ergodic Markov chain for which p(θ|y) is the unique stationary density.
The algorithm is defined by its update rule: For t = 1,2,…,T, given the current state θt−1, the update θt is generated by:
1. Sample a proposal, θ∗ ∼ J(θ∗|θt−1). 2. Calculate the Hastings ratio,
3. Set
r = p(θ∗|y) J (θt−1|θ∗) . p(θt−1|y) J (θ∗|θt−1)
θ∗ with probability min(r,1)
θt = θt−1 with probability 1 − min(r, 1) , i.e.,
sample u∼Unif(0,1); if u
Toy example
As a simple toy example, consider the target distribution θ ∼ Exponential(1) so p(θ|y) = e−θ , θ > 0 .
11
• For a Metropolis-Hastings independence sampler with θ∗ ∼ Exponential(λ) proposals, the acceptance probability is given by
−θ∗ −λθt−1
) = e λe = e(λ−1)(θ∗−θt−1)
e−θt−1 λe−λθ∗
• For a Metropolis random walk with θ∗ ∼ Normal(θt−1,σ2)
distributions, the acceptance probability reduces to r = p(θ∗|y) = e−(θ∗−θt−1) .
p(θt−1|y)
Courseworks → Files → Examples → Example12 .
12
∗ t−1 r = p(θ |y) g(θ
p(θt−1|y) g(θ∗)
Example: Two-dimensional Metropolis random walk
Target distribution: θ1, θ2 ∼ iid Normal(0, 1)
Proposal distribution: θ∗|θt−1 ∼ Normal2(θt−1, 0.22I)
Five simulation runs starting from different points.
50 iterations 500 iterations 5 chains combined
● ●
●● ● ● ● ●●
●● ● ●●●● ●
● ● ● ●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●● ●● ●●●●
● ● ● ● ●●
●
● ● ● ●
●●●
●●●●● ● ●●● ●●● ● ●●● ●● ●●● ●● ● ● ●●●● ●● ● ●● ● ● ● ●●●● ● ● ●●
●
● ● ● ● ● ● ●
●●●● ●
●● ●●● ● ●●●● ●● ● ●●●●●● ● ●●●●●●●●●●●● ● ● ● ● ●● ● ●●● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ●● ● ● ●● ● ● ● ● ● ● ● ● ●●● ●● ● ● ● ● ● ● ● ●● ●● ● ● ● ●
●●
● ● ● ●●● ●● ●● ●
● ●
● ● ●●●● ●●●●●●●●●●● ● ●●● ●● ●● ●●●●●●●
●
● ● ●
● ● ● ● ●
● ● ● ● ●
● ●
●● ● ● ● ●
● ●
● ●
●● ● ●● ● ● ● ●●●● ●
●
● ●●● ●●● ●●●●●●●●●●●●●●●●●● ● ●●●●●● ●●●
●
●
●
●●● ●●
●
●
●
●● ●●●●●● ●
●● ● ● ● ●
●
●
●
● ●
● ● ●●
●●● ● ●
● ●●
●● ●● ● ● ●●●●
●
● ● ● ● ●●● ● ● ●
● ● ●● ● ● ●●● ●
●● ● ●●●●●●
●
● ● ● ●●
●
●● ●● ●●●●● ●●●●●●●●●●●●●● ●●●●●●●● ●●●● ●● ● ● ●●● ● ●●● ●●● ● ●●●●● ●●●●●●●●●●●●● ● ● ● ●●●●● ●
●
● ●● ●●● ● ● ●
●● ●
● ● ●
● ●●●
● ●● ● ● ● ● ●●
●
●● ● ● ●
●● ● ●● ● ●
●
●●●●●●●●●●●●●●● ●●●●● ●●
●●● ● ●●●●●●●● ●●●●●●● ●●●● ●● ● ●●●●●●●●●●●●●●●●●●●●● ●
●● ● ●●● ●●●●●●●● ●●●● ● ● ●●●● ● ●●
● ●●●●●●●●● ●●●● ●●● ●●●● ● ● ●● ● ●●●●●●●●●●●●●●●● ●●●●●● ●●
●● ●●●● ●●●●●●●● ● ● ● ●
● ● ● ●●●
●●● ● ● ●● ●●
●●●●●●●● ●● ●●●●●●● ● ● ● ●● ● ●●● ●●●● ●●●● ● ● ●●●●●● ●●●●● ●● ●
●●● ●● ●
● ●● ● ● ● ●● ●●● ●●● ●● ●●●●●● ●●●● ●●●●●●● ●●●●●
● ●● ● ●● ●●
●
●●●●●● ●● ●
●
●
●●●●● ●
●
●● ● ●
●●
●● ●● ●●●●●●● ● ●●● ●
●
−4 −2 0 2 4 −4 −2 0 2 4 −4 −2 0 2 4
Coursesworks → Files → Examples → Ex11b Metropolis . 13
−4 −2 0 2 4
−4 −2 0 2 4
−4 −2 0 2 4