Given that G,j(T) and A1j(T) are selected as in Eq. 2.4 and 2.5, each state transition
matrix in the inhomogeneous Markov chain of the inhomogeneous algorithm satisfies all
of the sufficient conditions for stationary distribution existence and asymptotic conver-
gence to optimality developed for the homogeneous algorithm (i.e. irreducibility, aper-
iodicity and Eq. 2.8-2.10). Further, the explicit form of the resulting stationary
distribution is given by Eq. 2.11. Thus, for each transition matrix, PT), there exists an
eigenvector, q,, having eigenvalue 1 and satisfying the probability vector conditions.
Further, q. converges to the limiting distribution of Eq. 2.6 as Tk -+ 0. Consequently,
Theorem A7 can be used to establish strong ergodicity (and hence the desired conver-
gence behavior for Tk 0) provided (1) that weak ergodicity can be established and (2)
that the inequality appearing in Theorem A7 obtains.
Under the hypothesis that Gj(T) and Aj(T) are defined in accordance with Eq. 2.4
and 2.5, in which case the required eigenvector is explicitly provided by Eq. 2.11, and
that condition (1) (weak ergodicity) is satisfied, both [GeGe84] and [MiRo85] prove con-
dition (2) of the above. The development is straightforward but tedious. Of more interest
here is the means of establishing condition (1), because it leads to the annealing schedule
bound.
Both developments employ Theorem A6 to establish weak ergodicity. The general
approach is to use the definitions of Gj(T) and Aj(T), along with bounds on the extrema
of either the cost function [GeGe84] or the slope of the cost function [MiRo85] to define
bounds on the one step transition probabilities. The transition probability bound is then
employed to arrive at an upper bound on the t coefficient of ergodicity of Theorem A5,
which is used in turn in Theorem A6 to deduce a sufficient condition to guarantee weak
ergodicity. The condition is in the form of a lower bound on the annealing schedule.