Finite Markov Chains and Algorithmic Applications (Q4534877)

It is a very nice introduction to the modern theory of Markov chain simulation algorithms. Using finite state models only, the author describes MCMC technique (with the Gibbs and Metropolis samplers), perfect simulation and simulated annealing methods. The use of MCMC is illustrated by application to the counting of \(q\)-colorings of some graph. It is demonstrated how naive algorithms of counting (deterministic and i.i.d. Monte Carlo) fail in solving this problem and how MCMC produces a polynomial time approximation algorithm. The Propp-Wilson algorithm for the perfect simulation is described in the general setting and for the Ising model. The author discusses coupling from the past and sandwiching technique. Simulated annealing is applied to the traveling salesman problem. Correct and clear proofs are given for the main results. The author starts from the axioms of probability and finishes by proofs of convergence of simulated annealing schemes. Many examples and counterexamples discussed by the author and left as problems for the reader clarify the main concepts. 13 figures are really helpful for understanding the text. The book can be recommended for advanced undergraduate and beginning postgraduate students of mathematics, theoretical physics, statistics and computer science.