Finite Markov chains and algorithmic applications

Based on a lecture course given at Chalmers University of Technology, this book is suitable for advanced undergraduate and beginning graduate students in statistics and computer science, and for mathematicians. Necessary background in probability theory and Markov chains is developed, then applied to the study of a range of randomized algorithms with applications on optimization and other problems in computing. Algorithms covered are the Markov chain Monte Carlo method, simulated annealing, and the recently developed Propp- Wilson algorithm.