Exact Solution for a Class of Random Walk on the Hypercube

A class of families of Markov chains defined on the vertices of the n-dimensional hypercube, Ω n ={0,1} n , is studied. The single-step transition probabilities P n,ij , with i,j∈Ω n , are given by Pn,ij=\frac(1-a)dij(2-a)nPnij=(2−)n(1−)dij, where α∈(0,1) and d ij is the Hamming distance between i and j. This corresponds to flip independently each component of the vertex with probability \frac1-a2-a2−1−. The m-step transition matrix Pn,ijmPmnij is explicitly computed in a close form. The class is proved to exhibit cutoff. A model-independent result about the vanishing of the first m terms of the expansion in α of Pn,ijmPmnij is also proved.