 |
|
|
| | | | | |
|
|
|
|
|
Mixing Times for Random Walks on Finite Lamplighter Groups
|
Yuval Peres, University of California
David Revelle, University of California
|
Abstract
Given a finite graph G, a vertex of the lamplighter graph consists of a zero-one labeling of the vertices of G, and a marked vertex of G. For transitive graphs G, we show that, up to constants, the relaxation time for simple random walk in corresponding lamplighter graph is the maximal hitting time for simple random walk in G, while the mixing time in total variation on the lamplighter graph is the expected cover time on G. The mixing time in the uniform metric on the lamplighter graph admits a sharp threshold, and equals |G| multiplied by the relaxation time on G, up to a factor of log |G|.
For the lamplighter group over the discrete two dimensional torus of sidelength n, the relaxation time is of order n^2 log n, the total variation mixing time is of order n^2 log^2 n, and the uniform mixing time is of order n^4. In dimension d>2, the relaxation time is of order n^d, the total variation mixing time is of order n^d log n, and the uniform mixing time is of order n^{d+2}. These are the first examples we know of of finite transitive graphs with uniformly bounded degrees where these three mixing time parameters are of different
orders of magnitude.
|
Full text: PDF
Pages: 825-845
Published on: November 17, 2004
|
Bibliography
-
David Aldous and Persi Diaconis, Strong uniform times and finite
random walks, Adv. in Appl. Math. 8 (1987), no. 1,
69--97.
Math.
Review 88d:60175
-
David Aldous and James Allen Fill, Reversible markov chains and
random walks on graphs, Available at
http://www.stat.berkeley.edu/~aldous/RWG/book.html
-
David Aldous, Threshold limits for cover times, J. Theoret.
Probab. 4 (1991), no. 1, 197--211.
Math.
Review 91m:60123
-
Noam Berger, Claire Kenyon, Elchanan Mossel, and Yuval Peres,
Glauber Dynamics on Trees and Hyperbolic Graphs,
Extended abstract by Kenyon, Mossel, and Peres appeared in 42nd IEEE
Symposium on Foundations of Computer
Science (Las Vegas, NV, 2001)
arXiv:math.PR/0308284
-
Andrei Z. Broder and Anna R. Karlin, Bounds on the cover time, J.
Theoret. Probab. 2 (1989), no. 1, 101--120.
Math.
Review 90b:60079
-
Mu-Fa Chen, Trilogy of couplings and general formulas for lower bound of
spectral gap, Probability towards 2000 (New York, 1995), Lecture
Notes in
Statist. , vol. 128, Springer, New York, 1998, pp. 123--136.
Math.
Review 99h:60130
-
Amir Dembo, Yuval Peres, Jay Rosen, and Ofer Zeitouni, Cover times for
brownian motion and random walks in two dimensions, Ann. Math. (to
appear) ,
arXiv:math.PR/0107191
-
James Allen Fill and Clyde H. Schoolfield, Jr., Mixing times for Markov
chains on wreath products and related homogeneous spaces, Electron.
J.
Probab. 6 (2001), no. 11, 22 pp. (electronic).
Math.
Review 2002b:60121
-
Olle Häggström and Johan Jonasson, Rates of convergence for
lamplighter processes, Stochastic Process. Appl. 67
(1997), no. 2, 227--249.
Math.
Review 98j:60097
-
Peter Matthews, Covering problems for Brownian motion on spheres, Ann.
Probab. 16 (1988), no. 1, 189--199.
Math.
Review 89a:60190
-
Christophe Pittet and Laurent Saloff-Coste, Amenable groups,
isoperimetric profiles and random walks, Geometric group theory down
under
(Canberra, 1996) , de Gruyter, Berlin, 1999, pp. 293--316.
Math.
Review 2001d:20041
-
P. Révész, Clusters of a random walk on the plane, Ann.
Probab.
21 (1993), no. 1, 318--328.
Math.
Review 94f:60047
-
J.C. Reyes, Random walk, semi-direct products, and card shuffling,
Ph.D. thesis, Stanford University, 2002, pp. x+163.
-
Clyde H. Schoolfield, Jr., Random walks on wreath products of groups,
J.
Theoret. Probab. 15 (2002), no. 3, 667--693.
Math.
Review 2003f:60018
-
Frank Spitzer, Principles of random walks, second ed.,
Springer-Verlag,
New York, 1976, Graduate Texts in Mathematics, Vol. 34.
Math.
Review 52 #9383
MR{52 #9383}
|
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context