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.APPROX-RANDOM.2017.29
URN: urn:nbn:de:0030-drops-75787
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7578/
Go to the corresponding LIPIcs Volume Portal

Ben-Hamou, Anna ; Peres, Yuval

Cutoff for a Stratified Random Walk on the Hypercube

pdf-format:
LIPIcs-APPROX-RANDOM-2017-29.pdf (0.4 MB)

Abstract

We consider the random walk on the hypercube which moves by picking an ordered pair (i,j) of distinct coordinates uniformly at random and adding the bit at location i to the bit at location j, modulo 2. We show that this Markov chain has cutoff at time (3/2)n*log(n) with window of size n, solving a question posed by Chung and Graham (1997).

BibTeX - Entry

@InProceedings{benhamou_et_al:LIPIcs:2017:7578,
  author =	{Anna Ben-Hamou and Yuval Peres},
  title =	{{Cutoff for a Stratified Random Walk on the Hypercube}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{29:1--29:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7578},
  URN =		{urn:nbn:de:0030-drops-75787},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.29},
  annote =	{Keywords: Mixing times, cutoff, hypercube}
}

Keywords: Mixing times, cutoff, hypercube
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 11.08.2017

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