6
C. R. Acad. Sci. Paris, t. 324, Shie I, p. 1053-1058, 1997 ProbabilitCs/Probabi/ity Theory Estimations pour les chaties de Markov Aversibles Thierry DELMOTTE UniversitC de Cergy-Pontoise, Dbpartement de mathhmatiques, 2, avenue Adolphe Chauvin, 95302 Cergy-Pontoise, France. R&urn& On donne des estimations gaussiennes supCrieureset inf&ieures pour les chaines de Markov rCversibles sur un graphe sous deux conditions gCom&riques (r6gularitC du volume et inCgalitC de Poincark). Ce resultat est d’abord obtenu pour des chaines de Markov en temps continu g&e B une in6galitC de Hamack parabolique, puis les estimations des chaines en temps discret s’en dCduisent par comparaison. Lower and upper bounds for reversible Markov chains Abstract. We give Gaussian lower and upper bounds for reversible Markov chains on a graph under two geometric assumptions (volume regularity and Poincare’ inequaliv). This is jrst proved for continuous-time Markov chains via a parabolic Harnack inequalit_v. Then, the estimates for the discrete-time Markov chains are derived by comparison. Abridged English Version Let r be a connected locally uniformly finite graph, which means (we note z - y when z and y are neighbours) 320, Vx E r, #{y 1y N x} 5 Co. We will consider symmetric weights j+, = pYz > 0 on I’ x F such that pzY > 0 + (x N y or x = y). They will be called q-elliptic if: vx,yu, X- Y* l/v I pzyI rl and x = Y * pzyI v, and q-elliptic diagonal included if: vx,yu, (x- Y or x = Y) * l/v I cllly L 77. The distance d(x, y) is the smallest number of edges of a path between two points x and y. Balls are defined by B(s, T) = {y 1 d(x, y) 5 r}. We also note V(x, ?-) the volume (cardinal) of B(x, r). We will assume two geometric conditions: Volume regularity: vx E r,vr E w+! qx, 24 5 qq~,~). Note p&sent& par Gilles PISIER. 0764~4442/97/03241053 0 AcadCmie des SciencesElsevier, Paris 1053

Estimations pour les chaînes de Markov réversibles

Embed Size (px)

Citation preview

Page 1: Estimations pour les chaînes de Markov réversibles

C. R. Acad. Sci. Paris, t. 324, Shie I, p. 1053-1058, 1997

ProbabilitCs/Probabi/ity Theory

Estimations pour les chaties de Markov Aversibles

Thierry DELMOTTE

UniversitC de Cergy-Pontoise, Dbpartement de mathhmatiques,

2, avenue Adolphe Chauvin, 95302 Cergy-Pontoise, France.

R&urn& On donne des estimations gaussiennes supCrieures et inf&ieures pour les chaines de Markov rCversibles sur un graphe sous deux conditions gCom&riques (r6gularitC du volume et inCgalitC de Poincark). Ce resultat est d’abord obtenu pour des chaines de Markov en temps continu g&e B une in6galitC de Hamack parabolique, puis les estimations des chaines en temps discret s’en dCduisent par comparaison.

Lower and upper bounds for reversible Markov chains

Abstract. We give Gaussian lower and upper bounds for reversible Markov chains on a graph under two geometric assumptions (volume regularity and Poincare’ inequaliv). This is

jrst proved for continuous-time Markov chains via a parabolic Harnack inequalit_v. Then, the estimates for the discrete-time Markov chains are derived by comparison.

Abridged English Version

Let r be a connected locally uniformly finite graph, which means (we note z - y when z and y are neighbours) 320, Vx E r, #{y 1 y N x} 5 Co. We will consider symmetric weights j+, = pYz > 0

on I’ x F such that pzY > 0 + (x N y or x = y). They will be called q-elliptic if:

vx,yu, X- Y * l/v I pzy I rl and x = Y * pzy I v,

and q-elliptic diagonal included if:

vx,yu, (x- Y or x = Y) * l/v I cllly L 77.

The distance d(x, y) is the smallest number of edges of a path between two points x and y. Balls are defined by B(s, T) = {y 1 d(x, y) 5 r}. We also note V(x, ?-) the volume (cardinal) of B(x, r).

