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} ⁿ , is studied. The single-step transition probabilities P _n,ij , with i,j∈Ω _n , are given by P_n,ij=\frac(1-a)^d_ij(2-a)ⁿP_{n,ij}=\frac{(1-{\alpha})^{d_{ij}}}{(2-{\alpha})^{n}}, 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-a\frac{1-{\alpha}}{2-{\alpha}}. The m-step transition matrix P_n,ij^mP_{n,ij}^{m} 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 P_n,ij^mP_{n,ij}^{m} is also proved.