This book covers the basic theory of Markov chains and uses it to study three random algorithms with applications in optimization and computing:
(1) Markov Chain Monte Carlo.
(2) Perfect Simulation.
(3) Simulated Annealing.
The focus is on finite-state discrete-time Markov chains, which are technically more accessible than Markov chains with an infinite state space and/or a continuous time parameter.
The content of the book is:
Chapter 1: Basics of probability theory (reminder).
Chapters 2-6: Basics of Markov chain theory.
Chapters 7-9: Markov Chain Monte Carlo.
Chapters 10-12: Perfect Simulation.
Chapter 13: Simulated Annealing.
The course will be offered at a rate of one chapter per week. Each chapter includes a number of exercises, some of which require computer programming.
The course provides a solid introduction into an important area of modern probability theory.
Prerequisite
Inleiding kansrekening
Literature
O. H\“aggstr\“om, Finite Markov Chains and Algorithmic Applications, London Mathematical Society Student Texts 12, Cambridge University Press, 2002 (ISBN-13 978-0-521-89001-4 paperback)
Examination
Schriftelijk tentamen
Coursecode TUD
WI3604