Cover times for Brownian motion and random walks in two dimensions
By Amir Dembo, Yuval Peres, Jay Rosen, Ofer Zeitouni. 2001
204 citations recorded by the source corpus.
LetT (x;") denote the rst hitting time of the disc of radius " centered at x for Brownian motion on the two dimensional torus T 2 . We prove that sup x2T2T (x;")=j log"j 2 ! 2= as " ! 0. The same applies to Brownian motion on any smooth, compact connected, two- dimensional, Riemannian manifold with unit area and no boundary. As a consequence, we prove a conjecture, due to Aldous (1989), that the number of steps it takes a simple random walk to cover all points of the lattice torus Z 2 is asymptotic to 4n 2 (logn) 2 = . Determining these asymptotics is an essential step toward analyzing the fractal structure of the set of uncovered sites before coverage is complete; so far, this structure was only studied non-rigorously in the physics literature. We also establish a conjecture, due to Kesten and R ev esz, that describes the asymptotics for the number of steps needed by simple random walk in Z 2 to cover the disc of radius n.
Subfields: Geometry and Topology, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/32446dcfcb6e9f69585da6ad9e5a301333392b76
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Geometry and Topology
In Mathematical Physics
Citations in the corpus
- Extreme values for two-dimensional discrete Gaussian free field (2012, result): “An estimate in such precision was then achieved by Bramson and Zeitouni [17], by comparing the GFF with the modified branching random walk (MBRW) introduced therein.”
- The subleading order of two dimensional cover times (2014, methodology): “As in [10], we control hitting times via excursions between concentric circles at different scales, relying on an implicit tree structure.”
- Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees (2011, methodology): “For the 2D lattice, the asymptotics of the supremum of the Gaussian free field was determined in [9], and the asymptotics of cover times was established in [16].”
- A model of grid cell development through spatial exploration and spike time-dependent plasticity. (2014, unknown): “For a random walk on the 2D regular lattice Z 2 n of n × n nodes, the cover time scales as n 2 log 2 (n) (Dembo et al., 2004).”
- Late points for random walks in two dimensions (2003, methodology): “Consider the uncovered set Uε(α) = T 2 \Sε(2α(log ε)2/π) for 0 < α < 1 (in [4] we show that Uε(α) is empty if α > 1).”
- Markov Chains and Mixing Times (2008, background): “Zuckerman (1992) was the first to estimate the expected cover time to within a constant, while Dembo et al. (2004) show that E(C) ∼ 4 π n2(log n)2.”
- A new approach to strong embeddings (2007, background): “For instance, within the last ten years, the KMT embedding for the SRW played a pivotal role in the solution of a series of long-standing open questions about the simple random walk by the quartet of authors Dembo, Peres, Rosen, and Zeitouni [7, 8].”
- Gumbel fluctuations for cover times in the discrete torus (2012, background): “(For d = 1, 2, the asymptotic behaviour of E[CN ] is different; see [9] for d = 2, the case d = 1 is an exercise in classical probability theory.”
- TIGHTNESS FOR A FAMILY OF RECURSION EQUATIONS (2006, background): “Confirming a conjecture in [3], it was proved in [14] that πCn/4n(2)(logn)(2) → 1 in probability.”
- Extrema of log-correlated random variables: Principles and Examples (2016, background): “We refer the reader to [15,29] for results on this question.”
- Maximum of the Characteristic Polynomial of Random Unitary Matrices (2015, background): “Important non-Gaussian examples include cover times of the two-dimensional random walk on the torus whose leading order was determined in [27] and subleading”