Environmental Engineering Reference
In-Depth Information
MCMC algorithms as special cases. The Metropolis-Hastings algorithm proceeds by gen-
erating each new state of the Markov chain from a proposal distribution
q
(⋅|
x
(
k
)
) conditional
on the current state
x
(
k
)
and then accepts or rejects the sample with a certain acceptance
probability that depends on the current and proposed state. The Metropolis-Hastings algo-
rithm for generating
K
states of a Markov chain with stationary distribution equal to the
posterior distribution ′′
f
X
() can be summarized as follows.
Metropolis-hastings algorithm
1. Choose an arbitrary point
x
(0)
.
2.
k
= 1.
3. Generate a candidate
y
from
q
(
y
|
x
(
k
−1)
).
4. Compute the acceptance probability
Š
f
′′
()(
yx y
q
(
k
−
1
)
|
)
'
.
(
)
k
−
1
X
a
(
xy
, )
=
min
)
,
1
f
′′
(
x
(
k
−
1
)
) (
q
y x
|
(
k
−
1
)
X
5. Generate a sample
p
from the standard uniform distribution in [0,1].
6. If
p
<
a
(
x
(
k
−1)
,
y
), set
x
(
k
)
=
y
; otherwise, set
x
(
k
)
=
x
(
k
−1)
.
7.
k
=
k
+ 1.
8. Stop if
k
=
K
, else go to 2.
It is noted that evaluation of the acceptance probability does not require the knowledge of
the proportionality constant. The main computational effort consists of the evaluation of the
likelihood function for each candidate sample. Starting from a state that may or may not be
distributed according to the target distribution ′′
f
X
(),
it can be shown that, under certain restric-
tions on the choice of the proposal distribution, the algorithm will asymptotically converge to
the target distribution (Hastings 1970; Tierney 1994). However, the initial samples may follow a
significantly different distribution. Therefore, an initial number of samples (typically in the order
of 1000), constituting the so-called burn-in period, need to be discarded. It is often nontrivial
to assess whether the chain has converged after the initial burn-in phase (Plummer et al. 2006).
Typical choices of the proposal distribution
q
()
⋅|
x
are symmetric distributions centered
on the current state
x
(
k
)
, such as the normal or uniform distribution, leading to the so-called
random-walk samplers. The generated samples are correlated; however, their correlation can
be controlled by the choice of the dispersion parameter of the proposal distribution (Gelman
et al. 1996). However, the sample correlation increases significantly with the increase of the
dimension of the target distribution (Gelman et al. 1996). As a result, the classical Metropolis-
Hastings algorithm cannot be applied efficiently to high-dimensional problems. Some MCMC
algorithms (Duane et al. 1987; Roberts and Tweedie 1996; Haario et al. 2005; Cheung and
Beck 2009) can reduce the correlation of the Markov samples in high dimensions; however,
they require additional evaluations of the likelihood function or its gradient at each sample.
High-dimensional problems can be tackled efficiently in cases where a conjugate prior
describes each component of the prior distribution and hence its conditional distribution
given all other components can be derived analytically (see, e.g., Ching et al. 2006). In such
cases, it is advantageous to apply the so-called Gibbs sampling (Geman and Geman 1984).
Gibbs sampling, which can be understood as a special case of the Metropolis-Hastings
algorithm with acceptance probability of one, does not require parameter tuning and is
shown to accelerate the convergence of the chain to its stationary distribution as compared
to the classical Metropolis-Hastings algorithm (Gelman 2004).
k
(
)
Search WWH ::
Custom Search