Abstract
Discrete-time discrete-state finite Markov chains are versatile mathematical models for a wide range of real-life stochastic processes. One of most common tasks in studies of Markov chains is computation of the stationary distribution. We propose a new general controlled, easily distributed algorithm for this task. The algorithm includes as special cases a wide range of known, very different, and previously disconnected methods including power iterations, versions of Gauss-Southwell formerly restricted to substochastic matrices, and online distributed algorithms. We prove exponential convergence of our method, demonstrate its high efficiency, and derive straightforward control strategies that achieve convergence rates faster than state-of-the-art algorithms.
Original language | English |
---|---|
Article number | 18 |
Pages (from-to) | 1-43 |
Number of pages | 43 |
Journal | Journal of scientific computing |
Volume | 93 |
Issue number | 18 |
Early online date | 30 Aug 2022 |
DOIs | |
Publication status | Published - Oct 2022 |
Keywords
- Markov Chains
- Numerical methods
- Gauss-Southwell methods
- Coupling
- 22/3 OA procedure