Denumerable Markov Chains: With a Chapter of Markov Random Fields by David Griffeath

With the first edition out of print, we decided to arrange for republi­ cation of Denumerrible Markov Ohains with additional bibliographic material. The new edition contains a section Additional Notes that indicates some of the developments in Markov chain theory over the last ten years. As in the first edition and for the same reasons, we have resisted the temptation to follow the theory in directions that deal with uncountable state spaces or continuous time. A section entitled Additional References complements the Additional Notes. J. W. Pitman pointed out an error in Theorem 9-53 of the first edition, which we have corrected. More detail about the correction appears in the Additional Notes. Aside from this change, we have left intact the text of the first eleven chapters. The second edition contains a twelfth chapter, written by David Griffeath, on Markov random fields. We are grateful to Ted Cox for his help in preparing this material. Notes for the chapter appear in the section Additional Notes. J.G.K., J.L.S., A.W.K.

1: Prerequisites from Analysis.- 1. Denumerable Matrices.- 2. Measure Theory.- 3. Measurable Functions and Lebesgue Integration.- 4. Integration Theorems.- 5. Limit Theorems for Matrices.- 6. Some General Theorems from Analysis.- 2: Stochastic Processes.- 1. Sequence Spaces.- 2. Denumerable Stochastic Processes.- 3. Borel Fields in Stochastic Processes.- 4. Statements of Probability Zero or One.- 5. Conditional Probabilities.- 6. Random Variables and Means.- 7. Means Conditional on Statements.- 8. Problems.- 3: Martingales.- 1. Means Conditional on Partitions and Functions.- 2. Properties of Martingales.- 3. A First Martingale Systems Theorem.- 4. Martingale Convergence and a Second Systems Theorem.- 5. Examples of Convergent Martingales.- 6. Law of Large Numbers.- 7. Problems.- 4: Properties of Markov Chains.- 1. Markov Chains.- 2. Examples of Markov Chains.- 3. Applications of Martingale Ideas.- 4. Strong Markov Property.- 5. Systems Theorems for Markov Chains.- 6. Applications of Systems Theorems.- 7. Classification of States.- 8. Problems.- 5: Transient Chains.- 1. Properties of Transient Chains.- 2. Superregular Functions.- 3. Absorbing Chains.- 4. Finite Drunkard’s Walk.- 5. Infinite Drunkard’s Walk.- 6. A Zero-One Law for Sums of Independent Random Variables.- 7. Sums of Independent Random Variables on the Line.- 8. Examples of Sums of Independent Random Variables.- 9. Ladder Process for Sums of Independent Random Variables.- 10. The Basic Example.- 11. Problems.- 6: Recurrent Chains.- 1. Mean Ergodic Theorem for Markov Chains.- 2. Duality.- 3. Cyclicity.- 4. Sums of Independent Random Variables.- 5. Convergence Theorem for Noncyclic Chains.- 6. Mean First Passage Time Matrix.- 7. Examples of the Mean First Passage Time Matrix.- 8. Reverse Markov Chains.- 9. Problems.- 7: Introduction to Potential Theory.- 1. Brownian Motion.- 2. Potential Theory.- 3. Equivalence of Brownian Motion and Potential Theory.- 4. Brownian Motion and Potential Theory in n Dimensions.- 5. Potential Theory for Denumerable Markov Chains.- 6. Brownian Motion as a Limit of the Symmetric Random Walk.- 7. Symmetric Random Walk in n Dimensions.- 8: Transient Potential Theory.- 1. Potentials.- 2. The h-Process and Some Applications.- 3. Equilibrium Sets and Capacities.- 4. Potential Principles.- 5. Energy.- 6. The Basic Example.- 7. An Unbounded Potential.- 8. Applications of Potential-Theoretic Methods.- 9. General Denumerable Stochastic Processes.- 10. Problems.- 9: Recurrent Potential Theory.- 1. Potentials.- 2. Normal Chains.- 3. Ergodic Chains.- 4. Classes of Ergodic Chains.- 5. Strong Ergodic Chains.- 6. The Basic Example.- 7. Further Examples.- 8. The Operator K.- 9. Potential Principles.- 10. A Model for Potential Theory.- 11. A Nonnormal Chain and Other Examples.- 12. Two-Dimensional Symmetric Random Walk.- 13. Problems.- 10: Transient Boundary Theory.- 1. Motivation for Martin Boundary Theory.- 2. Extended Chains.- 3. Martin Exit Boundary.- 4. Convergence to the Boundary.- 5. Poisson-Martin Representation Theorem.- 6. Extreme Points of the Boundary.- 7. Uniqueness of the Representation.- 8. Analog of Fatou’s Theorem.- 9. Fine Boundary Functions.- 10. Martin Entrance Boundary.- 11. Application to Extended Chains.- 12. Proof of Theorem 10.9.- 13. Examples.- 14. Problems.- 11: Recurrent Boundary Theory.- 1. Entrance Boundary for Recurrent Chains.- 2. Measures on the Entrance Boundary.- 3. Harmonic Measure for Normal Chains.- 4. Continuous and T-Continuous Functions.- 5. Normal Chains and Convergence to the Boundary.- 6. Representation Theorem.- 7. Sums of Independent Random Variables.- 8. Examples.- 9. Problems.- 12: Introduction to Random Fields.- 1 Markov Fields.- 2. Finite Gibbs Fields.- 3. Equivalence of Finite Markov and Neighbor Gibbs Fields.- 4. Markov Fields and Neighbor Gibbs Fields: the Infinite Case.- 5. Homogeneous Markov Fields on the Integers.- 6. Examples of Phase Multiplicity in Higher Dimensions.- 7. Problems.- Notes.- Additional Notes.- References.- Additional References.- Index of Notation.