1
$\begingroup$

While doing a research work, I had to read about the Glauber dynamics for an Ising model. A wonderful account on this is given in the book Markov Chains and Mixing Times by Levin, Peres and Wilmer.

In Chapter 15 (proof of Theorem 15.1), the authors seem to show that the Glauber dynamics chain is $(1-\alpha/n)$-contracting for some $\alpha \in (0,1)$. However, what they show, is that if there are two points (spin configurations) with the Hamming distance between them (equivalently, half of the $L^1$ distance) being $1$, then the expected Hamming distance between the first steps of a (constructed) coupled Markov chain with initial configurations being these two spins, is bounded by $1-\alpha/n$.

Now, my question is, why is proving this with the Hamming distance between the initial spins $=1$ enough? Don't we have to start with two arbitrary spin configurations that do not necessarily disagree in exactly one index, say they disagree in $m$ indices, and then show that the expected distance between the first steps of the coupled chain is bounded by $(1-\alpha/n)m$? Is some kind of linear scaling going on here, that allows general distances between the initial spins to be reduced to distance $1$?

To add to this, in this paper ProjetEuclid link , the authors define the contracting property by considering initial state spins differing in one coordinate only. Why does this imply the actual contracting definition, where you have to show the existence of a coupling $(X,Y)$ such that the expected Hamming distance between $X$ and $Y$ is bounded by the contracting constant times the distance between the initial states (which may not be $1$)?

I think I am missing something really trivial, so please help me with this. Many thanks in advance.

$\endgroup$

1 Answer 1

2
$\begingroup$

The Hamming distance is a graph metric and therefore it suffices to check the expected distance between neighboring states contracts. Concretely, given two arbitrary initial states of Hamming distance $k$, find a path of length k connecting them by changing spins one by one. Then use the triangle inequality for the transportation metric, which is proved in the book you cite. You can also read about path coupling in the original paper of Bubbly and Dyer.

$\endgroup$
1
  • $\begingroup$ Thanks Yuval! The fact that the Wasserstein distance is indeed a metric (hence satisfies triangle inequality), was totally out of my mind for some reason. $\endgroup$
    – abcd
    Commented Sep 23, 2019 at 16:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .