# Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests

arXiv: https://arxiv.org/abs/2004.07220 · HTML: https://mlsanity.com/paper/2004.07220/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2020.

## Built on by (most cited first, 1 of 1)

- [The Power of Test-Time Training for Approximate Sampling](https://mlsanity.com/paper/2606.11437/) (2026)

## Abstract (arXiv)

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. In particular, given function μ: [n] choose k → ℝ≥ 0, our approximate exchange property implies that a simple local search algorithm gives a kO(k)-approximation of maxS μ(S) when μ is generated by a log-concave 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(nlog2 n). The best known result for sampling random forest was a FPAUS with high polynomial runtime recently found by citeALOV19, 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.