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 [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, ] \choose } \to _{\geq 0}, our approximate exchange property implies that a simple local search algorithm gives a k^{O(k)}-approximation of S \mu(S) when \mu is generated by a log-concave polynomial, and that greedy gives the same approximation ratio when \mu is strongly Rayleigh. As an application, } we show how to leverage down-up random walks to approximately sample  spanning trees in a graph with n edges in time O(n\log^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  .
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 [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. In particular, given function \mu: n] \choose k} \to \mathbb{R_{\geq 0}, our approximate exchange property implies that a simple local search algorithm gives a k^{O(k)}-approximation of S \mu(S) when \mu is generated by a log-concave polynomial, and that greedy gives the same approximation ratio when \mu 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 \mbox{%DIFAUXCMD ALOV19, CGM19 on the almost-linear time algorithm by [Sch18]. Our analysis works on weighted graphs too, and is the first to achieve nearly-linear running time for these problems .
R
Additionally,
In particular, given function \mu:
A
n
A
k
A
\mathbb{R
A
random forests or random
R
, improving
. The best known result for sampling random forest was a FPAUS with high polynomial runtime recently found by \mbox{%DIFAUXCMD ALOV19, CGM19
D
Schild
A
for these problems