``Introduction to the Numerical Solution of Markov Chains''

William J. Stewart

Billy's Home Page


Preface,   Organization,   Acknowledgements
Ordering Information

Table of Contents

  
Preface and Acknowledgments   xv 

1 MARKOV CHAINS  3 
  1.1 Introduction  3 
  1.2 Markov Chains  4 
  1.3 Discrete-Time Markov Chains  5 
      1.3.1 Definition  5 
      1.3.2 The Chapman--Kolmogorov Equations  6 
      1.3.3 Classification of States  8 
      1.3.4 Irreducibility  13 
      1.3.5 Probability Distributions  14 
      1.3.6 Steady-State Distributions of Ergodic Markov Chains  16 
  1.4 Continuous-Time Markov Chains  17 
      1.4.1 Definitions  17 
      1.4.2 Transition Probabilities and Transition Rates  18 
      1.4.3 The Embedded Markov Chain  20 
      1.4.4 The Chapman--Kolmogorov Equations  22 
      1.4.5 Probability Distributions  22 
  1.5 Nonnegative Matrices  24 
      1.5.1 Definition  24 
      1.5.2 Nonnegative Decomposable Matrices  25 
      1.5.3 The Theorem of Perron--Frobenius  26 
  1.6 Stochastic Matrices  28 
      1.6.1 Definition  28 
      1.6.2 Some Properties of Stochastic Matrices  28 
      1.6.3 Effect of the Discretization Parameter, \Delta t  31 
      1.6.4 Eigenvalues of Decomposable Stochastic Matrices  33 
      1.6.5 Eigenvectors of Decomposable Stochastic Matrices  35 
      1.6.6 Nearly Decomposable Stochastic Matrices  38 
  1.7 Cyclic Stochastic Matrices  39 
      1.7.1 Definition  39 
      1.7.2 Eigenvalues of Cyclic Stochastic Matrices  40 
      1.7.3 Example: A Decomposable System with Cyclic Subgroups  40 
  1.8 Indicators of State Clustering  42 
      1.8.1 Significance of Subdominant, Right-Hand Eigenvectors  42 
      1.8.2 A Resource Pool Example  44 
  1.9 Queueing Models  49 
      1.9.1 Specification  50 
      1.9.2 Markov Chain Analysis of Queueing Networks  53 
      1.9.3 Example 1: Two Stations in Tandem  54 
      1.9.4 Example 2: One Coxian and Two Exponential Servers  57 

2 DIRECT METHODS  61 
  2.1 Introduction  61 
  2.2 Direct Methods  63 
      2.2.1 Gaussian Elimination  63 
      2.2.2 The  LU  Decomposition  66 
      2.2.3 The  LDU  Decomposition  68 
      2.2.4 Inverse Iteration  68 
  2.3 Direct Methods and Markov Chains  70 
      2.3.1 Handling the Singularity  71 
      2.3.2 To Transpose or Not to Transpose  77 
  2.4 Implementation Considerations  78 
      2.4.1 Implementation in Two-Dimensional Storage Arrays  78 
      2.4.2 Compact Storage Schemes for Direct Methods  78 
      2.4.3 Simultaneous Row Generation and Reduction  81 
      2.4.4 Back-Substitution and Normalization  84 
  2.5 The GTH Advantage  84 
  2.6 Sample Experiments with Direct Methods  87 
      2.6.1 An Interactive Computer System Model  88 
      2.6.2 Two Coxian Queues: A Highly Structured Example  91 
  2.7 Stability, Conditioning, and Error Analysis  101 
      2.7.1 Stable Algorithms and Well-Conditioned Problems  101 
      2.7.2 Floating-Point Representation of Real Numbers  104 
      2.7.3 Backward Error Analysis  106 
      2.7.4 Error Analysis for Gaussian Elimination  109 
      2.7.5 Condition Numbers, Residuals, and the Group Inverse  117 

