Aggregation Algorithms for Perturbed Markov Chains with Applications to Networks Modeling

• Published in: SIAM journal on scientific computing 2008-01, Vol.31 (1), p.45-73
• Main Authors: Gambin, Anna, Krzyżanowski, Piotr, Pokarowski, Piotr
• Format: Article
• Language: English
• Subjects: Algorithms; Applied mathematics; Computer science; Forests; Iterative methods; Linear algebra; Linear equations; Markov analysis; Methods
• ISSN: 1064-8275; 1095-7197
• DOI: 10.1137/050624716

A powerly perturbed Markov chain (MC) is a family of finite MCs given by transition probability matrices $P(\varepsilon)=(p_{ij}(\varepsilon))$ (or generators for continuous-time MCs) such that $p_{ij}(\varepsilon)=\delta_{ij}\varepsilon^{d_{ij}}+o(\varepsilon^{d_{ij}})$, $\varepsilon\rightarrow0$. In the simplest case we have popular nearly completely decomposable (NCD) chains. It has been shown by directed forest expansions that solutions of linear systems related to $P(\varepsilon)$ have a form $x_i(\varepsilon)=\alpha_i\varepsilon^{a_i}+o(\varepsilon^{a_i})$ for some vectors $\boldsymbol{\alpha}=(\alpha_i)$ and $\mathbf{a}=(a_i)$. Many characteristics of MCs such as stationary distributions, mean passage times, or limiting matrices can be defined in this way. We present efficient combinatorial aggregation algorithms for computing $\mathbf{a}$ and $\boldsymbol{\alpha}$. The algorithms rely on grouping the states of MCs in such a way that the probability of changing the state inside the group is of a greater order of magnitude than the interactions between groups. In contrast to existing methods, our approach is based on a combinatorial framework and can be seen as an algorithmization of the famous matrix tree theorem. We establish some preliminary results on the complexity of our algorithms. Numerical experiments on several network models, such as queueing systems or the Google problem, show the potential applicability of the method in real-life problems.