Stochastic Bounds with a Low Rank Decomposition |
| |
Authors: | Ana Bušić Mouad Ben Mamoun |
| |
Affiliation: | 1. Inria, Paris, France;2. Faculté de Sciences, Univ. Mohammed V, Agdal, Rabat, Morocco |
| |
Abstract: | We investigate how we can bound a discrete time Markov chain (DTMC) by a stochastic matrix with a low rank decomposition. In the first part of the article, we show the links with previous results for matrices with a decomposition of size 1 or 2. Then we show how the complexity of the analysis for steady-state and transient distributions can be simplified when we take into account the decomposition. Finally, we show how we can obtain a monotone stochastic upper bound with a low rank decomposition. |
| |
Keywords: | Algorithms Discrete time Markov chains Low rank approximation Numerical computations Stochastic bounds |
|
|