Introduction to the Numerical Solution of Markov Chains (eBook)

William J. Stewart (Autor)

eBook Download: PDF

2021
Princeton University Press (Verlag)
978-0-691-22338-4 (ISBN)

Infos

A cornerstone of applied probability, Markov chains can be used to help model how plants grow, chemicals react, and atoms diffuse--and applications are increasingly being found in such areas as engineering, computer science, economics, and education. To apply the techniques to real problems, however, it is necessary to understand how Markov chains can be solved numerically. In this book, the first to offer a systematic and detailed treatment of the numerical solution of Markov chains, William Stewart provides scientists on many levels with the power to put this theory to use in the actual world, where it has applications in areas as diverse as engineering, economics, and education. His efforts make for essential reading in a rapidly growing field. Here Stewart explores all aspects of numerically computing solutions of Markov chains, especially when the state is huge. He provides extensive background to both discrete-time and continuous-time Markov chains and examines many different numerical computing methods--direct, single-and multi-vector iterative, and projection methods. More specifically, he considers recursive methods often used when the structure of the Markov chain is upper Hessenberg, iterative aggregation/disaggregation methods that are particularly appropriate when it is NCD (nearly completely decomposable), and reduced schemes for cases in which the chain is periodic. There are chapters on methods for computing transient solutions, on stochastic automata networks, and, finally, on currently available software. Throughout Stewart draws on numerous examples and comparisons among the methods he so thoroughly explains.

Produkt-Details

• Erscheint lt. Verlag: 12.1.2021
• Zusatzinfo: 41 line drawings 74 tables
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
• Schlagworte: Absorbing Markov chain • Absorbing state • algorithm • analysis of algorithms • Approximation • Arnoldi method • Arnoldi process • Asymptotic convergence rate • Block Gauss-Seidel • Block splitting • block triangular matrix • Calculation • Chapman–Kolmogorov equation • ChapmanЋolmogorov equation • Chebyshev approximation • Coefficient matrix • Computation • computational complexity theory • conditional probabilities • Conditioning • Conjugate Gradient Method • Connected vertices • Consistently ordered matrix • Continuity equation • continuous-time Markov chain • Continuous-time stochastic process • convergence • Convergence factors • convergence properties • Courtois problem • Cyclic tendencies • Decompositional methods • Decomposition method (constraint satisfaction) • Diagonal blocks • Diagram (category theory) • differential equation • directed graph • Direct Methods • Discretization parameter • domain decomposition methods • eigenvalues • Eigenvalues and Eigenvectors • Eigenvectors • Elliptic partial differential equation • Ephemeral states • Equation • ergodic theory • Erlang law • Error analysis (Mathematics) • Euler methods • Euler polygon • Explicit method • Factorization • Family of solution curves • Fixed-point theorem • Full pivoting • Function (mathematics) • Galerkin condition • Gaussian elimination • Gauss–Seidel method • Gauss transformation • GaussГeidel method • geometric distribution • Gerschgorin theorem • Guard vectors • hash function • Hermitian matrices • Hessenberg Matrices • Identity matrix • Indicator function • Infinitesimal generator (stochastic processes) • Initial Value Problem • Inverse iteration • Invertible matrix • Iteration • Iterative Method • Iterative process • Jacobian matrix and determinant • Jacobi method • Krylov subspace methods • Lanczos algorithm • Lanczos methods • linear differential equation • linear equation • Linear multistep method • Lipschitz continuity • Load-dependent • Lower Hessenberg matrix • Low-stepping transitions • Machine epsilon • Marca ordering • Markov Chain • markov chains • Markov model • Markov process • Markov Property • Markov reward model • Mathematical Optimization • Matrix (mathematics) • mean value analysis • Memoryless property • M-matrix • Multiple (mathematics) • Near-breakdown • Newton's method • Norm (mathematics) • Numerical analysis • Numerical Integration • Numerical Stability • Optimality property • ordinary differential equation • Orthogonal complement • Orthonormal basis • Overrelaxation • Parameter (computer programming) • partial differential equation • Permutation Matrix • Perron–Frobenius theorem • PerronІrobenius theorem • Poisson distribution • Poisson Point Process • Power iteration • Preconditioner • Predictor–corrector method • PredictorУorrector method • Probability • Probability Distribution • Probability space • Projection (linear algebra) • Projection method (fluid dynamics) • Proportionality (mathematics) • QR algorithm • QR decomposition • Queueing Theory • rate function • Rate of Convergence • Recurrence relation • Recursion (computer science) • renormalization • result • Scale factor (computer science) • Series (mathematics) • Sign (mathematics) • Simultaneous Equations • State-space Representation • stochastic • Stochastic matrix • stochastic petri net • Summation • Synchronization (computer science) • system of linear equations • Theorem • time complexity • transformation matrix • Transition rate matrix • Truncation error (numerical integration) • Variable (computer science)
• ISBN-10: 0-691-22338-6 / 0691223386
• ISBN-13: 978-0-691-22338-4 / 9780691223384