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 ) shows that there does not exist a random walk on Abelian groups (such as the hypercube) which mixes perfectly in exactly two steps.
|Title of host publication||In and Out of Equilibrium 3|
|Subtitle of host publication||Celebrating Vladas Sidoravicius|
|Editors||Maria Eulália Vares, Roberto Fernández, Luiz Renato Fontes, Charles M Newman|
|Place of Publication||Cham Switzerland|
|Number of pages||34|
|Publication status||Published - 2021|
|Name||Progress in Probability|