Entrywise perturbation theory and error analysis for Markov chains

DOI10.1007/BF01385743zbMath0804.65145MaRDI QIDQ1326397

Colm Art O'Cinneide

Publication date: 18 May 1994

Published in: Numerische Mathematik (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/133726

zbMATH Keywords

error analysisMarkov chainGaussian eliminationnumerical stabilityentrywise perturbationwell- conditioned problem

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Direct numerical methods for linear systems and matrix inversion (65F05) Probabilistic methods, stochastic differential equations (65C99)

Related Items

ON LATOUCHE–RAMASWAMI'S LOGARITHMIC REDUCTION ALGORITHM FOR QUASI-BIRTH-AND-DEATH PROCESSES ⋮ A note on entrywise perturbation theory for Markov chains ⋮ Applications of Paz's inequality to perturbation bounds for Markov chains ⋮ Acute perturbation of the group inverse ⋮ Red light green light method for solving large Markov chains ⋮ Accurate solutions of \(M\)-matrix algebraic Riccati equations ⋮ A direct projection method for Markov chains ⋮ A Performance Comparison of Density-of-States Methods ⋮ Accurate computation of the smallest eigenvalue of a diagonally dominant $M$-matrix ⋮ A rules-based approach for configuring chains of classifiers in real-time stream mining systems ⋮ Blockwise perturbation theory for nearly uncoupled Markov chains and its application ⋮ Computing singular values of diagonally dominant matrices to high relative accuracy ⋮ Stochastic and substochastic solutions for infinite-state Markov chains with applications to matrix-analytic methods ⋮ Optimizing steady state Markov chains by state reduction ⋮ Accurate numerical solution for shifted \(M\)-matrix algebraic Riccati equations ⋮ Markov chain sensitivity measured by mean first passage times ⋮ Parallel computing for Markov chains with islands and ports ⋮ Stationary distributions and mean first passage times of perturbed Markov chains ⋮ The state reduction and related algorithms and their applications to the study of Markov chains, graph theory, and the optimal stopping problem ⋮ Analysis of nonpreemptive priority queues with multiple servers and two priority classes ⋮ Sharp Entrywise Perturbation Bounds for Markov Chains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a direct method for the solution of nearly uncoupled Markov chains
• Non-negative matrices and Markov chains. 2nd ed
• Further Comparisons of Direct Methods for Computing Stationary Distributions of Markov Chains
• Computable Error Bounds for Aggregated Markov Chains
• Comparison of Some Direct Methods for Computing Stationary Distributions of Markov Chains
• Regenerative Analysis and Steady State Distributions for Markov Chains
• Derivatives and Perturbations of Eigenvectors
• Finite capacity vacation models with non-renewal input