Markov Chain Models - Rarity and Exponentiality

in failure time distributions for systems modeled by finite chains. This introductory chapter attempts to provide an over­ view of the material and ideas covered. The presentation is loose and fragmentary, and should be read lightly initially. Subsequent perusal from time to time may help tie the mat­ erial together and provide a unity less readily obtainable otherwise. The detailed presentation begins in Chapter 1, and some readers may prefer to begin there directly. §O.l. Time-Reversibility and Spectral Representation. Continuous time chains may be discussed in terms of discrete time chains by a uniformizing procedure (§2.l) that simplifies and unifies the theory and enables results for discrete and continuous time to be discussed simultaneously. Thus if N(t) is any finite Markov chain in continuous time governed by transition rates vmn one may write for pet) = [Pmn(t)] • P[N(t) = n I N(O) = m] pet) = exp [-vt(I - a )] (0.1.1) v where v > Max r v ' and mn m n law ~ 1 - v-I * Hence N(t) where is governed r vmn Nk = NK(t) n K(t) is a Poisson process of rate v indep- by a ' and v dent of N • k Time-reversibility (§1.3, §2.4, §2.S) is important for many reasons. A) The only broad class of tractable chains suitable for stochastic models is the time-reversible class.

0. Introduction and Summary.- 1. Discrete Time Markov Chains; Reversibility in Time.- §1.00. Introduction.- §1.0. Notation, Transition Laws.- §1.1. Irreducibility, Aperiodicity, Ergodicity; Stationary Chains.- §1.2. Approach to Ergodicity; Spectral Structure, Perron-Romanovsky-Frobenius Theorem.- §1.3. Time-Reversible Chains.- 2. Markov Chains in Continuous Time; Uniformization; Reversibility.- §2.00. Introduction.- §2.0. Notation, Transition Laws; A Review.- §2.1. Uniformizable Chains — A Bridge Between Discrete and Continuous Time Chains.- §2.2. Advantages and Prevalence of Uniformizable Chains.- §2.3. Ergodicity for Continuous Time Chains.- §2.4. Reversibility for Ergodic Markov Chains in Continuous Time.- §2.5. Prevalence of Time-Reversibility.- 3. More on Time-Reversibility; Potential Coefficients; Process Modification.- §3.00. Introduction.- §3.1. The Advantages of Time-Reversibility.- §3.2. The Spectral Representation.- §3.3. Potentials; Spectral Representation.- §3.4. More General Time-Reversible Chains.- §3.5. Process Modifications Preserving Reversibility.- §3.6. Replacement Processes.- 4. Potential Theory, Replacement, and Compensation.- §4.00. Introduction.- §4.1. The Green Potential.- §4.2. The Ergodic Distribution for a Replacement Process.- §4.3. The Compensation Method.- §4.4. Notation for the Homogeneous Random Walk.- §4.5. The Compensation Method Applied to the Homogeneous Random Walk Modified by Boundaries.- §4.6. Advantages of the Compensation Method. An Illustrative Example.- §4.7. Exploitation of the Structure of the Green Potential for the Homogeneous Random Walk.- §4.8. Similar Situations.- 5. Passage Time Densities in Birth-Death Processes; Distribution Structure.- §5.00. Introduction.- §5.1. Passage Time Densities for Birth-Death Processes.- §5.2. Passage Time Moments for a Birth-Death Process.- §5.3. PF?, Complete Monotonicity, Log-Concavity and Log-Convexity.- §5.4. Complete Monotonicity and Log-Convexity.- §5.5. Complete Monotonicity in Time-Reversible Processes.- §5.6. Some Useful Inequalities for the Families CM and PF?.- §5.7. Log-Concavity and Strong Unimodality for Lattice Distributions.- §5.8. Preservation of Log-Concavity and Log-Convexity under Tail Summation and Integration.- §5.9. Relation of CM and PF? to IFR and DFR Classes in Reliability.- 6. Passage Times and Exit Times for More General Chains.- §6.00. Introduction.- §6.1. Passage Time Densities to a Set of States.- §6.2. Mean Passage Times to a Set via the Green Potential.- §6.3. Ruin Probabilities via the Green Potential.- §6.4. Ergodic Flow Rates in a Chain.- §6.5. Ergodic Exit Times, Ergodic Sojourn Times, and Quasi-Stationary Exit Times.- §6.6. The Quasi-Stationary Exit Time. A Limit Theorem.- §6.7. The Connection Between Exit Times and Sojourn Times. A Renewal Theorem.- §6.8. A Comparison of the Mean Ergodic Exit Time and Mean Ergodic Sojourn Time for Arbitrary Chains.- §6.9. Stochastic Ordering of Exit Times of Interest for Time-Reversible Chains.- §6.10. Superiority of the Exit Time as System Failure Time; Jitter.- 7. The Fundamental Matrix, and Allied Topics.- §7.00. Introduction.- §7.1. The Fundamental Matrix for Ergodic Chains.- §7.2. The Structure of the Fundamental Matrix for Time-Reversible Chains.- §7.3. Mean Failure Times and Ruin Probabilities for Systems with Independent Markov Components and More General Chains.- §7.4. Covariance and Spectral Density Structure for Time-Reversible Processes.- §7.5. A Central Limit Theorem.- §7.6. Regeneration Times and Passage Times-Their Relation For Arbitrary Chains.- §7.7. Passage to a Set with Two States.- 8. Rarity and Exponentiality.- §8.0. Introduction.- §8.1. Passage Time Density Structure for Finite Ergodic Chains; the Exponential Approximation.- §8.2. A Limit Theorem for Ergodic Regenerative Processes.- §8.3. Prototype Behavior: Birth-Death Processes; Strongly Stable Systems.- §8.4. Limiting Behavior of the Ergodic and Quasi-stationary Exit Time Densities and Sojourn Time Densities for Birth-Death Processes.- §8.5. Limit Behavior of Other Exit Times for More General Chains.- §8.6. Strongly Stable Chains, Jitter; Estimation of the Failure Time Needed for the Exponential Approximation.- §8.7. A Measure of Exponentiality in the Completely Monotone Class of Densities.- §8.8. An Error Bound for Departure from Exponentiality in the Completely Monotone Class.- §8.9. The Exponential Approximation for Time-Reversible Systems.- §8.10. A Relaxation Time of Interest.- 9. Stochastic Monotonicity.- §9.00. Introduction.- §9.1. Monotone Markov Matrices and Monotone Chains.- §9.2. Some Monotone Chains in Discrete Time.- §9.3. Monotone Chains in Continuous Time.- §9.4. Other Monotone Processes in Continuous Time.- References.