A COMBINATORIAL APPROACH TO NEARLY UNCOUPLED MARKOV CHAINS I: REVERSIBLE MARKOV CHAINS

作者：Tifenbach Ryan M^*

来源：Electronic Transactions on Numerical Analysis, 2013, 40: 120-147.

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

A Markov chain is a sequence of random variables x(0), x(1),... that take values in a state space S. A set epsilon subset of S is referred to as an almost invariant aggregate if transitions from x(t) to x(t+1) where x(t) is an element of epsilon and x(t+1) (sic) epsilon 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.

• 出版日期2013