Loading Web-Font TeX/Math/Italic
| 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.