Finite Markov Chains and Algorithmic ApplicationsCambridge University Press, 30.05.2002 - 114 Seiten Based on a lecture course given at Chalmers University of Technology, this 2002 book is ideal for advanced undergraduate or beginning graduate students. The author first develops the necessary background in probability theory and Markov chains before applying it to study a range of randomized algorithms with important applications in optimization and other problems in computing. Amongst the algorithms covered are the Markov chain Monte Carlo method, simulated annealing, and the recent Propp-Wilson algorithm. This book will appeal not only to mathematicians, but also to students of statistics and computer science. The subject matter is introduced in a clear and concise fashion and the numerous exercises included will help students to deepen their understanding. |
Inhalt
Basics of probability theory | 1 |
Markov chains | 8 |
Computer simulation of Markov chains | 17 |
Irreducible and aperiodic Markov chains | 23 |
Stationary distributions | 28 |
Reversible Markov chains | 39 |
Markov chain Monte Carlo | 45 |
Fast convergence of MCMC algorithms | 54 |
The ProppWilson algorithm | 76 |
Sandwiching | 84 |
ProppWilson with readonce randomness | 93 |
Simulated annealing | 99 |
Further reading | 108 |
| 110 | |
| 113 | |
Approximate counting | 64 |
Andere Ausgaben - Alle anzeigen
Häufige Begriffe und Wortgruppen
aperiodic Markov chain Boltzmann distribution chain in Example chain is irreducible Chapter Chebyshev's inequality chessboard coalescence coin colors conditional probability consider counting problem defined definition denote edge Example 2.1 feasible configurations finite Gibbs sampler given graph G hard-core model Hence inhomogeneous Markov chain irreducible and aperiodic Ising model ladder walk Lemma Let Xo log(k Markov chain Xo Markov theory MCMC algorithm Metropolis chain neighbors number of q-colorings number of steps output P(Xmk permutation PG,q Pi,j probability distribution probability measure proof of Theorem Propp Propp-Wilson algorithm random numbers random q-colorings random variable random walk randomized algorithms restart reversible distribution run the chain s₁ sandwiching Show simulated annealing spin configuration square lattice stationary distribution Suppose temperature Theorem 5.2 total variation distance transition graph transition matrix Un+1 v₁ valid update function vertex set vertices