Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues (Texts in Applied Mathematics, 31)

✍ Scribed by Pierre Bremaud

• Publisher: Springer
• Year: 2008
• Tongue: English
• Leaves: 462
• Edition: Corrected
• Category: Library

✦ Synopsis

In this book, the author begins with the elementary theory of Markov chains and very progressively brings the reader to the more advanced topics. He gives a useful review of probability that makes the book self-contained, and provides an appendix with detailed proofs of all the prerequisites from calculus, algebra, and number theory. A number of carefully chosen problems of varying difficulty are proposed at the close of each chapter, and the mathematics are slowly and carefully developed, in order to make self-study easier. The author treats the classic topics of Markov chain theory, both in discrete time and continuous time, as well as the connected topics such as finite Gibbs fields, nonhomogeneous Markov chains, discrete- time regenerative processes, Monte Carlo simulation, simulated annealing, and queuing theory. The result is an up-to-date textbook on stochastic processes. Students and researchers in operations research and electrical engineering, as well as in physics and biology, will find it very accessible and relevant.

✦ Table of Contents

MARKOV CHAINS: GIBBS FIELDS, MONTE CARLO SIMULATION, AND QUEUES
Texts in Applied Mathematics
Title Page
Copyright Page
Dedication
Series Preface
Preface
From Pushkin to Monte Carlo
A Useful, Simple, and Beautiful Theory
Basic Theory and Advanced Topics
Acknowledgments
Contents
Chapter 1. Probability Review
1 Basic Concepts
1.1 Events
1.2 Random Variables
1.3 Probability
2 Independence and Conditional Probability
2.1 Independence of Events and of Random Variables
2.2 Bayes's Rules
2.3 Markov Property
3 Expectation
3.1 Cumulative Distribution Function
3.2 Expectation, Mean, and Variance
3.3 Famous Random Variables
4 Random Vectors
4.1 Absolutely Continuous Random Vectors
4.2 Discrete Random Vectors
4.3 Product Formula for Expectation
5 Transforms of Probability Distributions
5.1 Generating Functions
5.2 Characteristic Functions
6 Transformations of Random Vectors
6.1 Smooth Change of Variables
6.2 Order Statistics
7 Conditional Expectation of Discrete Variables
7.1 Definition and Basic Properties
7.2 Successive Conditioning
8 The Strong Law of Large Numbers
8.1 Borel–Cantelli Lemma
8.2 Almost-Sure Convergence
8.3 Markov's Inequality
8.4 Proof of Kolmogorov's SLLN
Problems
Chapter 2. Discrete-Time Markov Models
1 The Transition Matrix
1.1 Markov Property
1.2 Distribution of an HMC
2 Markov Recurrences
2.1 A Canonical Representation
2.2 A Few Famous Examples
3 First-Step Analysis
3.1 Absorption Probability
3.2 Mean Time to Absorption
4 Topology of the Transition Matrix
4.1 Communication
4.2 Period
5 Steady State
5.1 Stationarity
5.2 Examples
6 Time Reversal
6.1 Reversed Chain
6.2 Time Reversibility
7 Regeneration
7.1 Strong Markov Property
7.2 Regenerative Cycles
Problems
Chapter 3. Recurrence and Ergodicity
1 Potential Matrix Criterion
1.1 Recurrent and Transient States
1.2 Potential Matrix
1.3 Structure of the Transition Matrix
2 Recurrence and Invariant Measures
3 Positive Recurrence
3.1 Stationary Distribution Criterion
3.2 Examples
4 Empirical Averages
4.1 Ergodic Theorem
4.2 Examples
4.3 Renewal Reward Theorem
Problems
Chapter 4. Long Run Behavior
1 Coupling
1.1 Convergence in Variation
1.2 The Coupling Method
2 Convergence to Steady State
2.1 Positive Recurrent Case
2.2 Null Recurrent Case
2.3 Thermodynamic Irreversibility
2.4 Convergence Rates via Coupling
3 Discrete-Time Renewal Theory
3.1 Renewal Equation
3.2 Renewal Theorem
3.3 Defective Renewal Sequences
4 Regenerative Processes
4.1 Renewal Equation of a Regenerative Process
4.2 Regenerative Theorem
5 Life Before Absorption
5.1 Infinite Sojourns
5.2 Time to Absorption
6 Absorption
6.1 Fundamental Matrix
6.2 Absorption Matrix
Problems
Chapter 5. Lyapunov Functions and Martingales
1 Lyapunov Functions
1.1 Foster's Theorem
1.2 Queuing Applications
2 Martingales and Potentials
2.1 Harmonic Functions and Martingales
2.2 The Maximum Principle
3 Applications of Martingales to HMCs
3.1 The Two Pillars of Martingale Theory
3.2 Transience and Recurrence via Martingales
3.3 Absorption via Martingales
Problems
Chapter 6. Eigenvalues and Nonhomogeneous Markov Chains
1 Finite Transition Matrices
1.1 Perron–Frobenius Theorem
1.2 Quasi-stationary Distributions
2 Reversible Transition Matrices
2.1 Eigenstructure and Diagonalization
2.2 Spectral Theorem
3 Convergence Bounds Without Eigenvectors
3.1 Basic Bounds, Reversible Case
3.2 Nonreversible Case
4 Geometric Bounds
4.1 Weighted Paths
4.2 Conductance
5 Probabilistic Bounds
5.1 Separation and Strong Stationary Times
5.2 Convergence Rates via Strong Stationary Times
6 Fundamental Matrix of Recurrent Chains
6.1 Definition of the Fundamental Matrix
6.2 Mutual Time-Distance Matrix
6.3 Variance of Ergodic Estimates
7 The Ergodic Coefficient
7.1 Dobrushin's Inequality
7.2 Interaction Coefficients and Coincidence
8 Nonhomogeneous Markov Chains
8.1 Ergodicity of Nonhomogeneous Markov Chains
8.2 Block Criterion of Weak Ergodicity
8.3 Sufficient Condition of Strong Ergodicity
Problems
Chapter 7. Gibbs Fields and Monte Carlo Simulation
1 Markov Random Fields
1.1 Neighborhoods and Local Specification
1.2 Cliques, Potential, and Gibbs Distributions
2 Gibbs–Markov Equivalence
2.1 From the Potential to the Local Specification
2.2 From the Local Specification to the Potential
3 Image Models
3.1 Textures
3.2 Lines and Points
4 Bayesian Restoration of Images
4.1 MAP Likelihood Estimation
4.2 Penalty Methods
5 Phase Transitions
5.1 Spontaneous Magnetization
5.2 Peierls's Argument
6 Gibbs Sampler
6.1 Simulation of Random Fields
6.2 Convergence Rate of the Gibbs Sampler
7 Monte Carlo Markov Chain Simulation
7.1 General Principle
7.2 Convergence Rates in MCMC
7.3 Variance of Monte Carlo Estimators
8 Simulated Annealing
8.1 Stochastic Descent and Cooling
8.2 Convergence of Simulated Annealing
Problems
Chapter 8. Continuous-Time Markov Models
1 Poisson Processes
1.1 Point Processes
1.2 Counting Process of an HPP
1.3 Competing Poisson Processes
2 Distribution of a Continuous-Time HMC
2.1 Transition Semigroup
2.2 Infinitesimal Generator
3 Kolmogorov's Differential Systems
3.1 Finite State Space
3.2 General Case
3.3 Regular Jumps
4 The Regenerative Structure
4.1 Strong Markov Property
4.2 Embedded Chain and Transition Times
4.3 Explosions
5 Recurrence
5.1 Stationary Distribution Criterion of Ergodicity
5.2 Time Reversal
6 Long-Run Behavior
6.1 Ergodic Chains
6.2 Absorbing Chains
Problems
Chapter 9. Poisson Calculus and Queues
1 Continuous-Time Markov Chains as Poisson Systems
1.1 Strong Markov Property of HPPs
1.2 From Generator to Markov Chain
2 Stochastic Calculus of Poisson Processes
2.1 Counting Integrals and the Smoothing Formula
2.2 Kolmogorov's Forward System via Poisson Calculus
2.3 Watanabe's Characterization of Poisson Processes
3 Poisson Systems
3.1 The Purely Poissonian Description
3.2 The GSMP construction
3.3 Markovian Queues as Poisson Systems
4 Markovian Queuing Theory
4.1 Isolated Markovian Queues


4.4 Markovian Queuing Networks
Problems
Appendix
1 Number Theory and Calculus
1.1 Greatest Common Divisor
1.2 Abel's Theorem
1.3 Lebesgue's Theorems for Series
1.4 Infinite Products
1.5 Tychonov's Theorem
1.6 Subadditive Functions
2 Linear Algebra
2.1 Eigenvalues and Eigenvectors
2.2 Exponential of a Matrix
2.3 Gershgorin's Bound
3 Probability
3.1 Expectation Revisited
3.2 Lebesgue's Theorems for Expectation
Bibliography
Author Index
Subject Index
Texts in Applied Mathematics (continued from page ii)
Back Cover