A Combinatorial Approach to Nearly Uncoupled Markov Chains

A discrete-time Markov chain on a state space S is a sequence of random variables X = fx0; x1; : : :g that take on values in S. A Markov chain is a model of a system which changes or evolves over time; the random variable xt is the state of the system at time t. A subset E S is referred to as an almost invariant aggregate if whenever xt 2 E, then with high probability xt+1 2 E, as well. That is, if there is a small positive value such that if xt 2 E then the probability that xt+1 =2 E is less than or equal to , then E is an almost invariant aggregate. If E is such an aggregate and xt 2 E, then the probability that xt+1; : : : ; xt+s 2 E is at least (1-E)s. A Markov chain tends to remain within its almost invariant aggregates (if it possesses any) for long periods of time. We refer to the Markov chain X as nearly uncoupled (with respect to some positive ) if its associated state space contains two or more disjoint almost invariant aggregates. Nearly uncoupled Markov chains are characterised by long periods of relatively constant behaviour, punctuated by occasional drastic changes in state. We present a series of algorithms intended to construct almost invariant aggregates of a given Markov chain. These algorithms are iterative processes which utilise a concept known as the stochastic complement. The stochastic complement is a method by which a Markov chain on a state space S can be reduced to a random process on a proper subset S0 S, while preserving many of the algebraic properties of the original Markov chain. We pay special attention to the reversible case. A Markov chain is reversible if it is symmetric in time { by which we mean that if we were to reverse the order of the variables x1; : : : ; xt, for some relatively large t, the resulting process would be essentially indistinguishable from the original Markov chain