Anchored expansion and random walk (Q5930045)

Let \(G=(V,w)\) be an infinite weighted graph, that is a countable set \(V\) together with a symmetric function \(w: V\times V\to[0,\infty)\). The set of edges, \(E\), contains by definition all pairs of vertices (i.e., pairs of elements of \(V\)) such that the value of \(w\) for this pair is positive. The weight \(w(v)\) of a vertex \(v\in V\) is defined as the sum of all weigths over the incident edges, and the volume \(|\cdot|\) of an edge or of a vertex set is defined as the sum of the weights over the set. The edge boundary \(\partial S\) of a vertex set \(S\) is the set of edges with one vertex inside \(S\) and one outside. The Cheeger constant is the supremum over all nonnegative numbers \(i\) such that \(|\partial S|\geq i|S|\) for any \(S\subset V\), i.e., such that the strong isoperimetric inequality holds with this \(i\). Positivity of the Cheeger constant implies that the spectral radius of the Markov kernel on \(V\) associated with \(w\) is smaller than one. However, positivity of the Cheeger constant is a rather fragile property which is easily destroyed by elementary manipulations like random perturbations or geometric stretching. The notion of the anchored expansion property proves more stable. This property does not require the strong isoperimetric inequality to hold for any vertex set \(S\), but only for all such sets with possibly some exceptions provided that every vertex is contained in only finitely many connected exceptional sets \(S\). The main result of the paper is the proof that the natural random walk on \(V\) has positive speed provided that the weighted graph \(G\) has the \(w_0\)-bounded geometry for some \(w_0>0\), i.e., provided that all positive edge weights are at least 1 and all vertex weights are at most \(w_0\). (The latter property implies the anchored expansion property.) The lower bound for the speed of the walk depends on the optimal anchored expansion constant and \(w_0\) only. This result answers a question by \textit{I. Benjamini, R. Lyons} and \textit{O. Schramm} [in: Random walks and discrete potential theory. Symp. Math. 39, 56-84 (1999; Zbl 0958.05121)] in the affirmative. Furthermore, a stretched-exponential estimate of order \(1/3\) for the powers of the associated Markov kernel is derived.