satisfied. Beyond these requirements, existence of the stationary distribution of each Mar-
kov chain in the homogeneous algorithm only requires that the chain produced by PT be
irreducible and periodic (Definitions A7 and A9).
If A,(T) is selected as the Metropolis criterion, Eq. 2.4, then
Vi,j E, VT > 0 : Aj(T) > 0.
Thus, from Eq. 2.3, the irreducibility requirement is transferred to the next state genera-
tion mechanism, G,(T). Note that from Theorem Al, irreducibility can readily be
achieved within the definition supplied by Eq. 2.5. Also, in [MiRo85], Theorem A2 is
used to show that a sufficient condition for aperiodicity is
VT > 03i,je E 3 A(T) < 1.
This condition is satisfied by the Metropolis criterion provided the trivial case indicated
by
Vi,j eE : C(i) = C(j)= Copt
is excluded, because then k,l always exist such that
C(l) = Co, < C(k). Eq. 2.7
The sufficient condition on Aj(T) can then be met by selecting i = 1 and j = k. (Use Eq.
2.7 in Eq. 2.4).
Although existence of the stationary distribution (or at least sufficient conditions on
Gij(T) and Aj(T) to ensure its existence) are now established, and examples of Gi and Aj
which meet these conditions provided, actually achieving the stationary distribution is
only guaranteed after an infinite number of state transitions. This is equivalent to the ther-
mal equilibrium constraint on the temperature schedule for annealing solids discussed in
Section 2.2. Each Markov chain in the sequence representing the homogeneous algorithm
is subject to this requirement, and consequently must be of infinite length.
Next, sufficient conditions to assure convergence of the stationary distribution of
the final Markov chain in the homogeneous algorithm to the desired optimal distribution