A class of random walks on the hypercube

Andrea Collevecchio, Bob Griffiths

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review


We introduce a general class of time inhomogeneous random walks on the N-hypercube. These random walks are reversible with an N-product Bernoulli stationary distribution and have a property of local change of coordinates in a transition. Several types of representations for the transition probabilities are found. The paper studies cut-off for the mixing time. We observe that for a sub-class of these processes with long range (i.e. non-local) there exists a critical value of the range that allows an almost-perfect mixing in at most two steps. That is, the total variation distance between the two steps transition and stationary distributions decreases to zero as the dimension of the hypercube N increases. Notice that a well-known result (Theorem 1 in [6]) shows that there does not exist a random walk on Abelian groups (such as the hypercube) which mixes perfectly in exactly two steps.
Original languageEnglish
Title of host publicationIn and Out of Equilibrium 3
Subtitle of host publicationCelebrating Vladas Sidoravicius
EditorsMaria Eulália Vares, Roberto Fernández, Luiz Renato Fontes, Charles M Newman
Place of PublicationCham Switzerland
Number of pages34
ISBN (Electronic)9783030607548
ISBN (Print)9783030607531
Publication statusPublished - 2021

Publication series

NameProgress in Probability
PublisherSpringer Nature
ISSN (Print)1050-6977
ISSN (Electronic)2297-0428

Cite this