Cutoff for a stratified random walk on the hypercube

Electronic Communications in Probability

Anna Ben-Hamou¹ 

关键词: Markov chains;    mixing times;    cutoff;    hypercube;   

DOI  :  10.1214/18-ECP132

学科分类：统计和概率

来源: Institute of Mathematical Statistics

【 摘 要 】

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 $\frac{3} {2}n\log n$ with window of size $n$, solving a question posed by Chung and Graham (1997).

【 授权许可】

CC BY