Algebraic algorithms for sampling from conditional distributions (Q1807063)

This paper aims to describe the construction of new Markov chain algorithms for sampling from discrete exponential families conditional on a sufficient statistic. Section 2 introduces the necessary stochastic and statistical background. Section 3 contains the main contribution of the paper: it shows how to compute a Markov basis using tools from computational algebra. More precisely, to find a Markov basis is proved to be equivalent to finding a set of generators of an ideal in a polynomial ring, using Gröbner bases. To represent this ideal in a way suitable for computation is illustrated by MATHEMATICA and MAPLE programs. The next sections of the paper include detailed treatments of the proposed technique for some important special cases: contingency tables (Section 4), logistic regression (in Section 5), and the spectral analysis of permutation data (Section 6).