Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests

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(k log k). Our bound has no dependence on n or the starting point, unlike the previous analyses [Ana+19; 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. In particular, given function µ : ( [n] k ) → R ≥0 , our approximate exchange property implies that a simple local search algorithm gives a k O(k) -approximation of max S µ(S) when µ is generated by a logconcave polynomial, and that greedy gives the same approximation ratio when µ is strongly Rayleigh. As an application, we show how to leverage down-up random walks to approximately sample random forests or random spanning trees in a graph with n edges in time O(n log 2 n). The best known result for sampling random forest was a FPAUS with high polynomial runtime recently found by [Ana+19; CGM19]. For spanning tree, we improve 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 for these problems. Our algorithms can be naturally extended to support approximately sampling from random forests of size between k 1 and k 2 in time O(n log 2 n), for fixed parameters k 1 , k 2 , as well as approximate sampling random independent set of matroid M of rank k on a ground set of n elements using O(kn log k) calls to the independence oracle of M.