Page 188 - Applied Probability
P. 188
9. Descent Graph Methods
the way to the desired full restriction site AGCT. Once AGCT is attained,
the next base encountered will completely disrupt the pattern, and we are
back again at A, C, G, or T. This second chain has transition matrix
A C G T AG AGC AGCT 173
A .32 .18 0 .27 .23 0 0
C .37 .23 .05 .35 0 0 0
G .30 .21 .25 .24 0 0 0
P = T .23 .19 .25 .33 0 0 0 .
AG .30 0 .25 .24 0 .21 0
AGC .37 .23 .05 0 0 0 .35
AGCT .23 .19 .25 .33 0 0 0
9.3 The Hastings-Metropolis Algorithm and
Simulated Annealing
The Hastings-Metropolis algorithm is a device for constructing a Markov
chain with a prescribed equilibrium distribution π on a given state space
[13, 28]. Each step of the chain is broken into two stages, a proposal stage
and an acceptance stage. If the chain is currently in state i, then in the
proposal stage a new destination state j is proposed according to a proba-
bility density q ij = q(j | i). In the subsequent acceptance stage, a random
number is drawn uniformly from [0, 1] to determine whether the proposed
step is actually taken. If this number is less than the Hastings-Metropolis
acceptance probability
!
π j q ji
a ij =min 1, , (9.5)
π i q ij
then the proposed step is taken. Otherwise, the proposed step is declined,
and the chain remains in place.
Historically, Metropolis et al. [28] considered only symmetric proposal
densities with q ij = q ji . In this case the acceptance probability reduces to
!
π j
a ij =min 1, . (9.6)
π i
It is also noteworthy that in applying either formula (9.5) or formula (9.6),
the π i need only be known up to a multiplicative constant.
To prove that π is the equilibrium distribution of the chain constructed
from the Hastings-Metropolis scheme (9.5), it suffices to check that detailed
balance holds. If π puts positive weight on all points of the state space, it is
clear that we must impose the requirement that the inequalities q ij > 0 and
q ji > 0 are simultaneously true or simultaneously false. This requirement
