Blockwise perturbation theory for nearly uncoupled Markov chains and its application Original Research Article

Let P be the transition matrix of a nearly uncoupled Markov chain. The states can be grouped into aggregates such that P has the block form P=(Pij)i,j=1k, where Pii is square and Pij is small for i≠j. Let πT be the stationary distribution partitioned conformally as πT=(π1T,…,πkT). In this paper we bound the relative error in each aggregate distribution πiT caused by small relative perturbations in Pij. The error bounds demonstrate that nearly uncoupled Markov chains usually lead to well-conditioned problems in the sense of blockwise relative error. As an application, we show that with appropriate stopping criteria, iterative aggregation/disaggregation algorithms will achieve such structured backward errors and compute each aggregate distribution with high relative accuracy.