Convergence, Rank Reduction and Bounds for the Stationary Analysis of Markov Chains

Markov chains;bounds;stationary analysis;stochastic ordering;rank reduction;convergence

Peng, Bin ; William J. Stewart, Committee Chair,Peng, Bin ; William J. Stewart ; Committee Chair

University:North Carolina State University

关键词: Markov chains;    bounds;    stationary analysis;    stochastic ordering;    rank reduction;    convergence;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/3085/etd.pdf?sequence=2&isAllowed=y

美国|英语

来源: null

【 摘 要 】

We introduce a rank reduction method for computing stationary distributions of Markov chains for which low-rank iteration matrices can be formed.We first prove that, for an irreducible Markov chain, a necessary and sufficient condition for convergence in a single iteration is that the iteration matrix have rank one. Since most iteration matrices have rank larger than 1, we also consider the Wedderburn rank-1 reduction formula and develop a rank reduction procedure that takes an initial iteration matrix with rank greater than one and modifies it in successive steps, under the constraint that the exact solution be preserved at each step, until a rank-1 iteration matrix is obtained. When the iteration matrix has rank r, the proposed algorithm has time complexity O(r∧2n). Secondly we investigate the relationship among lumpability, weak lumpability, quasi-lumpability and near complete decomposability. These concepts are important in aggregating and disaggregating Markov chains. White's algorithm for identifying all possible lumpable partitions for Markov chains is improved by incorporating lumpability tests on special state orderings. Finally, instead of computing exact stationary distributions, we design stochastic-ordering-based techniques to bound them. Upper bounds can be obtained by using constructive algorithms developed recently. We observe that the more lumpable partitionings, the more accurate the upper bound for the state of interest both with matrix transformation and without matrix transformation. Lastly we combine the approaches of state permutation, matrix transformation and state partitioning to improve the quality of the upper bound for the state of interest.