11
$\begingroup$

I guess I understand the equation of the detailed balance condition, which states that for transition probability $q$ and stationary distribution $\pi$, a Markov Chain satisfies detailed balance if $$q(x|y)\pi(y)=q(y|x)\pi(x),$$

this makes more sense to me if I restate it as:

$$\frac{q(x|y)}{q(y|x)}= \frac{\pi(x)}{\pi(y)}. $$

Basically, the probability of transition from state $x$ to state $y$ should be proportional to the ratio of their probability densities.

$\endgroup$
8
$\begingroup$

It is not true that MCMC fulfilling detailed balance always yield the stationary distribution. You also need the process to be ergodic. Let's see why:

Consider $x$ to be a state of the set all possible states, and identify it by the index $i$. In a markov process, a distribution $p_t(i)$ evolves according to

$$p_t(i) = \sum_{j} \Omega_{j \rightarrow i} p_{t-1}(j)$$

where $\Omega_{j \rightarrow i}$ is the matrix denoting the transition probabilities (your $q(x|y)$).

So, we have that

$$p_t(i) = \sum_{j} (\Omega_{j \rightarrow i})^t p_{0}(j)$$

The fact that $\Omega_{j \rightarrow i}$ is a transition probability implies that its eigenvalues must belong to the interval [0,1].

In order to ensure that any initial distribution $p_{0}(j)$ converges to the asymptotic one, you have to ensure that

  • 1 There is only one eigenvalue of $\Omega$ with value 1 and it has a unique non-zero eigenvector.

To ensure that $\pi$ is the asymptotic distribution, you need to ensure that

  • 2 The eigenvector associated with eigenvalue 1 is $\pi$.

Ergodicity implies 1., detailed balance implies 2., and that is why both form a necessary and sufficient condition of asymptotic convergence.

Why detailed balance implies 2:

Starting from

$$p(i)\Omega_{ij} = \Omega_{ji} p(j)$$

and summing over $j$ in both sides, we obtain

$$p(i) = \sum_{j}\Omega_{ji} p(j)$$

because $\sum_{j} \Omega_{ij} = 1$, since you always transit to somewhere.

The above equation is the definition of eigenvalue 1, (easier to see if you write it in vector form:)

$$ 1.v = \Omega\cdot v$$

$\endgroup$
  • $\begingroup$ The OP does not ask whether it is unique or not he asks how does MCMC with detailed balance is enough to yield an invariant probability density. $\endgroup$ – gatsu Jun 7 '17 at 8:59
  • 1
    $\begingroup$ The first sentence of this answer is "It is not true that MCMC fulfilling detailed balance always yield the stationary distribution." So, no, detailed balance is not enough to yield and invariant density... How does that does not answer the question? $\endgroup$ – Jorge Leitão Jun 7 '17 at 20:10
0
$\begingroup$

I think it does, because for an irreducible MC if detailed balance is satisfied then it has a unique stationary distribution, but for it to be independent of initial distribution it also has to be aperiodic.

In case of MCMC we start from a data point and then propose a new point. We may or may not move to the proposed point i.e we have a self loop which makes an irreducible MC aperiodic.

Now by virtue of satisfying DB it also has positive recurrent states, i.e mean return time to the states is finite. So the chain that we construct in MCMC is irreducible, aperiodic and positive recurrent, which means it is an ergodic chain.

We know that for an irreducible ergodic chain a stationary distribution exists which is unique and independent of initial distribution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.