×

A combinatorial approach to nearly uncoupled Markov chains. I: Reversible Markov chains. (English) Zbl 1288.65011

Summary: A Markov chain is a sequence of random variables \(x_{0}, x_{1}, \ldots\) that take values in a state space \(\mathcal{S}\). A set \(\mathcal{E} \subseteq \mathcal{S}\) is referred to as an almost invariant aggregate if transitions from \(x_{t}\) to \(x_{t+1}\) where \(x_{t} \in \mathcal{E}\) and \(x_{t+1} \notin \mathcal{E}\) are exceedingly rare. A Markov chain is referred to as nearly uncoupled if there are two or more disjoint almost invariant aggregates contained in its state space. Nearly uncoupled Markov chains are characterised by long periods of relatively constant behaviour punctuated by sudden, extreme changes. We present an algorithm for producing almost invariant aggregates of a nearly uncoupled reversible Markov chain. This algorithm utilises the stochastic complement to iteratively reduce the order of the given state space.

MSC:

65C40 Numerical analysis or methods applied to Markov chains
60J22 Computational methods in Markov chains
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
15B51 Stochastic matrices
PDFBibTeX XMLCite
Full Text: EMIS