We will assume two geometric conditions: Volume regularity:

vx E r,vr E w+! qx, 24 5 qq~,~).

Note p&sent& par Gilles PISIER.

0764~4442/97/03241053 0 AcadCmie des SciencesElsevier, Paris 1053

Page 2: Estimations pour les chaînes de Markov réversibles

T. Delmotte

Poincare inequality:

Given a weight CL, we construct a reversible Markov chain (note that every reversible Markov chain may be constructed in this way).

plJ(x: 2) = 6(x, z). P(X,Y) = $$, where n(z) = 1 /L,~, Pk,+l(X?Z) = CP(CY)Pk(Y,Z).

Y Y

The aim of this Note is to prove the conjecture proposed in [l]: assume b is n-elliptic diagonal included, then

(1) vn,x,y, d(x,y) In. * V(L) e

- 5 prL(xc!y) 5 c --cd(s,y)?

V(x,&i)e ” ’

where c! C > 0 depend only on 7, Co, Ci, and C2. For d(x, y) > n,, pn(z, y) = 0. Similar results are known for groups (see [6]) and manifolds

(see [ 111). In [l], this is proved when the volume growth is linear. The first step is a Hamack inequality for solutions of a continuous-time parabolic equation. Assume

p is v-elliptic, then there exists C = C(v, Co, Ci! Cs) > 0 such that for all ~a, s, r and every positive solution u on [s, s + ~“1 x B(za, r) of, Vt E [s; s + ~~1,

x E B(xo, r - 1) =+ n(x)&u(t, 2) = c pzy[U(t, y) - u(t>x)]> (7%)

;: Il,y[u(t: Y) - u(t,x)] - ( c CLzyMt, xc>> YEB(Q>~) Y@(Q,~)

we have

supu 5 ci$u, Q-

where Q- = [s + r2/6, s + r-*/3] x B( ~0, r/2) and Q+ = [s + 2r2/3, s + r”] x B(zo, r/2). +oO

The continuous-time Markov chain Pt(x, z) = ept c $p~( z, z) is a solution of (#a). Thus, we k=O

can use the parabolic Harnack inequality and obtain, when p is q-elliptic,

where Cp and cp depend only on 7, Ca, C, and Ca.

1054

Page 3: Estimations pour les chaînes de Markov réversibles

Estimations pour les chaines de Markov rCversibles

The second step is a comparison between p and P. Assume p is elliptic diagonal included (so that p(z,z) > a) and compute P,, and p,, with p = p - o6:

Pn(x, Y) = f+-l)n g” $kb, Y) and p,(z, y) = 2 C~cF’p~(z:, y). k=O

To compare the two sums we study ck = 7Z!CPk

(n _ /,++-l)nnk (’ s Ic 5 nh

The first technical result is:

n 2 $ and I,% - (1 - Q),~I 5 afi ==+ ck 2 C(%a).

With that, we can prove that if p is q-elliptic diagonal included,

d(z, y/)2 5 n and n 2 N =+ p,(z, y) 2 cPV(z: &z),

where Q,, C,, N > 0 depend only on q, Ca, Ci, and C2. Applying many times this lower bound for ~Z(x~y)~ 5 n, we get the one in (1) for d(z, y) 5 7~.

1. Introduction

Soit I un graphe connexe localement uniformement fini, c’est-a-dire tel que (on note IG N y quand z et y sont voisins) X0, Vx E r, #{ y 1 y N X} 5 Co. On considbre des poids symetriques ,uzy = pyz 2 0 sur I? x I? tels que pzy > 0 =3 (X N y ou x = y). On dira que p est q-elliptique si :

v’z,yu,z - y * l/v I pIy I rl et x = Y * by 2 v: et rl-elliptique diagonale in&se si :

vx; y E r, cx - y 011 x = Y) * l/q 5 I-lzy I 7. La distance d(x? y) est le plus petit nombre d’aretes d’un chemin reliant les points x et y. Les boules sont dtfinies par B(x, T-) = {y 1 d(x, y) 5 r}. E n fi n, on note V(x, r) le volume (cardinal) de B(x, T-).

On suppose verifites les deux conditions geometriques suivantes : RCgularitt du volume :

vx E r,vT E w+, v(~,~T-) 5 c~v(~,T-).

Intgalite de Poincare :

1

Oil fB = V(xo,r) x:EB(zo T) c f(x).

1055

Page 4: Estimations pour les chaînes de Markov réversibles

T. Delmotte

A partir du poids LL, on peut construire une chaine de Markov reversible :

po(.r.,i) = 6(x:, z), p(x:,y) = !52L avec n(2) = Cpsy. n ( II: )

Yk+l(:~, z) = -&(:r:. y)p(y. 2). Y Y

Le but de cette Note est de demontrer la conjecture Cnoncee dans [l] :

THI~OREME 1. - Si p est q-elliptique diagonale incluse. alors

oti c,C > 0 ne dtfpendent que de r/, Co, Cl et C2. Pour d(:c, y) > *r)., p, (z, y) = 0. Dans [I], ce resultat ttait demontre pour une croissance du volume

lidaire. Par ailleurs, ce type de resultat est connu dans le cadre des groupes (voir [6]) ou des varietes (voir [ 111). Toute chaine de Markov reversible peut &tre construite comme ci-dessus, pzy &ant son noyau par rapport a sa mesure invariante, et on peut reformuler les hypotheses d’ellipticite en hypotheses semblables sur le noyau de la chaine. Enfin, si on s’indresse a une chaine de Markov de portee simplement finie (~4,~ > 0 + d(z) y) 5 0, il est toujours possible de changer la structure

du graphe &, > 0 + :I: N y) tout en conservant la regularite du volume et une inegalite de Poincare.

2. Temps continu

La premiere etape de la demonstration du Theoreme 1 est une inegalite de Hamack parabolique.

THCORBME 2. - Si p est q-elliptique, alors il existe C = C(rl, C;b, Cl, C,) > 0 telle que pour tous x0, .s, T et toutefonction positive u sur [s: s + T-“1 x B(zo, T), solution de, V’t E [s, s + ~“1,

(#)I

i

Y

d(zo,z) = [,r] ===+- Il(s)&uit s) 2 c pry[71(t,y) - u(t,z)] - ( c pL,y)u(t!Z). yEB(.z,,r) Y@~(m.r)

on ait :

supu 2 CiJIlJIlu,

Q-

oti Q- = [s + r2/6,s + r-“/3] x B( zo3r/2) et Q+ = [s + 2r2/3,s + ?] x B(zo,r/2). La demonstration est une adaptation de la methode de Moser (voir [8]). La discretisation tree des

difficult&, c’est pourquoi nous gardons un temps continu. 11 reste la discretisation de l’espace, mais cet obstacle a deja et6 leve dans trois travaux simultanes [3], [7], [9] sans variable temps. A part des problemes techniques de decoupage de l’espace, il suffit d’adapter les calculs de differentiation pour reprendre la demonstration de [ll] sur les varietes (voir [5]).

La chaine de Markov en temps continu pt(z:, z) = e-t E $p~(c, 2) est solution de (#b). “=O

L’inCgalitC de Harnack parabolique en donne ainsi les estimattons suivantes :

LEMME 3. - Si p est q-elliptique, alors :

vz,y,t. Pt(2,y) I CP V(z, j/z) ’

1056

Page 5: Estimations pour les chaînes de Markov réversibles

Estimations pour les chaines de Markov r6versibles

02 C, et cp ne dkpendent que de 7, Co, Cl et C2. Les deux premiers rksultats s’obtiennent en appliquant 1’inCgalitC A des fonctions pt(z, ~0). Pour

le troisikme, on fait en plus apparaitre une fonction de d(z, y) et t (voir [2]) qui se rCduit au -cpd(T,y)?

terme e t si d(z, y) 5 t, soit par une mkthode de perturbation du semi-groupe due ?I E. B. Davies (thtort%me 6.3 de [lo]), soit par un principe du maximum intCgrC (voir [4]). La condition d(z, y) < i est essentielle et on peut comprendre pourquoi la fonction introduite dans [2] a un comportement diffkent pour les petites valeurs de t en observant que, z et y ktant fix&, P,(z,y) N pd(z.y)(x,y)td(z.y)/d(x.y)! quand t + 0.

3. Temps discret

La deuxikme &ape consiste B comparer p et P. Si p est elliptique diagonale incluse (de sorte que p(z, CT) 2 a), on peut mettre P, et p, sous forme de sommes de p = p - aS.

et p,(z, y) = 2 Ci@n-kpk(z, y). k=O

Pour les comparer, on etudie les ck = 7LbIPk

’ (n- ~)!e(ct-l)nnk (' 5 ' 5 n)'

LEMME 4.

Une premikre condquence immkdiate est :

LEMME 5. - Si Vx;p(x!x) > CY > 0, alors Vx, y, ‘n, p,(x,y) 2 C(a)P,(z,y). En utilisant les estimations en temps continu, on dCmontre ainsi :

LEMME 6. - Si p est rl-elliptique diagonale incluse (de sorte que V’s, p(x, x) 2 P), alors :

d(x, Y)~ 5 71 et 7~ L N ==+ P~.(x, Y) 2 V(x:j;;) 1

02 I+, C,, N > 0 ne dependent que de 7, Co, Cl et C2. L’estimation supkrieure dkcoule directement du Lemme 5, elle est utiliske sous cette forme simple

dans la dkmonstration de l’estimation infkieure. On Ccrit en effet /I? = 2cu et on applique l’estimation superieure 2 p’ = p/( 1 - a), ce qui donne :

@k(z, y) 5 ‘(’ - Q)k. V(x: VG)

1057

Page 6: Estimations pour les chaînes de Markov réversibles

1. Delmotte

A l’aide de cette inegalite, on demontre que :

kf't > 0; 3a, c a@k(s, Y) 5 tV(z, 6). IL-(1-a)nl>afi

En choisissant t = cp/2, on parvient ainsi a transmettre I’estimation inferieure de P a p. La majoration du Theo&me 1 s’obtient en utilisant la troisieme assertion du Lemme 3. Pour

dtmontrer la minoration du Theo&me 1, on applique plusieurs fois l’estimation inferieure precedente. Dans un travail ulttrieur (voir [5]), on vtrifie que ces estimations gaussiennes impliquent une version

de l’inegalite de Hamack en temps discret, puis que celle-ci implique les conditions de regularit du volume et d’inegalite de Poincart. Finalement, l’inegalite de Harnack parabolique sur les graphes Cquivaut a la conjonction de la regular&Z du volume et de l’inegalite de Poincare, ce qui est l’analogue discret des resultats de L. Saloff-Coste sur les varietes (voir [l 11).

Note remise le 3 fhier 1997, acceptee le 17 mars 1997.

Rbfkrences bibliographiques

[I] Coulhon T. et Saloff-Coste L., 1993. Minorations pour les chaines de Markov unidimensionnelles. Probab. Theory R&II. Fields 97. p. 423-431.

[2] Davies E. B., 1993. Large deviations for heat kernels on graphs. J. London Math. Sot. (2). 47, p. 65-72. [3] Delmotte T., 1997. Intgalite de Hamack elliptique sur les graphes. Cokquium Mafhemaficum, 72. 1, p. 19-37. [4] Grigor’yan A. Gaussian upper bounds for the heat kernel on arbitrary manifolds. A paraitre dam J. Difewnrial Geometry. [5] Delmotte T. Parabolic Hamack inequality and estimates of Markov chains on graphs. Prtipublicarian.

[6] Hehisch W. et Saloff-Coste L., 1993. Gaussian estimates for Markov chains and random walks on groups. Ann. Probab. 21, (2), p. 673-709.

[7] Holopainen I. et Soardi P. M., 1997. Strong Liouville theorem for p-harmonic functions on graphs. Ann. Acad. Sci.

Fennicae Math.. 22. p. 205-226. [8] Moser J., 1964. A Harnack Inequality for Parabolic Differential Equations. Comm. Pure A,@. Mufh., 17, p. 101-134. [9] Rigoli M., Salvatori M. et Vignati M. A global Harnack inequality on graphs and some related consequences.

Pr&publication. [IO] Saloff-Coste L., 1992. Uniformly elliptic operators on Riemannian manifolds. J. Diferential Geometry 36, p. 417-450.

[ 1 I] Saloff-Coste L., 1995. Parabolic Harnack inequality for divergence form second order differential operators. Potential analysis. 4, 4, p. 429-467.

1058