Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures
summary
Proves that homogeneous measures with the stochastic covering property (including strong Rayleigh/determinantal and balanced matroid laws such as uniform spanning trees) satisfy a 1‑Lipschitz concentration bound P{|F−E F|>a} ≤ exp(−a^2/(8K)), using a K‑step Doob martingale from a sequential K‑sampling procedure plus a coupling that shifts conditioned laws by one bit. Extends to non‑homogeneous strong Rayleigh laws with a weaker bound exp(−3e a^2/(16a+2μ)).
AI-written summary · about