Cutoff for a stratified random walk on the hypercube

DOI10.1214/18-ECP132MaRDI QIDQ1663741zbMATH OpenFDO

Authors Anna Ben-Hamou, Yuval Peres

Publication date 23 August 2018

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

Full work available at URL https://arxiv.org/abs/1705.06153, https://projecteuclid.org/euclid.ecp/1527300061

zbMATH Keywords

cutoffhypercubeMarkov chainsmixing times

Mathematics Subject Classification ID

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

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).

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

Cites work

• KAZHDAN CONSTANTS FOR SL_n(ℤ)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On the complexity of matrix reduction over finite fields
• Stratified random walks on then-cube
• Walks on generating sets of Abelian groups

Cited in

(10)

• Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
• A non-local random walk on the hypercube
• Fast mixing of a randomized shift-register Markov chain
• A discrete random walk on the hypercube
• Cutoff for a stratified random walk on the hypercube
• 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)