# A Fast MCMC for the Uniform Sampling of Binary Matrices with Fixed Margins

arXiv: https://arxiv.org/abs/1904.03836 · HTML: https://mlsanity.com/paper/1904.03836/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2019.

## Built on by (most cited first, 1 of 1)

- [Efficient Generation of Binary Magic Squares](https://mlsanity.com/paper/2511.00547/) (2025)

## Abstract (arXiv)

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.