Mathematics – Probability
Scientific paper
2011-09-20
Mathematics
Probability
1 figure
Scientific paper
Suppose that $\CG$ is a finite, connected graph and $X$ is a lazy random walk on $\CG$. The lamplighter chain $X^\diamond$ associated with $X$ is the random walk on the wreath product $\CG^\diamond = \Z_2 \wr \CG$, the graph whose vertices consist of pairs $(f,x)$ where $f$ is a labeling of the vertices of $\CG$ by elements of $\Z_2$ and $x$ is a vertex in $\CG$. There is an edge between $(f,x)$ and $(g,y)$ in $\CG^\diamond$ if and only if $x$ is adjacent to $y$ in $\CG$ and $f(z) = g(z)$ for all $z \neq x,y$. In each step, $X^\diamond$ moves from a configuration $(f,x)$ by updating $x$ to $y$ using the transition rule of $X$ and then sampling both $f(x)$ and $f(y)$ according to the uniform distribution on $\Z_2$; $f(z)$ for $z \neq x,y$ remains unchanged. We give matching upper and lower bounds on the uniform mixing time of $X^\diamond$ provided $\CG$ satisfies mild hypotheses. In particular, when $\CG$ is the hypercube $\Z_2^d$, we show that the uniform mixing time of $X^\diamond$ is $\Theta(d 2^d)$. More generally, we show that when $\CG$ is a torus $\Z_n^d$ for $d \geq 3$, the uniform mixing time of $X^\diamond$ is $\Theta(d n^d)$ uniformly in $n$ and $d$. A critical ingredient for our proof is a concentration estimate for the local time of random walk in a subset of vertices.
Komjáthy Júlia
Miller Jason J.
Peres Yuval
No associations
LandOfFree
Uniform mixing time for Random Walk on Lamplighter Graphs 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 Uniform mixing time for Random Walk on Lamplighter Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uniform mixing time for Random Walk on Lamplighter Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-147102