2020/02/20 by Andrea Collevecchio, Collevecchio, Andrea, Robert Griffiths +1
Mathematics · #60J10 #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2002.09059
openalex publication_date 2020/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a general class of random walks on the N-hypercube, study cut-off for the mixing time, and provide several types of representation for the transition probabilities. 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 three steps. In other words, the total variation distance between the three steps transition and the stationary distribution decreases geometrically in N, which is the dimension of the hypercube. In some cases, the walk mixes almost-perfectly in exactly two steps. Notice that a well-known result (Theorem 1 in Diaconis and Shahshahani (1986)) shows that there exist no random walk on Abelian groups (such as the hypercube) which mixes perfectly in exactly two steps.