zbMATH — the first resource for mathematics

Giant component and vacant set for random walk on a discrete torus. (English) Zbl 1141.60057
The authors consider symmetric nearest neighbour random walk \(X\) on the \(d\)-dimensional (\(d\geq3\)) integer lattice torus \(E:=\big(\mathbb{Z}/(N\mathbb{Z})\big)^d\) of side-length \(N\). It is well-known that the cover time is of order \(N^d\log N\) if \(d\geq3\). In this paper, Benjamini and Sznitman investigate the percolative structure of the set \(V\subset E\) of sites that are not visited by \(X\) up to time \(uN^d\), where \(u>0\) is assumed to be small. First of all they show (Corollary 4.5) that there are constants \(c=c(d)\) and \(c'=c'(d)\) such that \[ \lim_{N\to\infty}\mathbb{P}[e^{-cu}\leq \# V/N^d\leq e^{-c'u}]=1. \] In Theorem 1.2 it is shown for \(d\geq 4\) and for any \(\beta\in(0,1)\) and \(K>0\) that if \(u>0\) is small enough, then with probability tending to one (as \(N\to\infty\)), with probability tending to one, every point \(x\in E\) is in distance at most \(N^\beta\) to some point in \(V\) that is in a straight line segment in \(V\) of length at least \(K\log N\). The next results hold for \(d\) larger than some \(d_0\) (and which the reviewer computed to be actually \(d_0=123\)). In Corollary 2.6 it is shown for \(d\geq d_0\) that if \(u>0\) is small enough, then with probability tending to one (as \(N\to\infty\)) there is a unique connected component \(O\subset V\) that contains straight line segments (in any of the \(d\) directions) of size \(c_0\log N\) (where \(c_0\) is a dimension dependent constant). Moreover, in Corollary 4.6 it is shown that for \(d\geq d_0\), for any \(\gamma\in(0,1)\) and \(u=u(\gamma)>0\) sufficiently small, with probability tending to one, the cardinality of \(O\) is a least \(\gamma N^d\). That is, \(O\) contains a substantial fraction (depending on \(u\)) of points of \(E\). However, it remains open if \(V\) contains more connected components of substantial size.

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60G50 Sums of independent random variables; random walks
82B41 Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics
Full Text: DOI arXiv
[1] Aldous, D.: On the time taken by random walks on finite groups to visit every state. Z. Wahrsch. Verw. Gebiete 62 , 361-374 (1983) · Zbl 0488.60011 · doi:10.1007/BF00535260
[2] Aldous, D., Fill, J.: Reversible Markov chains and random walks on graphs. http://www.stat. berkeley.edu/√£ldous/RWG/book.html.
[3] Alon, N., Benjamini, I., Stacey, A.: Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 , 1727-1745 (2004) · Zbl 1046.05071 · doi:10.1214/009117904000000414 · arxiv:math/0207112
[4] Brummelhuis, M. J. A. M., Hilhorst, M. J.: Covering a finite lattice by a random walk. Phys. A 176 , 387-408 (1991)
[5] Dembo, A., Peres, Y., Rosen, J., Zeitouni, O.: Cover times for Brownian motion and random walks in two dimensions. Ann. of Math. 160 , 433-464 (2004) · Zbl 1068.60018 · doi:10.4007/annals.2004.160.433 · euclid:annm/1111770725 · arxiv:math/0107191
[6] Dembo, A., Peres, Y., Rosen, J., Zeitouni, O.: Late points for random walks in two dimensions. Ann. Probab. 34 , 219-263 (2006) · Zbl 1100.60057 · doi:10.1214/009117905000000387 · arxiv:math/0303102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.