3 ITERATIVE METHODS  121 
  3.1 The Power Method  121 
      3.1.1 Introduction  121 
      3.1.2 Application to an Arbitrary Matrix, A  122 
      3.1.3 Application to a Stochastic Matrix, P  124 
      3.1.4 Comparison with Matrix Powering  125 
  3.2 Jacobi, Gauss--Seidel, SOR, and Symmetric SOR  125 
      3.2.1 The Nonhomogeneous Case  126 
      3.2.2 The Method of Jacobi  127 
      3.2.3 The Method of Gauss--Seidel  128 
      3.2.4 The SOR Method  131 
      3.2.5 The Symmetric SOR Method: SSOR  132 
      3.2.6 Examples  133 
  3.3 Block Iterative Methods  138 
      3.3.1 MATLAB Code and Examples  141 
  3.4 Preconditioned Power Iterations  143 
      3.4.1 Gauss--Seidel, SOR, and SSOR Preconditionings  144 
      3.4.2 ILU  Preconditioning  144 
      3.4.3 Examples  146 
      3.4.4 Summary  150 
  3.5 Implementation Considerations  151 
      3.5.1 Sparse Storage Schemes  151 
      3.5.2 Choice of an Initial Iteration Vector  155 
      3.5.3 Normalization of Successive Approximations  156 
      3.5.4 Testing for Convergence  156 
      3.5.5 Choosing a Relaxation Parameter for SOR  159 
      3.5.6 The Effect of State Space Orderings on Convergence  163 
  3.6 Convergence Properties  169 
      3.6.1 Definitions  169 
      3.6.2 Convergence Theorems  170 
      3.6.3 Application to Markov Chains  176 

4 PROJECTION METHODS  177 
  4.1 Introduction  177 
      4.1.1 Preliminaries  177 
      4.1.2 General Projection Processes  179 
      4.1.3 Projection Processes for Linear Systems  179 
      4.1.4 Projection Processes for Eigenvalue Problems  181 
      4.1.5 Application to Markov Chains  181 
  4.2 Simultaneous Iteration  182 
      4.2.1 A Generic Subspace Iteration Algorithm  182 
      4.2.2 ``LOPSI'': A Lopsided Simultaneous Iteration Algorithm  184 
  4.3 Krylov Subspaces  187 
      4.3.1 Gram--Schmidt Orthogonalization Procedures  188 
  4.4 GMRES and the Method of Arnoldi  190 
      4.4.1 Arnoldi for Eigensolutions  190 
      4.4.2 FOM --- The Full Orthogonalization Method  192 
      4.4.3 GMRES --- The Generalized Minimal Residual Method  194 
      4.4.4 Application to Markov Chains  196 
      4.4.5 Examples  196 
      4.4.6 Iterative, Incomplete, and Preconditioned Methods  197 
      4.4.7 Examples, continued  199 
      4.4.8 Implementation  201 
      4.4.9 The Complete Iterative GMRES Algorithm with Preconditioning  205 
  4.5 Lanczos and Conjugate Gradients  207 
      4.5.1 The Symmetric Lanczos Algorithm  207 
      4.5.2 The Unsymmetric Lanczos Algorithm  210 
      4.5.3 The ``Look-Ahead'' Lanczos Algorithm  214 
      4.5.4 CG -- The Conjugate Gradient Algorithm  215 
      4.5.5 CGNR --- Conjugate Gradient for the Normal Equations  218 
      4.5.6 BCG and CGS --- Conjugate Gradient for Nonsymmetric Systems  220 
      4.5.7 Preconditioning  222 
      4.5.8 Examples  224 
  4.6 MATLAB Programs  225 

