A fast MCMC algorithm for the uniform sampling of binary matrices with fixed margins

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1690-1706
Number of pages17
JournalElectronic Journal of Statistics
Volume14
Issue number1
DOIs
StatePublished - 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Binary matrix
  • Fixed margins
  • MCMC
  • Uniform sampling

Fingerprint

Dive into the research topics of 'A fast MCMC algorithm for the uniform sampling of binary matrices with fixed margins'. Together they form a unique fingerprint.

Cite this