English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Curveball algorithm is a variation on well-known switch-based Markovchain approaches for uniformly sampling binary matrices with fixed row andcolumn sums. Instead of a switch, the Curveball algorithm performs a so-calledbinomial trade in every iteration of the algorithm. Intuitively, this couldlead to a better convergence rate for reaching the stationary (uniform)distribution in certain cases. Some experimental evidence for this has beengiven in the literature. In this note we give a spectral gap comparison betweentwo switch-based chains and the Curveball chain. In particular, this comparisonallows us to conclude that the Curveball Markov chain is rapidly mixingwhenever one of the two switch chains is rapidly mixing. Our analysis directlyextends to the case of sampling binary matrices with forbidden entries (underthe assumption of irreducibility). This in particular captures the case ofsampling simple directed graphs with given degrees. As a by-product of ouranalysis, we show that the switch Markov chain of the Kannan-Tetali-Vempalaconjecture only has non-negative eigenvalues if the sampled binary matriceshave at least three columns. This shows that the Markov chain does not have tobe made lazy, which is of independent interest. We also obtain an improvedbound on the smallest eigenvalue for the switch Markov chain studied byGreenhill for uniformly sampling simple directed regular graphs.

Comparing the Switch and Curveball Markov Chains for Sampling Binary Matrices with Fixed Marginals