Finite Markov Chains and Algorithmic Applications

✍ Scribed by Olle Häggström

• Publisher: Cambridge University Press
• Year: 2002
• Tongue: English
• Leaves: 126
• Series: London Mathematical Society Student Texts 52
• Edition: 1
• Category: Library

✦ Synopsis

This text is ideal for advanced undergraduate or beginning graduate students. The author first develops the necessary background in probability theory and Markov chains before using it to study a range of randomized algorithms with important applications in optimization and other problems in computing. The book will appeal not only to mathematicians, but to students of computer science who will discover much useful material. This clear and concise introduction to the subject has numerous exercises that will help students to deepen their understanding.

✦ Table of Contents

Cover......Page 1
Title Page......Page 5
Contents......Page 7
Preface......Page 9
1 Basics of probability theory......Page 13
2 Markov chains......Page 20
3 Computer simulation of Markov chains......Page 29
4 Irreducible and aperiodic Markov chains......Page 35
5 Stationary distributions......Page 40
6 Reversible Markov chains......Page 51
7 Markov chain Monte Carlo......Page 57
8 Fast convergence of MCMC algorithms......Page 66
9 Approximate counting......Page 76
10 The Propp-Wilson algorithm......Page 88
11 Sandwiching......Page 96
12 Propp-Wilson with read-once randomness......Page 105
13 Simulated annealing......Page 111
14 Further reading......Page 120
References......Page 122
Index......Page 125