TY - JOUR

T1 - Poisson approximation for non-backtracking random walks

AU - Alon, Noga

AU - Lubetzky, Eyal

N1 - Funding Information:
∗ Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation, by an ERC advanced grant and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. ∗∗ Research partially supported by a Charles Clore Foundation Fellowship. Received August 30, 2007

PY - 2009/11

Y1 - 2009/11

N2 - Random walks on expander graphs were thoroughly studied, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the vertices of a graph. The authors of [3] studied non-backtracking random walks on regular graphs, and showed that their mixing rate may be up to twice as fast as that of the simple random walk. As an application, they showed that the maximal number of visits to a vertex, made by a non-backtracking random walk of length n on a high-girth n-vertex regular expander, is typically (1+o(1)))log n/log log n, as in the case of the balls and bins experiment. They further asked whether one can establish the precise distribution of the visits such a walk makes. In this work, we answer the above question by combining a generalized form of Brun's sieve with some extensions of the ideas in [3]. Let Nt denote the number of vertices visited precisely t times by a non-backtracking random walk of length n on a regular n-vertex expander of fixed degree and girth g. We prove that if g = ω(1), then for any fixed t, Nt/n is typically 1/et! + o(1). Furthermore, if g = Ω(log log n), then Nt/n is typically 1+o(1)/et! niformly on all t ≤ (1 - o(1)) log n/log log n and 0 for all t ≥ (1 + o(1)) log n/log log n. In particular, we obtain the above result on the typical maximal number of visits to a single vertex, with an improved threshold window. The essence of the proof lies in showing that variables counting the number of visits to a set of sufficiently distant vertices are asymptotically independent Poisson variables.

AB - Random walks on expander graphs were thoroughly studied, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the vertices of a graph. The authors of [3] studied non-backtracking random walks on regular graphs, and showed that their mixing rate may be up to twice as fast as that of the simple random walk. As an application, they showed that the maximal number of visits to a vertex, made by a non-backtracking random walk of length n on a high-girth n-vertex regular expander, is typically (1+o(1)))log n/log log n, as in the case of the balls and bins experiment. They further asked whether one can establish the precise distribution of the visits such a walk makes. In this work, we answer the above question by combining a generalized form of Brun's sieve with some extensions of the ideas in [3]. Let Nt denote the number of vertices visited precisely t times by a non-backtracking random walk of length n on a regular n-vertex expander of fixed degree and girth g. We prove that if g = ω(1), then for any fixed t, Nt/n is typically 1/et! + o(1). Furthermore, if g = Ω(log log n), then Nt/n is typically 1+o(1)/et! niformly on all t ≤ (1 - o(1)) log n/log log n and 0 for all t ≥ (1 + o(1)) log n/log log n. In particular, we obtain the above result on the typical maximal number of visits to a single vertex, with an improved threshold window. The essence of the proof lies in showing that variables counting the number of visits to a set of sufficiently distant vertices are asymptotically independent Poisson variables.

UR - http://www.scopus.com/inward/record.url?scp=74249104239&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=74249104239&partnerID=8YFLogxK

U2 - 10.1007/s11856-009-0112-z

DO - 10.1007/s11856-009-0112-z

M3 - Article

AN - SCOPUS:74249104239

VL - 174

SP - 227

EP - 252

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

SN - 0021-2172

IS - 1

ER -