文章基本信息

标题：Cutoff for a Stratified Random Walk on the Hypercube
本地全文：下载
作者：Anna Ben-Hamou ; Yuval Peres
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：29:1-29:10
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.29
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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).
关键词：Mixing times; cutoff; hypercube