2020/04/15 by Nima Anari, Anari, Nima, Kuikui Liu +7
Chemistry · Mathematics · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mass Spectrometry Techniques and Applications #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2004.07220
openalex publication_date 2020/04/15 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
We prove tight mixing time bounds for natural random walks on bases of\nmatroids, determinantal distributions, and more generally distributions\nassociated with log-concave polynomials. For a matroid of rank k on a ground\nset of n elements, or more generally distributions associated with\nlog-concave polynomials of homogeneous degree k on n variables, we show\nthat the down-up random walk, started from an arbitrary point in the support,\nmixes in time O(k\log k). Our bound has no dependence on n or the starting\npoint, unlike the previous analyses [ALOV19,CGM19], and is tight up to constant\nfactors. The main new ingredient is a property we call approximate exchange, a\ngeneralization of well-studied exchange properties for matroids and valuated\nmatroids, which may be of independent interest. In particular, given function\n\μ: [n] choose k \→ \ℝ\≥ 0, our approximate exchange\nproperty implies that a simple local search algorithm gives a\nkO(k)-approximation of \maxS \μ(S) when \μ is generated by a\nlog-concave polynomial, and that greedy gives the same approximation ratio when\n\μ is strongly Rayleigh.\n As an application, we show how to leverage down-up random walks to\napproximately sample random forests or random spanning trees in a graph with\nn edges in time O(n\log2 n). The best known result for sampling random\nforest was a FPAUS with high polynomial runtime recently found by citeALOV19,\nCGM19. For spanning tree, we improve on the almost-linear time algorithm by\n[Sch18]. Our analysis works on weighted graphs too, and is the first to achieve\nnearly-linear running time for these problems.\n