On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)

DOI10.1214/19-AIHP991zbMath1434.60190arXiv1808.06157OpenAlexW3011034947MaRDI QIDQ2179619

Oanh Nguyen, Evita Nestoridi

Publication date: 13 May 2020

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.06157

zbMATH Keywords

cutoffrandom graphsmixing timecontingency table

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)

Related Items (1)

A class of random walks on the hypercube

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random generation of \(2 \times 2 \times\dots \times 2 \times J\) contingency tables
• Brunn--Minkowski inequalities for contingency tables and integer flows
• Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums
• Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
• Testing for independence in a two-way table: New interpretations of the chi-square statistic
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• The asymptotic number of non-negative integer matrices with given row and column sums
• The asymptotic number of labeled graphs with given degree sequences
• Comparison theorems for reversible Markov chains
• Comparison techniques for random walk on finite groups
• Mixing times of lozenge tiling and card shuffling Markov chains
• Polynomial-time counting and sampling of two-rowed contingency tables
• Counting integer flows in networks
• Algebraic algorithms for sampling from conditional distributions
• Asymptotic enumeration by degree sequence of graphs of high degree
• Negative examples for sequential importance sampling of binary contingency tables
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Sequential importance sampling for multiway tables
• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
• A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
• An approximation algorithm for counting contingency tables
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
• Generating a random permutation with random transpositions
• Sampling contingency tables
• The degree sequence of a random graph. I. The models
• New permanental upper bounds for nonnegative matrices
• [https://portal.mardi4nfdi.de/wiki/Publication:4705324 Random generation of 2�n contingency tables]
• On sampling with Markov chains
• Characterizing optimal sampling of binary contingency tables via the configuration model
• The number of graphs and a random graph with a given degree sequence
• What Does a Random Contingency Table Look Like?
• Approximately Counting Integral Flows and Cell-Bounded Contingency Tables
• Enumerating Contingency Tables via Random Permanents
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Asymptotic Enumeration of Hypergraphs by Degree Sequence
• Sampling binary contingency tables with a greedy start
• Sampling binary contingency tables with a greedy start
• A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant

This page was built for publication: On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)