Summary.
We consider random walks on classes of graphs defined on the d-dimensional binary cube ℤ2 d 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. In this paper 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wilson, D. Random random walks on ℤ2 d . Probab Theory Relat Fields 108, 441–457 (1997). https://doi.org/10.1007/s004400050116
Issue Date:
DOI: https://doi.org/10.1007/s004400050116