Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees
share
We prove tight mixing time bounds for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomials. For a matroid of rank k on a ground set of n elements, or more generally distributions associated with log-concave polynomials of homogeneous degree k on n variables, we show that the down-up random walk, started from an arbitrary point in the support, mixes in time O(klog k). Our bound has no dependence on n or the starting point, unlike the previous analyses [ALOV19, CGM19], and is tight up to constant factors. The main new ingredient is a property we call approximate exchange, a generalization of well-studied exchange properties for matroids and valuated matroids, which may be of independent interest. Additionally, we show how to leverage down-up random walks to approximately sample spanning trees in a graph with n edges in time O(nlog^2 n), improving on the almost-linear time algorithm by Schild [Sch18]. Our analysis works on weighted graphs too, and is the first to achieve nearly-linear running time.
READ FULL TEXT