Markov chains detailed balance

Viewing the SA algorithm in terms of Markov chains, Greene and Supowit [8] pointed out that any type of function may be used for the decision making process about acceptance of new configurations, provided the detailed balance equation for the Markov process is satisfied. 

The MC method [2-4] generates a sequence (Markov chain) of configurations in (/ -space. The procedure can be constructed to ensure that, in the long-enough-term , configurations will appear in that chain with any probability density, T s( 9 ) (the S stands for sampling ) we care to nominate. The key requirement (it is not strictly necessary [5] and-as we shall see - it is not always sufficient) is that the transitions, from one configuration g to another q, should respect the detailed balance condition... 

A Markov chain is ergodic if it eventually reaches every state. If, in addition, a certain symmetry condition - the so-called criterion of detailed balance or microscopic reversibility - is fulfilled, the chain converges to the same stationary probability distribution of states, as we throw dice to decide which state transitions to take one after the other, no matter in which state we start. Thus, traversing the Markov chain affords us with an effective way of approximating its stationary probability distribution (Baldi Brunak, 1998). 

In Section 5.1 we introduce the stochastic processes. In Section 5.2 we will introduce Markov chains and define some terms associated with them. In Section 5.3 we find the n-step transition probability matrix in terms of one-step transition probability matrix for time invariant Markov chains with a finite state space. Then we investigate when a Markov ehain has a long-run distribution and discover the relationship between the long-run distribution of the Markov chain and the steady state equation. In Section 5.4 we classify the states of a Markov chain with a discrete state space, and find that all states in an irreducible Markov chain are of the same type. In Section 5.5 we investigate sampling from a Markov chain. In Section 5.6 we look at time-reversible Markov chains and discover the detailed balance conditions, which are needed to find a Markov chain with a given steady state distribution. In Section 5.7 we look at Markov chains with a continuous state space to determine the features analogous to those for discrete space Markov chains. 

TIME-REVERSIBLE MARKOV CHAINS AND DETAILED BALANCE 117... 

Thus, to find a Markov chain that has the desired steady state probabilities, we have to find the transition probabilities of a Markov chain that satisfies the detailed balance condition. The detailed balance condition won t be satisfied by the transition probabilities of most Markov chains. 

Theorem 5 The Markov chain having transition probabilities given by p j satisfies the detailed balance condition, and thus it has the desired steady state distribution. Proof ... 

Time reversible Markov chains satisfy the detailed balance condition. Let (x) be the steady state density and /(v x) be the density function of the one-step transitions... 

A time-reversible Markov chain has transition probabilities satisfying the detailed balance condition. 

If a Markov chain has transition probabilities that satisfy the detailed balance condition, then tt is the steady state distribution for the Markov chain. 

Green (1995) took another approach to this problem. He set up reversible jump Markov chains that make the probabilities for a jump from each point in one model space to another point in another model space satisfy the detailed balance equation. This allows the long-run distribution of the reversible jump Markov chain include the posterior probability of each model as well as the posterior distribution of the parameters within each model. 

Summing (B ) over x, we recover (B).) (B ) is called the detailed-balance condition-, a Markov chain satisfying (B ) is called reversible0 (B ) is equivalent to the self-adjointness of P as on operator on the space / (tt). In this case, it follows from the spectral theorem that the autocorrelation function Caa ) has a spectral representation... 

---