Parabolic Harnack inequality and estimates of Markov chains on graphs. (English) Zbl 0922.60060

Let \(\Gamma\) be a graph and let \(p_n(x,y)\) be the kernel of the standard random walk on \(\Gamma\). The author is interested in finding conditions under which one has the following Gaussian estimate: \[ {c\over V(x,\sqrt{n})}e^{-Cd(x,y)^{2}/n}\leq p_n(x,y)\leq {C\over V(x,\sqrt{n})}e^{-cd(x,y)^{2}/n} \] for some constants \(c\) and \(C\), where \(V(x,n)\) is the cardinality of the ball of center \(x\) and radius \(n\), with the assumptions that \(d(x,y)\leq n\) and that all the vertices of \(\Gamma\) are loops. The author proves that the inequalities hold for graphs of polynomial growth under an isoperimetric assumption such as Poincaré inequality. This proves a conjecture made by T. Coulhon and L. Saloff-Coste [Probab. Theory Relat. Fields 97, No. 3, 423-431 (1993; Zbl 0792.60063)]. The author proves in fact a characterization of the parabolic Harnack inequality. The result is a discrete counterpart of a result of L. Saloff-Coste [Potential Anal. 4, No. 4, 429-467 (1995; Zbl 0840.31006)]. The author gives, as an application of the Harnack inequality, a new proof of the theorem of J. Nash on the Hölder regularity for solutions of the elliptic/parabolic equation.


60G50 Sums of independent random variables; random walks
31C20 Discrete potential theory
60J45 Probabilistic potential theory
Full Text: DOI EuDML