Georgia Institute of Technology College of Sciences

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 and Sarah Cepeda, we compare different test statistics and study the combinatorial structure of the finite lattice Ising model. We propose a new method for exact goodness-of-fit testing. Our technique avoids computing a Markov basis but builds 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.