Exact sampling and counting for fixed-margin matrices

Abstract

The uniform distribution on matrices with specified row and column sums is often a natural choice of null model when testing for structure in two-way tables (binary or nonnegative integer). Due to the difficulty of sampling from this distribution, many approximate methods have been developed. We will show that by exploiting certain symmetries, exact sampling and counting is in fact possible in many nontrivial real-world cases. We illustrate with real datasets including ecological co-occurrence matrices and contingency tables.

Published in at http://dx.doi.org/10.1214/13-AOS1131 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org). arXiv admin note: text overlap with arXiv:1104.0323

References in corpus (2)

• Importance sampling for weighted binary random matrices with specified margins
• Exact Enumeration and Sampling of Matrices with Specified Margins

Cited by in corpus (7)

• The Babe Ruth Algorithm: a fast, unbiased procedure to randomize presence-absence data matrices with fixed row and column totals
• Recursive Pathways to Marginal Likelihood Estimation with Prior-Sensitivity Analysis
• Improved estimates for the number of non-negative integer matrices with given row and column sums
• GAMA: A Novel Algorithm for Non-Convex Integer Programs
• Lower bounds for contingency tables via Lorentzian polynomials
• An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
• Lattice Coding for Downlink Multiuser Transmission