×

Random random walks on \(\mathbb{Z}_2^d\). (English) Zbl 0896.60034

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.

MSC:

60G50 Sums of independent random variables; random walks
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
PDFBibTeX XMLCite
Full Text: DOI