Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.
  1. To sample a target distribution, it suffices to construct a Markov chain with the target distribution being its limiting distribution.

    Note that such a MC may not satisfy the detailed balance equation with respect to the limiting distribution. But Metropolis-Hastings algorithms require that. So, I wonder what (good or bad) this extra requirement can bring?

    For example,

    • Will it reduce the mixing time of the MC, i.e., increase the rate of convergence of the distribution of $X_t$ to the target one?
    • Does it have some computation purpose(s)?
  2. If the detailed balance equation is not required to be satisfied, what are some ways to construct a MC (its transitional kernels, more specifically) such that its limiting distribution is the target one?

  3. Given any target distribution, does there always exist a MC (its transitional kernels, more specifically) such that it has the limiting distribution, its limiting distribution is the target one, and/or it satisfies the detailed balance equation with respect to its limiting distribution?

share|improve this question
    
A guide to a trivial constructive proof that there does always exist a MC that fulfills the requirements is to consider a MC that consists of independent draws from the target distribution itself. –  jbowman Dec 12 '12 at 19:42
    
@jbowman: Thanks! It makes me think of another question: Suppose a MC reaches its limiting distribution at time t. Is it correct that all the points (i.e. draws) in the same run (i.e. same sample path) after t are not necessarily independent with each other, but those points/draws that are sufficiently far apart in time are? –  Tim Dec 12 '12 at 20:17
add comment

1 Answer

I'll address question 2.

If you fix a distribution supported on a finite set, the Markov chains which have that distribution as a stable distribution form a polytope. You can interpolate between any two by following one rule with probability $p$ and the other with probability $1-p$ and the convex combination will also preserve the stable distribution.

Another way to look at the polytope is the space of maximal flows in a network with a source and a sink for each state, and complete (bipartite) connections between the sources and sinks, so that the capacity of each source/sink is the probability of the corresponding state in the distribution. The Markov chains where total balance is satisfied are the intersection of this polytope with a subspace.

Given any cycle of length $2n$ in this complete bipartite graph and a maximal flow so that the even edges all carry at least $c \gt 0$, you can produce another maximal flow by reducing the amounts carried by the even edges by $c$, and increasing the amounts carried by the odd edges by $c$. The new flow generically does not satisfy detailed balance even if the original does. So, this is a way to produce Markov chains with the same stable distribution which do not satisfy detailed balance.

share|improve this answer
    
+1 Thanks, Douglas! –  Tim Dec 13 '12 at 12:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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