Algebraic algorithms for sampling from conditional distributions

1998/02/01 by Persi Diaconis, Bernd Sturmfels · 31 citations
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Advanced Combinatorial Mathematics #Polynomial and algebraic computation

paper · pdf · doi:10.1214/aos/1030563990

Abstract

We construct Markov chain algorithms for sampling from discrete exponential families conditional on a sufficient statistic. Examples include contingency tables, logistic regression, and spectral analysis of permutation data. The algorithms involve computations in polynomial rings using Gröbner bases.

Cited by

• On unirational varieties with poset parameterizations
• Markov bases and subbases for bounded contingency tables
• Lower bounds for contingency tables via Lorentzian polynomials
• Markov degree of configurations defined by fibers of a configuration
• Arithmetical rank of toric ideals associated to graphs
• Saturated fractions of two-factor designs
• Toric fiber products
• Random Transpositions on Contingency Tables
• SAT-sampling for statistical significance testing in sparse contingency tables
• Testing Hardy-Weinberg equilibrium with a simple root-mean-square\n statistic
• Efficient, Differentially Private Point Estimators
• Learning selection strategies in Buchberger's algorithm
• Fixed-width output analysis for Markov chain Monte Carlo
• Semigroups and sequential importance sampling for multiway tables and beyond
• On robustness and related properties on toric ideals
• Exact sampling algorithms for Latin squares and Sudoku matrices via\n probabilistic divide-and-conquer
• Non-asymptotic goodness-of-fit tests and model selection in valued stochastic blockmodels
• Minimal Markov basis for tests of main effect models for 2^p-1 fractional factorial designs of resolution p
• A Markov basis for two-state toric homogeneous Markov chain model without initial parameters
• Vertex Collapsing and Cut Ideals
• Normal binary graph models
• Markov Combinations of Discrete Statistical Models
• Markov complexity of monomial curves
• Coauthorship and citation networks for statisticians: Comment
• Statistical Challenges with High Dimensionality: Feature Selection in Knowledge Discovery
• Finite Groebner bases in infinite dimensional polynomial rings and applications
• Ideals of Graph Homomorphisms
• Markov Property in Generative Classifiers
• Estimating the size of a set using cascading exclusion
• Algebraic Unimodular Counting
• Multiresolution Analysis of Incomplete Rankings

Related

• Markov Chain Monte Carlo sampling for conditional tests: A link between\n permutation tests and algebraic statistics
• An introduction to computational algebraic statistics
• Direct sampling from conditional distributions by sequential maximum likelihood estimations
• Algorithm for direct sampling from conditional distributions of toric models
• Markov bases: a 25 year update