employed, the conditions are satisfied, and that the corresponding stationary distribution
is provided by
exp{-(C(i) Cop)/kT}
Vi E: qT(i)= -C /kT} Eq. 2.11
Yexp{-(C(j) Cop/kT}
J
The key to that development is that the Gij(T) and A2j(T) of Eq. 2.4 and 2.5 satisfy the
detailed balance equation, the symmetry of G~i being a critical consideration.
The behavior required by Eq. 2.10(1) is limiting behavior as T -- 0. Thus, these
conditions assure convergence to the global minimum with probability one (i.e. conver-
gence of the stationary distribution to Eq. 2.6), only if the sequence of Markov chains is
infinite and lim T, = 0. Recalling that a guarantee of achieving the stationary distribution
requires that each Markov chain be of infinite length, the homogeneous algorithm is seen
to require a doubly infinite sequence of solutions composed of an infinite sequence of
infinitely long Markov chains.
2.4.2.2 The Inhomogeneous Algorithm
The behavior of the homogeneous algorithm, which requires that an infinite number
of transitions be executed at each control parameter value, clearly is not very useful. The
following reviews two published convergence results which extend the ideas developed
for the homogeneous algorithm to the inhomogeneous counterpart [GeGe84, MiRo85].
These results adopt the sufficient conditions on Gi(T) and Aj(T) developed for the homo-
geneous algorithm as a starting point (i.e. irreducibility, aperiodicity and Eq. 2.8-2.10)
and extend them to the case in which each time-homogeneous Markov chain is finite
length (i.e. to the inhomogeneous algorithm). The key products of this effort are lower
bounds on the algorithm control parameter's approach to zero. In both cases discussed
here, the bound is of the form K/log(k) where k is the index of the Markov chain repre-
senting the inhomogeneous algorithm and K is independent of k. The following is a brief
sketch of the approach taken to arrive at these results. It is common to both.