2
$\begingroup$

Is there a discrete space Markov chain, starting from a fixed state, whose stationary distribution is a multimodal distribution and that mixes in polynomial time?

For example, Ising model on say a complete graph has a multimodal stationary distribution at low temperature. Critical $\beta$ (i.e. inverse temperature) is known to be $\beta_c=1$. So $\beta>1$ is low temperature regime. Single-site Glauber dynamics for Ising model at low temperature on a complete graph is known to mix exponentially slow. Here is a proof. I believe faster mixing Swendsen-Wang dynamics which update multiple spins in one step also mix exponentially slow at low temperature.

So I am wondering if there is a fundamental barrier and no Markov chain can mix in polynomial time, starting from a fixed state, at low temperature for Ising model on say a complete graph? Or is it that no one has found such a Markov chain yet?

Coupling is often used to prove upper bounds on mixing time. If there exists a contractive coupling, then a chain mixes in polynomial time. Here is a paper that proves that there exists a contractive coupling for a Markov chain on a continuous state space and a multimodal stationary distribution. For instance, see example 2.4 in this paper which talks about a Gaussian mixture.

$\endgroup$
11
  • 3
    $\begingroup$ What does multimodal mean? For example if you have a biased random walk on $[-n,n]$ with the bias away from the origin, you would probably call that multimodal with exponential mixing time. Now if you add a small transition probability from $n$ to $-n$ and vice gersa, the mixing time becomes polynomial, but you presumably would still call it multimodal? $\endgroup$ Commented Sep 7, 2022 at 10:28
  • 1
    $\begingroup$ Also, when it comes to whether "no Markov chain can mix in polynomial time", what class of Markov chains would you like to consider? Obviously there is a Markov chain which just consists of a sequence of i.i.d. samples from the stationary distribution, and which mixes in time $1$. $\endgroup$ Commented Sep 7, 2022 at 16:53
  • 1
    $\begingroup$ @JamesMartin I had mentioned the Markov chain starts from a fixed state. Obviously, if one samples from stationary distribution itself, there is no use even studying a Markov chain to sample from the stationary distribution. $\endgroup$
    – Garfield
    Commented Sep 7, 2022 at 18:56
  • 1
    $\begingroup$ @AnthonyQuas I had given an explicit example of a multimodal distribution. Ising model at low temperature has two peaks. Here is what I mean by a multimodal distribution. en.wikipedia.org/wiki/Multimodal_distribution. $\endgroup$
    – Garfield
    Commented Sep 7, 2022 at 19:06
  • 1
    $\begingroup$ @AnthonyQuas For your example for biased walk on $[-n,n]$ without a connection between $-n,n$, the stationary distribution of the walk is concentrated at $-n,n$. So yes, it is a multimodal stationary distribution. When there is a transition probability from $n$ to $-n$, how small a transition probability are we talking about? What does the stationary distribution look like? If it is still concentrated at $-n,n$, then yes, it would still be a multimodal stationary distribution. $\endgroup$ Commented Sep 7, 2022 at 19:22

2 Answers 2

2
$\begingroup$

The OP seems specifically interested in ergodic Markov chains with a unique stationary distribution $\pi$. The following example is admittedly a bit contrived, but is helpful to illustrate some general principles discussed more below.

Claim: There exists a Markov chain with a "bimodal" stationary distribution, such that the mixing time of the chain is logarithmic in $n$.

"Bimodal" just means there are two distinct states where $\pi$ is larger than in other states.

Proof. Let $\Delta_i(t)$ denote the total variation distance between a Markov chain starting at the $i$th state and the stationary distribution $\pi$. For any accuracy parameter $\epsilon>0$, define the mixing time: $$ \tau(\epsilon) := \max_i \min\{ t > 0 : \Delta_i(t) < \epsilon \} \;. $$ A chain that displays rapid mixing is given by the following lazy Markov chain with $n \times n$ transition matrix: $$ P_{ij} = \begin{cases} 1/2 & \text{if $i=j$} \\ 1/4 & \text{if $i \notin \{1,n \}$ and $j \in \{1, n \}$} \\ 1/(2 (n-1)) & \text{if $i \in \{1,n\}$ and $j\ne i$} \\ 0 & \text{else} \end{cases} $$ The stationary distribution of this chain satisfies $$ \pi \propto \left( 1, \frac{2}{n-1}, \cdots, \frac{2}{n-1},1 \right) $$ which is bimodal (concentrated at the endpoints), and with spectral gap $\gamma=1/2$, and since the chain is reversible, the mixing time satisfies $$ \tau(\epsilon) \le 2 \log\left(\frac{2 n-3}{\epsilon}\right) $$ which is logarithmic in $n$. $\Box$

