Uniformity of the uncovered set of random walk and cutoff for lamplighter chains

DOI10.1214/10-AOP624zbMATH Open1251.60058arXiv0912.5523WikidataQ101584061 ScholiaQ101584061MaRDI QIDQ414277FDOQ414277

Authors: Jason Miller, Yuval Peres 

Publication date: 11 May 2012

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: We show that the measure on markings of $mathbf{Z}_n^d$, $dgeq3$, with elements of $0,1$ given by i.i.d. fair coin flips on the range $mathcalR$ of a random walk $X$ run until time $T$ and 0 otherwise becomes indistinguishable from the uniform measure on such markings at the threshold $T=1/2T_{mathrmcov}(mathbf{Z}_n^d)$. As a consequence of our methods, we show that the total variation mixing time of the random walk on the lamplighter graph $mathbf{Z}_{2}wrmathbf{Z}_n^d$, $dgeq3$, has a cutoff with threshold $1/2T_{mathrmcov}(mathbf{Z}_n^d)$. We give a general criterion under which both of these results hold; other examples for which this applies include bounded degree expander families, the intersection of an infinite supercritical percolation cluster with an increasing family of balls, the hypercube and the Caley graph of the symmetric group generated by transpositions. The proof also yields precise asymptotics for the decay of correlation in the uncovered set.

Full work available at URL: https://arxiv.org/abs/0912.5523

Recommendations

• Properties of uniform random walks in bounded convex bodies
• A note on the Poisson boundary of lamplighter random walks
• Cutoff phenomenon for nearest Lamperti's random walk
• Uniform mixing time for random walk on lamplighter graphs
• Cutpoints of non-homogeneous random walks
• Unbounded discrepancy of deterministic random walks on grids
• Unbounded discrepancy of deterministic random walks on grids
• The uniform asymptotics of the overshoot of a random walk with light-tailed increments
• Saturated chains of subsets and a random walk

zbMATH Keywords

random walkmixing timecover timecovered setlamplighter walk

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Ergodicity, mixing, rates of mixing (37A25)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• Shuffling Cards and Stopping Times
• Generating a random permutation with random transpositions
• Title not available (Why is that?)
• Parabolic Harnack inequality and estimates of Markov chains on graphs
• Random walks on supercritical percolation clusters
• Intersections of random walks.
• Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk
• Cover times for Brownian motion and random walks in two dimensions
• Late points for random walks in two dimensions
• Surface order large deviations for high-density percolation
• Threshold limits for cover times
• On the mixing time of a simple random walk on the super critical percolation cluster
• Covering problems for Markov chains
• Surface order large deviations for Ising, Potts and percolation models
• Rates of convergence for lamplighter processes
• Kac's moment formula and the Feynman-Kac formula for additive functionals of a Markov process
• Brownian motion on compact manifolds: cover time and late points
• Mixing times for random walks on finite lamplighter groups

Cited In (16)

• Uniform mixing time for random walk on lamplighter graphs
• Uniformity of the late points of random walk on \({\mathbb {Z}}_{n}^{d}\) for \(d \geq 3\)
• Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
• An exposition to information percolation for the Ising model
• Saturated chains of subsets and a random walk
• Cutoff for the Swendsen-Wang dynamics on the lattice
• The cutoff phenomenon for random birth and death chains
• Cutoff for the non reversible SSEP with reservoirs
• Mixing trichotomy for an Ehrenfest urn with impurities
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Cutoff for lamplighter chains on fractals
• A spectral characterization for concentration of the cover time
• Painting a graph with competing random walks
• Information percolation and cutoff for the stochastic Ising model
• On binomial sums, additive energies, and lazy random walks
• Cutoff for the asymmetric riffle shuffle

This page was built for publication: Uniformity of the uncovered set of random walk and cutoff for lamplighter chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414277)