A fast MCMC algorithm for the uniform sampling of binary matrices with fixed margins
Guanyang Wang
Abstract
Uniform sampling of binary matrix with fixed margins is an important and difficult problem in statistics, computer science, ecology and so on. The well-known swap algorithm would be inefficient when the size of the matrix becomes large or when the matrix is too sparse/dense. Here we propose the Rectangle Loop algorithm, a Markov chain Monte Carlo algorithm to sample binary matrices with fixed margins uniformly. Theoretically the Rectangle Loop algorithm is better than the swap algorithm in Peskun’s order. Empirically studies also demonstrates the Rectangle Loop algorithm is remarkablely more efficient than the swap algorithm.
Topics & Concepts
MathematicsRectangleAlgorithmSwap (finance)Binary numberMarkov chain Monte CarloMarkov chainSampling (signal processing)Slice samplingBinary dataMatrix (chemical analysis)Monte Carlo methodRejection samplingLoop (graph theory)Logical matrixMathematical optimizationStochastic matrixMonte Carlo algorithmRamer–Douglas–Peucker algorithmMarkov processSample (material)Gibbs samplingMarkov Chains and Monte Carlo MethodsRandom Matrices and ApplicationsMatrix Theory and Algorithms