Spectral Gap for the Binary Fixed-Margin Swap Chain

Jul 16, 2026

Upload by Anda

Explicit spectral-gap lower bounds are established for the lazy swap Markov chain on m×n binary matrices with prescribed row and column sums. The chain serves as a standard sampler for fixed-margin null models in ecology, statistics, and network analysis, addressing a Kannan–Tetali–Vempala conjecture on rapid mixing for all feasible margins. For every feasible margin set, the spectral gap is at least (m^2−1)−(n^2−1), and the bound is shown tight in the worst case, confirming the conjecture in a stronger quantitative form.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages26

Reading Time1 h 6 min

Introduction

Main Result

Comparison to a Two-row Heat-bath Chain

The two-row heat-bath chain

Spectral gap comparison

Reduction to Three Rows

Analysis of the Three-row Model

Overview

The scalar count sector

Johnson harmonics and non-scalar sectors

Proof of the three-row inequality

Proofs of the Main Theorem and Corollary

arXiv :2606 .22636v2 [math .PR] 13 Jul 2026 Spectral Gap for the Binary Fixed-Margin Swap Chain Weibo Fu ∗ Qian Qin † Guanyang Wang ‡ July 14, 2026 Abstract We prove an explicit spectral-gap lower bound for the lazy swap chain on binary matrices with prescribed row and column sums. This chain is a standard sampler for fixed-margin null models in ecology, statistics, and network analysis. Kannan, Tetali, and Vempala (KTV) conjectured that it mixes rapidly for all feasible margins (Kannan et al. , 1997) . We show that for every feasible set of margins on an m × n binary matrix, the lazy swap chain has spectral gap at least 􀀒m2􀀓 −1 􀀒n2􀀓 −1 . The bound is tight in the worst case. Thus, our result proves this KTV conjecture in a stronger quantitative form. The same spectral-gap bound also verifies the Mihail–Vazirani conjecture (Mihail, 1992; Kaibel, 2004) for fixed-margin 0/1-matrix polytopes. The proof gives a new route to fixed-margin sampling that avoids stability assumptions and canonical-path constructions. We compare the swap chain with a two-row heat-bath chain and use a local-to-global spectral reduction to reduce the analysis from arbitrary m × n matrices toa three-row problem. The remaining three-row inequality is then proved by separating the scalar column-count sector from the non-scalar Johnson harmonic sectors. The proof itself was generated by ChatGPT 5.5 Pro. ChatGPT proposed the whole proof strategy, including the comparison with the two-row heat-bath chain, the reduction to the three-row case, and the decomposition of the three-row function space into the count sector and the Johnson harmonic sectors. It also generated all the technical lemmas and initial proofs. The author’s role was to pose the problem, guide the search direction, evaluate the AI-generated arguments, rewrite the proof, and take responsibility for the final form and validity of the result. The full proof of the main theorem has been formalized in Lean, and the accompanying formalization is available at the anonymous repository [https://github.com/guanyangwang/](https://github.com/guanyangwang/)[ ](https://github.com/guanyangwang/)[ktv-swap-lean](ktv-swap-lean.)[.](ktv-swap-lean.) Contents 1 Introduction 2 2 Main Result 5 3 Comparison to a Two-row Heat-bath Chain 6 3.1 The two-row heat-bath chain ............................... 6 3.2 Spectral gap comparison .................................. 7 ∗[wfu@math.princeton.edu](wfu@math.princeton.edu)[ ](wfu@math.princeton.edu)†[qqin@umn.edu](qqin@umn.edu)[ ](qqin@umn.edu)‡[guanyang.wang@rutgers.edu](guanyang.wang@rutgers.edu) 4 Reduction to Three Rows 9 5 Analysis of the Three-row Model 12 5.1 Overview .......................................... 12 5.2 The scalar count sector ................................... 12 5.3 Johnson harmonics and non-scalar sectors ........................ 15 5.3.1 Johnson harmonic preliminaries .......................... 15 5.3.2 Generated sectors and the coefficient matrices .................. 17 5.4 Proof of the three-row inequality ............................. 20 6 Proofs of the Main Theorem and Corollary 2.4 21 1 Introduction Binary matrices are a natural way to encode binary relations between two sets of objects. For example, in ecology, one may record which bird species are observed on which islands by an m × n binary matrix A, where Aij = 1 if species i is present on island j, and Aij = 0 otherwise. A basic task is to generate uniformly random binary matrices with prescribed row and column sums. This problem arises naturally in ecological null models. Given an observed species–island matrix, ecologists ask whether its pattern reflects real ecological structure, such as competition between species, or can be explained by random chance after controlling for species prevalence and island richness. This leads to the fixed-margin null model, in which one samples uniformly from all binary matrices with the same row and c

FAQs

What problem does the document address?

It analyzes the mixing behavior of the lazy swap Markov chain used to sample uniformly random binary matrices with fixed row and column sums (fixed margins).

What is the main spectral-gap result?

For every feasible set of margins on an m×n binary matrix, the lazy swap chain has a spectral gap bounded below by an explicit expression in m and n, and the worst-case bound is tight.

How does the proof approach avoid traditional methods?

It compares the swap chain to a two-row heat-bath chain and applies a local-to-global spectral reduction to reduce the analysis from general m×n matrices to a three-row model, then proves a remaining three-row inequality by decomposing into scalar count and Johnson harmonic sectors.

Jul 16, 2026

Upload by Anda