A new combinatorial algorithm for large Markov chains. (Extended abstract)

From MaRDI portal





One considers nearly decomposable Markov chains. The algorithm is based on grouping the states of a Markov chain in such a way that the probability of changing the state inside a group is of greater order of magnitude than interactions between groups. For solving such chains the methods of aggregation and iterative aggregation/disaggregation are the most suitable. The proposed combinatorial aggregation approach can be seen as a generalization of existing aggregation algorithms, in contrast to them it gives a procedure approximating the mean hitting time. This approach is successful in computing characteristics other than stationary distribution, which are solutions of non-transposed systems of equations. For the entire collection see [Zbl 0970.00027].











This page was built for publication: A new combinatorial algorithm for large Markov chains. (Extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2760208)