| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

1. Spin systems

Open questions proposed for spin systems, primarily the Ising and Potts models and variants therein.

Recall that the Ising model on a graph $G=(V,E)$ is a distribution on $\Omega=\{\pm 1\}^{V(G)}$ with probability \[\mathbb P(\sigma)\propto \exp(\beta \sum_{(i,j)\in E} \sigma_i \sigma_j)\,. \] and the $q$-state Potts model is a random assignment of colors $\sigma\in \{1,...,q\}^{V(G)}$ with probability \[\mathbb P(\sigma)\propto \exp(\beta \sum _{(i,j)\in E} \boldsymbol 1\{\sigma_i =\sigma_j\}) \]

    1. Universal lower bound for Potts


      Add remark

      Problem 1.1.

      [Yuval Peres] Consider the $q$-Potts model or uniform $q$ proper colorings on a general graph $G$. Is there a universal $\asymp n\log n$ lower bound on the mixing time uniform in the temperature? Is there always an $\frac {n\log n}2$ lower bound?
          [Hayes, Sinclair] proved an $\frac {n\log n}d$ lower bound on graphs of maximum degree $d$.

      [Ding, Peres] proved an $\frac {n\log n}2$ lower bound for the Ising model on general graphs.

        • Spin glass with i.i.d. couplings


          Add remark

          Problem 1.2.

          [Andrea Montanari] Consider the spin glass model on $\mathbb{Z}_n^d$ with i.i.d. couplings, i.e. with Hamiltonian given by $$ H_n(\sigma)= \sum_{(i,j)\in E_n} J_{ij}\sigma_i\sigma_j\, , $$ where $J=(J_{ij})$ is a random symmetric matrix with i.i.d. $\pm 1$ entries. The Gibbs distribution is given by $$ \mu_n(\sigma)= \frac{1}{Z_n}\exp(\beta H_n)\, . $$ Fix a realization of $J_{ij}$ and consider the Glauber dynamics. Does there exist $\beta_0$ and $\varepsilon>0$ such that, for all $\beta\geq\beta_0$, the mixing time of this chain is at least $\exp(n^\varepsilon)$?

            • Fast mixing for anti-ferromagnetic Ising at high temperature


              Add remark

              Problem 1.3.

              [Allan Sly] Take a (random) $d$-regular graph, and consider the anti-ferromagnetic Ising model, i.e. $J_{ij}=-1$ for all $i,j$. Can we show show fast mixing $O(n\log n)$ up to $$(d-1)\tanh(\beta)<1 \, ?$$
                  This is known for the ferromagnetic Ising model, i.e. when $J_{ij}=1$ [Mossel, Sly 2013]. Also known: explicit sampling, decay of correlations.

                • Mixing time for ferromagnetic Ising at critical temperature


                  Add remark

                  Problem 1.4.

                  [Eyal Lubetzky] What is the mixing time for the ferromagnetic Ising model at critical temperature $\beta=\beta_c$ on a random $d$-regular graph? Is it $n^c$?

                    • Censoring for the Potts model


                      Add remark

                      Problem 1.5.

                      [Yuval Peres] Consider the $q$-state Potts model (say with $q=3$ for concreteness) and start from all green. Is it the case that deterministically censoring a sequence of spin flips can only increase the total variation distance to stationarity?
                          This is known for monotone chains by [Peres, Winkler].

                        • Diagnostics

                              We seek diagnostic tests for knowing that a general spin system is mixed on a general graph $G$.

                          Add remark

                          Problem 1.6.

                          1. Consider the ferromagnetic Ising model on a general graph $G$. Which two $x,y\in\Omega$ maximize $\|P^t(x,\cdot)-P^t(y,\cdot)\|_{TV}$? More generally, is it true that in any monotone reversible chain, the maximal and minimal initial configurations maximize the total variation distance between two chains?

                          2. Can one use a diagnostic to estimate $t_{\mbox{mix}}$ up to $O(1)$? Of course, answering question (1) would answer this as well.

                          3. Consider the $3$-Potts model for a general graph $G$. Can one devise a diagnostic to differentiate between $t_{\mbox{mix}}=O(n\log n)$ and $\exp(\Omega(n))$?
                              For monotone spin systems, the answer to (1) is known up to a multiplicative factor that is on the order of the volume of the system. This implies that (2) is known up to $O(\log n)$ using the distance between the all plus and all minus initial configurations.

                            • Noisy majority model

                                  The noisy majority model with parameter $\epsilon\in (0,1)$ is a spin system on a graph $G$ that is the stationary distribution of the following Markov chain on $\Omega=\{\pm 1\}^{V(G)}$: assign each vertex a rate-$1$ Poisson clock. When the clock at a site rings, the spin at that vertex randomizes according to a $\mbox{Ber}(\frac 12)$ with probability $\epsilon$ and chooses the majority of the spins of its neighbors and itself with probability $1-\epsilon$ (flipping a coin in the event of a tie).

                              Add remark

                              Problem 1.7.

                              Consider the noisy majority model on $\mathbb Z_n^d$ for $d>1$. Show there exists a fixed $\epsilon>0$ such that $t_{\mbox{mix}}\gtrsim \exp(n^{\epsilon})$ (should be true for $\exp(cn)$).

                                  Cite this as: AimPL: Markov chain mixing times, available at http://aimpl.org/markovmixing.