Markov bases have been developed in algebraic statistics for exact goodness-of-fit testing. They connect all elements in a fiber (given by the sufficient statistics) and allow building a Markov chain to approximate the distribution of a test statistic by its posterior distribution. However, finding a Markov basis is often computationally intractable. In addition, the number of Markov steps required for converging to the stationary distribution depends on the connectivity of the sampling space.
In this joint work with Caroline Uhler, we study the combinatorial structure of the finite lattice Ising model and propose a new method for exact goodness-of-fit testing which avoids computing a Markov basis. Our technique is to build a Markov chain consisting only of simple moves (i.e. swaps of two interior sites). These simple moves might not be sufficient to create a connected Markov chain. We prove that when a bounded change in the sufficient statistics is allowed, the resulting Markov chain is connected. The proposed algorithm not only overcomes the computational burden of finding a Markov basis, but it might also lead to a better connectivity of the sampling space and hence a faster convergence.