## Random Random Walks on *Z*_{2}^{d}

We consider random walks on classes of graphs defined on the *d*-dimensional
binary cube *Z*_{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.
*Probability Theory and Related Fields*, 108(4):441--457, 1997.

PostScript version

This article is also available at Springer's website.