@inbook{dbaa7ffbcf82411caae0dbf36cafb35f,

title = "A Class of Random Walks on the Hypercube",

abstract = "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.",

keywords = "Hypercube, Markov chain, Mixing, Random walk",

author = "Andrea Collevecchio and Griffiths, {Robert C.}",

note = "Progr. Probab. In and out of equilibrium. 3. Celebrating Vladas Sidoravicius, 265–298, Progr. Probab., 77, Birkh{\"a}user/Springer, Cham, ",

year = "2021",

doi = "10.1007/978-3-030-60754-8_13",

language = "English",

isbn = "9783030607531",

volume = "77",

series = "Progress in Probability",

publisher = "Springer",

pages = "265--298",

editor = "{Eul{\'a}lia Vares}, Maria and Roberto Fern{\'a}ndez and {Renato Fontes}, Luiz and Newman, {Charles M}",

booktitle = "In and Out of Equilibrium 3",

}