INSEAD Library

Includes bibliographical references and index and glossary

Digitized

Non-Negative Matrices and Markov Chains Contents Glossary of Notation and Symbols PART I FINITE NON-NEGATIVE MATRICES CHAPTER 1 Fundamental Concepts and Results in the Theory of Non-negative Matrices 1.1 The Perron-Frobenius Theorem for Primitive Matrices 1.2 Structure of a General Non-negative Matrix 1.3 Irreducible Matrices 1.4 Perron-Frobenius Theory for Irreducible Matrices Bibliography and Discussion Exercises xv 1 3 3 11 18 22 25 26 CHAPTER 2 Some Secondary Theory with Emphasis on Irreducible Matrices, and Applications 2.1 The Equations: (sl -- T)x = c Bibliography and Discussion to §2.1 Exercises on §2.1 2.2 Iterative Methods for Solution of Certain Linear Equation Systems Bibliography and Discussion to §2.2 Exercises on §2.2 2.3 Some Extensions of the Perron-Frobenius Structure Bibliography and Discussion to §2.3 Exercises on §2.3 2.4 Combinatorial Properties Bibliography and Discussion to §2.4 Exercises on §2.4 30 30 38 39 41 44 44 45 53 54 55 60 60 2.5 Spectrum Localization Bibliography and Discussion to §2.5 Exercises on §2.5 2.6 Estimating Non-negative Matrices from Marginal Totals Bibliography and Discussion to §2.6 Exercises on §2.6 61 64 66 67 75 79 CHAPTER 3 Inhomogeneous Products of Non-negative Matrices 3.1 Birkhoff's Contraction Coefficient: Generalities 3.2 Results on Weak Ergodicity Bibliography and Discussion to §§3.1-3.2 Exercises on X3.1-3.2 3.3 Strong Ergodicity for Forward Products Bibliography and Discussion to §3.3 Exercises on §3.3 3.4 Birkhoff's Contraction Coefficient: Derivation of Explicit Form Bibliography and Discussion to §3.4 Exercises on §3.4 80 80 85 88 90 92 99 100 100 111 111 CHAPTER 4 Markov Chains and Finite Stochastic Matrices 4.1 Markov Chains 4.2 Finite Homogeneous Markov Chains Bibliography and Discussion to §§4.1-4.2 Exercises on §4.2 4.3 Finite Inhomogeneous Markov Chains and Coefficients of Ergodicity 4.4 Sufficient Conditions for Weak Ergodicity Bibliography and Discussion to N4.3-4.4 Exercises on §§4.3-4.4 4.5 Strong Ergodicity for Forward Products Bibliography and Discussion to §4.5 Exercises on §4.5 4.6 Backwards Products Bibliography and Discussion to §4.6 Exercises on §4.6 112 113 118 131 132 134 140 144 147 149 151 152 153 157 158 PART II COUNTABLE NON-NEGATIVE MATRICES 159 CHAPTER 5 Countable Stochastic Matrices 5.1 Classification of Indices 5.2 Limiting Behaviour for Recurrent Indices 5.3 Irreducible Stochastic Matrices 161 161 168 172 5.4 The "Dual" Approach; Subinvariant Vectors 5.5 Potential and Boundary Theory for Transient Indices 5.6 Example Bibliography and Discussion Exercises 181 191 194 195 CHAPTER 6 Countable Non-negative Matrices 6.1 The Convergence Parameter R, and the R-Classification of T 6.2 R-Subinvariance and Invariance; R-Positivity 6.3 Consequences for Finite and Stochastic Infinite Matrices 6.4 Finite Approximations to Infinite Irreducible T 6.5 An Example Bibliography and Discussion Exercises 199 200 205 207 210 215 218 219 CHAPTER 7 Truncations of Infinite Stochastic Matrices 7.1 Determinantal and Cofactor Properties 7.2 The Probability Algorithm 7.3 Quasi-stationary Distributions Bibliography and Discussion Exercises 221 222 229 236 242 242 APPENDICES Appendix A. Some Elementary Number Theory Appendix B. Some General Matrix Lemmas Appendix C. Upper Semi-continuous Functions Bibliography Author Index Subject Index 245 247 252 255 257 271 275