  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 $\max_{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 \cite{ALOV19,
CGM19}. For spanning tree, we improve 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.
