2026-09-12T16:33:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8146 2026-09-04T19:48:14Z ddc:004 open_access

Random Walks in Polytopes and Negative Dependence Peres, Yuval Singh, Mohit Vishnoi, Nisheeth K. Random walks Matroid Polytope Brownian motion Negative dependence We present a Gaussian random walk in a polytope that starts at a point inside and continues until it gets absorbed at a vertex. Our main result is that the probability distribution induced on the vertices by this random walk has strong negative dependence properties for matroid polytopes. Such distributions are highly sought after in randomized algorithms as they imply concentration properties. Our random walk is simple to implement, computationally efficient and can be viewed as an algorithm to round the starting point in an unbiased manner. The proof relies on a simple inductive argument that synthesizes the combinatorial structure of matroid polytopes with the geometric structure of multivariate Gaussian distributions. Our result not only implies a long line of past results in a unified and transparent manner, but also implies new results about constructing negatively associated distributions for all matroids. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuval Peres and Mohit Singh and Nisheeth K. Vishnoi 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.50 urn:nbn:de:0030-drops-81464 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.50 eng https://creativecommons.org/licenses/by/3.0/legalcode