# zbMATH — the first resource for mathematics

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.

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