Volume 40, pp. 120-147, 2013.

A combinatorial approach to nearly uncoupled Markov chains I: Reversible Markov chains

Ryan M. Tifenbach

Abstract

A Markov chain is a sequence of random variables $x_0,x_1,\dots$ 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.

Full Text (PDF) [425 KB], BibTeX

Key words

nearly uncoupled Markov chain, reversible Markov chain, stochastic complement, stochastic matrix

AMS subject classifications

15A18, 15A51, 60J10, 60J20, 65F15

Links to the cited ETNA articles

[6]	Vol. 29 (2007-2008), pp. 46-69 David Fritzsche, Volker Mehrmann, Daniel B. Szyld, and Elena Virnik: An SVD approach to identifying metastable states of Markov chains
[15]	Vol. 38 (2011), pp. 17-33 Ryan M. Tifenbach: On an SVD-based algorithm for identifying meta-stable states of Markov chains