
> 
> 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](https://link.springer.com/content/pdf/10.1007/s00440-008-0189-z.pdf). 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](https://arxiv.org/pdf/1805.00452.pdf) 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.



Polynomial time mixing Markov chain for multimodal distribution
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)](https://link.springer.com/article/10.1007/s00440-008-0189-z) 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.


