License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.50
URN: urn:nbn:de:0030-drops-81464
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8146/
Go to the corresponding LIPIcs Volume Portal

Peres, Yuval ; Singh, Mohit ; Vishnoi, Nisheeth K.

Random Walks in Polytopes and Negative Dependence

pdf-format:
LIPIcs-ITCS-2017-50.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{peres_et_al:LIPIcs:2017:8146,
  author =	{Yuval Peres and Mohit Singh and Nisheeth K. Vishnoi},
  title =	{{Random Walks in Polytopes and Negative Dependence}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{50:1--50:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8146},
  URN =		{urn:nbn:de:0030-drops-81464},
  doi =		{10.4230/LIPIcs.ITCS.2017.50},
  annote =	{Keywords: Random walks, Matroid, Polytope, Brownian motion, Negative dependence}
}

Keywords: Random walks, Matroid, Polytope, Brownian motion, Negative dependence
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI