Wilson, David Bruce Random random walks on \(\mathbb{Z}_2^d\). (English) Zbl 0896.60034 Probab. Theory Relat. Fields 108, No. 4, 441-457 (1997). Summary: We consider random walks on classes of graphs defined on the \(d\)-dimensional binary cube \(\mathbb{Z}^d_2\) by placing edges on \(n\) randomly chosen parallel classes of vectors. The mixing time of a graph is the number of steps of a random walk before the walk forgets where it started, and reaches a random location. We resolve a question of Diaconis by finding exact expressions for this mixing time that hold for all \(n>d\) and almost all choices of vector classes. This result improves a number of previous bounds. Our method, which has application to similar problems on other Abelian groups, uses the concept of a universal hash function, from computer science. Cited in 10 Documents MSC: 60G50 Sums of independent random variables; random walks 60B15 Probability measures on groups or semigroups, Fourier transforms, factorization Keywords:random walk; hypercube; mixing time; threshold; Abelian groups PDFBibTeX XMLCite \textit{D. B. Wilson}, Probab. Theory Relat. Fields 108, No. 4, 441--457 (1997; Zbl 0896.60034) Full Text: DOI