Cutoff for a stratified random walk on the hypercube

DOI10.1214/18-ECP132zbMATH Open1397.60096arXiv1705.06153MaRDI QIDQ1663741FDOQ1663741

Anna Ben-Hamou, Yuval Peres

Publication date: 23 August 2018

Published in: Electronic Communications in Probability (Search for Journal in Brave)

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 $frac32nlogn$ with window of size $n$, solving a question posed by Chung and Graham (1997).

Full work available at URL: https://arxiv.org/abs/1705.06153

Recommendations

• Cutoff for a stratified random walk on the hypercube
• Stratified random walks on then-cube
• Cutpoints of non-homogeneous random walks
• A class of random walks on the hypercube
• Cutoff for random walk on dynamical Erdős-Rényi graph
• Cutoff phenomena for random walks on random regular graphs
• Cutoff phenomenon for random walks on Kneser graphs
• Cutoff phenomenon for nearest Lamperti's random walk
• A discrete random walk on the hypercube

zbMATH Keywords

cutoffhypercubeMarkov chainsmixing times

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cites Work

• Title not available (Why is that?)
• Walks on generating sets of Abelian groups
• KAZHDAN CONSTANTS FOR SL_n(ℤ)
• On the complexity of matrix reduction over finite fields
• Stratified random walks on then-cube

Cited In (6)

• Fast mixing of a randomized shift-register Markov chain
• Approximate unitary \(t\)-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Cutoff for product replacement on finite groups
• An affine walk on the hypercube
• Cutoff for the Fredrickson-Andersen one spin facilitated model
• On mixing times for stratified walks on thed-cube

This page was built for publication: Cutoff for a stratified random walk on the hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1663741)