Markov Chain Monte Carlo

In this chapter, we introduce and study time-independent Markov chains. The basic topics are covered including the random walk on a graph representation, the matrix representation, the state probability vector, the matrix calculation of it, and the invariant distribution. The Perron–Frobenius theorem is proved and used to show that regular Markov Chains have an invariant distribution which is the limit of the state probability vector as t increases. The very important Metropolis Algorithm is introduced which will play a central role in the rest of the book. It is shown that a Markov chain defined by the Metropolis Algorithm satisfies detail balance which implies that such a chain is regular. It is shown that a regular Markov Chain admits the calculation of expectations of the invariant distribution. The Metropolis–Hasting extension of the Metropolis algorithm is given. Statistical mechanics is developed as a prelude to studying the simulated annealing optimization method. The Boltzmann factor is derived from first principles. The application is made to the Ising Model and used to demonstrate the concept of phase change which sometimes occurs in simulated annealing implementations. Applications are made to the Monomer-Dimer problem, counting problems, and coupling from the past.