"Markov Chains: Analytic and Monte Carlo Computations" introduces the main notions related to Markov chains and provides explanations on how to characterize, simulate, and recognize them. Starting with basic notions, this book leads progressively to advanced and recent topics in the field, allowing the reader to master the main aspects of the classical theory. This book also features: Numerous exercises with solutions as well as extended case studies. A detailed and rigorous presentation of Markov chains with discrete time and state space. An appendix presenting probabilistic notions that are necessary to the reader, as well as giving more advanced measure-theoretic notions.
Preface ix
List of Figures xi
Nomenclature xiii
Introduction xv
1 First steps 1 (46)
1.1 Preliminaries 1 (1)
1.2 First properties of Markov chains 2 (9)
1.2.1 Markov chains, finite-dimensional 2 (3)
marginals, and laws
1.2.2 Transition matrix action and 5 (4)
matrix notation
1.2.3 Random recursion and simulation 9 (1)
1.2.4 Recursion for the instantaneous 10 (1)
laws, invariant laws
1.3 Natural duality: algebraic approach 11 (10)
1.3.1 Complex eigenvalues and spectrum 11 (4)
1.3.2 Doeblin condition and strong 15 (2)
irreducibility
1.3.3 Finite state space Markov chains 17 (4)
1.4 Detailed examples 21 (26)
1.4.1 Random walk on a network 21 (1)
1.4.2 Gambler's ruin 22 (3)
1.4.3 Branching process: evolution of a 25 (2)
population
1.4.4 Ehrenfest's Urn 27 (6)
1.4.5 Renewal process 33 (3)
1.4.6 Word search in a character chain 36 (2)
1.4.7 Product chain 38 (2)
Exercises 40 (7)
2 Past, present, and future 47 (32)
2.1 Markov property and its extensions 47 (4)
2.1.1 Past σ-field, filtration, 47 (1)
and translation operators
2.1.2 Markov property 48 (2)
2.1.3 Stopping times and strong Markov 50 (1)
property
2.2 Hitting times and distribution 51 (9)
2.2.1 Hitting times, induced chain, and 51 (2)
hitting distribution
2.2.2 "One step forward" method, 53 (7)
Dirichlet problem
2.3 Detailed examples 60 (19)
2.3.1 Gambler's ruin 60 (4)
2.3.2 Unilateral hitting time for a 64 (3)
random walk
2.3.3 Exit time from a box 67 (1)
2.3.4 Branching process 67 (4)
2.3.5 Word search 71 (2)
Exercises 73 (6)
3 Transience and recurrence 79 (40)
3.1 Sample paths and state space 79 (8)
3.1.1 Communication and closed 79 (1)
irreducible classes
3.1.2 Transience and recurrence, 80 (3)
recurrent class decomposition
3.1.3 Detailed examples 83 (4)
3.2 Invariant measures and recurrence 87 (10)
3.2.1 Invariant laws and measures 87 (2)
3.2.2 Canonical invariant measure 89 (2)
3.2.3 Positive recurrence, invariant 91 (2)
law criterion
3.2.4 Detailed examples 93 (4)
3.3 Complements 97 (22)
3.3.1 Hitting times and superharmonic 97 (2)
functions
3.3.2 Lyapunov functions 99 (6)
3.3.3 Time reversal, reversibility, and 105 (3)
adjoint chain
3.3.4 Birth-and-death chains 108 (3)
Exercises 111 (8)
4 Long-time behavior 119 (36)
4.1 Path regeneration and convergence 119 (9)
4.1.1 Pointwise ergodic theorem, 120 (4)
extensions
4.1.2 Central limit theorem for Markov 124 (2)
chains
4.1.3 Detailed examples 126 (2)
4.2 Long-time behavior of the 128 (12)
instantaneous laws
4.2.1 Period and aperiodic classes 128 (4)
4.2.2 Coupling of Markov chains and 132 (7)
convergence in law
4.2.3 Detailed examples 139 (1)
4.3 Elements on the rate of convergence 140 (15)
for laws
4.3.1 The Hilbert space framework 140 (3)
4.3.2 Dirichlet form, spectral gap, and 143 (3)
exponential bounds
4.3.3 Spectral theory for reversible 146 (3)
matrices
4.3.4 Continuous-time Markov chains 149 (1)
Exercises 150 (5)
5 Monte Carlo methods 155 (16)
5.1 Approximate solution of the Dirichlet 155 (7)
problem
5.1.1 General principles 155 (1)
5.1.2 Heat equation in equilibrium 156 (2)
5.1.3 Heat equation out of equilibrium 158 (1)
5.1.4 Parabolic partial differential 159 (3)
equations
5.2 Invariant law simulation 162 (9)
5.2.1 Monte Carlo methods and ergodic 162 (1)
theorems
5.2.2 Metropolis algorithm, Gibbs law, 163 (3)
and simulated annealing
5.2.3 Exact simulation and backward 166 (5)
recursion
Appendix A Complements 171 (24)
A.1 Basic probabilistic notions 171 (6)
A.1.1 Discrete random variable, 171 (4)
expectation, and generating function
A.1.2 Conditional probabilities and 175 (2)
independence
A.2 Discrete measure convergence 177 (6)
A.2.1 Total variation norm and maximal 177 (3)
coupling
A.2.2 Duality between measures and 180 (2)
functions
A.2.3 Weak convergence of laws and 182 (1)
convergence in law
A.3 Measure-theoretic framework 183 (12)
A.3.1 Probability spaces 183 (2)
A.3.2 Measurable spaces and functions: 185 (1)
signed and nonnegative
A.3.3 Random variables, their laws, and 186 (6)
expectations
A.3.4 Random sequences and Kolmogorov 192 (3)
extension theorem
References 195 (2)
Solutions for the exercises 197 (32)
Index 229
新书报道