Algebraic algorithms for sampling from conditional distributions

1998/02/01 by Persi Diaconis, Bernd Sturmfels · 664 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithm #Computer science #Conditional probability distribution #Contingency table #Discrete mathematics #Exponential family #Markov chain #Mathematics #Permutation (music) #Polynomial and algebraic computation #Resampling #Sampling (signal processing) #Statistic #Statistics #Sufficient statistic #Topological and Geometric Data Analysis

paper · pdf · doi:10.1214/aos/1030563990

published in The Annals of Statistics 26(1) (Institute of Mathematical Statistics)

openalex publication_date 1998/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

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 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 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
• Gröbner bases of contraction ideals
• A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
• Markov Property in Generative Classifiers
• Exploiting Symmetries in the Computation of Graver Bases
• Estimating the size of a set using cascading exclusion
• Algebraic Unimodular Counting
• Multiresolution Analysis of Incomplete Rankings
• Exact conditional goodness-of-fit tests for the mixed membership stochastic block model
• Combinatorial degree bound for toric ideals of hypergraphs
• Maximum Entropy in the framework of Algebraic Statistics: A First Step
• Binomial fibers and indispensable binomials
• Toric geometry of cuts and splits
• Markov bases for two-way change-point models of ladder determinantal tables
• Semigroups and sequential importance sampling for multiway tables
• A new correlation coefficient, its orthogonal decomposition and associated tests of independence
• Higher Lawrence configurations
• Random sampling of Latin squares via binary contingency tables and probabilistic divide-and-conquer
• Privacy-Preserving Data Sharing for Genome-Wide Association Studies
• Binomiality of colored Gaussian models
• Three Counterexamples on Semigraphoids
• On Atomic Density of Numerical Semigroup Algebras
• A Multiresolution Analysis Framework for the Statistical Analysis of Incomplete Rankings
• On the Existence of Unbiased Hypothesis Tests: An Algebraic Approach
• Algebraic Bayesian analysis of contingency tables with possibly zero-probability cells
• Pfaffian Systems of A-Hypergeometric Systems II --- Holonomic Gradient Method
• A computer algebra system for R: Macaulay2 and the m2r package
• Multilevel Sampling in Algebraic Statistics
• Prolongations and computational algebra
• On the generalized Scarf complex of lattice ideals
• Markov and lattice bases for Forman-Ricci curvature of graphs
• An Early History of Toric Ideals
• Borel graphs generated by finitely many bounded-to-1 commuting Borel functions and hyperfinite equivalence relations
• Phase transition in random contingency tables with non-uniform margins
• Markov bases for noncommutative Fourier analysis of ranked data
• Degree Bounds for a Minimal Markov Basis for the Three-State Toric Homogeneous Markov Chain Model
• Accurate Parametric Inference for Small Samples
• A class of statistical models to weaken independence in two-way contingency tables
• Truncated Markov bases and Gröbner bases for Integer Programming
• Markov basis and Gröbner basis of Segre–Veronese configuration for testing independence in group-wise selections
• Learning Fast Monomial Orders for Gröbner Basis Computations
• Monomial ideals and the Scarf complex for coherent systems in reliability theory
• Markov chain Monte Carlo tests for designed experiments
• Hierarchical subspace models for contingency tables
• Algebraic Statistics in OSCAR
• Equivariant Gröbner bases of symmetric toric ideals
• On robust toric ideals of weighted oriented graphs
• Minimal and minimal invariant Markov bases of decomposable models for contingency tables
• Operational Interpretation of Rényi Information Measures via Composite Hypothesis Testing Against Product and Markov Distributions
• The circuit ideal of a vector configuration
• Separating Geometry From Interference in Constrained Quantum Optimization
• Toric ideals of graphs minimally generated by a Gröbner basis

Related

• Markov Chain Monte Carlo sampling for conditional tests: A link between 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