Mixing times for random walks on finite lamplighter groups

Details Mixing times for random walks on finite lamplighter groups Mixing times for random walks on finite lamplighter groups

2004-04-08

arxiv.org/abs/math/0404190v1

Mathematics

Probability

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Mixing times for random walks on finite lamplighter groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Mixing times for random walks on finite lamplighter groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mixing times for random walks on finite lamplighter groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-158724