5 BLOCK HESSENBERG MATRICES AND SOLUTION BY RECURSION  231 
  5.1 Hessenberg Matrices  231 
      5.1.1 Definitions  231 
      5.1.2 Standard Queueing Recursions as Forward 
            Substitutions  232 
      5.1.3 Block Hessenberg Matrices  233 
  5.2 Block Recursive Methods  234 
      5.2.1 The Recursive Procedure  235 
      5.2.2 Example: A Telephone System with N Lines and K Operators  240 
  5.3 The Matrix-Geometric Approach  258 
      5.3.1 Introduction  258 
      5.3.2 Matrix Geometric Solutions: The Matrix R  258 
      5.3.3 Implementation: Computing R and \pi_0  260 
      5.3.4 Example: The \lambda/C_2/1 Queue  262 
      5.3.5 Alternative Methods for Finding R  264 
      5.3.6 The Quasi-Birth-Death (QBD) Case  266 
  5.4 Explicit Solution of Matrix-Geometric Problems  270 
      5.4.1 Queueing Systems for Which R May Be Explicitly Computed  272 
      5.4.2 Systems for Which R Must Be Computed Explicitly  278 
      5.4.3 Systems for Which R Must Be Computed Iteratively  280 
      5.4.4 Example: A Markovian Queue with N Servers Subject to Breakdowns and Repairs  281 

6 DECOMPOSITIONAL METHODS  285 
  6.1 NCD Markov Chains  285 
      6.1.1 Introduction and Background  285 
      6.1.2 Definitions  286 
      6.1.3 Block Solutions  287 
      6.1.4 The Coupling Matrix  289 
      6.1.5 The NCD Approximation --- A Rayleigh--Ritz Refinement Step  292 
  6.2 Stochastic Complementation  294 
      6.2.1 Definition  294 
      6.2.2 Properties of the Stochastic Complement  296 
      6.2.3 Computing Stationary Distributions by Stochastic Complementation  299 
      6.2.4 Relationship with Block Gaussian Elimination  300 
      6.2.5 Computational Aspects of Stochastic Complementation  302 
  6.3 Iterative Aggregation/Disaggregation Methods  307 
      6.3.1 Introduction  307 
      6.3.2 The Basic IAD Algorithm  307 
      6.3.3 The Takahashi IAD Algorithm  311 
      6.3.4 Other IAD Variants  316 
      6.3.5 Restructuring an NCD Matrix  316 
      6.3.6 Implementation Considerations  320 
      6.3.7 MATLAB Experiments  323 
      6.3.8 A Large Experiment  325 
  6.4 Convergence Properties and Behavior  332 
      6.4.1 Necessary Conditions for a ``Regular'' NCD Stochastic Matrix  332 
      6.4.2 Three Lemmas to Characterize Approximations  336 
      6.4.3 A Convergence Theorem  340 

7 P-CYCLIC MARKOV CHAINS  343 
  7.1 Introduction  343 
  7.2 Directed Graphs and P-Cyclic Matrices  348 
      7.2.1 Graph Terminology and Definitions  348 
      7.2.2 Primitive and Cyclic Matrices  352 
  7.3 P-Cyclic Markov Chains  355 
      7.3.1 The Embedded Markov Chain  355 
      7.3.2 Markov Chains with Periodic Graphs  355 
      7.3.3 Computation of the Periodicity  356 
  7.4 Numerical Methods Applied to P-Cyclic Matrices  359 
      7.4.1 Direct Methods  359 
      7.4.2 The Gauss--Seidel Iterative Method  360 
      7.4.3 Numerical Experiments  361 
  7.5 Reduced Schemes  364 
      7.5.1 Reduced Schemes Associated with a Stochastic Matrix  364 
      7.5.2 Reduced Schemes Associated with an Infinitesimal Generator  366 
      7.5.3 Numerical Methods Based on the Reduced Scheme  367 
      7.5.4 Numerical Experiments  369 
  7.6 IAD Methods for NCD, P-Cyclic Markov Chains  371 
      7.6.1 Iterative Aggregation/Disaggregation (IAD) Methods  372 
      7.6.2 Ordering for Periodicity and Decomposability  372 
      7.6.3 Application to P-Cyclic Matrices  373 
  7.7 Block SOR and Optimum Relaxation  374 
      7.7.1 Introduction  374 
      7.7.2 A 3-Cyclic Queueing Network Example  377 
      7.7.3 A P-step Iteration Procedure  380 
      7.7.4 Convergence Conditions for Block SOR  391 
      7.7.5 Applicable Values for the Relaxation Parameter  394 
      7.7.6 Convergence Testing in the Extended Sense  398 
      7.7.7 Optimal Convergence Factors and Associated \omega values  400 
      7.7.8 Computing the Subvector Multipliers  403 

