Random random walks on ℤ2
d |
| |
Authors: | David Bruce Wilson |
| |
Institution: | (1) University of California, 387 Soda Hall Berkeley, CA 94720-1776, USA e-mail: dbwilson@alum.mit.edu, US |
| |
Abstract: | 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. |
| |
Keywords: | and phrases Random walk hypercube mixing time threshold |
本文献已被 SpringerLink 等数据库收录! |
|