Snake Algorithm: A Rejection-Free Sampler for Binary Matrices with Fixed Margins
This talk presents a new algorithm for sampling binary matrices with fixed row and column sums, a problem with applications in network, ecology, differential privacy, and theoretical computer science. We introduce the 'Snake' algorithm, unlike existing methods, finds a random, swappable loop at every step. Our algorithm features a rejection-free design and scales better with the matrix's size, proving particularly efficient for high-dimensional and sparse matrices common in practical applications.
I am interested in Monte Carlo, Markov chain, and Markov chain Monte Carlo. I am also actively learning quantum computing recently.