8 TRANSIENT SOLUTIONS  407 
  8.1 Introduction  407 
  8.2 Uniformization  408 
      8.2.1 The Basic Concepts  408 
      8.2.2 The Truncation Error  410 
      8.2.3 Implementation  411 
  8.3 Methods Applicable to Small State Spaces  413 
      8.3.1 Matrix Decompositional Methods  414 
      8.3.2 Matrix Scaling and Powering  416 
  8.4 Ordinary Differential Equation (ODE) Solvers  422 
      8.4.1 Ordinary Differential Equations  423 
      8.4.2 Numerical Solutions and Stability  426 
      8.4.3 Elementary Numerical Algorithms  429 
      8.4.4 Stiff ODEs  434 
      8.4.5 Single-Step Methods  436 
      8.4.6 Multistep Methods  444 
      8.4.7 Software Sources and Comparisons  450 
  8.5 Krylov Subspace Methods  453 
      8.5.1 Introduction  453 
      8.5.2 The Basic Krylov Subspace Approach  454 
      8.5.3 Corrected Schemes and Error Bounds  457 
      8.5.4 Error Estimates and Step Size Control  458 
  8.6 Selected Experiments  460 

9 STOCHASTIC AUTOMATA NETWORKS  463 
  9.1 Introduction  463 
  9.2 Noninteracting Stochastic Automata  464 
      9.2.1 Independent, Two-Dimensional Markov Chains  464 
      9.2.2 Basic Properties of Tensor Algebra  464 
      9.2.3 Probability Distributions  466 
  9.3 Interacting Stochastic Automata  467 
      9.3.1 A Simple Example  467 
      9.3.2 Functional Transition Rates and Synchronizing Events  467 
      9.3.3 The Effect of Synchronizing Events  469 
      9.3.4 The Effect of Functional Transition Rates  472 
  9.4 Computing Probability Distributions  474 
  9.5 Multiplication with a Vector  475 
      9.5.1 The Nonfunctional Case  476 
      9.5.2 Multiplication in the Presence of Functional Elements  479 
      9.5.3 The Use of Symmetric Permutations  480 
      9.5.4 When All Else Fails  481 
  9.6 Iterative Solution Methods  483 
      9.6.1 Unpreconditioned Methods  483 
      9.6.2 Preconditioning  484 
  9.7 A Queueing Network Example  486 

10 SOFTWARE  491 
   10.1 The Categories of Available Software  491 
        10.1.1 Introduction  491 
        10.1.2 Libraries of Numerical Algorithms  492 
        10.1.3 Queueing Networks  493 
        10.1.4 Stochastic Petri Nets  496 
        10.1.5 Other Software  498 
   10.2 MARCA --- MARkov Chain Analyzer  500 
        10.2.1 Basic Concepts and Terminology  500 
        10.2.2 Model Definition in MARCA  503 
        10.2.3 Numerical Methods  504 
   10.3 XMARCA: A Graphical Interface for Queueing Networks  505 
        10.3.1 Introduction  505 
        10.3.2 Building a Queueing Network Model  506 
        10.3.3 Converting the Graphical Representation  509 
        10.3.4 Matrix Generation and Numerical Solutions  509 
        10.3.5 Displaying Results  512 

Bibliography   513 
Index   529 

Billy's Home Page