In general, energy and/or entropic barriers can cause chains that make only local moves to mix with exponential time. This is, e.g., the case with Glauber dynamics applied to the mean-field Ising (or Curie-Weiss) model at low temperature; see, e.g. Theorem 3 of Levin/Luczak/Peres (2010) and references therein. In contrast, the above chain is contrived to make global moves, and doesn't really have any type of barriers, which is why it mixes so fast.

$\endgroup$
2
  • $\begingroup$ Thanks, that was helpful. I have studied your 2018 paper (Coupling and convergence for HMC). Are you aware of any chain for mean-field Ising model or Ising model on a bounded degree graph at low temperature for which the mixing time is polynomial? $\endgroup$
    – Garfield
    Commented Sep 7, 2022 at 19:51
  • $\begingroup$ At extremely low temperatures, not aware of any local chain that can achieve a poly mixing time from an arbitrary start. As far as I can tell, the best known non-asymptotic result for a local chain (Glauber) is arxiv.org/pdf/0806.1906.pdf See Figure 1 for a nice visual showing a window of size $O(1/\sqrt{n})$ around the critical temperature such that the mixing time is poly. For chains based on global moves (notably Swendsen-Wang and Parallel Tempering), the results are mixed with some poly and others exp; see arxiv.org/abs/1702.05797 for a nice survey and result. $\endgroup$ Commented Sep 8, 2022 at 2:07
2
$\begingroup$

As noted in the comment by James Martin, some assumption is needed on the Markov chain, e.g., that each step of the chain can be implemented on a Turing machine in polynomial time.

The Swendsen-Wang dynamics for the (Ferromagnetic) Ising model on a complete graph $K_n$ mixes in at most $O(n^{1/4})$ iterations, see [1]. More generally, on any graph, this dynamics has polynomial mixing time [2], although the sharp exponent is not known; it is possible that the bound $O(n^{1/4})$ from [1] holds true for all graphs, but the known bounds are far greater.

The Swendsen-Wang dynamics for the Potts model on a complete graph $K_n$ has exponential mixing time at low temperatures [3].

perhaps most pertinent is the work of Alan Sly [4] that relates sampling to computational hardness.

[1] Long, Yun, Asaf Nachmias, Weiyang Ning, and Yuval Peres. A power law of order 1/4 for critical mean field Swendsen-Wang dynamics. American Mathematical Soc., 2014. https://www.google.com/books/edition/A_Power_Law_of_Order_1_4_for_Critical_Me/YNlVBQAAQBAJ?hl=en&gbpv=1&pg=PP1&printsec=frontcover

[2] Guo, Heng, and Mark Jerrum. "Random cluster dynamics for the Ising model is rapidly mixing." In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1818-1827. Society for Industrial and Applied Mathematics, 2017.

[3] Gheissari, Reza, Eyal Lubetzky, and Yuval Peres. "Exponentially slow mixing in the mean-field Swendsen-Wang dynamics." In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1981-1988. Society for Industrial and Applied Mathematics, 2018.

[4] Sly, Allan. "Computational transition at the uniqueness threshold." In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 287-296. IEEE, 2010.

$\endgroup$
2
  • 2
    $\begingroup$ Thanks for taking the time to share this review; glad you highlighted the comment by @JamesMartin, which is important in practice and sometimes overlooked: one would indeed need that each step of the chain be implementable in poly time for the mixing time result to be of much value. I guess per step of Glauber is $O(1)$ and Swendsen-Wang is $O(n)$. $\endgroup$ Commented Sep 8, 2022 at 9:36
  • 1
    $\begingroup$ @NawafBou-Rabee And thank you for sharing your perspective on this important problem. $\endgroup$ Commented Sep 8, 2022 at 17:44

Your Answer

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

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