文章基本信息

标题：Random Walks in Polytopes and Negative Dependence
本地全文：下载
作者：Yuval Peres ; Mohit Singh ; Nisheeth K. Vishnoi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：67
页码：50:1-50:10
DOI：10.4230/LIPIcs.ITCS.2017.50
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Random walks; Matroid; Polytope; Brownian motion; Negative dependence