1. Problem 15.37 Let c(i) be a given function on a finite set I. For any i ∈ I,a local neighborhood N(i) of other points from I is given such that k ∈ N(j)if j ∈ N(k). For ease, it is assumed that each set N(i) contains the same number of points. The following Markov chain is defined on I. If the current state is i, a candidate state j is chosen at random from N(i). The next state of the process is always j if c(j) < c(i); otherwise, the process moves to j with probability e−c(j)/T /e−c(i)/T and stays ini with probability 1 − e−c(j)/T/e−c(i)/T. Here T >

0 is a control parameter. It is assumed that the sets N(i) are such that the Markov chain is irreducible (that is, any state is accessible from any other state). Then, the unique equilibrium probabilities of the Markov chain are given by πi = e−c(i)/T/ k∈I e−c(k)/T for i ∈ I. Prove this result by verifying the reversibility condition e−c(j)/T pjk = e−c(k)/T pkj for all j,k, where the pjk are theone-steptransitionprobabilitiesoftheMarkovchain.Remark:ifthefunction c(i) assumes its absolute minimuminauniquepointm,thenπm → 1asT → 0

(verify). This fact is exploited in the simulated annealing algorithm that is often used to find the minimum of a function on a finite but very large set.