6

  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?

jonsca
  • 1,772
Tim
  • 19,445
  • 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

1 Answers1

2

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.

Douglas Zare
  • 10,658