Markov chains, quotient ideals and connectivity with positive margins

We present algebraic methods for studying connectivity of Markov moves with margin positivity. The purpose is to develop Markov sampling methods for exact conditional inference in statistical models where a Markov basis is hard to compute. In some cases positive margins are shown to allow a set of Markov connecting moves that are much simpler than the full Markov basis. Introduction Advances in algebra have impacted in a fundamental way the study of exponential families of probability distributions. In the 1990s, computational methods of commutative algebra were brought into statistics to solve both classical and new problems in the framework of exponential family models. In some cases, the computations are of an algebraic nature or could be made algebraic with some work, as in the cumulant methods of (Pistone and Wynn 1999). In other cases, the computations are ultimately Monte Carlo averages and the algebra plays a secondary role in designing algorithms. This is the nature of the work of (Diaconis and Sturmfels 1998). Commutative algebra is also used in statistics for experimental design (Pistone et al. 2001) where exponential families are not the focus. (Diaconis and Sturmfels 1998) showed how computing a generating set for a toric ideal is fundamental to irreducibility of a Markov chain on a set of constrained tables. This theory gives a method for obtaining Markov chain moves, such as the genotype sampling method of (Guo and Thompson 1992), extensions to graphical models (Geiger et al. 2006) and beyond (Hosten and Sullivant 2004).