To some extent, it would be accurate to summarize the contents of this book as an intolerably protracted description of what happens when either one raises a transition probability matrix P (i.e., all entries (P) are nonnegative and each row of P sums to 1) to higher and higher powers or one exponentiates R(P-I), where R is a diagonal matrix with non-negative entries. Indeed, when it comes right down to it, that is all that is done in this book. However, I, and others of my ilk, would take offense at such a dismissive characterization of the theory of Markov chains and processes with values in a countable state space, and a primary goal of mine in writing this book was to convince its readers that our offense would be warranted.

Preface

Chapter 1 Random Walks A Good Place to Begin

 1.1. Nearest Neighbor Random Wlalks on Z

1.1.1. Distribution at Time n

1.1.2. Passage Times via the Reflection Principle

1.1.3. Some Related Computations

1.1.4. Time of First Return

1.1.5. Passage Times via Functional Equations

 1.2. Recurrence Properties of Random Walks

1.2.1. Random Walks on Zd

1.2.2. An Elementary Recurrence Criterion

1.2.3. Recurrence of Symmetric Random Walk in Zz

1.2.4. nansience in Z3

 1.3. Exercises

Chapter 2 Doeblin’S Theory for Markov Chains

 2.1. Some Generalities

2.1.1. Existence of Markov Chains

2.1.2. Transion Probabilities＆Probability Vectors

2.1.3. nansition Probabilities and Functions

2.1.4. The Markov Property

 2.2. Doeblin’S Theory

2.2.1. Doeblin’S Basic Theorem

2.2.2. A Couple of Extensions

2.3. Elements of Ergodic Theory

2.3.1. The Mean Ergodic Theorem

2.3.2. Return Times

2.3.3. Identification of π

 2.4. Exercises

Chapter 3 More about the Ergodic Theory of Markov Chains

 3.1. Classification of States

3.1.1. Classification，Recurrence，and Transience

3.1.2. Criteria for Recurrence and Transmnge

3.1.3. Periodicity

 3.2. Ergodic Theory without Doeblin

3.2.1. Convergence of Matrices

3.2.2. Ab el Convergence

3.2.3. Structure of Stationary Distributions

3.2.4. A Small Improvement

3.2.5. The Mcan Ergodic Theorem Again

3.2.6. A Refinement in The Aperiodic Case

3.2.7. Periodic Structure

 3.3. Exercises

Chapter 4 Markov Processes in Continuous Time

 4.1. Poisson Processes

4.1.1. The Simple Poisson Process

4.1.2. Compound Poisson Processes on Z

 4.2. Markov Processes with Bounded Rates

4.2.1. Basic Construction

4.2.2. The Markov Property

4.2.3. The Q—Matrix and Kolmogorov’S Backward Equation

4.2.4. Kolmogorov’S Forward Equation

4.2.5. Solving Kolmogorov’S Equation

4.2.6. A Markov Process from its Infinitesimal Characteristics

 4.3. Unbounded Rates

4.3.1. Explosion

4.3.2. Criteria for Non.explosion or Explosion

4.3.3. What to Do When Explosion Occurs

 4.4. Ergodic Properties.

4.4.1. Classification of States

4.4.2. Stationary Measures and Limit Theorems

4.4.3. Interpreting πii

 4.5. Exercises

Chapter 5 Reversible Markov Proeesses

 5.1. R，eversible Markov Chains

5.1.1. Reversibility from Invariance

5.1.2. Measurements in Quadratic Mean

5.1.3. The Spectral Gap

5.1.4. Reversibility and Periodicity

5.1.5. Relation to Convergence in Variation

 5.2. Dirichlet Forms and Estimation of β

5.2.1. The Dirichlet Fo·rm and Poincar4’S Inequality，

5.2.2. Estimating β+

5.2.3. Estimating β-

 5.3. Reversible Markov Processes in Continuous Time

5.3.1. Criterion for Reversibility

5.3.2. Convergence in L2(π) for Bounded Rates

5.3.3. L2(π)Convergence Rate in General

5.3.4. Estimating λ

 5.4. Gibbs States and Glauber Dynamics

5.4.1. Formulation

5.4.2. The Dirichlet Form

 5.5. Simulated Annealing

5.5.1. The Algorithm

5.5.2. Construction of the Transition Probabilities

5.5.3. Description of the Markov Process

5.5.4. Choosing a Cooling Schedule

5.5.5. Small Improvements

 5.6. Exercises

Chapter 6 Some Mild Measure Theory

 6.1. A Description of Lebesgue's Measure Theory

6.1.1. Measure Spaces

6.1.2. Some Consequences of Countable Additivity

6.1.3. Generating a-Algebras

6.1.4. Measurable Functions

6.1.5. Lebesgue Integration

6.1.6. Stability Properties of Lebesgue Integration

6.1.7. Lebesgue Integration in Countable Spaces

6.1.8. Fubini's Theorem

 6.2. Modeling Probability

6.2.1. Modeling Infinitely Many Tosses of a Fair Coin

 6.3. Independent Random Variables

6.3.1. Existence of Lots of Independent Random Variables

 6.4. Conditional Probabilities and Expectations

6.4.1. Conditioning with Respect to Random Variables

Notation

References

Index