2
$\begingroup$

Here exponentially localized can be thought in a non-rigorous manner as a measure that is mostly supported on a sparse number of nodes.

Some intuition can gained by thinking about a diffusion process, e.g., we know that in presence of a "confining potential" e.g., $V(x)\approx x^2/2$, the Fokker-Planck equation in 1D will have an exponentially localized stationary distribution (Boltzmann distribution).

$\dfrac{\partial P}{\partial t}-\partial_x(P\partial_x V)=\sigma\partial_{xx}P$

Is there corresponding Markov Chain literature that also studies such localization properties, e.g. providing conditions on the Markov chain transition matrix that lead to such localization ?

$\endgroup$
4
  • $\begingroup$ What about MCMC for any Gibbs measure? $\endgroup$ Commented Feb 8, 2023 at 19:56
  • $\begingroup$ @SteveHuntsman Can you elaborate more. I understand MCMC constructs a Markov Chain with a given distribution. But if you are given such a chain, can you tell (without actually computing the stationary distribution) that the stationary distribution will be localized ? $\endgroup$ Commented Feb 9, 2023 at 3:39
  • $\begingroup$ Can I interpret the question as something like "when can one guarantee that a Markov chain admit an invariant measure which has good concentration properties, without explicit knowledge of said invariant measure?"? $\endgroup$
    – πr8
    Commented Feb 9, 2023 at 23:10
  • 1
    $\begingroup$ @πr8 Yes, thats the spirit of the question. $\endgroup$ Commented Feb 9, 2023 at 23:15

1 Answer 1

2
+200
$\begingroup$

I will give some answers in terms of diffusion processes, since the examples are easiest for me to describe in that context. There are more general examples which follow the same pattern, but typically require additional care to state rigorously.

Suppose that you are interested in the Markov process

$$\mathrm{d} X = b(X) \, \mathrm{d} t + \mathrm{d} W,$$

with $b$ some vector field. If $b$ is contractive, in the sense that for some $K > 0$, the inequality

$$\langle b(X) - b(Y), X - Y\rangle \leqslant - K \| X - Y \|_2^2$$

holds globally, then it follows that the invariant measure of the process is unique and has sub-Gaussian concentration with a constant depending on $K$, see e.g. here for details.

Actually, suppose that it only holds that

$$\langle b(X) - b(Y), X - Y\rangle \leqslant - K ( \| X - Y \| ) \cdot \| X - Y \|_2^2$$

for some regular function $K$ which may be negative, but satisfies $\lim \inf_{r \to \infty} K(r) > 0$, i.e. 'distant contractivity'. In this case, sub-Gaussian concentration again holds for the invariant measure (under a few bonus regularity assumptions, and with a slightly harder-to-derive constant) as a consequence of the results in this work.

In another direction, suppose that the same diffusion satisfies a drift condition, i.e. there is some positive, coercive function $V$ with reasonable sub-level sets such that

$$LV \leqslant -\gamma V + C$$

for some $\gamma, C > 0$, where $L$ is the infinitesimal generator of the diffusion. Then, results along the lines of this work give that the invariant measure satisfies a Poincaré inequality, and hence admits sub-exponential concentration. Under stronger drift conditions, a subset of the same authors are able to obtain various stronger concentration properties; see this chapter for a collection of examples to this effect.

[ Note: I realised after initial posting that this latter example requires the reversibility of the process, which is often difficult to check without knowing the invariant measure of the process ]

$\endgroup$
2
  • $\begingroup$ Thanks, I have started going through these papers. They all seem to be in the "class" of the examples similar to the one that I mention in the OP. Are there qualitatively other ways of "certifying/guaranteeing" or even guessing the sparsity of the invariant distribution of a given Markov chain ? $\endgroup$ Commented Feb 15, 2023 at 17:10
  • $\begingroup$ Depends on what sort of scenarios you have in mind. I am most familiar with settings in which the Markov chain i) has 'local' dynamics and ii) mixes quickly; often the combination of these two is sufficient to guarantee that the invariant measure is well-concentrated. $\endgroup$
    – πr8
    Commented Feb 16, 2023 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.