Introduction to the Numerical Solution of Markov Chains

Name: Introduction to the Numerical Solution of Markov Chains
Brand: Princeton University Press
Price: 172.99 EUR
Availability: OnlineOnly

William J. Stewart(Autor*in)

Princeton University Press

1. Auflage

Erschienen am 12. Januar 2021

561 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-0-691-22338-4 (ISBN)

172,99 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Person

Inhalt

Cover Page
Half-title Page
Title Page
Copyright Page
Dedication Page
Contents
Preface and Acknowledgments
1. Markov Chains
1.1 Introduction
1.2 Markov Chains
1.3 Discrete-Time Markov Chains
1.3.1 Definition
1.3.2 The Chapman-Kolmogorov Equations
1.3.3 Classification of States
1.3.4 Irreducibility
1.3.5 Probability Distributions
1.3.6 Steady-State Distributions of Ergodic Markov Chains
1.4 Continuous-Time Markov Chains
1.4.1 Definitions
1.4.2 Transition Probabilities and Transition Rates
1.4.3 The Embedded Markov Chain
1.4.4 The Chapman-Kolmogorov Equations
1.4.5 Probability Distributions
1.5 Nonnegative Matrices
1.5.1 Definition
1.5.2 Nonnegative Decomposable Matrices
1.5.3 The Theorem of Perron-Frobenius
1.6 Stochastic Matrices
1.6.1 Definition
1.6.2 Some Properties of Stochastic Matrices
1.6.3 Effect of the Discretization Parameter
1.6.4 Eigenvalues of Decomposable Stochastic Matrices
1.6.5 Eigenvectors of Decomposable Stochastic Matrices
1.6.6 Nearly Decomposable Stochastic Matrices
1.7 Cyclic Stochastic Matrices
1.7.1 Definition
1.7.2 Eigenvalues of Cyclic Stochastic Matrices
1.7.3 Example: A Decomposable System with Cyclic Subgioups
1.8 Indicators of State Clustering
1.8.1 Significance of Subdominant, Right-Hand Eigenvectors
1.8.2 A Resource Pool Example
1.9 Queueing Models
1.9.1 Specification
1.9.2 Markov Chain Analysis of Queueing Networks
1.9.3 Example 1: Two Stations in Tandem
1.9.4 Example 2: One Coxian and Two Exponential Servers
2. Direct Methods
2.1 Introduction
2.2 Direct Methods
2.2.1 Gaussian Elimination
2.2.2 The LU Decomposition
2.2.3 The LDU Decomposition
2.2.4 Inverse Iteration
2.3 Direct Methods and Markov Chains
2.3.1 Handling the Singularity
2.3.2 To Transpose or Not to Transpose
2.4 Implementation Considerations
2.4.1 Implementation in Two-Dimensional Storage Arrays
2.4.2 Compact Storage Schemes for Direct Methods
2.4.3 Simultaneous Row Generation and Reduction
2.4.4 Back-Substitution and Normalization
2.5 The GTH Advantage
2.6 Sample Experiments with Direct Methods
2.6.1 An Interactive Computer System Model
2.6.2 Two Coxian Queues: A Highly Structured Example
2.7 Stability, Conditioning, and Error Analysis
2.7.1 Stable Algorithms and Well-Conditioned Problems
2.7.2 Floating-Point Representation of Real Numbers
2.7.3 Backward Error Analysis
2.7.4 Error Analysis for Gaussian Elimination
2.7.5 Condition Numbers, Residuals, and the Group Inverse
3. Iterative Methods
3.1 The Power Method
3.1.1 Introduction
3.1.2 Application to an Arbitrary Matrix, A
3.1.3 Application to a Stochastic Matrix, P
3.1.4 Comparison with Matrix Powering
3.2 Jacobi, Gauss-Seidel, SOR, and Symmetric SOR
3.2.1 The Nonhomogeneous Case
3.2.2 The Method of Jacobi
3.2.3 The Method of Gauss-Seidel
3.2.4 The SOR Method
3.2.5 The Symmetric SOR Method : SSOR
3.2.6 Examples
3.3 Block Iterative Methods
3.3.1 MATLAB Code and Examples
3.4 Preconditioned Power Iterations
3.4.1 Gauss-Seidel, SOR , and SSOR Preconditionings
3.4.2 ILU Preconditioning
3.4.3 Examples
3.4.4 Summary
3.5 Implementation Considerations
3.5.1 Sparse Storage Schemes
3.5.2 Choice of a n Initial Iteration Vector
3.5.3 Normalization of Successive Approximations
3.5.4 Testing for Convergence
3.5.5 Choosing a Relaxation Parameter for SOR
3.5.6 The Effect of State Space Orderings on Convergence
3.6 Convergence Properties
3.6.1 Definitions
3.6.2 Convergence The orems
3.6.3 Application to Markov Chains
4. Projection Methods
4.1 Introduction
4.1.1 Preliminaries
4.1.2 General Projection Processes
4.1.3 Projection Processes for Linear Systems
4.1.4 Projection Processes for Eigenvalue Problems
4.1.5 Application to Markov Chains
4.2 Simultaneous Iteration
4.2.1 A Generic Subspace Iteration Algorithm
4.2.2 "LOPSI": A Lopsided Simultaneous Iteration Algorithm
4.3 Krylov Subspaces
4.3.1 Gram-Schmidt Orthogonalization Procedures
4.4 GMRES and the Method of Arnoldi
4.4.1 Arnoldi for Eigensolutions
4.4.2 FOM - The Full Orthogonalization Method
4.4.3 GMRES - The Generalized Minimal Residual Method
4.4.4 Application to Markov Chains
4.4.5 Examples
4.4.6 Iterative, Incomplete, and Preconditioned Methods
4.4.7 Examples , continued
4.4.8 Implementatio
4.4.9 The Complete Iterative GMRES Algorithm with Preconditioning
4.5 Lanczos and Conjugate Gradients
4.5.1 The Symmetric Lanczos Algorithm
4.5.2 The Unsymmetric Lanczos Algorithm
4.5.3 The "Look-Ahead" Lanczos Algorithm
4.5.4 CG -The Conjugate Gradient Algorithm
4.5.5 CGNR - Conjugate Gradient for The Normal Equations
4.5.6 BCG and CGS - Conjugate Gradient for Non symmetric Systems
4.5.7 Preconditioning
4.5.8 Examples
4.6 MATLAB Programs
5. Block Hessenberg Matrices and Solution by Recursion
5.1 Hessenberg Matrices
5.1.1 Definitions
5.1.2 Standard Queueing Recursions as Forward Substitutions
5.1.3 Block Hessenberg Matrices
5.2 Block Recursive Methods
5.2.1 The Recursive Procedure
5.2.2 Example: A Telephone System with N Lines and K Operators
5.3 The Matrix-Geometric Approach
5.3.1 Introduction
5.3.2 Matrix Geometric Solutions: The Matrix R
5.3.3 Implementation: Computing
5.3.4 Example: The Queue
5.3.5 Alternative Methods for Finding R
5.3.6 The Quasi-Birth-Death (QBD) Case
5.4 Explicit Solution of Matrix-Geometric Problems
5.4.1 Queueing Systems for Which R May Be Explicitly Computed
5.4.2 Systems for Which R Must Be Computed Explicitly
5.4.3 Systems for Which R Must Be Computed Iteratively
5.4.4 Example: A Markovian Queue with N Servers Subject to Breakdowns and Repairs
6. Decompositional Methods
6.1 NCD Markov Chains
6.1.1 Introduction and Background
6.1.2 Definitions
6.1.3 Block Solutions
6.1.4 The Coupling Matrix
6.1.5 The NCD Approximation - A Rayleigh-Ritz Refinement Step
6.2 Stochastic Complementation
6.2.1 Definition
6.2.2 Properties of the Stochastic Complement
6.2.3 Computing Stationary Distributions by Stochastic Complementation
6.2.4 Relationship with Block Gaussian Elimination
6.2.5 Computational Aspects of Stochastic Complementation
6.3 Iterative Aggregation/Disaggregation Methods
6.3.1 Introduction
6.3.2 The Basic IAD Algorithm
6.3.3 The Takahashi IAD Algorithm
6.3.4 Other IAD Variants
6.3.5 Restructuring an NCD Matrix
6.3.6 Implementation Considerations
6.3.7 MATLAB Experiments
6.3.8 A Large Experiment
6.4 Convergence Properties and Behavior
6.4.1 Necessary Conditions for a "Regular" NCD Stochastic Matrix
6.4.2 Three Lemmas to Characterize Approximations
6.4.3 A Convergence Theorem
7. P- Cyclic Markov Chains
7.1 Introduction
7.2 Directed Graphs and P-Cyclic Matrices
7.2.1 Graph Terminology and Definitions
7.2.2 Primitive and Cyclic Matrices
7.3 p-Cyclic Markov Chains
7.3.1 The Embedded Markov Chain
7.3.2 Markov Chains with Periodic Graphs
7.3.3 Computation of the Periodicity
7.4 Numerical Methods Applied to p-Cyclic Matrices
7.4.1 Direct Methods
7.4.2 The Gauss-Seidel Iterative Method
7.4.3 Numerical Experiments
7.5 Reduced Schemes
7.5.1 Reduced Schemes Associated with a Stochastic Matrix
7.5.2 Reduced Schemes Associated with an Infinitesimal Generator
7.5.3 Numerical Methods Based on the Reduced Scheme
7.5.4 Numerical Experiments
7.6 IAD Methods for NCD, p-Cyclic Markov Chains
7.6.1 Iterative Aggregation/Disaggregation (IAD) Methods
7.6.2 Ordering for Periodicity and Decomposability
7.6.3 Application to p-Cyclic Matrices
7.7 Block SOR and Optimum Relaxation
7.7.1 Introduction
7.7.2 A 3-Cyclic Queueing Network Example
7.7.3 A p-step Iteration Procedure
7.7.4 Convergence Conditions for Block SOR
7.7.5 Applicable Values for the Relaxation Parameter
7.7.6 Convergence Testing in the Extended Sense
7.7.7 Optimal Convergence Factors and Associated w values
7.7.8 Computing the Subvector Multipliers
8. Transient Solutions
8.1 Introduction
8.2 Uniformization
8.2.1 The Basic Concepts
8.2.2 The Truncation Error
8.2.3 Implementation
8.3 Methods Applicable to Small State Spaces
8.3.1 Matrix Decompositional Methods
8.3.2 Matrix Scaling and Powering
8.4 Ordinary Differential Equation (ODE) Solvers
8.4.1 Ordinary Differential Equations
8.4.2 Numerical Solutions and Stability
8.4.3 Elementary Numerical Algorithms
8.4.4 Stiff ODEs
8.4.5 Single-Step Methods
8.4.6 Multistep Methods
8.4.7 Software Sources and Comparisons
8.5 Krylov Subspace Methods
8.5.1 Introduction
8.5.2 The Basic Krylov Subspace Approach
8.5.3 Corrected Schemes and Error Bounds
8.5.4 Error Estimates and Step Size Control
8.6 Selected Experiments
9. Stochastic Automata Networks
9.1 Introduction
9.2 Noninteracting Stochastic Automata
9.2.1 Independent, Two-Dimensional Markov Chains
9.2.2 Basic Properties of Tensor Algebra
9.2.3 Probability Distributions
9.3 Interacting Stochastic Automata
9.3.1 A Simple Example
9.3.2 Functional Transition Rates and Synchronizing Events
9.3.3 The Effect of Synchronizing Events
9.3.4 The Effect of Functional Transition Rates
9.4 Computing Probability Distributions
9.5 Multiplication with a Vector
9.5.1 The Nonfunctional Case
9.5.2 Multiplication in The Presence of Functional Elements
9.5.3 The Use of Symmetric Permutations
9.5.4 When All Else Pails
9.6 Iterative Solution Methods
9.6.1 Unpreconditioned Methods
9.6.2 Preconditioning
9.7 A Queueing Network Example
10. Software
10.1 The Categories of Available Software
10.1.1 Introduction
10.1.2 Libraries of Numerical Algorithms
10.1.3 Queueing Networks
10.1.4 Stochastic Petri Nets
10.1.5 Other Software
10.2 MARCA - MARkov Chain Analyzer
10.2.1 Basic Concepts and Terminology
10.2.2 Model Definition in MARCA
10.2.3 Numerical Methods
10.3 XMARCA: A Graphical Interface for Queueing Networks
10.3.1 Introduction
10.3.2 Building a Queueing Network Model
10.3.3 Converting the Graphical Representation
10.3.4 Matrix Generation and Numerical Solutions
10.3.5 Displaying Results
Bibliography
Index

Systemvoraussetzungen

Als PDF speichern Als Link merken