Nash-Williams and Heat Kernel Lower Bounds, Probabilistically

Itai Benjamini The Weizmann Institute

Let G be a graph. Consider the Simple Random Walk (SRW) on G. Nash-Williams (1959) gave a classical sufficient condition for recurrence. See also Doyle-Snell (1984). The proofs of the Nash-Williams criterion involve potential theory (electrical arguments). Below, we would like to give a very short probabilistic proof, and remark about on-diagonal lower bounds.

Assume that C_{n}, n ∈ N, is a collection of nested cut sets of edges around a base vertex v.

Theorem(Nash-Williams): If ∑_{n} |C_{n}|^{−1} = ∞, then the SRW on G is recurrent.

Proof: To handle graphs admitting no bound on the degrees refine G to get G′, by dividing any edge of G into two edges. That is, add a new vertex in the “middle” of any edge of G. The SRW on G′ induces the SRW on G by deleting from the range of the SRW all the new vertices it visited. Thus it is enough to prove the Theorem for G′.

Let g(v, u) denote the green function for the refined graph, that is the expect number of visits to u of the SRW starting at v. If g(v, v) = ∞, we are done, so assume g(v, v) < ∞. Let μ_{n}(x), x ∈ C_{n}, be the harmonic measure supported on C_{n} for the SRW starting at v, where x ∈ C_{n} runs over the new vertices dividing the edges in the cut set. Denote by A_{n} the event that the SRW hits C_{n} once and returns to v.

Prob(A_{n}) ≥ g(v, v)^{−1} ∑_{x∈C_{n}} μ_{n}^{2}(x) ≥ (g(v, v)|C_{n}|)^{−1}.

The first ≥ is by conditioning on which x you hit and summing over individual paths from v to x and from x to v, the second ≥ is by Cauchy-Schwarz.

For n > m, Prob(A_{n}|A_{m}) = Prob(A_{n}). because if A_{m} happens, then once the SRW returns to v after hitting C_{m} its starts a SRW from v with no conditioning. By Borel-Cantelli infinitely many A_{n}’s occur. □

In Particular for transient graphs Π_{n<m}(1 − (g(v, v)|S_{n}|)^{−1}) (S_{n} is the sphere at distance n) is a bound on the probability of not returning to v before leaving the ball of radius m.

Assume that G is transient. Perform a continuous time SRW on G, so that the heat kernel is monotone. We can use the events A_{n} to get on-diagonal lower bound for the heat kernel. Let h_{n} be the hitting time of C_{n}. Conditioned on A_{n}, A_{n} is not likely to happen before time 2(E(h_{n}) − Var^{1/2}(h_{n})). By the monotonicity of the heat kernel we get that

P_{2(E(h_{n})−Var^{1/2}(h_{n}))}(v, v) ≥ c(Var^{1/2}(h_{n})|C_{n}|)^{−1}.

It gives, up to a constant, the right bound in Z^{d} and other examples. See Benjamini, Chavel, Feldman, (1996) for a related on diagonal lower bound.

I would like to thank Oded Schramm for useful remarks.

References

[1] Benjamini, I. Chavel, I. Feldman, E. (1996), Heat Kernel Lower Bounds on Riemannian Manifolds Using the Old Ideas of Nash, Proc. London Math. Soc. 72, 215–240.

[2] Doyle, P. G. Snell, J. L. (1984), Random Walks and Electric Networks, The Carus Math. Monographs 22 Math. Assoc. of Amer.

[3] Nash-Williams, C. St. J. A. (1959), Random Walk and Electric Currents in Networks. Proc. Cambridge Phil. Soc. 55, 181–194.