Chaînes de Markov : Concepts et Applications
Chaînes de Markov : Concepts et Applications
Jean Brard
Avertissement
Ces notes sont en cours d'laboration. Il se peut donc qu'y subsistent un certain nombre d'erreurs, d'incohrences, et/ou de passages inachevs.
7
9 12 17 19 21 23 26 26 27 35 36 37 38 38 41
45
45 45 46 48 49
63
64 65
4 3.1.2 Des martingales . . . . . . . . . . . . . . . . . . 3.1.3 Questions d'unicit . . . . . . . . . . . . . . . . 3.1.4 Quelques exemples classiques . . . . . . . . . . 3.2 Mesures et lois invariantes . . . . . . . . . . . . . . . . 3.2.1 Renvers dans le temps d'un noyau par rapport invariante . . . . . . . . . . . . . . . . . . . . . 3.2.2 Mesures invariantes et rcurrence/transience . . 3.2.3 Rversibilit . . . . . . . . . . . . . . . . . . . . 3.3 Exercices supplmentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . une mesure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 70 73 75 77 79 85 87
. . . . .
. . . . .
. . . . .
93
93 94 95 98 98
Xn
5.1 Plan de cette partie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Preuve par renouvellement . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Preuve par couplage et distance en variation totale . . . . . . . . . . 5.3.1 Distance en variation totale entre deux mesures de probabilit et couplage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Approche par couplage pour la convergence des chanes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Temps stationnaires forts et distance en sparation . . . . . . . . . . 5.4.1 Deux exemples de temps stationnaires forts . . . . . . . . . . 5.5 Approche spectrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.1 Approche spectrale dans le cas o S est ni . . . . . . . . . . 5.6 Thorie L2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6.1 Gnralits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6.2 Formes de Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . 5.6.3 Le cas rversible . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Entropie relative . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
101
108 113 117 117 118 120 120 121 123 125
6 Une premire approche quantitative de l'ergodicit pour la distance en variation totale 129
6.1 Ergodicit de degr 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.2 Ergodicit gomtrique . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.2.1 Ergodicit uniforme . . . . . . . . . . . . . . . . . . . . . . . 140
7.1 Approche par renouvellement . . . . . . . . . . . . . . . . . . . . . . 146 7.2 Approche par les martingales et l'quation de Poisson . . . . . . . . 158 7.3 Calculs asymptotiques de variance . . . . . . . . . . . . . . . . . . . 163 8.1 Un critre de non-rcurrence positive. . . 8.2 Un critre de transience . . . . . . . . . . 8.3 Un critre de rcurrence . . . . . . . . . . 8.4 Un critre de rcurrence positive . . . . . 8.4.1 Un critre d'ergodicit gomtrique 9.1 Intrt des mthodes MCMC . . 9.2 Qualit de l'approximation . . . . 9.3 Deux exemples . . . . . . . . . . 9.3.1 Algorithme de Metropolis 9.3.2 Echantillonneur de Gibbs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
145
8 Critres de drive
167
175
175 176 177 177 177
10 Appendice : Mmento sur les martingales 11 Appendice : Mmento sur la thorie ergodique
179 181
Introduction
Les suites de variables alatoires prsentant une structure de dpendance markovienne sont probablement, aprs les suites de variables alatoires i.i.d., l'une des catgories d'objets les plus tudies en probabilits. Elles jouent un grand rle la fois dans la thorie et dans les applications, et ont fait l'objet de dveloppements considrables depuis leur introduction par A. A. Markov au dbut du vingtime sicle. Dans ce cours, nous ne pouvons bien entendu prsenter qu'une petite slection de rsultats sur le sujet. Ces notes traitent principalement des chanes temps et espace discret, et, parmi les questions abordes, mentionnons : la proprit de Markov et ses diverses extensions, les proprits de rcurrence/transience, le problme des mesures invariantes, le comportement asymptotique de la loi d'une chane de Markov ainsi que des fonctions additives de ses trajectoires, les mthodes de Monte-Carlo par chanes de Markov. Un large ventail de techniques (couplage, rgnration, tude du semigroupe, rseaux lectriques) est prsent pour l'tude de ces questions. La lecture de ces notes, issues d'un cours de 2me anne de Master, suppose une connaissance pralable de la thorie des probabilits discrtes, et, pour certains points, fait appel la thorie gnrale de la mesure, aux proprits des martingales et des rudiments de thorie ergodique1 . De nombreux ouvrages sur le sujet existent (nous avons par exemple utilis l'ouvrage [7] pour la prparation de ces notes), consacrs aux chanes de Markov en gnral, ou certains aspects plus spcialiss de la question. En gnral, des rfrences sont donnes au fur et mesure du texte pour permettre un approfondissement des sujets prsents.
Les proprits et dnitions qui nous seront utiles concernant les martingales et la thorie ergodique sont rappeles en appendice.
Chapitre 1
Proprit de Markov
pi (xi , xi+1 ).
(1.1)
On dit alors que (Xn )n0 est une chane de Markov de loi initiale et de famille de noyaux de transition (pn (, ))n0 . On vrie sur la dnition ci-dessus que la
10 loi de la suite (Xn )n0 est compltement dtermine par la donne de la loi initiale et de la famille de noyaux de transition. On peut donner une dnition similaire pour une chane de longueur nie : tant donn m 1, une suite de variables X0 , . . . , Xm valeurs dans S est une chane de Markov de loi initiale et de de famille de noyaux de transition (pn (, ))0nm1 si (1.1) est satisfaite pour tout n m.
Exercice 1 Montrer que si la proprit (1.1) est vrie pour un entier donn n 1,
elle est automatiquement vrie pour tout m n.
On dduit de cette dnition la proprit fondamentale suivante, appele proprit de Markov.
(Xn )n0 sur un ensemble ni ou dnombrable S , dnie sur un espace de probabilit (, F, P ), pour tous m 0 et n m + 1, et toute suite x0 , . . . , xn d'lments de S telle que P (X0:m = x0:m ) > 0, P (Xm+1:n = xm+1:n |X0:m = x0:m ) = P (Xm+1:n = xm+1:n |Xm = xm ).
On nonce souvent cette proprit de manire informelle en disant que, pour une chane de Markov (o l'indice m est interprt comme un temps), les tats futurs de la chane ne dpendent de ses tats passs que par l'intermdiaire de l'tat prsent. La preuve rsulte de (1.1) par un calcul immdiat conduisant l'identit suivante :
P (Xm+1:n = xm+1:n |X0:n = x0:n ) = pm (xm , xm+1 ) pn1 (xn1 , xn ).
(1.2)
On note que l'expression ci-dessus n'est autre que la probabilit pour que les n m premiers pas d'une chane de Markov de loi initiale xm et de famille de noyaux de transition (pm+k )k0 soient donns par xm+1 , . . . , xn . Dit de manire informelle : Sachant toutes les valeurs passes jusqu'au temps n (y compris la valeur de Xn ), la chane se comporte partir du temps n comme une nouvelle chane de Markov, issue de Xn . On dduit de ce qui prcde le lien suivant entre la loi et les noyaux de transition pi (, ) intervenant dans la dnition que nous avons donne d'une chane de Markov :
= loi de X0 ,
(1.3)
(1.4)
Observons que la donne de (Xn )n0 n'impose aucune contrainte sur la valeur de pn (x, ) lorsque P (Xn = x) = 0. Il est cependant plus commode de supposer a priori dans la dnition d'une chane de Markov que l'on a aaire un noyau de transition.
Proprit de Markov
11
Inversement, si une suite de variables alatoires (Xn )n0 vrie la proprit nonce dans la proposition 1, on vrie que, en dnissant et pn (, ) par les identits (1.3) et (1.4) ci-dessus, et en dnissant arbitrairement pn (x, ) lorsque P (Xn = x) = 0, la dnition d'une chane de Markov est satisfaite. Autrement dit, la proprit de Markov caractrise les chanes de Markov.
Exercice 2 Vrier que (Xn )n0 est une chane de Markov si et seulement si, pour
tous n 0, il existe une fonction fn dnie sur S S telle que, pour tous x0 , . . . , xn S tels que P (X0 = x0 , . . . , Xn = xn ) > 0,
P (Xn+1 = y|X0:n = x0:n ) = fn (xn , y) X0 , . . . , Xn valeurs dans un ensemble ni ou dnombrable S et dnies sur (, F, P ). Supposons qu'il existe des fonctions g0 , . . . , gn1 dnies sur S S telles que P (X0:n = x0:n ) = n1 i=0 gi (xi , xi+1 ). Montrer que X0 , . . . , Xn est une chane de Markov sur S . Prciser
Une manire plus sophistique, mais quivalente, d'noncer la proprit de Markov, consiste faire appel la notion de tribu et de probabilit conditionnelle une tribu. Etant donne une variable alatoire Z dnie sur (, F), nous utiliserons la notation classique (Z) pour la sous-tribu de F engendre par Z . Plus particulirement, pour tout n 0, nous utiliserons la notation Fn := (X0 , . . . , Xn ). On peut alors reformuler la proprit de Markov de la manire suivante.
(Xn )n0 sur un ensemble ni ou dnombrable S , dnie sur un espace de probabilit (, F, P ), pour tous m 0 et n m + 1, et toute suite xm+1 , . . . , xn d'lments de S , l'galit suivante a lieu P presque srement : P (Xm+1:n = xm+1:n |Fm ) = P (Xm+1:n = xm+1:n |(Xm )).
Exercice 4 Vrier l'quivalence entre les proprits nonces dans les propositions 1 et 2.
Dans certains exemples, on peut tre amen tudier la validit de la proprit nonce dans la proposition 2 en remplaant la ltration (Fn )n0 par une plus grosse. Plus prcisment, supposons donne une famille de sous-tribus (Gm )m0 telle que, pour tous n m, Gm Gn , et vriant Fm Gm pour tout m 0. On dit que (Xn )n0 vrie la proprit de Markov par rapport (Gm )m0 si la proprit nonce dans la proposition 2 est valable lorsque l'on remplace Fn par Gn .
12
Exercice 6 Supposons donne en plus de (Xn )n0 une famille de variables alatoires
(Yn )n0 valeurs dans un ensemble ni ou dnombrable (et dnies sur (, F, P )), et que (Xn )n0 vrie la proprit de Markov par rapport la famille de tribus dnies par Gn := (Fn , Y0 , . . . , Yn ). Donner une formulation de la proprit de Markov
Lorsque les noyaux de transition associs aux dirents pas de la chane sont identiques, c'est--dire qu'il existe un noyau p telle que pn = p pour tout n, on dit que l'on a aaire une chane de Markov homogne (ou parfois, mais cette terminologie n'est pas trs heureuse, de chane de Markov probabilits de transition stationnaires). Dans ce cours, nous considrerons principalement des chanes de Markov homognes, et cette proprit d'homognit sera sous-entendue la plupart du temps. Quand nous aurons aaire des chanes pour lesquelles cette proprit est en dfaut, nous le spcierons en parlant de chane de Markov inhomogne.
1.2 Exemples
Exercice 7 Vrier qu'une suite de variables alatoires i.i.d. forme une chane de
Markov. Quels sont la loi initiale et le noyau de transition correspondants ?
(Zn )n0 dnies sur (, F, P ), posons, pour tout n, Xn := (Z0 , . . . , Zn ). Montrer que (Xn )n 0 est une
L'exercice ci-dessus montre que toute suite de variables alatoires discrtes peut en fait tre transforme en une chane de Markov. Cependant, la chane ainsi obtenue possde souvent une structure trop complexe pour que l'on puisse utilement analyser son comportement, ce qui limite quelque peu la porte de la remarque.
1) Considrons une suite de i.i.d. de fonctions alatoires (fi )i0 de S dans S (S S tant muni de la tribu produit), dnies sur un espace de probabilit (, F, P ). Vrier que, pour tout x S , la suite de variables alatoires dnie par X0 (x) := x et, pour n 1, Xn (x) := fn1 f0 (x), est une chane de Markov homogne dont les probabilits de transition sont donnes par p(x, y) = P (f (x) = y). 2) Est-il ncessaire que les fonctions alatoires que l'on compose possdent soient identiquement distribues pour que l'on obtienne une chane de Markov ? Mme question avec l'indpendance de ces fonctions entre elles ?
Proprit de Markov
13
3) Inversement, montrer que, tant donne un noyau de transition p(, ) sur S S , on peut toujours dnir une suite de fonctions telle que (Xn (x))n0 soit une chane de Markov initialise en x et possdant p pour noyau de transition. Indication : on peut par exemple chercher crire fi (x) sous la forme f (x, Ui ), la suite (Ui )i0 tant i.i.d. et de loi uniforme sur [0, 1]. Discuter de la pertinence de ce rsultat pour la simulation.
D'aprs l'exercice ci-dessus, on voit que la notion de chane de Markov apparat comme la gnralisation stochastique la plus simple d'un systme dynamique discret : au lieu de composer de manire rpte une fonction donne avec elle-mme, on compose des fonctions alatoires indpendantes possdant toujours la mme loi. Une proprit intressante de ce type de construction par fonctions itres est de dnir un ot alatoire, et, plus spciquement, d'autoriser la dnition simultane, sur le mme espace de probabilit, de plusieurs trajectoires d'une chane de Markov en partant d'tats initiaux dirents. Nous reviendrons sur ce point lorsque nous discuterons de manire plus gnrale les liens entre chanes de Markov et couplage.
G = (V, E) ni ou dnombrable (V dsigne l'ensemble de sommets, E l'ensemble des artes orientes, i.e. un sous-ensemble de V V ), et une application w : E R+ telle que, pour tout v1 V , 0 < v2 ; (v1 ,v2 )E w(v1 , v2 ) < +, la marche alatoire sur le graphe G associe aux poids w est dnie par une loi initiale arbitraire, et les probabilits de transition suivantes : pour tous v1 , v2 V tels que (v1 , v2 ) E , p(v1 , v2 ) := w(v1 , v2 )
v3 ; (v1 ,v3 )E
Exercice 10 (Marche alatoire sur un graphe orient) Etant donn un graphe orient
1 w(v1 , v3 ) .
1) Vrier que l'on dnit bien ainsi un noyau de transition. 2) Vrier que toute chane de Markov utilisant le mme noyau pour chacun de ses pas (ce que nous appellerons une chane de Markov homogne), peut se reprsenter sous cette forme.
non-orient G = (V, E) ni ou dnombrable (V dsigne l'ensemble de sommets, E l'ensemble des artes non-orientes, i.e. un sous-ensemble de V V quotient par la relation d'quivalence identiant (x, y) et (y, x) ; nous noterons {x, y} l'arte nonoriente ayant x et y pour extrmits), et une application w : E R+ telle que, pour tout v V , pour tout v1 V , 0 < v2 ; {v1 ,v2 }E w({v1 , v2 }) < +, la marche alatoire sur le graphe G associe aux poids w est dnie par une loi initiale arbitraire,
14
1 w({v1 , v3 }) .
1) Vrier que l'on dnit bien ainsi un noyau de transition. 2) Obtient-on une notion dirente en considrant une pondration aecte aux sommets plutt qu'aux artes ? 3) Prciser en quoi cette notion dire de celle dnie dans l'exercice prcdent.
Un exemple particulirement simple de marche alatoire est celui o toutes les artes du graphe se voient accorder un poids gal (ce qui suppose qu'un sommet ne puisse tre reli qu' un nombre ni d'autres sommets). On parle alors souvent de "la" marche alatoire sur le graphe sans prciser les poids.
Exercice 12 (Marche alatoire sur un groupe) Etant donn un goupe G ni ou dnombrable, et une famille de variables alatoires (gi )i0 i.i.d. valeurs dans G, on dnit, pour toute variable alatoire X0 valeur dans G, les variables alatoires Xi pour i 1 par Xi := gi1 g0 X0 . 1) Montrer que la suite (Xi )i0 est une chane de Markov sur G. Quel est le noyau de transition correspondant ? Mme question en dnissant Xi := X0 g0 gi1 . 2) Cette chane de Markov est-elle ncessairement une marche alatoire sur un graphe non-orient au sens de l'exercice prcdent ? 3) Inversement une marche alatoire dnie sur le graphe de Cayley de G (associ un jeu donn de gnrateurs) non-orient, est elle toujours une marche alatoire sur le groupe au sens du prsent exercice ?
Un exemple canonique de marche alatoire sur un groupe est la marche alatoire simple symtrique sur Zd , dnie par P (g0 = ei ) := 1/(2d), o (e1 , . . . , ed ) dsigne la base canonique de Zd et B := {+e1 , . . . , +ed , e1 , . . . , ed }.
M l'ensemble des mesures de probabilit sur B := {+e1 , . . . , +ed , e1 , . . . , ed }. d Pour tout lment w = (wx )xZd MZ (appel environnement), on dnit un noyau de transition p(w)(, ) sur Zd par p(w)(x, x ei ) = wx (ei ), pour 1 i d. A prsent, on considre une famille de variables alatoires i.i.d. T = (Tx )xZd valeurs dans M, et une suite de variables alatoires (Xn )n0 valeurs dans Zd telle que, conditionnellement T, (Xn )n0 est une chane de Markov admettant p(T) pour famille de noyaux de transition, initialise en X0 = 0. 1) Montrer que (Xn )n0 n'est pas une chane de Markov en gnral.
Proprit de Markov
15
2) Montrer que la suite de variables alatoires dnie par Tn := (TXn +x )xZd est une chane de Markov. On appelle (Tn )n0 l'environnement vu de la marche. (Pour simplier les problmes de mesurabilit, on pourra supposer que Tx ne peut prendre qu'un nombre ni de valeurs distinctes.)
G = (V, E) un graphe (nous donnons ici le cas d'un graphe orient, il sut de changer les (v1 , v2 ) en {v1 , v2 } dans les formules ci-dessous pour obtenir le cas non-orient), ni ou dnombrable, 0 un paramtre x, et w0 : E R+ un jeu de poids comme
dans l'exercice 11. On spcie par rcurrence la loi d'une suite de variables alatoires (Xn )n0 valeurs dans V en supposant la loi de X0 donne et en posant, pour toute arte e E ,
n1 i=0
wn (e) := w0 +
et
1
wn (e)
1) Montrer que (Xn )n0 n'est pas une chane de Markov en gnral. 2) Montrer qu'en revanche la suite (Xn , wn )n0 est une chane de Markov. suivant : la premire gnration (numrote 0) est constitue d'un nombre donn p 1 d'individus. A chaque gnration, chaque individu appartenant cette gnration donne lieu un nombre alatoire d'enfants, qui appartiennent la gnration suivante, la rgle tant que les nombres d'enfants obtenus par les dirents individus aux cours des direntes gnrations sont des variables alatoires i.i.d. Montrer que la suite de variables alatoires (Xn )n0 dnie par Xn :=nombre d'individus prsents dans la gnration numro n, constitue une chane de Markov.
total de N 1 particules, divis en deux cavits, numrotes 1 et 2, qui communiquent. A chaque pas de temps, une particule parmi les N est choisie uniformment au hasard, et passe de la cavit o elle se trouve l'autre. Montrer que, en dnissant Xn :=nombre de particules dans la cavit 1, la suite (Xn )n1 forme une chane de Markov. Quel est son noyau de transition ? noyau de transition p(, ) sur S , et une fonction f S R , un entier M 1 et un + entier m 1. on dnit un noyau de transition q sur S M de la manire suivante.
16
Pour tout 1 i M , on fabrique indpendamment m ralisations indpendantes Yij , 1 j m de la loi p(xi , ). Ensuite, on eectue M tirages indpendants selon la loi de probabilit
i,j
f (Yij )Y j
i
j i,j f (Yi )
et l'on note (Z1 , . . . , ZM ) le M uplet ainsi obtenu. Le noyau de transition q est alors dni par q((x1 , . . . , xM ), ) := loi de (Z1 , . . . , ZM ). 1) Donner une expression plus explicite du noyau q . 2) On appelle q un noyau de mutation-slection. Comment expliquer ce terme ? Proposer d'autres types de slection bass sur la fonction f .
(x)(y),
o x y signie que x et y sont voisins au sens du graphe Zd , i.e. d |xi yi | = 1. i=1 On dnit ensuite un mcanisme de transition sur S de la manire suivante : on choisit un tat initial 0 S arbitraire, et la rgle pour passer de n n+1 est la suivante : on choisit x {M, . . . , 0, . . . , +M }d selon la loi uniforme, et l'on dnit x x x x n par n (y) := n (y) pour y = x, et n (x) := n (x). Si H(n ) H(n ), le nouvel x x tat n+1 est n . Dans le cas contraire, le nouvel tat est n avec une probabilit gale x exp((H(n ) H(n ))), et reste gal sinon, o > 0 est un paramtre x.. 1) Vrier que l'on dnit ainsi une chane de Markov. 2) Comment se comporte la chane lorsque 0 et + ?
La chane de Markov dnie dans l'exercice ci-dessus fournit un modle trs simpli de la dynamique d'un matriau ferromagntique, dans lequel des spins qui peuvent valoir +1 ou 1 sont disposs aux sommets d'un rseau rgulier, l'nergie attache une conguration de spins favorisant l'alignement de spins voisins. Elle fournit galement un moyen de simulation pour le comportement l'quilibre de ce type de systme, comme nous le verrons ultrieurement, dans un cadre plus gnral.
S l'ensemble des pages ouaibe existant un instant donn. Soit N := card S . Pour une page x S donne, soit kx le nombre de pages vers lesquelles x contient des liens. Si x contient un lien vers y , on pose p(x, y) :=
Proprit de Markov
17
/kx + (1 )/N , tandis que, si x ne contient pas de lien vers y , on pose p(x, y) = (1 )/N . 1) Montrer que l'on dnit bien ainsi un noyau de transition sur S .
(Xn )n0 sur un ensemble ni ou dnombrable S , dnie sur un espace de probabilit (, F, P ), pour tout m 0, tout x0 , . . . , xm tel que P(X0:m = x0:m ) > 0, et tout A HN , P (Xm+1: A|X0:m = x0:m ) = P (Xm+1: A|Xm = xm ).
pi (xi , xi+1 ).
riables alatoires (Xn )n0 dnie sur un espace de probabilit (, F, P ), (Xn )n0 est une chane de Markov de loi initiale et de famille de noyaux de transition
18
p = (pk (, ))k0 si et seulement si la loi de (Xn )n0 , vue comme variable alatoire dnie sur (, F, P ) et valeurs dans (S N , HN ), est gale P,p . En d'autres termes, si, pour tout A HN , P (X0: A) = P,p (A).
Nous utiliserons la notation Ex,p pour dsigner l'esprance relative P,p . Dans le cas homogne, nous noterons P,p plutt que P,p , et nous omettrons mme souvent de mentionner la dpendance de la loi de la chane vis--vis de p, pour ne conserver que celle vis--vis du point de dpart, c'est--dire que nous emploierons la notation P en lieu et place de P,p . La mme remarque vaut pour les esprances par rapport Pp , que nous noterons plutt E,p et E . La proposition ci-dessus illustre le fait que la proprit d'une famille de variables alatoires (Xn )n0 d'tre une chane de Markov (par rapport sa ltration naturelle) ne dpend que de la loi de probabilit de cette suite de variables alatoires. Il est parfois trs utile, pour tudier les proprits de la trajectoire (Xn )n0 , de se ramener l'espace-image des trajectoires (S N , HN , P,p ), que l'on appelle parfois l'espace canonique associ la chane de Markov. Introduisons donc quelques notations supplmentaires relatives cet espace. Dans le cas o est la mesure de Dirac = x , nous emploierons la notation Px,p de prfrence Px ,p (et donc Px,p ou Px dans le cas homogne). De mme, l'esprance sera note Ex,p (et Ex,p ou Ex dans le cas homogne). On note au passage que la probabilit P,p peut s'crire comme un mlange de telles probabilits associes des lois initiales concentres en un point :
P,p =
xS
(x)Px,p .
Lorsque nous travaillerons avec l'espace canonique, nous utiliserons encore les notations Xn pour dsigner les variables alatoires associes aux coordonnes successives de la trajectoire, autrement dit, tant donn (x0 , x1 , . . .) S N , nous poserons Xn (x0: ) = xn pour tout n 0. (Attention, les expressions faisant intervenir simultanment l'espace (, F) et l'espace (S N , HN ) pourront donc se rvler lgrement ambigus car les notations Xn et Fn n'auront pas la mme signication selon qu'elles portent sur le premier ou le deuxime espace.) Les oprateurs de dcalage n sur S N sont dnis pour tout n 0 par
n (x0 , x1 , . . .) = (xn , xn+1 , . . .).
Nous utiliserons la mme notation pour le dcalage correspondant eectu sur les noyaux, autrement dit, n (p) est la suite de noyaux (pn+k )k0 Pour tout n 0, et conformment aux notations dnies prcdemment pour une chane de Markov
Proprit de Markov
19
gnrale, nous noterons Fn la sous-tribu de HN engendre par les variables Xk , 0 k n. On vrie que, sur l'espace probabilis (S N , HN , P,p ), la suite de variables alatoires (Xn )n0 , valeurs dans S , est bien une chane de Markov de loi initiale et de famille de noyaux de transition p = (pk )k0 , ce qui prouve en particulier que, pour toute loi et toute famille de noyaux de transision p, il existe une chane de Markov qui leur est associe. La proprit de Markov peut se r-exprimer dans ce contexte de la manire suivante (en concatnant la proposition 1 et (1.2)) :
(1.5)
L'criture de l'identit ci-dessus peut paratre un peu sibylline, car elle fait intervenir les variables Xn la fois pour dnir les vnements dont on considre la probabilit, et dans l'expression de leurs probabilits. Pour se rassurer, on peut rcrire cette identit sous la forme
1 P,p (m (A)|Fm ) = PXm ,m (p) (A), P,p p.s.
Enn, si l'on veut repartir d'une expression faisant intervenir l'espace (, F, P ), on pourra crire, en faisant attention aux ambiguits de notation, que
P (Xm: A|Fm ) = PXm ,m (p) (A), P p.s.
un espace de probabilit (, F, P ) et valeur dans un ensemble ni ou dnombrable S , une variable alatoire T dnie sur (, F, P ) valeurs dans N {+} est appele un temps d'arrt de (Xn )n0 lorsque, pour tout n N, l'vnement {T = n} s'exprime en fonction de X0 , . . . , Xn , ou, en termes plus prcis, {T = n} Fn = (X0 , . . . , Xn ).
Un exemple fondamental de temps d'arrt est fourni par les temps d'atteinte, par exemple dnis par T := inf{n 0; Xn B}, o B S .
20
rt. Donner d'autres exemples de variables alatoires valeurs dans N {+} qui ne sont pas des temps d'arrt.
Exercice 21 Montrer que les temps d'atteinte dnis ci-dessus sont des temps d'ar-
Proposition 6 Etant donne une chane de Markov (Xn )n0 , dnie sur (, F, P ),
valeurs dans un ensemble ni ou dnombrable S , de loi initiale et de famille de noyaux de transitions p = (pn )n0 , et un temps d'arrt T de la suite (Xn )n0 , la proprit suivante est vrie : pour tout m 0 et tout A HN , et toute suite x0 , . . . , xm d'lments de S tels que P (X0:T = x0:T , T = m) > 0,
P (XT : A|X0:T = x0:T , T = m) = Pxm ,m (p) (A).
(1.6)
La proprit nonce dans la proposition est appele proprit de Markov forte, par opposition la proprit discute jusqu' prsent, que l'on peut rebaptiser proprit de Markov simple. Sachant toutes les valeurs passes jusqu'au temps T (et en particulier la valeur de XT ), la chane se comporte partir du temps T comme une nouvelle chane de Markov, issue de XT . On voit bien que, du fait que T est suppos tre un temps d'arrt, l'vnement {T = m} s'exprime en termes des variables X0 , . . . , Xm , et que (1.6) est donc une consquence de la proprit de Markov usuelle. En introduisant la tribu FT sur dnie comme l'ensemble des vnements C F tels que C {T = n} Fn pour tout n 0, on peut rcrire l'quation (1.6) sous la forme suivante : sur l'vnement {T < +}, on a, pour tout A HN , l'identit P (XT : A|FT ) = PXT ,T (p) (A), P p.s. (1.7)
1) Prouver la proprit de Markov forte nonce dans la proposition ci-dessus. 2) Vrier l'quivalence des formulations (1.6) et (1.7). En particulier, montrer que T est mesurable par rapport FT .
Exercice 23 Vrier qu'avec notre dnition, tout temps d'arrt T de (Xn )n0 se
factorise ncessairement sous la forme T = T ((Xn )0 ), o T est une variable alatoire dnie sur (S N , HN ) constituant un temps d'arrt pour la chane de Markov forme par la succession des coordonnes sur l'espace canonique (que nous notons galement (Xn )n0 en gnral, mais cela introduirait trop d'ambigut d'utiliser cette notation ici).
Notons que la notion de temps d'arrt peut-tre gnralise de la manire suivante : tant donne une famille croissante de tribus (Gn )n0 , on dit que T est un temps d'arrt par rapport (Gn )n0 lorsque pour tout n 0, {T = n} Gn . Si, en outre, Fn Gn pour tout n 0, et si (Xn )n0 vrie la proprit de Markov
Proprit de Markov
21
par rapport (Gn )n0 , la proprit de Markov forte est encore vrie. Un exemple simple de cette situation est le cas o, pour tout n, l'vnement T = n s'exprime en fonction de X0 , . . . , Xn et d'autres variables alatoires, indpendantes de la suite (Xi )i0 . En revanche, la conclusion de l'exercice ci-dessus n'est plus vrie dans ce cadre gnral.
loi de (Xt )Ti (a)t<Ti+1 (a) est identique la loi (sur l'espace canonique) de (Xt )0t<T1 (a) par rapport la probabilit Pa .
lire de deux manires quivalentes : comme dans l'nonc de la proprit (1.6), en conditionnant par la valeur exacte prise par T1 (a) et par toute la trajectoire X0 , . . . , XT1 (a), ou en termes de la tribu (X0 , . . . , XT1 (a) ), comme dans l'nonc de la proprit (1.7).
Nous obtenons donc la dcomposition d'une trajectoire de la chane en tronons de trajectoire suivant les retours successifs en a, que l'on peut rsumer de la manire suivante. On commence par le tronon (Xt )0t<T1 (a) . Si ce tronon est inni (c'est-dire si la chane n'atteint jamais a aprs son point de dpart), la dcomposition est termine. Si ce tronon est ni, on lui ajoute un tronon de trajectoire possdant la loi de (Xt )0t<T1 (a) par rapport la probabilit Pa , et l'on continue d'ajouter de manire i.i.d. de tels tronons jusqu' obtenir ventuellement un tronon inni, auquel cas la dcomposition s'arrte. Si la dcomposition ne s'arrte jamais, la trajectoire est constitue, en plus de son tronon initial, d'une suite innie i.i.d. de tronons de trajectoire de longueurs nies.
Dnition 2 Posons
N (a) =
+ i=1 1(Xi
22 En appliquant de manire rpte la proposition ci-dessus, on obtient le rsultat suivant, qui explicite la loi de N (a).
Bien entendu, P (N (a) = 0) = 1 P (T1 (a) < +). Par consquent, N (a) est presque srement ni, et l'on a en particulier
E(N (a)) = P (T1 (a) < +)(1 Pa (T1 (a) < +))1 .
Si Pa (T1 (a) < +) = 1, N (a) vaut 0 avec probabilit 1 P (T1 (a) < +), et + avec probabilit P (T1 (a) < +).
On peut prciser un peu la dcomposition d'une trajectoire dcrite prcdemment. Avec probabilit P (T1 (a) < +), la trajectoire revient en a. S'y greent alors, selon que Pa (T1 (a) < +) = 1 ou que Pa (T1 (a) < +) = 1, une innit de tronons i.i.d. possdant la loi de (Xt )0t<T1 (a) par rapport la probabilit Pa , ou un nombre ni N (a) 1 de tronons i.i.d. possdant la loi de (Xt )0t<T1 (a) par rapport la probabilit Pa (|T1 (a) < +), suivi d'une trajectoire innie possdant la loi de (Xt )0t<T1 (a) par rapport la probabilit Pa (|T1 (a) = +). Pour formaliser prcisment la discussion, le lemme lmentaire suivant est utile :
Lemme 2 Soit un espace mesurable (A, A) et une loi sur A. Considrons l'espace
c'est--dire la runion disjointe
C form par les suites nies d'lments de A de longueur suprieure ou gale 1, {n} An .
nN{+}
C :=
On munit C de la tribu engendre par les vnements de la forme {n} D, o D An , pour n dcrivant N {+}. Supposons que A est partitionn en deux parties mesurables A1 et A2 , et considrons prsent une variable alatoire (N, (Zi )1i<N +1 ) valeurs dans C vriant les deux proprits suivantes : N = inf{i 1; Xi A2 } (avec la convention inf = +) ; pour tout k 1, conditionnellement au fait que N > k, la variable alatoire Zk+1 est indpendante de (Z1 , . . . , Zk ) et suit la loi . Si (A2 ) = 0, on a que N = + p.s. et que, conditionnellement l'vnement N = +, la suite (Zn )n0 est i.i.d. de loi . Dans le cas o 0 < (A2 ) < 1, on a les proprits suivantes : la loi de N est gomtrique de paramtre (A2 ) ;
Proprit de Markov
23
pour tout k N, conditionnellement N = k, les variables (Z1 , , Zk ) sont indpendantes ; pour tout k N, conditionnellement N = k, la loi de Zi est (|A1 ) si 1 i < k et (|A2 ) si i = k .
Exercice 24 Prouver le lemme ci-dessus. Exercice 25 Appliquer le lemme ci-dessus pour vrier la validit de la discussion
qui le prcde.
1.6 Action sur les mesures, action sur les fonctions : le noyau comme oprateur linaire
Dans toute cette partie, S dsigne un ensemble ni ou dnombrable. Nous commenons par dnir diverses oprations associant noyaux, fonctions, et mesures sur S . Tout d'abord, tant donns deux noyaux de transition p et q sur S , on dnit le produit pq par la formule : pour tout x, y S
(pq)(x, y) :=
zS
et l'on vrie que l'on a ainsi dni un nouveau noyau de transition sur S . A prsent, tant donne une mesure positive sur S , et un noyau de transition p sur S , le produit p est dni par la formule : pour tout x S
(p)(x) =
yS
(y)p(y, x),
avec la convention 0 + = 0, et l'on vrie que l'on a ainsi dni une nouvelle mesure positive sur S , possdant la mme masse que : (p)(S) = (S). Pour une fonction positive ( valeurs dans [0, +]) f sur S , et un noyau de transition p sur S , on dnit galement le produit pf , par la formule
(pf )(x) =
yS
f (y)p(x, y),
avec la convention 0+ = 0. On vrie que l'on a ainsi dni une nouvelle fonction positive sur S , et l'on note que supxS (pf )(x) supxS f (x). Enn, tant donne une mesure positive sur S et une fonction positive f , nous noterons
f :=
xS
f (x)(x).
les parties positives et ngatives donnent chacune lieu une valeur nie.
= + (dirence de deux mesures positives) et d'une fonction valeurs relles f = f+ f (crite comme dirence de sa partie positive et ngative), pourvu que
24
si p, q, r sont trois noyaux de transition sur S , (pq)r = p(qr) ; si p, q sont deux noyaux de transition sur S et une mesure positive sur S , (pq) = (p)q ; si p, q sont deux noyaux de transition sur S et f une fonction positive sur S , (pq)f = p(qf ) ; si p est un noyau de transition sur S , une mesure positive, et f une fonction positive sur S , (p)f = (pf ). Ces proprits restent vries en considrant des mesures signes et des fonctions relles donnant lieu des parties positives et ngatives nies dans toutes les expressions.
Mme s'il ne couvre pas la totalit des cas possibles, on peut nanmoins retenir le rsultat suivant.
Proposition 10 L'action d'un noyau de transition droite (sur les fonctions) d-
nit un oprateur linaire continu de norme 1 de (S) dans lui-mme. L'action d'un noyau de transition gauche (sur les mesures) dnit un oprateur linaire continu de norme 1 de 1 (S) dans lui-mme. Les actions gauche et droite sont duales pour la dualit entre mesures signes de masse nie et fonctions bornes.
Proprit de Markov
25
On note que le rsultat de la proposition est encore valable si l'on considre des fonctions relles pour lesquelles les parties positives et ngatives donnent toutes les deux une valeur nie dans les expression considres.
On en dduit la proprit suivante, qui ne fait que traduire la proprit de semigroupe de la suite des noyaux itrs (pn )n0 , et que l'on peut dduire directement de la proprit de Markov, connue sous le nom d'quation de Chapman-Kolmogorov :
Px (Xn+m = y) =
zS
On retient notamment de ce qui prcde que la loi de probabilit de l'tat dans lequel se trouve une chane de Markov aprs n pas s'obtient en composant l'action successive de n oprateurs linaires sur sa loi initiale ; de la mme faon, la fonction indiquant, pour chaque tat initial possible dans S , la valeur moyenne de f sur l'tat de la chane aprs n pas en partant de cet tat initial, s'obtient en composant l'action de n oprateurs linaires sur f . (Attention au fait que les compositions ne s'eectuent pas dans le mme ordre dans les deux cas !) C'est cette remarque fondamentale qui permet d'utiliser, pour tudier les chanes de Markov, les techniques lies la composition d'oprateurs linaires (et notamment les mthodes spectrales), en particulier dans le cas homogne o l'on a aaire l'action d'un mme oprateur linaire compos avec lui-mme.
gne de noyau de transition p, et f : S S une fonction borne. On dnit une suite de variables alatoires (Mn )n0 par
n1
Exercice 28 Soit p un noyau de transition, (Xn )n0 une chane de Markov homo-
Mn := f (Xn ) f (X0 )
k=0
1) Montrer que (Mn )n0 est une martingale par rapport la ltration (Fn )n0 . 2) Montrer que, rciproquement, une suite de variables alatoires (Xn )n0 telle que proprit ci-dessus est vrie, est ncessairement une chane de Markov homogne associe au noyau p.
26
Dnition 3 Etant donn un espace mesurable (S, S), on appelle noyau de transi-
tion toute application p(, ) de S S dans R+ telle que : pour tout A S , x p(x, A) est une application mesurable de (S, S) dans R muni de sa tribu Borlienne ; pour tout x S , p(x, ) est une mesure de probabilit sur (S, S).
Ensuite, l'action d'un noyau sur les mesures et sur les fonctions se dnit de manire analogue celle dcrite prcdemment, de mme que la mesure P,p sur l'espace des trajectoires. On peut alors par exemple caractriser la proprit de Markov par l'identit (1.5), mais les autres versions de la proprit de Markov peuvent galement se gnraliser sans grande dicult. Si la dnition des chanes de Markov dans ce contexte ne pose gure de problmes, le comportement des objets ainsi dnis peut se rvler sensiblement plus complexe que dans le cas o l'espace est discret, et de nombreuses pathologies sont susceptibles d'apparatre. Dans une certaine mesure, il est possible d'adapter les mthodes et les rsultats qui prvalent dans le cas des espaces discrets, en gnral au prix d'hypothses de rgularit supplmentaires sur le noyau de transition de la chane. Pour un exemple simple, consulter par exemple la discussion de la notion de chane de Harris dans [18]. Pour des dveloppements beaucoup plus pousss, voir par exemple les ouvrages [36, 40, 43].
Proprit de Markov
27
ainsi que l'identit p0 = I , o I est le noyau de transition dni pour tout x S par I(x, x) = 1 et I(x, y) = 0 pour y = x. Une famille de variables alatoires (Xt )tR+ dnies sur un espace probabilis (, F, P ) et valeurs dans l'ensemble ni ou dnombrable S , sera appele une chane de Markov (homogne) en temps continu s'il existe une loi de probabilit sur S et un semi-groupe (pt (, ))tR+ de noyaux de transition1 tels que, pour toute famille d'indices 0 =: t0 < t1 < . . . < tn , et toute suite x0 , . . . , xn d'lments de S , on ait l'identit n
P (Xt0 :tn = x0:n ) = (x0 )
i=1
pti+1 ti (xi1 , xi ).
De manire quivalente, on peut demander que, pour tous m 0 et n m + 1, toute famille d'indices 0 =: t0 < t1 < . . . < tn , et toute suite x0 , . . . , xn d'lments de S telle que P (Xt0 :tm = x0:m ) > 0,
P (Xtm+1 :tn = xtm+1 :tn |Xt0 :tm = xt0 :tm ) = P (Xtm+1 :tn = xtm+1 :tn |Xtm = xtm ),
Attention : l'indice t dans la notation pt (, ) employe ici ne joue pas le mme rle que l'indice n dans la notation pn (, ) utilise dans le cas discret. Dans le cas discret, l'indice n permet de considrer des chanes de Markov n'ayant pas le mme noyau de transition chaque pas, c'est-dire inhomognes. Dans le cas prsent, nous dcrivons une chane de Markov homogne, et l'indice t doit tre employ du fait que, les trajectoires tant indexes par une variable de temps continue, celles-ci ne peuvent pas tre dcoupes en "pas" lmentaires comme dans le cas discret. En fait, il faut plutt rapprocher la notation pt de la notation pn employe pour dsigner la puissance n-me du noyau p.
1
28 les autres caractrisations de la proprit de Markov donnes dans le cas discret pouvant tre adaptes de manire similaire. Comme dans le cas discret, apparat alors comme la loi de X0 , et pt (x, y) doit vrier pt (x, y) := P (Xs+t (y)|Xs = x) lorsque P (Xs = x) > 0. On voit facilement d'aprs la dnition que, dans le cas o P (Xu = x) > 0, on doit avoir l'quation (dite de Chapman-Kolmogorov) ps+t (x, y) = P (Xs+t+u = y|Xu = x) = s t s t zS p (x, z)p (z, y) = (p p )(x, y), ce qui explique le fait que nous avons suppos a priori que (pt )tR+ forme un semi-groupe. Bien entendu, comme dans le cas discret, il n'y a en ralit aucune contrainte portant sur la valeur de ps (x, ) lorsque P (Xt = x) = 0 pour tout t R+ (on peut alors toujours supposer que, dans ce cas, ps (x, x) = 1 et ps (x, y) = 0 pour y = x, ce qui permet de garantir la proprit de semi-groupe). On note que la donne du semi-groupe (pt )tR+ et de la loi initiale caractrise compltement2 la loi de (Xt )tR+ en temps que variable alatoire de S R+ munie de la tribu engendre par les coordonnes, cette loi tant uniquement dtermine par ses marginales de dimension nie. La proprit de Markov de (Xt )tR+ apparat en fait comme une proprit de cette loi, et ne peut donc servir directement caractriser des proprits telles que la rgularit des trajectoires de la forme t Xt (), qu'il est pourtant ncessaire de considrer pour obtenir une thorie satisfaisante. Nous dirons qu'une fonction de R+ dans S est sauts rguliers si elle continues droite avec des limites gauche en tout point, et n'eectue qu'un nombre ni de sauts dans tout intervalle born. Nous dirons qu'une famille de variables alatoires (Xt )tR+ dnie sur un espace probabilis (, F, P ) est sauts rguliers si, hormis pour dans un ensemble de probabilit nulle sous P , la fonction t Xt () est sauts rguliers. Ensuite, un semi-groupe de noyaux de transition (pt )t0 sera dit rgulier si, pour toute loi de probabilit sur S (ou, simplement toute loi de probabilit de la forme = x avec x S ), il existe une chane de Markov sauts rguliers de loi initiale et de semi-groupe (pt )t0 . Il possible de dvelopper la thorie des chanes de Markov en temps continu partir de l'tude des proprits analytiques de ce semi-groupe (voir par exemple [7, 4]). Cependant, comme nous ne souhaitons donner dans ce cours, qui traite essentiellement du temps discret, qu'un bref aperu de la notion, nous prsentons plutt une construction, essentiellement quivalente, mais s'appuyant sur les chanes de Markov temps discret. Nous expliquons dans la suite le lien prcis entre les deux points de vue. Plutt que de partir d'un semi-groupe (pt )tR+ de noyaux de transition, nous supposerons donc donne une famille de taux de sauts = ((x, y), x, y S),
Inversement, on peut toujours construire une chane de Markov en temps continu associe un semi-groupe et une loi initiale donns.
2
Proprit de Markov
29
les (x, y) tant des nombres rels vriant la condition (x, y) 0 pour tous x, y S, x = y , ainsi que la condition (x, x) = yS (x, y) (qui impose donc que la somme gurant dans le membre de droite de l'quation soit nie). Partant de , on dnit ensuite un noyau de transition q(, ) sur S de la manire suivante. Si |(x, x)| > 0, on pose, pour tout y = x,
q(x, y) := (x, y) , z=x (x, z)
et par consquent q(x, x) := 0. Si (x, x) = 0, q(x, x) := 1, et, par consquent, q(x, y) := 0 pour tout y = x. On considre ensuite une chane de Markov (Zn )n0 de loi initiale et de noyau de transition q(, ), et une suite de variables alatoires (n )n0 vriant la proprit suivante : conditionnellement (Zk )k0 les variables alatoires (n )n0 sont indpendantes, la loi (conditionnelle) de n tant exponentielle de paramtre (Zn , Zn ) = y=Xn (Xn , y), lorsque cette quantit est strictement positive, et n tant pris gal + dans le cas contraire3 . La variable alatoire Texpl. := + n n=0 est appele le temps d'explosion. On dnit ensuite, pour tout t [0, Texpl. [, la variable alatoire Xt , de la manire suivante : pour tout n 0, Xt := Zn pour tout t [0 + + n1 , 0 + + n [. Lorsque P (Texpl. < +) = 0, on dit qu'il n'y a pas d'explosion en temps ni, et l'on peut dnir Xt pour tout t R+ . On observe alors que, presque srement, la trajectoire (Xt )tR+ ainsi obtenue est sauts rguliers. On a en fait le rsultat suivant, dont la preuve utilise essentiellement la proprit d'absence de mmoire de la loi exponentielle.
Thorme 1 Avec les notations prcdentes, dans le cas o il n'y a pas d'explosion
en temps ni, la famille de variables alatoires (Xt )tR+ est une chane de Markov en temps continu sauts rguliers, au sens dni prcdemment.
30
Thorme 2 Si
chane de Markov sauts rguliers de mme loi partir de la construction base sur les taux de sauts prsente ci-dessus. On peut employer pour cette construction la famille de taux de sauts dnie par (l'existence des limites ci-dessous, et le fait qu'elles dnissent eectivement une famille de taux de sauts font partie du thorme) :
(x, y) = lim ph (x, y) , x = y, h0 h (ph (x, x) 1) . h0 h
(Xt )tR+ est une chane de Markov en temps continu associe un semi-groupe rgulier de noyaux de transition pt (, ), il est possible d'obtenir une
(x, x) = lim
Nous allons vrier directement, pour la construction base sur les taux de sauts, que les limites gurant dans le thorme 2 sont bien satisfaites. Partons donc d'une chane de Markov ainsi construite, initialise selon la loi x . Posons (x) := (x, x), et supposons que (x) > 0, sans quoi le rsultat annonc est trivial. Pour y = x, on a
P (Xh = y) = P (Z1 = y, 1 < h, 1 + 2 > h) + P (Xh = y, 1 < h, 1 + 2 < h). (1.8)
Constatons dj que, par dnition, P (Z1 = y, 1 < h) = q(x, y)(1 e(x)h ), d'o le fait que limh0 h1 P (Z1 = y, 1 < h) = q(x, y)(x) = (x, y). Au vu de (1.8), on en dduit qu'il sut de montrer que P (1 + 2 < h) = o(h) lorsque h tend vers zro pour prouver le rsultat concernant ph (x, y). On peut par exemple crire que P (1 + 2 < h) P (1 < h, 2 < h), puis, en dcoupant selon la valeur de Z1 , crire que
P (1 < h, 2 < h) =
zS
d'o
P (1 < h, 2 < h) =
zS
Par convergence domine, on vrie que limh0 zS q(x, z)(1 e(z)h ) = 0, d'o le rsultat lorsque y = x. Le cas y = x peut tre trait de la mme manire. Dans ce contexte, la famille de taux (x, y) constitue ce que l'on appelle le gnrateur innitsimal du semi-groupe pt (, ). Comme pour les noyaux de transition, on peut dnir l'action du gnrateur droite sur les fonctions par (f )(x) = yS (x, y)f (y), et gauche sur les mesures par ()(x) = yS (y)(y, x). Pour une fonction ou une mesure positive ne prenant que des valeurs nies, la dnition a toujours un sens car (x, y) 0 sauf si x = y . On tend la dnition aux fonctions et aux mesures non-ncessairement positives par le procd habituel. Au vu des thormes prcdents, on dduit la proposition suivante.
Proprit de Markov
31
(pt )tR+ est en-
S est de cardinal ni, on a toujours < +) = 0, et plus gnralement lorsque sup |(x, x)| < +.
Exercice 33 Montrer que, sur l'vnement {Texpl. < +}, avec probabilit 1, chaque lment de S ne doit tre visit qu'un nombre ni de fois par la chane (Zn )n0 . Exercice 34 Le but de cet exercice est d'tablir la caractrisation suivante, dite
critre de Reuter : tant donn une famille de taux de sauts , il n'y a pas d'explosion en temps ni si et seulement si, pour tout nombre rel positif > 0, le systme d'quations
+ (x, x)ux =
yS, y=x
(x, y)uy ; x S,
n'admet aucune solution u = (ux )xS positive, borne, et distincte de ux 0. 1) On dnit, pour tout x S et tout > 0, ux () := E(exp(Texpl. )), o l'esprance est prise par rapport la contruction ayant pour loi initiale x . Montrer que, dans le cas o P (Texpl. < +) > 0, ux () fournit la solution recherche au systme. 2) On suppose prsent que nous disposons d'une solution u = (ux )xS ngative, borne, et distincte de ux 0 au systme, et que, par ailleurs, P (Texpl. < +) = 0. Montrer alors que la famille de variables alatoires (exp(t)uXt )t0 constitue une martingale (on peut se contenter de le vrier pour les t de la forme t = 0 + +n ). Conclure une contradiction en analysant le comportement lorsque t +.
On peut rcrire le rsultat nal du thorme 2 sous la forme
ph I = , h0 h lim
32 o la limite a lieu coordonne par coordonne pour tout (x, y) S . En crivant, pour t R+ , que pt+h pt = (ph I)pt = pt (ph I), on s'attend ce que les deux quations suivantes soient vries (bien entendu, ce n'est qu'un calcul purement formel pour l'instant, car il y a de srieux problmes de convergence rgler) :
dpt dpt = pt , = pt , dt dt
(1.9) (1.10)
L'quation (1.9) est appele quation de Kolmogorov rtrograde, tandis que (1.10) est appele quation de Kolmogorov progressive. Pour que cette quation est un sens, on doit s'assurer et de la direntiabilit des fonctions t pt (x, y), et de la convergence des sries qui apparaissent dans les quations. Nous n'en donnerons pas la preuve (voir par exemple [4]), mais il est en fait possible de vrier rigoureusement ces proprits.
Mt := f (Xt ) f (X0 )
0
(f )(Xs )ds,
Proprit de Markov
33
Dans le cas o l'on souhaite construire la dynamique partir d'une famille de taux de sauts, il est possible de donner une ralisation explicite de celle-ci au moyen d'une famille de processus de Poisson. Plus prcisment, on supposera donne une famille P(x, y), x, y S , x = y , de processus de Poisson sur R+ (vus comme des sousensembles alatoires), mutuellement indpendants, chaque P(x, y) ayant un taux constant gal (x, y). Considrons n 0, et supposons donns les valeurs Zn = x et 0 + + n1 = t utiliss pour la construction. On dnit alors t comme le plus petit lment de la runion des ensembles P(x, y)]t, +[ pour y S , et x comme l'lment de S vriant t P(x, x ). Compte-tenu de nos hypothses sur , avec probabilit 1, t existe et vrie t > t, tandis que x est unique. On dnit alors Zn+1 := x et n := t t. Une interprtation intuitive utile de la construction donne ci-dessus peut se rsumer ainsi : lorsque la chane est dans l'tat x, au cours d'un intervalle de temps innitsimal dt, la probabilit que la chane eectue un saut vers y = x est donne par (x, y)dt.
Exercice 36 Prouver que la construction dnie ci-dessus satisfait bien les propri-
Dans le cas o la famille de taux de sauts est borne, il est possible de donner une reprsentation plus simple de la dynamique, ne faisant appel qu' un seul processus de Poisson. Supposons donc donn un nombre rel > 0 tel que supxS |(x, x)| . Dnissons alors le noyau de transition r(, ) sur S de la manire suivante : si x = y , on pose r(x, y) := (x,y) , et r(x, x) = 1 y=x r(x, y). En d'autres termes,
r = I + /.
Notre hypothse sur assure que l'on dnit bien ainsi un noyau de transition. La construction reprend alors les tapes de la construction gnrale partir des taux de sauts, mais en modiant les dnitions de Zn et n . Plus prcisment, on considre donc une chane de Markov (Zn )n0 de loi initiale et de noyau de transition r(, ), et une suite de variables alatoires (n )n0 i.i.d. de loi exponentielle de paramtre . En posant, pour tout t R+ , Nt = card{i; 0 + + i1 < t} on obtient la reprsentation Xt = ZNt , (Nt )t0 tant le processus de comptage associ au processus de Poisson dont les accroissements sont donns par les variables alatoires (n )n0 . Insistons sur le fait que Nt est indpendant de la chane (Zn )n0 .
Exercice 37 Prouver que la construction dnie ci-dessus satisfait bien les proprits attendues de la construction par les taux de sauts.
Par rapport la construction gnrale, on constate que les lois des dates auxquelles ont lieu les sauts ne dpendent pas des tats dans lesquels la chane se trouve,
34 ce que l'on corrige en introduisant des sauts ctifs d'un tat vers lui-mme. On vrie facilement que l'on a alors, pout tout t R+ , la relation
+
pt =
n=0
rk
tk t e = et(rI) = et . k
Exercice 38 Vrier que, dans le cas particulier ci-dessus, les quations de Kolmogorov progressive et rtrograde sont vries.
Mentionnons une famille importante de chanes de Markov en temps continu : les processus de naissance et de mort. L'espace d'tats de ces processus est l'ensemble N des entiers naturels, et les seuls sauts autoriss consistent ajouter ou retrancher 1 l'tat courant. Plus prcisment, on suppose que l'on a deux suites (i )i0 et (i )i1 , et que, pour tout x 0, (x, x + 1) := x , tandis que pour tout x 1, (x, x 1) := x . Les taux (x, y) avec y {x 1, x, X + 1} sont gaux 0.
chaque intervalle de temps innitsimal dt, chaque individu de la population peut mourir avec probabilit dt, ou, au contraire, donner naissance un autre individu, avec probabilit dt, indpendamment des autres individus prsents. Montrer que la population totale est dcrite par un processus de naissance et de mort. Quels sont les paramtres correspondants ?
taux de sauts x := x (et pas de mort, donc x := 0), et vriant X0 := 1. 1) Montrer qu'il n'y a pas d'explosion en temps ni. 2) On pose, pour tout > 0, f (t) := E[exp(Xt )]. Grce aux quations de Kolmogorov, trouver une quation direntielle satisfaite par f , et la rsoudre. 3) En dduire que, pour tout t 0 et n 1, P (Xt = n) = a(1a)n , o a := exp(t). 4) Retrouver la loi de Xt l'aide d'un argument purement probabiliste. (Indication : reprsenter la gnalogie du processus, et la considrer rebrousse-temps). 5) Que dire de la loi de exp(t)Xt lorsque t + ? 6) Montrer que (exp(t)Xt )t0 est une martingale. En dduire que limt+ exp(t)Xt existe presque srement. 7) On considre prsent non plus un, mais deux processus de naissance indpendants (Xt )t0 et (Yt )t0 avec X0 := A et Y0 := B . Soit (n )n0 la suite croissante des instants des sauts de Xt et Yt (avec 0 := 0). Quelle est la loi de la suite (Xn , Yn )n0 ? 8) Retrouver partir des questions prcdentes le fait que la proportion de boules rouges dans une urne de Plya contenant initialement A boules rouges et B boules
Proprit de Markov
35
blanches (avec A, B 1), et dans laquelle on ajoute chaque tirage une boule supplmentaire de la mme couleur que celle qui vient d'tre tire, converge presque srement vers une valeur limite distribue selon une loi Beta de paramtres (A, B).
n n 1 1 + + + n n n1 n 1 0
= +.
36 point de dpart possibles pour le processus, c'est--dire ici une famille de mesures de probabilit (Px )xS sur D([0, +), S), vriant les conditions suivantes : Px (X0 = x) = 1 ; pour tout A F , x Px (A) est mesurable ; pour tout x S et tout t 0,
1 Px (t (A)|Ft ) = PXt (A), Px p.s.,
o Ft et t sont dnis de manire analogue au cas discret. On voit que la proprit de Markov est ici traduite par la troisime condition. Comme dans le cas temps continu/espace discret, on peut dvelopper une thorie dcrivant les liens entre semi-groupe et gnrateur innitsimal, mais celle-ci est beaucoup plus dicile et sophistique. Un exemple classique de processus de Markov en temps continu et espace nondiscret est le mouvement Brownien (voir par exemple [44, 28, 46]), pour lequel l'espace d'tats est typiquement R ou Rd . Un autre exemple est constitu par les systmes de particules en interaction (voir par exemple [32, 31]), pour lesquels l'espace d est typiquement de la forme S Z , o S est discret.
En d'autres termes, les valeurs du champ sur l'ensemble A ne dpendent des valeurs du champ l'extrieur de A que par l'intermdiaire des valeurs prises sur la frontire sparant A et l'extrieur de A.
Exercice 43 Montrer que, si (Xm )0mn est une chane de Markov, elle constitue
galement un champ Markovien associ au graphe G dont les sommets sont forms par l'ensemble [[1, n]], deux entiers tant relis par une arte s'ils dirent de 1.
Proprit de Markov
37
de V constitue une clique de G si toute paire de sommets distincts de C est relie par une arte de G. Un potentiel de Gibbs sur S V associ la structure de graphe de G est la donne, pour toute clique C , d'une fonction WC dnie sur S C et valeurs dans ] , +]. On construit alors une fonction d'nergie associe dnie sur S V et valeurs dans ] , +] en posant
H((xv )vV ) :=
C
Exercice 44 Etant donn un graphe ni G = (V, E), on dit qu'un sous-ensemble C
WC ((xv )vC ).
Une famille de variables alatoires valeurs dans S indexe par V constitue un champ de Gibbs lorsque sa loi jointe est associe un potentiel de Gibbs par l'intermdiaire de la relation :
P ((Xv )vV = (xv )vV ) = 1 exp(H((xv )vV )), Z
o > 0, et o Z est une constante de normalisation. Montrer que tout champ de Gibbs est un champ markovien.
En fait, la rciproque au rsultat de l'exercice ci-dessus est vraie : tout champ markovien (sous rserve d'une condition de non-dgenerescence) est un champ de Gibbs pour un certain potentiel, au moins dans le cas d'un graphe ni (la situation est bien plus complexe dans le cas d'un graphe inni).
Exercice 45 Vrier que, dans l'exercice 43, le champ markovien que l'on obtient en
considrant une chane de Markov est bien un champ de Gibbs. Prciser le potentiel correspondant.
de Gibbs.
L'ouvrage [7] contient une discussion des champs markoviens. Pour un traitement plus dtaill, voir par exemple [23] et les rfrences qu'il contient.
38 Pour caractriser une telle chane de Markov, on supposera donne une loi initiale sur S M , et une famille de noyaux de transition (pn )n0 de S M vers S (c'est--dire que, . pour tout n 0 et x S M , pn (x, ) est une probabilit sur S ). L'analogue de la proprit de Markov est slors le suivant : pour toute suite x0 , . . . , xn (avec n + 1 M)
nM
pi (xi:i+M 1 , xi+M ).
D'un point de vue formel, cette notion se ramne en fait exactement la notion usuelle de chane de Markov, comme le montre l'exercice suivant.
Exercice 47 Etant donne une suite de variables alatoires (Xn )n0 , montrer qu'il
y a quivalence entre les deux proprits suivantes : la suite (Xn )n0 est une chane de Markov d'ordre M ; la suite (Xi:i+M 1 )i0 est une chane de Markov sur S M 1 . Prciser le lien entre les noyaux de transition dans les deux cas.
Proprit de Markov
39
la loi initiale et la famille de noyaux de transition (pk )k0 , tandis que, conditionnellement (Xn )n0 , les variables alatoires (Yk )k0 sont indpendantes, la loi de Yk sur V tant donne par qk (Xk , ). Comme la terminologie le suggre, ce type de modles est employ pour dcrire des suites de variables observes, dont la dpendance est en fait contrle par une suite markovienne de variables non-observes. Ce type de modle est employ dans de nombreuses applications, par exemple pour le traitement du signal, la reconnaissance de la parole, ou la modlisation de squences biologiques telles que l'ADN. D'un point de vue thorique, la notion de chane de Markov cache s'identie en fait avec celle de chane de Markov partiellement observe. Les exercices suivants dveloppent un peu ce point de vue.
Exercice 49 Dans cet exercice, on montre que les notions de chane de Markov
cache et de chane de Markov partiellement observe sont en fait quivalentes. 1) Etant donne une chane de Markov (Xn )n0 , et une fonction f : S V , montrer que la suite (Xn , f (Xn )) est une chane de Markov cache. 2) Rciproquement, montrer que, si (Xn , Yn )n0 est une chane de Markov cache, on peut reprsenter Yn sous la forme Yn = f (Zn ), o (Zn )n0 est une chane de Markov.
paramtre 1/2, (n )n0 . Dnissons Xn := (n , n+1 ). 1) Montrer que (Xn )n0 est une chane de Markov. Que peut-on dire de la suite (X2n )n0 ? 2) Sur {0, 1}2 , dnissons la fonction f par f (0, 0) := 0, f (0, 1) = f (1, 0) := 1, f (1, 1) := 2, et considrons la suite (Yn )n0 dnie par Yn := f (Xn ). Montrer que (Yn )n0 n'est pas une chane de Markov, mme si l'on s'autorise considrer des chanes plusieurs pas de mmoire. cation f : S V , et une chane de Markov (Xn )n0 sur S de noyau de transition p. 1) Supposons que p vrie la proprit (*) suivante : pour tous x, y S tels que f (x) = f (y), on a l'galit p(x, f 1 (v)) = p(y, f 1 (v)) pour tout v V . (Nous employons la notation p(x, A) := zA p(x, z).) Montrer qu'alors (f (Xn ))n0 est une chane de Markov. Quel est le noyau de transition correspondant ? 2) Montrer que, pour un noyau irrductible, il y a en fait quivalence entre la proprit (*) dnie la question prcdente, et la proprit suivante : pour toute loi initiale sur S , (f (Xn ))n0 est une chane de Markov pour la probabilit P,p .
Tout un ensemble de mthodes et d'algorithmes ont t dvelopps pour l'infrence statistique dans le contexte chanes de Markov caches. Pour motiver l'exercice
40 qui suit, posons-nous la question de savoir comment calculer la probabilit d'une squence de valeurs observes. Dans le cas d'une chane de Markov, la rponse est immdiate : la probabilit d'observer la suite de valeurs x0 , . . . , xn est donne par le produit (x0 )p0 (x0 , x1 ) pn1 (xn1 , xn ). Dans le cas d'une chane de Markov cache, la probabilit d'une suite de valeurs observe y0 , . . . , yn est donne par
(x0 )p0 (x0 , x1 ) pn1 (xn1 , xn )q0 (x0 , y0 ) qn (xn , yn ).
x0:n S n+1
Clairement, calculer une telle somme est trs rapidement impossible, mme si S ne comporte qu'un petit nombre d'tats. L'algorithme dcrit dans l'exercice suivant montre comment des algorithmes de calcul itratifs peuvent tre employs pour rsoudre ce type de problme.
suppose que les ensembles d'tats S et V sont nis. On considre une chane de Markov cache (Xn , Yn )n0 avec les notations , pi , qi dnies prcdemment, et une suite de valeurs observes y0 , . . . , yn . 1) On dnit une suite (i (x))0in , x S , de la manire suivante. Pour initialiser, on pose 0 (x) := (x)q0 (x, y0 ). Puis par rcurrence :
i+1 (x) :=
zS
Expliquer comment on peut en dduire la probabilit P (Y0:n = y0:n ) 2) On cherche prsent une suite d'tats cachs x0 , . . . , xn qui maximise la probabilit P (Y0:n = y0:n , X0:n = x0:n ). On dnit deux suites (i (x))0in et (i (x))1in , x S , de la manire suivante. Pour initialiser, on pose 0 (x) := (x)q0 (x, y0 ). Ensuite,
i+1 (x) := max i (z)pi (z, x)qi+1 (x, yi+1 ),
zS
et i+1 (x) est dni comme l'un quelconque des z ralisant le maximum dans l'expression ci-dessus. On dnit ensuite x comme l'un quelconque des x ralisant le n maximum de n (x), puis, par rcurrence, x := i+1 (x ). Montrer que la suite i i+1 x , . . . , x ralise le maximum recherch. n 0
Pour approfondir le sujet, voir par exemple l'ouvrage [8].
Proprit de Markov
41
(1.11)
Si A est compatible-Markov, on peut donc dnir sans ambiguit, pour tout x tel qu'il existe x0:m A vriant xn = x, la notation n (x) := n (x0:n ). Montrer qu'un ensemble de la forme C0 Cm est toujours compatible-Markov. Donner un exemple d'ensemble compatible-Markov ne pouvant pas se mettre sous cette forme. 2) A prsent, considrons une chane de Markov (Xn )0n m d'espace d'tats S , dnie sur (, F, P ), et de famille de noyaux de transition (pn )0nm1 . Montrer que, si A est compatible-Markov, X0 , . . . , Xm forme une chane de Markov par rapport la probabilit conditionnelle P (|X0:m A). Montrer que les noyaux de transition correspondants sont donns, pour tout xn tel que P (Xn = xn |X0:m A) > 0 par la formule :
qn (xn , xn+1 ) := pn (xn , xn+1 ) gn+1 (xn+1 ) , gn (xn )
o
gn (xn ) := P (Xn:m n (xn )|Xn = xn ).
3) Donner un exemple d'ensemble A tel que X0 , . . . , Xn n'est pas une chane de Markov par rapport la probabilit P (|X0:m A).
et A S . On utilise la notation 0 =: T0 (A) < T1 (A) < T2 (A) < . . . pour dsigner les instant successifs d'atteinte de A. Sur l'espace canonique, on dnit la suite (Zn )n0 par Zn := XTn (A) . Montrer que, si x A, la suite (Zn )n0 est une chane de Markov sous la probabilit Px . de S 3 vers S , c'est--dire une fonction associant tout triplet d'lments de S une mesure de probabilit sur S . Soit N 1, et a, b S . On dnit alors un noyau de transition sur S N de la manire suivante. Etant donn (x1 , . . . , xN ) S N , soit (Z 1 , . . . , Z N ) une famile de variables alatoires indpendantes telles que, pour tout
4
42
1 i N , la loi de Zi soit donne par p((xi1 , xi , xi+1 ), ), avec la convention x1 := a et xN +1 := b. On dnit alors p((x1 , . . . , xN ), ) comme la loi de (Z 1 , . . . , Z N ). On se donne ensuite un point de dpart x x0 := (x1 , . . . , xN ), et l'on considre 0 0 une chane de Markov (Xn )n0 initialise en X0 := x0 et de noyau de transition p. 1 N On note Xn := (Xn , . . . , Xn ). i i 1) Montrer que, pour tout n 1 x, la suite (X0 , . . . , Xn )1iN est une chane de Markov d'ordre 2 sur S n+1 . 2) Montrer que, pour tout n 1 et 1 i N x, conditionnellement la donne i i i i de (X0 , . . . , Xn ) pour tout j = i, la suite (X0 , . . . , Xn ) est une chane de Markov.
d'ordre total note . On rappelle (ou non ?) la dnition suivante : tant donnes deux mesures de probabilit 1 et 2 sur S , on dit que 1 est domine par 2 (ou que 2 domine 1 ) si 1 (f ) 2 (f ) pour toute fonction croissante f : S R. 1) Etant donnes deux variables alatoires Y1 et Y2 dnies sur un mme espace de probabilit (, F, P ), on suppose que P (Y1 Y2 ) = 1. Montrer que la loi de X2 domine la loi de X1 . 2) Montrer que la rciproque de la question prcdente est vraie : si 1 et 2 sont deux mesures de probabilit sur S , et si 1 est domine par 2 , alors il existe un espace de probabilit (, F, P ) et deux variables alatoires Y1 et Y2 de lois respectives 1 et 2 , et vriant P (Y1 Y2 ) = 1. Indication : comparer 1 ({x; a x}) et 2 ({x; a x}) pour a S , et utiliser un dcoupage d'intervalles. Remarque : ce rsultat est encore vrai pour des ensembles partiellement ordonns, mais la preuve est plus dlicate (c'est le thorme de Strassen, voir par exemple [33] pour une preuve). 3) Appliquer les rsultats prcdents an de montrer la proprit suivante. Etant donn un noyau de transition p sur Z tel que, pour tout x, p(x, x1)+p(x, x+1) = 1, et tant donns x < y tels que x y 2Z, et n 1, la loi de Xn sous la probabilit Px,p est domine par la loi de Xn sous la probabilit Py,p . Le rsultat est-il encore vrai si l'on ne suppose pas que x y 2Z ? Indication : fabriquer un couplage appropri. 4) Appliquer les rsultats prcdents an de montrer la proprit suivante. Etant donn un noyau de transition p sur Z tel que, pour tout x, p(x, x1)+p(x, x+1) = 1, et tant donns a Z, et x < y a tels que x y 2Z, et n 1 tel que Py,p (Xi a, 0 i n) > 0, montrer que la loi de Xn sous la probabilit Px,p (|Xi a, 0 i n) est domine par la loi de Xn sous la probabilit Py,p (|Xi a, 0 i n). Le rsultat est-il encore vrai si l'on ne suppose pas que x y 2Z ? Indication : fabriquer un couplage appropri.
Exercice 56 Dans cet exercice, on considre un ensemble ni S , muni d'une relation
Proprit de Markov
43
le thorme de Diaconis-Freedman (voir [13]) sur la caractrisation des mlanges de chanes de Markov. Plus prcisment, nous dirons qu'une suite de variables alatoires (Xn )n0 valeurs dans un ensemble ni ou dnombrable S est un mlange de chanes de Markov s'il existe une loi initiale et une loi Q sur l'ensemble des noyaux de transition sur S (muni de la tribu engendre par les applications (x, y) p(x, y)) tels que, pour tout n 0 et toute suite x0 , . . . , xn S ,
n1
P (X0:n = x0:n ) =
(x0 )
i=0
On dnit ensuite une relation d'quivalence sur l'ensemble des suites nies d'lments de S en considrant deux suites comme quivalentes lorsqu'elles ont le mme tat initial et que, pour tous x, y S , elles comportent exactement le mme nombre de transitions de l'tat x vers l'tat y . (En particulier, deux telles suites ont obligatoirement la mme longueur). Nous dirons enn que (Xn )n0 est partiellement changeable lorsque, pour tout n 0 et tout couple x0:n et y0:n de suites quivalentes, on a l'galit
P (X0:n = x0:n ) = P (X0:n = y0:n ).
Le thorme de Diaconis-Freedman est alors le suivant : une suite (Xn )n0 pour laquelle P (Xi = X0 pour une innit d'indices i) = 1 est un mlange de chanes de Markov si et seulement si elle est partiellement changeable. 1) Montrer que si (Xn )n0 est un mlange de chanes de Markov, (Xn )n0 doit ncessairement tre partiellement changeable. 2) Donner un exemple d'une suite (Xn )n0 partiellement changeable qui n'est pas un mlange de chanes de Markov. Indication : un exemple dterministe peut sure. Dans la suite de l'exercice, on suppose donne une suite (Xn )n0 partiellement changeable vriant la condition P (Xi = X0 pour une innit d'indices i) = 1, et l'on cherche prouver que celle-ci est un mlange de chanes de Markov. 3) Montrer que l'on peut, sans perte de gnralit, supposer que P (X0 = x) = 1 pour un certain x S . On supposera donc cette condition vrie dans la suite. 4) On dnit la suite (Li )i1 de suites nies de S de la manire suivante. Appelons S0 , S1 , . . . les valeurs successives des indices n pour lesquels Xn = x (on a donc S0 = 0). Pour tout i 1, on pose alors Li := XSi :Si+1 1 . Montrer que la suite (Li )i1 est changeable, au sens suivant : pour tout entier n 1, et toute permutation des entiers {1, . . . , n}, loi
(L1 , . . . , Ln ) = (L(1) , . . . , L(n) ).
5) Dnissons la tribu asymptotique de la suite (Li )i1 par G := i1 (Lj ; j i). Vrier que la suite (Xn )n0 conserve la proprit d'changeabilit partielle conditionnellement G .
44
6) Montrer que, si les (Li )i0 sont i.i.d., la suite (Xn )n0 est une chane de Markov. 7) Conclure en utilisant le thorme de De Finetti, qui arme que, du fait de leur proprit d'changeabilit tablie en 4), les variables (Li )i1 sont i.i.d. conditionnellement G .
(X0 , . . . , Xn ) est une chane de Markov (a priori inhomogne), c'est galement le cas de (Xn , . . . , X0 ). Dans le cas o l'on part d'une
chane homogne, obtient-on toujours une chane homogne en eectuant ce retournement du temps ?
Exercice 59 Soient
S, V , deux ensembles nis ou dnombrables, et f : S V une application. Soient par ailleurs un noyau de transition p sur S et un noyau de transition q sur V . Si dsigne une probabilit sur S , on note f la probabilit image de par f , c'est--dire la probabilit dnie sur V par (f )(A) = (f 1 (A)). 1) On suppose que, pour toute probabilit sur S , (f )q = f (p).
(1.12)
Montrer que, si (Xn )n0 est une chane de Markov sur S de loi initiale , (f (Xn ))n0 est une chane de Markov sur V de loi initiale f et de noyau de transition q . 2) Donner une condition plus explicite portant sur p, q, f quivalente la condition (1.12) ci-dessus. 3) Lorsque la proprit (1.12) ci-dessus est vrie avec V = S et q = p, on dit que p est invariante sous l'action de f . Montrer qu'une marche alatoire ( gauche) sur un groupe est invariante par la multiplication ( gauche) par un lment du groupe.
Chapitre 2
Dcompositions de l'espace d'tats, rcurrence/transience
Dans ce chapitre, nous introduisons diverses dcompositions importantes de l'espace d'tats bases sur les proprits de communication entre les points vis--vis du noyau.
Exercice 60 Donner un exemple dans lequel il n'y a que des points inessentiels, un
exemple dans lequel il n'y a que des points essentiels, et un exemple o les deux types de points coexistent.
46
p(, )), alors pm (x, y) = 0 pour tout m. En d'autres termes, l'ensemble des points essentiels est stable par p(, ) : si x Sess. , p(x, Sess. ) = 1.
Par l'absurde. On sait qu'il existe z et k tels que pk (y, z) > 0 et pn (z, y) = 0 pour tout n. S'il existe m tel que pm (x, y) > 0, on en dduit que pm+k (x, z) > 0. Comme x est essentiel, il existe tel que p (z, x) > 0. Par consquent, p +m (z, y) > 0, ce qui contredit le fait que la probabilit d'atteindre y en partant de z soit nulle.
Preuve :
Exercice 61 Vrier que Siness. n'est, quant lui, pas ncessairement stable.
Lorsque x est un point inessentiel, la proposition 8 peut alors s'appliquer x, car Px (T1 (x) < +) < 1 par dnition, et l'on voit donc que, quelle que soit la loi initiale choisie, le nombre de visites en x par une chane de noyau de transition p est ni presque srement, et possde mme une queue dcroissance gomtrique. Cette remarque justie en quelque sorte la terminologie employe.
valence sur S .
Exercice 62 Prouver la proposition. Exercice 63 Montrer que la classe de communication de x n'est autre que la runion des points se trouvant sur les cycles issus de x possdant une probabilit positive d'tre parcourus. Proposition 15 Les ensembles Sess. et Siness. sont stables par cette relation d'quivalence : si x communique avec y et si x Sess. , y Sess. .
Proposition 16 Si
47
Preuve :
Par l'absurde. Si x C , p(x, y) > 0 et y ne communique pas avec x, on a ncessairement que pk (y, x) = 0 pour tout k. Ainsi, x est inessentiel, ce qui contredit le fait que x Sess.
On tire de ce qui prcde la reprsentation suivante d'une trajectoire de la chane. Initialise en un point essentiel, la chane reste pour toujours conne la classe de communication du point dont elle est issue. Initialise en un point inessentiel, au contraire, elle nit toujours par sortir de la classe de communication de son point initial, et cette sortie est obligatoirement dnitive. Si le point atteint lors de cette sortie est inessentiel, le mme scnario se rpte. Inversement, si le point atteint lors de la sortie est essentiel, la chane reste ensuite pour toujours conne dans la classe de communication du point qu'elle vient d'atteindre.
Exercice 65 Montrer que, si S est de cardinal ni, toute trajectoire nit, avec une
probabilit gale 1, par atteindre un point essentiel.
On dit que p(, ) est irrductible si x communique avec y pour tous x, y dans S . D'aprs les propositions prcdentes, la restriction de p(, ) restreint une classe de communication de Sess. est irrductible. Quitte enlever de S les points inessentiels par rapport au noyau de transition considr (qui ne sont visits qu'un nombre ni de fois sur toute la dure d'une trajectoire), et tudier sparment les chanes obtenues par restriction sur chaque classe de Sess. , (rappelons que celles-ci sont stables), on peut donc se ramener tudier des noyaux de transition irrductibles. Ceci ne signie pas que le comportement de la chane partir de points inessentiels soit inintressant !
tion irrductible, tous les points de S ont une probabilit positive d'tre visits, quelle que soit la loi initiale, et, par consquent, ce noyau est le seul compatible avec cette chane. On peut donc parler d'une chane de Markov irrductible sur un ensemble S . Attention cependant, la notion d'irrductibilit dpend de l'ensemble S dans lequel on considre que la chane prend ses valeurs : une chane, vue comme famille de variables alatoires dans un ensemble S1 pourra se rvler irrductible sur S1 , mais pas sur un ensemble S2 contenant S1 . il existe m 1 tel que pm (x, x) > 0.
S est ni, et o p peut donc se reprsenter comme une matrice, quelles proprits de cette matrice l'existence de sous-ensembles de S stables par p correspond-elle ?
48
et tudier leurs ensembles de points essentiels, inessentiels, et les classes d'quivalence pour la relation de communication de l'ensemble des points essentiels.
2.1.3 Priode
On dnit la priode (par rapport p(, )) d'un point x par
d(x) = p.g.c.d.{n 1; pn (x, x) > 0}.
(Avec la convention que p.g.c.d. = +). Pour un noyau irrductible, on constate que la priode est ncessairement nie pour tout point. Par exemple, on voit facilement que, pour (le noyau de transition de) la marche alatoire simple sur Z, la priode de tout point est gale 2.
0.
Exercice 68 Montrer par un exemple que l'on n'a pas ncessairement pd(x) (x, x) >
Preuve :
Remarque 5 Une condition susante trs simple pour avoir apriodicit dans le
cas d'une chane irrductible est qu'il existe au moins un point x tel que p(x, x) > 0.
p(, ) irrductible et de priode d. Considrons x et y dans S . Si pm (x, y) > 0 et pn (x, y) > 0, alors d divise m n.
Soit a tel que pa (y, x) > 0. On a donc pm+a (x, x) > 0 et pn+a (x, x) > 0. Donc d divise m + a et n + a.
49
Sous les hypothses de la proposition ci-dessus, dnissons, pour tout x S et tout h Z/dZ, l'ensemble
Ch (x) = {y S; m 0, pm (x, y) > 0, m = h},
titionn en d classes d'quivalence pour la relation per. , et, pour tout x S les classes sont exactement l'ensemble des Ch (x), h Z/dZ. Qui plus est, pour tout x S , p(x, Ch+1 ) = 1.
Exercice 69 Prouver les deux propositions ci-dessus. Proposition 21 Supposons p(, ) irrductible et de priode d. Pour tout h Z/dZ,
les classes d'quivalence de S pour per. sont stables par pd (, ), et la restriction de pd (, ) l'une quelconque de ces classes est irrductible et apriodique.
Preuve :
L'irrductibilit est une consquence immdiate de l'irrductibilit de p(, ) et de la discussion ci-dessus. Quant l'apriodicit, c'est galement vident vu la dnition de la priode. Ainsi, quitte dcomposer une chane irrductible en d sous-chanes correspondant chacune un tat sur d de la chane originale, on peut se ramener tudier des chanes de Markov irrductibles et apriodiques.
x est rcurrent, Px (Ti (x) < +) = 1 pour tout i, autrement dit, x est visit une innit de fois, ou encore Px (N (x) = +) = 1.
Proposition 22 Si
50
Preuve :
Voir la proposition 8.
Proposition 23 Si
x est transient, Px (N (x) < +) = 1 et Ex (N (x)) < +. On a mme que la loi de N (x) sous Px est exactement une loi gomtrique de paramtre Px (T1 (x) = +) > 0.
Preuve :
Idem.
Px (Xi = x) = +.
i=1
Preuve :
+ i=1 1(Xi +
Ex (N (x)) =
i=1
Ex (1(Xi = x)) =
i=1
Px (Xi = x).
Si x est transient, Ex (N (x)) est ni d'aprs la proposition prcdente. Si x est rcurrent, N (x) est inni avec probabilit 1 sous Px , donc videmment Ex (N (x)) est inni. On note que, dans le cas o (Xn )n0 est une suite de variables alatoires i.i.d., le critre ci-dessus correspond simplement l'application du lemme de Borel-Cantelli.
Exercice 71 On utilise vraiment la proprit de Markov pour prouver le rsultat cidessus. Pour une suite de variables alatoires quelconque telle que X0 = x, le fait que + i=1 P (Xi = x) = + (ou, de manire quivalente, le fait que E(N (x)) = +), n'entrane pas en gnral que P (N (x) = +) = 1. Donner un exemple d'une telle situation.
Proposition 24 Supposons
p(, ) irrductible. La rcurrence d'un point de S implique celle de tous les autres points.
On parlera donc de chanes de Markov irrductibles rcurrentes ou transientes, ou de noyau rcurrent ou transient.
Preuve :
51
autrement dit Px (T1 (y) < T1 (x)) est strictement positive. A chaque retour en x (et chaque passage en x est toujours suivi d'un nouveau passage en x), on a donc une probabilit Px (T1 (y) < T1 (x)) de visiter y avant de revenir en x, indpendamment de tout ce qui prcde. Par consquent, Px (T1 (y) < +) = 1. A prsent, Py (T1 (x) < +) doit ncessairement tre gale 1, ce sans quoi on aurait, lors du premier passage en y , une probabilit non-nulle de ne jamais revenir en x, ce qui contredirait la rcurrence de x. Enn, il est clair que Py (T1 (x) < +) = 1 et Px (T1 (y) < +) = 1 entranent que Py (T1 (y) < +) = 1, donc y est rcurrent. Lorsque p(, ) est irrductible, on parle donc du fait que p(, ) est rcurrent ou transient (sans spcier de point), ou que la chane est rcurrente ou transiente.
+) = 1 pour tous x et y .
Proposition 25 Supposons
Preuve :
y est rcurrent.
D'aprs la preuve prcdente, Px (T1 (y) < +) = 1. On utilise ensuite le fait que
Proposition 26 Supposons
p(, ) irrductible. Si p(, ) est transient, on a ncessairement que Ex (N (y)) < + pour tous x et y , et l'on a mme que, pour tout k 1, Px (N (y) = k) = Px (T1 (y) < +)(Py (T1 (y) < +))k1 Px (T1 (y) = +),
et
Px (N (y) = 0) = Px (T1 (y) = +).
Preuve :
Proposition 8.
seulement si le sous-groupe de Zd engendr par le support de la loi des pas est gal Zd .
Zd ) L'objectif de cet exercice est de prouver que la marche alatoire simple symtrique sur Zd est rcurrente lorsque d 2 et transiente lorsque d 3. Pour cela, on se
(2.1)
52
2) Noter que l'on pourrait dduire le rsultat pour d 1 du rsultat pour d = 1 si les coordonnes de la marche alatoire taient des marches alatoires simples unidimensionnelles indpendantes, ce qui n'est pas le cas. En revanche, il y a eectivement indpendance entre les coordonnes conditionnellement aux nombres de pas eectus sur chacune des coordonnes. Prouver d'abord ce rsultat, puis l'utiliser pour dduire (2.1) partir du cas d = 1. Dans le cas d = 2, il est possible d'viter cet argument en considrant les projections de la marche alatoires sur les deux bissectrices, ce qui permet d'obtenir deux marches alatoires exactement indpendantes. 3) Reprouver le rsultat avec l'approche suivante, dont le potentiel de gnralisation est plus important : calculer explicitement la transforme de Fourier de x pn (0, x) et l'inverser. On notera au passage que (2.1) s'obtient en extrapolant (non-rigoureusement) le thorme de la limite centrale pour en faire un thorme limite local. Par ailleurs, malgr la rcurrence en dimension 1 et 2, le thorme de la limite centrale entrane que, aprs n pas, la marche alatoire est typiquement une distance de l'ordre de n1/2 de son point de dpart. Le mme rsultat est valable en dimension d 3, pour lequel la chane est transiente. Par ailleurs, on note qu'en dimension 3, bien qu'il y ait transience, aucune coordonne de la marche ne tend vers .
symtrique support born) On considre une marche alatoire irrductible sur le groupe Z que l'on note (Xn )n0 , initialise en 0. On suppose que la loi des incrments est symtrique et support born. Nous allons montrer que la chane est rcurrente. Notons (n )n1 la suite des incrments de la chane. 1) Montrer que les vnements
A+ := {lim sup n1/2 Xn = +}, A := {lim sup n1/2 Xn = },
n+ n+
sont mesurables par rapport la tribu asymptotique n1 (0 , . . . , n ). On rappelle que, d'aprs la loi du 0-1 de Kolmogorov, les v.a. (n )n1 tant i.i.d., tout vnement de cette tribu est de probabilit 0 ou 1. 2) Montrer que P (A+ ) = P (A ). 3) Montrer que, pour tout K 0,
P (lim sup n1/2 Xn > K) lim sup P (n1/2 Xn > K).
n+ n+
4) Utiliser le thorme de la limite centrale pour dduire de ce qui prcde que P (A+ ) > 0, d'o P (A+ ) = 1. 5) Conclure.
53
considre une marche alatoire irrductible sur le groupe Zd dont la distribution des pas prsente un biais, c'est--dire possde une esprance non-nulle. Montrer qu'une telle marche est toujours transiente.
but de cet exercice est de prouver qu'une marche alatoire irrductible sur le groupe Z dont la distribution des pas est d'esprance nulle, est toujours rcurrente. A cette n, on introduit, pour tout x Z et n 0,
n
Z : cas centr) Le
gn (x) :=
k=0
pk (0, x),
o p est le noyau de transition associ la marche. 1) Prouver que gn (x) est l'esprance du nombre de visites en x aprs n pas de la marche initialise en 0 (en incluant le point de dpart dans le dcompte des sites). 2) En utilisant la proprit de Markov, prouver que, pour tous n 0, et x Z, gn (0) n pk (x, 0). En dduire que, pour tout n 0 et x Z, on a gn (0) gn (x). k=0 3) On note A := { , , + }. Dduire de ce qui prcde que, pour tout n 0, et tout 1, on a
gn (0) 1 |A |
n
gn (x).
xA
4) Prouver l'identit
gn (x) =
xA
pk (0, x).
k=0 xA
5) Pour un rel a > 0 x, on pose n := an . Prouver (en utilisant la loi des grands nombres) que, pour tout a > 0, on a
lim inf
n+
pn (0, x) 1.
xA
n
6) Dduire de ce qui prcde que + pk (0, 0) = +, et conclure que 0 est un point k=0 rcurrent. 7) Qu'est-ce qui empche d'tendre l'argument en dimension plus grande ?
exp(ix)(x).
54
L'objectif de cet exercice est de montrer que la marche est rcurrente si et seulement si
t1 [0,2]d
lim
1 1 t()
+
d = +.
1) Montrer que
+
pn (0, 0) = lim
n=0
t1
tn pn (0, 0).
n=0
tn pn (0, 0) =
n=0
1 (2)d
tn ()n d.
n=0 [0,2]d
1 1 ()
d = +.
Il est en fait possible de montrer que la rciproque est vraie, ce qui fournit un critre plus joli que celui prouv dans l'exercice, mais la preuve est sensiblement plus dlicate.
En utilisant le critre de l'exercice prcdent, prouver1 les rsultats suivants : 1) Une marche alatoire irrductible sur Z avec des pas centrs est rcurrente. 2) Une marche alatoire irrductible sur Z2 avec des pas centrs et possdant un moment d'ordre 2 ni est rcurrente. 3) Une marche alatoire irrductible sur Zd avec d 3 est toujours transiente.
Pour approfondir les questions de rcurrence/transience des marches alatoires sur le groupe Zd , consulter par exemple consulter l'ouvrage [50].
Z par p(x, x + 1) = 1 p(x, x 1) = pour tout x > 0, p(x, x 1) = 1 p(x, x + 1) = pour tout x > 0, et p(0, 1) = p(0, 1) = 1/2. 1) Montrer que, lorsque > 1/2, ce noyau est transient. 2) Montrer qu'une trajectoire initialise en 0 tend vers + avec probabilit 1/2, et vers avec probabilit 1/2.
55
x est positivement rcurrent (pour p(, )) si Ex (T1 (x)) < +. Dans le cas contraire, on dit que x est rcurrent nul.
d'un point entrane celle de tous les autres. Il en va donc de mme de la rcurrence nulle.
Proposition 27 Supposons
On parlera donc de chanes de Markov irrductibles positivement rcurrentes ou rcurrentes nulles, ou de noyau rcurrent nul ou transient.
Preuve :
Donnons-nous un point x S rcurrent positif, et un point quelconque y S dirent de x. Montrons d'abord que Ex (T1 (y)) < +. Notons d'abord que, du fait de la rcurrence de la chane, on doit ncessairement avoir que Px (T1 (y) < T1 (x)) > 0. Introduisons le nombre N de retours en x eectus avant de toucher y pour la premire fois, soit
T1 (y)
N :=
n=1
1(Xn = x),
et le temps ncessaire pour, partant de XN (qui vaut alors x) l'instant N , atteindre y pour la premire fois, soit
U := T1 (y) TN (x).
T1 (y) =
i=1
+ U.
(2.2)
En faisant appel la proprit de Markov forte et au lemme 2, on dduit les faits suivants. Premirement, sous Px , conditionnellement la valeur de N , les variables alatoires
T1 (x), T2 (x) T1 (x)), . . . , (TN (x) TN 1 (x)), U
sont indpendantes. Toujours sous Px et conditionnellement la valeur de N , les variables alatoires T1 (x), (T2 (x) T1 (x)), . . . , (TN (x) TN 1 (x)) possdent toutes la mme loi, savoir celle de T1 (x) sous la probabilit Px (|T1 (y) > T1 (x)), tandis que U possde la loi de T1 (y) sous la probabilit Px (|T1 (y) < T1 (x)). De plus, la loi de N est gomtrique de paramtre Px (T1 (y) < T1 (x)). A prsent,
Ex (T1 (y)|T1 (y) < T1 (x)) Ex (T1 (x)|T1 (y) < T1 (x)) Ex (T1 (x) < +, Px (T1 (y) < T1 (x))
56 car x est rcurrent positif. Si Px (T1 (y) < T1 (x)) = 1, on a N = 0 Px p.s., et l'on peut dduire le rsultat recherch de (2.2). Dans le cas contraire, on montre comme ci-dessus que Ex (T1 (x)|T1 (x) < T1 (y)) < +. En reprenant (2.2), et en utilisant les proprits d'indpendance des (Ti (x) Ti1 (x))1in conditionnellement N , on en dduit alors que
Ex (T1 (y)) Ex (N ) Ex (T1 (x)|T1 (x) < T1 (y)) + Ex (T1 (y)|T1 (y) < T1 (x)) < +.
Montrons prsent que Ey (T1 (x)) < +. D'aprs ce qui prcde, Ex (T1 (x)|T1 (y) < T1 (x)) < +. Clairement, la loi de T1 (x) T1 (y) sous la probabilit Px (|T1 (y) < T1 (x)) est identique la loi de T1 (x) sous Py , grce la proprit de Markov. Donc Ey (T1 (x)) = Ex (T1 (x) T1 (y)|T1 (y) < T1 (x)) Ex (T1 (x)|T1 (y) < T1 (x)) < +. A prsent, on crit que, sur l'espace canonique, T1 (y) T1 (x) + T1 (y) T1 (x) . Au vu du fait que Ey (T1 (x)) < + et Ex (T1 (y)) < +, ceci entrane la conclusion Ey (T1 (y)) < +.
sont rcurrentes nulles. Indication : en dimension 1, la loi du temps de premier retour en zro se calcule explicitement2 , et l'on obtient que Px (T1 (x) n) Cn1/2 .
Z et Z2
S est ni, toute chane de Markov irrductible est ncessairement positivement rcurrente. Indication : pour x S x, il existe, pour tout y S , un entier m(y, x) 1 tel que pm(y,x) (y, x) > 0. En posant m (x) := maxxS m(y, x), considrer des intervalles de temps successifs de longueur m (x).
Exercice 84 On se donne un arbre drgulier enracin, avec d 1, et l'on considre le noyau de transition dni de la manire suivante : seules sont autorises les transitions d'un sommet vers son pre ou vers l'un de ses ls, la probabilit de transition d'un sommet dirent de la racine l'un quelconque de ses ls est un nombre x p, la probabilit de transition d'un sommet dirent de la racine son pre est un nombre x q , les probabilits de transition de la racine vers ses ls tant chacune gale 1/d.
Par exemple, l'aide du principe de rexion, ou encore du calcul des nombres de Catalan bas sur leur relation de rcurrence au moyen des sries gnratrices, voir galement l'exercice 106
2
57
1) En fonction de p, q, d, discuter le caractre rcurrent positif/rcurrent nul/transient, du noyau ainsi dni. Indication : pour la rcurrence positive, on peut utiliser le fait que, si les (i )i0 sont des variables alatoires i.i.d. valant 1, on a une ingalit, valable pour tout n 0, de la forme
P
1
+ + n
[E(1 ) h, E(1 ) + h] /
exp(c(h)n),
avec c(h) > 0 si h > 0. 2) Quels sont les noyaux pour lesquels on peut facilement utiliser un couplage avec le cas trait la question 1) pour conclure quant au caractre rcurrent positif/rcurrent nul/transient ? On se donne un noyau de transition p irrductible sur un ensemble ni ou dnombrable S . On considre ensuite un noyau q sur S tel que, pour tout couple x, y d'lments de S tels que (x, y) AA, q(x, y) = p(x, y). En ce sens, q est une modi/ cation locale de p. L'objectif de cet exercice est de prouver que, si q est irrductible, q possde le mme comportement que p en ce qui concerne la rcurrence/transience, et la rcurrence positive/rcurrence nulle. 1) On utilise la notation T1 (A) pour dsigner le premier instant d'atteinte de A strictement postrieur l'instant 0. Montrer que, pour tout x A, conditionnellement l'vnement T1 (A) > 1, la loi de (Xn )0nT1 (A) est la mme sous Px,p et Px,q . 2) Conclure.
On considre l'espace A des trajectoires innies (x0 , x1 , x2 , . . .) valeurs dans Zd , initialises en 0, et eectuant des pas au plus proche voisin, A tant muni de la tribu engendre par les coordonnes. La notation (e1 , . . . , ed ) dsigne la base canonique de Zd , et on pose B := {+e1 , . . . , +ed , e1 , . . . , ed }. Pour (x0 , x1 , x2 , . . .) A, on a donc que x0 = 0 et xn+1 xn B pour tout n 0. Pour tout h 1, on dnit sur A les suites de variables (Rk )k0 , (Sk )k0 et (Dk )k0 par rcurrence de la manire suivante. Pour initialiser, on pose R0 := 0, D0 := 0. Ensuite, pour tout k 0, on pose
Sk+1 := inf{n Dk ; Xn e1 = Rk + 1}, Dk+1 := inf{n Sk+1 ; Xn e1 = Rk }, Rk+1 := sup{Xn e1 ; Sk+1 n Dk+1 }.
58
A prsent, considrons une marche alatoire (Xn )n0 sur le groupe Zd , initialise en 0, et eectuant des pas au plus proche voisin. Plus prcisment, on se donne une famille de variables alatoires i.i.d. (i )i1 valeurs dans B , dnies sur un espace de probabilit (, F, P ), et Xn est dni par X0 := 0 et Xn := n i pour n 1. i=1 On suppose en outre que la marche est biaise positivement dans la direction +e1 , autrement dit, que E(1 e1 ) > 0. 1) Montrer que ((Xn )n0 ) est ni avec probabilit 1. 2) La variable alatoire (Xn )n0 est-elle en gnral un temps d'arrt pour la ltration dnie par Fn := (X0 , . . . , Xn ) ? On dnit prsent par rcurrence
1 := ((Xn )n0 ),
puis
i+1 := i + ((Xi +n Xi )n0 ).
4) Montrer que, pour tout i 1, conditionnellement Fi , la loi de (Xi +n Xi )n0 n'est autre que la loi de (Xn )n0 conditionnelle l'vnement B := {Xn e1 0 pour tout n 0}. (Commencer par le cas i = 1.) 5) En dduire que 1 , 2 1 , 3 2 , . . . sont des variables indpendantes, possdant toutes la mme distribution l'exception de 1 . Mme question avec r1 , r2 r1 , r3 r2 .
L'exercice prcdent montre comment on peut dcouper la trajectoire d'une marche alatoire biaise en tronons indpendants et (sauf le premier) identiquement distribus. Comme nous le verrons dans un chapitre ultrieur, une telle dcomposition est un premier pas pour prouver des thormes limites tels que la loi des grands nombres ou le thorme de la limite centrale, par exemple. Bien entendu, pour la marche alatoire simple, ce rsultat n'est pas trs intressant car on dispose de beaucoup d'autres techniques pour l'tudier. En revanche, l'approche dveloppe dans cet exercice peut encore tre utilise dans certains modles de marches alatoires en milieu alatoire, et de marches alatoires en auto-interaction, pour lesquels les autres approches ne sont pas utilisables.
branchement de Galton-Watson, dans lequel une population initialement constitue d'un individu volue, chaque individu donnant lieu un nombre alatoire de descendants dans la gnration suivante, les nombres de descendants des dirents individus
59
tant choisis de manire i.i.d. selon une loi de reproduction xe sur N. On dit qu'il y a extinction si le nombre d'individus prsents dans la population s'annule aprs un certain nombre de gnrations. Dans le cas contraire, on dit qu'il y a non-extinction. La thorie classique des processus de Galton-Watson, base sur le calcul des fonctions gnratrices, permet (entre autres) d'tablir le rsultat suivant. En notant m l'esprance (ventuellement innie) du nombre de descendants d'un individu dans la gnration suivante, c'est--dire l'esprance de , il y a extinction presque sre lorsque m 1, et non-extinction avec probabilit strictement positive si m > 1. Nous montrons ici comment relier cette proprit la rcurrence/transience d'une marche alatoire. 1) Aller lire (ou relire) d'urgence un expos de la thorie classique des processus de Galton-Watson, par exemple celui de [53]. On dnit une suite (Zn )n0 de parties nies de N, et une suite (Kn )n0 de variables alatoires valeurs entires, de la manire suivante. On suppose donne une suite (Mn )n0 de variables i.i.d. de loi . Initialement, Z0 := {1} et K0 := 1. Ensuite, tant donn Zn et Kn , on distingue deux cas. Si Zn = , Zn+1 := Zn et Kn+1 := Kn . Si Zn = , on pose
Zn+1 := Zn {Kn + 1, Kn + 2, . . . , Kn + Mn } \ {min Zn }, Kn+1 := Kn + Mn .
2) Prouver que la probabilit d'extinction d'un processus de Galton-Watson de loi de reproduction et contenant initialement un individu, est la probabilit pour qu'il existe un n partir duquel Zn = . 3) Montrer que la suite (card Zn )n0 est en fait une marche alatoire sur le groupe Z. Quelle est la loi de ses incrments ? 4) A partir des proprits de rcurrence/transience des marches alatoires sur Z, en dduire le critre m 1 pour avoir une probabilit d'extinction strictement positive. 5) On dnit T := inf{n 1; Zn = }, avec la convention inf = +. Montrer que la variable alatoire 1 + T 1 Mn est gale T et possde la mme loi que n=0 le nombre total d'individus dans la gnalogie (la somme des populations totales de chaque gnration) d'un processus de Galton-Watson de loi de reproduction et contenant initialement un individu. En dduire que ce nombre est d'esprance nie dans le cas < 1, et d'esprance innie dans le cas = 1. 6) L'approche de cet exercice permet de retrouver partiellement le critre de rcurrence/transience des marches alatoires sur le groupe Z dont l'esprance des pas est dnie, partir de la thorie classique des processus de Galton-Watson. Quel type de loi exactement peut-on traiter au moyen de cette approche ?
60
On considre une marche alatoire simple (Xn )n0 sur Z (ventuellement biaise), initialise en 1. On note T1 (0) le premier temps de retour en 0 de la chane, et, pour tout j 1, on dnit la variable alatoire
Nj := card {n 0; n T1 (0), (Xn , Xn+1 ) = (j, j + 1)}.
1) Montrer que la loi de la suite (Nj )0j<T1 (0) est la mme que la loi des nombres d'individus dans les gnrations successives d'un processus de Galton-Watson comportant initialement un individu, considres jusqu' l'extinction du processus (si celle-ci n'a pas lieu, on prend en compte la totalit de la trajectoire). 2) A partir du critre d'extinction pour les processus de Galton-Watson, retrouver la fait que la marche alatoire retourne presque srement en 0 si et seulement si le biais est ngatif ou nul. 3) Inversement, retrouver dans ce cas particulier le critre d'extinction pour les processus de Galton-Watson partir des rsultats sur les temps de retour en 0 pour la marche.
L'exercice ci-dessus ne fait que reprouver un rsultat que l'on peut obtenir par des moyens plus simples. Cependant, l'approche dveloppe dans cette exercice, base sur un lien entre les trajectoires d'une marche alatoire uni-dimensionnelle, et un processus de branchement, peut tre applique pour traiter certaines marches alatoires en milieu alatoire ou en auto-interaction, l o les autres approches ne peuvent pas ncessairement se gnraliser.
Pour x, y S , posons t(x, y) := Ex (T (y)), o T (y) est le temps d'atteinte de y , et Hn := n 1/k . Le but de cet exercice est de montrer l'encadrement suivant : k=1
H|S| min t(x, y) E(Trec. ) H|S| max t(x, y),
x=y x=y
o |S| dsigne le nombre d'lments de S . 1) Rappeler pourquoi t(x, y) < + pour tous x, y S . Montrer ensuite que l'on a E(Trec. ) < +. On considre prsent une permutation alatoire uniforme J1 , . . . , J|S| des lments de S indpendante de la chane de Markov tudie, et l'on pose, pour tout 1 m |S|,
Cm := max T (Ji ),
1im
61
et
5) Montrer que (1 1/n) minx=y t(x, y) E(C1 ) (1 1/n) maxx=y t(x, y). 6) Conclure.
62
Chapitre 3
Thorie du potentiel, mesures et lois invariantes
La thorie classique du potentiel s'est dveloppe partir de la notion de potentiel telle qu'elle apparat en physique (par exemple le potentiel lectrique ou gravitationnel), et tudie notamment l'oprateur Laplacien et les fonctions harmoniques. Il est possible de dvelopper une thorie du potentiel (en fait, plusieurs thories) pour les chanes de Markov, dans laquelle le rle du Laplacien est dvolu l'oprateur p I . Dans le cas du mouvement Brownien, l'analogue de p I est le gnrateur innitsimal du processus, qui s'identie au Laplacien usuel, et l'on retrouve donc exactement la thorie classique du potentiel. Comme nous le verrons, les analogues probabilistes des objets et des rsultats de la thorie du potentiel classique jouent un rle trs important dans l'tude des chanes de Markov. Pour une introduction la thorie du potentiel pour les chanes de Markov, consulter par exemple [39]. Pour approfondir, voir par exemple [43], et [50] pour le cas des marches alatoires sur le groupe Zd . Un rle central dans la thorie du potentiel est jou par l'quation de Poisson
V = f,
o V est le potentiel et f est une fonction donne. L'analogue dans notre cadre, est l'quation de Poisson discrte pu = u + c, (3.1) o p est un noyau de transition sur S , et o u et c sont des fonctions dnies sur S et valeurs relles, c tant suppose valeurs positives, et u pouvant ventuellement prendre les valeurs . Dnissons la fonction de Green G(, ) sur S S par
+ + +
G(x, y) :=
n=0
p (x, y) =
n=0
Px (Xn = y) = Ex
n=0
1(Xn = y) .
(3.2)
64 En utilisant simplement l'identit ppn (x, y) = pn+1 (x, y), on voit directement partir de la dnition que, pour tout y S ,
pG(, y) + I(, y) = G(, y),
(3.3)
et on obtient donc une solution positive de l'quation de Poisson discrte (3.1) cidessus en posant, pour tout x S ,
u(x) :=
yS
c(y)G(x, y).
c(Xn ) .
mme pour u.
(3.4)
65
(3.5)
et l'quation obtenue est l'quation de Laplace. Telle qu'crite ci-dessus, avec une condition au bord xe, l'quation (3.5) est appele problme de Dirichlet, et les solutions de l'quation sont les fonctions harmoniques. Lorsque l'on suppose seulement que l'on a l'ingalit u(x) pu(x), on dit que l'on a aaire une fonction sur-harmonique, et les solutions de l'quation de Poisson gnrale (3.4) sont donc des fonctions sur-harmoniques, puisque nous supposons toujours que c 0.
GD (x, y) :=
n=0
pn (x, y). D
Noter que, bien que pD ne soit pas un noyau de transition, on peut dnir toutes les oprations ici, l'itration de pD avec lui-mme de la mme faon que pour les noyaux de transition. Par convention, p0 (x, y) vaut 1 si x = y et x, y D, et 0 D sinon. Nous utiliserons dans la suite la notation suivante : tant donne une chane de Markov (Xn )n0 , la notation T dsigne le premier temps d'atteinte de D, soit
T := inf{n 0; Xn D},
avec la convention usuelle inf = +. Cette notation permet de rcrire GD d'une manire plus probabiliste :
+ T 1
GD (x, y) =
n=0
Px (Xn = y, T > n) = Ex
n=0
1(Xn = y) .
Considrons y D x. Comme dans le cas sans frontire, en utilisant simplement l'identit pD pn = pn+1 , on voit directement partir de la dnition que, D D
[pGD (, y)] (x) + I(x, y) = GD (x, y) pour tout x D.
(3.6)
66 Ainsi, on peut construire une solution positive de l'quation de Poisson (3.4) associe c, mais avec 0, en posant
uD (x) :=
yD
uD (x) = Ex
n=0
D'autre part, en utilisant cette fois l'identit pn p = pn+1 , on montre que l'on a D D l'quation duale pour les mesures GD (x, ) sur S , savoir que, pour x D x,
[GD (x, )p] (y) + I(x, y) = GD (x, y) pour tout y D,
(3.7)
tandis que
GD (x, y) :=
n=0
(3.8)
67
Considrons y D x. On vrie ici encore partir de la dnition que, pour tout x D, (pI)(x, y) + (pGD p)(x, y) = p(x, y) + (pGD p)(x, y) = GD (x, y). On en dduit donc que
[pGD (, y)] (x) = GD (x, y) pour tout x D,
on obtient une solution positive de l'quation de Poisson 3.4 associe , mais avec c 0, c'est--dire une solution au problme de Dirichlet. Une expression probabiliste de uD est alors donne par
uD (x) = Ex (c(XT )1(T < +)) .
(3.4) en posant
Nous verrons plus tard qu'il est galement intressant de considrer la dnition suivante, duale de celle de GD . Dnissons GD (, ) sur D S par
GD (x, y) := I(x, y) + pGD (x, y) = I(x, y) +
zD
GD (x, y) :=
n=0
Px (Xn = y, T1 > n) = Ex
n=0
1(Xn = y) ,
68 avec la convention usuelle inf = +. On peut alors eectuer le calcul dual de celui men pour GD , savoir que, x D tant x, on a, pour tout y D, l'identit (Ip)(x, y) + (pGD p)(x, y) = p(x, y) + (pGD p)(x, y) = GD (x, y), d'o
[GD p(x, )] (y) = GD (x, y) pour tout y D,
(3.9)
tandis que
(3.10)
mais que cette dernire expression n'est pas en gnrale gale I(x, y).
Preuve :
On note que le calcul eectu dans la preuve ci-dessus est exactement celui qui conduit la martingale de l'exercice 28.
est borne, et est solution de l'quation de Poisson sans frontire (3.1). Si c 0, c'est-dire dans le cas d'une fonction harmonique, la suite [f (Xn )]n0 est une martingale par rapport la ltration (Fn )n0 . Dans le cas gnral de l'quation de Poisson, on a seulement le fait que f est sur-harmonique, et que [f (Xn )]n0 est une sur-martingale.
69
Il sut d'appliquer le rsultat du thorme ci-dessus, qui permet de vrier facilement par rcurrence, dans le cas o f est suppose positive mais pas ncessairement borne, que E (f (Xn )) < + pour tout n et que l'on a la proprit de martingale (ou de sur-martingale). Dans le cas avec frontire absorbante, on a le rsultat suivant :
Preuve :
Preuve :
Par ailleurs, la condition T > n entrane que T (n + 1) = n + 1 et T n = n. En utilisant le fait que l'vnement {T = n} est mesurable par rapport Fn du fait que T est un temps d'arrt, on constate ainsi que P p.s.,
E (f (XT (n+1) )|Fn )1(T > n) = E (f (Xn+1 )|Fn )1(T > n) = pf (Xn )1(T > n)
tandis que
pf (Xn )1(T > n) = [f (XT n ) c(XT n )] 1(T > n).
Si T n, on a en revanche l'galit f (XT (n+1) ) = f (XT n ) = f (XT ), et 1(T n)f (XT ) est mesurable par rapport Fn , d'o le fait que, P p.s.,
E (f (XT (n+1) )|Fn )1(T n) = f (XT n )1(T n).
On note que le calcul ci-dessus revient considrer la martingale (Mn )n0 de l'exercice 28 et exploiter le fait que (MT n )n0 est ncessairement une martingale.
est borne, et est solution de l'quation de Poisson avec frontire absorbante (3.4). Si c 0, c'est--dire dans le cas d'une fonction harmonique, la suite [f (XT n )]n0 est une martingale par rapport la ltration (Fn )n0 . Dans le cas gnral de l'quation de Poisson, on a seulement le fait que f est sur-harmonique, et que [f (XT n )]n0 est une sur-martingale.
70 Il sut d'appliquer le rsultat du thorme ci-dessus, qui permet de vrier facilement par rcurrence, dans le cas o f est suppose positive mais pas ncessairement borne, que E (f (XT n )) < + pour tout n et que l'on a la proprit de martingale (ou de sur-martingale).
Preuve :
o ]0, 1[. 1) Montrer que, lorsque = 1/2, il existe une fonction harmonique positive nonconstante. 2) Montrer que, lorsque = 1/2, les seules fonctions harmoniques positives sont les constantes, mais qu'il existe nanmoins des fonctions harmoniques non-constantes.
Sur cet exemple, on constate donc qu'il n'y a pas ncessairement unicit pour le problme de Dirichlet (et donc pour l'quation de Poisson en gnral), mme si l'on impose la solution de ne prendre que des valeurs positives. En revanche, la solution uD + uD construite dans la section prcdente possde la proprit trs importante d'tre une solution positive minimale de l'quation, ce qui est prcis par le thorme suivant.
on a ncessairement
h uD + uD .
Preuve :
uK (x) := D
yD
c(y)
n=0
Px (Xn = y, T > n) ,
71
et
uK (x) D :=
yD
K1
(y)
n=0
Px (Xn = y, T = n) .
En reprenant les calculs de fonction de Green eectus prcdemment, on vrie facilement que uK+1 (x) = (puK )(x) + c(x) pour tout x D, tandis que uK+1 (x) = 0 D D sur D, tandis que uK+1 (x) = (puK )(x) pour tout x D et uK (x) = (x) sur D. D D D En posant uK (x) := uK (x) + uK (x), on en dduit que uK+1 (x) = (puK )(x) + c(x) D D pour tout x D, tandis que uK (x) = (x) sur D. Par ailleurs, on voit facilement partir de la dnition que, pour tout x S ,
K+
K+
Supposons donne une fonction h vriant les hypothses du thorme. On a h u0 = 0. Ensuite, par rcurrence, on voit que si l'on a h uK , on doit avoir, pour x D, h(x) ph(x)+c(x) puK (x)+c(x) = uK+1 (x). Par ailleurs, si x D, on a h(x) (x) = uK+1 (x). On en dduit que h uK pour tout K , d'o h uD + uD en passant la limite. Nous avons vu que la positivit ne susait pas en gnral pour obtenir l'unicit. Il est donc ncessaire d'introduire des hypothses supplmentaires. Un rsultat gnral d'unicit est le thorme suivant.
existe une solution borne de l'quation de Poisson, celle-ci est ncessairement gale uD + uD .
On se donne une solution h borne, et on utilise le thorme 6 pour dduire le fait que
n1 k=0
Preuve :
Mn := h(XT n ) h(X0 ) +
est une martingale. On a donc Ex (Mn ) = Ex (M0 ) = 0, d'o le fait que, pour tout x S,
(T 1)K
h(x) = Ex (h(XT K )) + Ex
k=0
c(Xk ) .
Lorsque K tend vers l'inni, le premier terme du membre de droite de l'quation ci-dessus converge vers Ex (h(XT )), par convergence domine, du fait que h est suppose borne et T ni presque srement. Comme h sur D, Ex (h(XT )) =
72
Ex ((XT )) = uD (x). Le deuxime terme du membre de droite de l'quation ciT 1 dessus converge, quant lui, vers Ex k=0 c(Xk ) = uD (x), par convergence monotone, en utilisant l'hypothse que c 0. On en dduit nalement que h(x) = uD (x) + uD (x).
Corollaire 11 SI l'ensemble
S est ni et si le noyau est irrductible, l'quation de Poisson possde toujours une unique solution donne par uD + uD .
On note que le thorme ne garantit pas en gnral l'existence de solutions bornes : sous les hypothses du thorme, il existe une solution borne si et seulement si uD + uD est borne. Du fait que la valeur sur la frontire est impose par l'quation, il ne peut exister de solution borne que si la condition au bord est elle-mme borne. Dans ce dernier cas, on voit, partir de la dnition, que uD est automatiquement borne, ce qui ramne la question de l'existence de solutions bornes l'tude du caractre born ou non de uD . En particulier, si l'on considre le problme de Dirichlet, uD 0, et l'on a donc le rsultat suivant.
Corollaire 12 Lorsque
est borne, le problme de Dirichlet possde une et une seule solution borne, donne par uD .
En revanche, lorsque c n'est pas identiquement nulle, il est possible qu'il n'existe aucune solution borne de l'quation (rappelons qu'il sut de vrier que uD n'est pas borne pour que cela soit le cas). C'est bien entendu le cas si c n'est pas borne, car l'existence d'une solution borne de l'quation entrane automatiquement, par dirence, que c doit tre borne, mais il est possible qu'il n'existe pas de solution borne mme si c l'est.
Exercice 98 Donner un exemple pour lequel uD n'est pas borne bien que c le soit.
Par ailleurs, on note que, si l'on supprime l'hypothse que la probabilit d'absorption par la frontire est gale 1, le rsultat d'unicit du thorme tombe en dfaut. En eet, en prenant 1 et c 0, on voit que uD (x) := Px (T < +), et que uD n'est pas constante car uD vaut 1 sur D et l'on suppose qu'il existe un x D tel que uD (x) < 1. Comme la fonction constante gale 1 est aussi une solution borne, on n'a pas unicit. L'exercice suivant fournit une preuve alternative l'unicit dans le cas o l'ensemble S est ni, en s'appuyant sur une version discrte du principe du maximum pour les fonctions harmoniques (stricto sensu, il s'agit plutt un principe du minimum pour les fonctions sur-harmoniques).
73
et un noyau p sur S tel que Px (T < +) = 1 pour tout x D. On suppose que h : S R vrie h(x) ph(x) pour tout x D, et h(x) 0 sur D. Nous cherchons montrer que le minimum de h sur S est ncessairement atteint sur D. Pour cela, on considre x tel que h(x ) = min h, et l'on suppose que x D. On introduit ensuite D0 := {x }, et on dnit par rcurrence, pour tout i 1, Si := {y S; x Di1 , p(x, y) > 0}. 1) Montrer que, pour tout i, h est constante sur Si gale min h. 2) Montrer qu'il existe ncessairement i 0 tel que Si D = . 3) Conclure que le minimum de h est atteint sur D. 4) En dduire qu'il ne peut exister qu'une solution l'quation de Poisson.
o 0 < < 1 est un nombre rel x, et c : S R est une fonction donne. Montrer que, si l'on suppose c borne, l'unique solution de l'quation est fournie par la formule
+
u(x) := Ex
n=0
n c(Xn ) .
et un noyau p sur S tel que Px (T < +) = 1 pour tout x D. On suppose que h : S R vrie h(x) ph(x) pour tout x D, et h(x) 0 sur D. Nous cherchons montrer que le minimum de h sur S est ncessairement atteint sur D. Pour cela, on considre x tel que h(x ) = min h, et l'on suppose que x D. On introduit ensuite D0 := {x }, et on dnit par rcurrence, pour tout i 1, Si := {y S; x Di1 , p(x, y) > 0}. 1) Montrer que, pour tout i, h est constante sur Si gale min h. 2) Montrer qu'il existe ncessairement i 0 tel que Si D = . 3) Conclure que le minimum de h est atteint sur D. 4) En dduire qu'il ne peut exister qu'une solution l'quation de Poisson.
74
appelons TA le temps d'atteinte de A et TB le temps d'atteinte de B . Pour tout x S , posons u(x) := Px (TA < TB ). On a donc u 1 sur A et u 0 sur B . En posant D := S \ (A B), montrer que u est harmonique sur D, i.e. (pf )(x) = f (x) pour tout x B . Que peut-on dire du caractre (sur-, sous-)harmonique de u sur S tout entier ?
A de S , appelons TA le temps d'atteinte de A. Pour tout x S , posons v(x) := Ex (TA ). On a donc v 0 sur A. En posant D := S \A, montrer que u vrie l'quation v(x) = pv(x)+1 pour tout x D.
Exercice 104 Etant donn un ensemble ni S , proposer une mthode permettant
au noyau dnie par p(x, x + 1) = et p(x, x 1) = 1 pour tout x Z, avec 0 < < 1. Etant donn a, b Z tels que a < b, on dnit T comme le temps d'atteinte de l'ensemble {a, b}, soit T := inf{n 0; Xn {a, b}}. 1) Montrer (lmentairement) que, partant de a x b, Px (T < +) = 1 et mme Ex (T ) < +. 2) En rsolvant l'quation de Poisson associe, donner, pour tout a x b la valeur de Ex (T ), et de Px (XT = a) et Px (XT = b). 3) En faisant tendre a ou b vers , retrouver le critre de rcurrence/transience de la marche. Dans le cas transient, comment s'exprime la probabilit de revenir en un point ? 4) Retrouver ces rsultats en faisant directement appel aux martingales suivantes :
[Xn n(2 1)]n0 , 1
Xn n0 2 pour = 1/2, Xn n n0
Exercice 105 (La ruine du joueur) On considre la marche simple sur Z, associe
pour = 1/2.
Quel rapport ces martingales entretiennent-elles avec la rsolution de l'quation de Poisson de la question 2) ?
T (0) le premier temps d'atteinte de 0. Pour 1/2, et x 1, donner la valeur de Ex (exp(T )) pour tout > 0.
un noyau de transition dni sur N, tel que p(x, y) est nul moins que y {x 1, x, x + 1}. On introduit les notations x := p(x, x 1) (avec la convention 0 := 0), x := p(x, x + 1) et x := p(x, x).
75
1) A quelle condition sur les , , le noyau est-il irrductible sur N ? On introduit la fonction g dnie sur N par
n1 m
g(n) :=
m=0 j=1
j . j
Avec les conventions usuelles = 0 et = 1, on constate que g(0) = 0 et g(1) = 1. 2) Pour tous a, b N tels que a < b, et tout a x b, montrer que
Px (T (a) < T (b)) = g(b) g(x) , g(b) g(a) g(x) g(a) . g(b) g(a)
et
Px (T (b) < T (a)) =
3) En dduire que, sous l'hypothse que le noyau est irrductible, il y a rcurrence si et seulement si
+ m m=0 j=1
j = +. j
Est-il surprenant que les j n'interviennent pas dans ce critre ? 4) Dans le cas transient, comment s'exprime P0 (T (0) < +) ? 5) Discuter de la rcurrence/transience lorsque j 0 et que j est de la forme j = 1/2 + j avec j Aj u pour A, u > 0.
76 Dans le cas d'une mesure de probabilit invariante, on parle plus volontiers de loi invariante. Deux mesures invariantes triviales sont la mesure constamment gale 0 et la mesure constamment gale +. Toute autre mesure invariante sera dite nontriviale. Par ailleurs, nous appellerons propre une mesure positive sur S qui vrie 0 < (x) < + pour tout x S . On a en fait le rsultat suivant.
Supposons qu'il existe x tel que (x) = 0. Par sous-invariance, on a, pour tout n 0, yS (y)pn (y, x) (x). Par positivit de , on a donc (y) = 0 ds que pn (y, x) = 0. Par irrductibilit, pour tout y S existe un n tel que ce soit le cas. On raisonne de mme en supposant que (x) = + pour un x. Avant de donner davantage de dtails, mentionnons ds maintenant quelques consquences, immdiates, mais importantes, de l'existence d'une mesure de probabilit invariante.
Preuve :
Proposition 29 Si
77
tout nombre rel s 1, et tout f Ls (), pf est bien dni et ni, et pf Ls (). De plus, l'action sur les fonctions
p : Ls () Ls ()
f Ls () avec
Concernant l'action sur les mesures, notons tout d'abord que l'invariance de signie que est un vecteur propre associ la valeur propre 1, par exemple pour l'action sur 1 (S). (Noter que la fonction constante gale 1 est, quant elle, un vecteur propre associ l'action duale sur les fonctions de (S).) Enonons maintenant une contrepartie la proposition 30 pour l'action ( gauche) de p sur les mesures. En fait, on fait agir p gauche sur la densit des mesures par rapport .
alors (p) est bien dni, et (p)/ Ls (). L'action correspondante de p de Ls () dans lui-mme dnit un oprateur linaire continu et de norme 1.
On a galement le corollaire :
3.2.1 Renvers dans le temps d'un noyau par rapport une mesure invariante
Etant donn un noyau de transition irrductible p, et une mesure invariante nontriviale de p, le noyau renvers dans le temps de p par rapport est dni, pour tous x, y S , par :
p(x, y) = p(y, x) (y) . (x)
(3.11)
78
p est un noyau de transition irrductible vriant la proprit suivante : pour toute suite x0 , . . . , xn d'lments de S (x0 )p(x0 , x1 ) p(xn1 , xn ) = (xn )(xn , xn1 ) p(x1 , x0 ). p
Exercice 110 Prouver la proposition ci-dessus. Proposition 33 Avec les notations ci-dessus, est invariante pour p, et le renvers
dans le temps de p par rapport n'est autre que p.
Exercice 111 Prouver la proposition ci-dessus. Exercice 112 On considre un noyau de transition irrductible p possdant une loi
de probabilit invariante . 1) Prouver que, pour tout n 0, la loi de (Xn , . . . , X0 ) sous P,p est identique la loi de (X0 , . . . , Xn ) sous P,. p 2) Montrer que, tant donne une chane de Markov (Xn )n0 de loi initiale et de noyau de transition p, il est possible, quitte enrichir l'espace de probabilit sousjacent, de dnir une suite de variables alatoires (Xn )n0 telle que (Xn )nZ soit une chane de Markov de noyau de transition p (i.e. telle que toute sous-suite nie (Xn )anb soit une telle chane de Markov).
Preuve :
(y) = (y)
p(y, x)
yS
p(y, x)(y).
yS
79
Exercice 113 Prouver la proposition 31 ainsi que son corollaire partir de la proposition 30 et de la dualit ci-dessus.
Comme consquence, on obtient par exemple la dualit suivante entre fonctions (sur-)harmoniques et mesures (sous-)invariantes.
Proposition 36 Etant donn une fonction positive g telle que 0 < g(x) < + pour
tout x S , il y a quivalence entre les deux proprits suivantes : g est harmonique (resp. sur-harmonique) pour p la mesure dnie sur S par (x) := g(x)(x) est invariante (resp. sous-invariante) pour p.
Consquence directe de la proposition 35.
Preuve :
1(Xi = x) =
(3.12)
et notons que
cycle (a) = 1. a
tive dnie sur S par cycle := GD (a, ) est non-triviale et invariante pour p(, ). a
Preuve :
En vertu de la section prcdente, nous savons dj que cycle p(y) = cycle (y) a a pour tout y S \ {a}. Par ailleurs, l'identit (3.10) montre que la validit de l'identit pour y = a quivaut la validit de l'identit pour la fonction duale, soit
80
p [GD (, a)] (a) = GD (, a). Rappelons l'expression de GD (x, y) pour x D / et y D : Px (XT = y, T < +) ,
o, dans notre contexte, T est le premier temps d'atteinte de a. Du fait de la rcurrence de la chane, on a ncessairement que XT = a avec probabilit 1, d'o le fait que GD (, a) est la fonction constante gale 1. La fonction GD (, a) est donc videmment harmonique, ce qui entrane le rsultat voulu. On note que la preuve nous permet de comprendre pourquoi on choisit un ensemble D rduit un seul point : c'est le moyen de garantir le fait que la fonction GD (, a) est harmonique sur S tout entier et pas seulement sur D.
de cycle est satisfaite partout, sauf en a. En a, on a cycle (a) = 1 tandis que a a cycle cycle a p(a) = Pa (T1 < +) < 1. La mesure a n'est donc pas invariante, mais sous-invariante.
Proposition 39 La masse totale de cycle n'est autre que Ea (T1 (a)). Par consquent, a
cycle est de masse totale nie si et seulement si a est rcurrent positif. a
La proposition ci-dessus donne une manire simple de vrier que, si S est ni, toute chane irrductible est positivement rcurrente. Aprs la question de l'existence vient naturellement celle de l'unicit des mesures invariantes. Nous commenons par traiter le problme pour les fonctions (sur)harmoniques, pour lesquelles les techniques de martingale fournissent une preuve lgante.
Soit f une fonction sur-harmonique positive pour p. En considrant l'espace canonique des trajectoires, on en dduit que, pour tout b S , la suite [f (Xn )]n0 est une sur-martingale positive par rapport la ltration (Fn )n0 et la probabilit Pb . Le thorme de convergence de Doob entrane donc que f (Xn ) converge presque srement dans R lorsque n tend vers l'inni. En appelant L la limite (alatoire) de cette martingale, et en notant le fait que tout lment de S est, par irrductibilit et rcurrence de p, visit une innit de fois, on obtient que L = f (x) pour tout x, et donc que f est une fonction constante. On note que ce rsultat n'est pas vrai en gnral si l'on s'autorise considrer
Preuve :
81
des fonctions de signe quelconque. Par exemple, toutes les fonctions anes sont harmoniques pour la marche simple symtrique sur Z, qui est pourtant rcurrente. Nous pouvons prsent noncer la contrepartie du rsultat ci-dessus pour les mesures.
p(, ) est irrductible et rcurrent, cycle est, une constante a multiplicative prs, l'unique mesure sous-invariante non-triviale, a tant choisi arbitrairement dans S . (Rappelons que, dans ce cas, cycle n'est pas seulement sousa
Proposition 41 Si
Preuve :
Considrons le noyau p renvers dans le temps de p par rapport cycle , et soit a une mesure invariante non-triviale (et donc propres) . La fonction g dnie sur S par g(x) = (x)/cycle (x) est, d'aprs les propositions prcdentes, sur-harmonique a pour p Comme p est rcurrent, p l'est aussi et, par consquent, g doit tre constante. cycle Par consquent, et a sont proportionnelles. Pour une preuve lmentaire, voir par exemple [18]). En particulier, on voit que, pour une chane rcurrente, toutes les mesures de la forme cycle , a dcrivant S , sont en fait proportionnelles les unes aux autres. a
Exercice 114 (Saines lectures) Lire les preuves lmentaires (sans martingales)
prsentes dans [18, 7] de l'unicit d'une mesure invariante non-triviale pour un noyau rcurrent.
Pour faire une petite synthse de ce qui prcde :
l'unicit ( une constante multiplicative prs) d'une mesure invariante non-triviale. Le fait que cette mesure soit de masse nie est quivalent au fait que la chane soit positivement rcurrente.
On retrouve ainsi que, pour une chane irrductible, la rcurrence positive d'un point entrane celle de tous les autres points : la rcurence positive (i.e. le fait que Ex (T1 (x)) < +) d'un point entrane la rcurrence de la chane. Par consquent, toutes les cycle sont proportionnelles cycle (et propres), donc Ea (T1 (a)) < + a x pour tout a. On retrouve galement le fait que toute chane irrductible sur un espace d'tats ni est positivement rcurrente. Dans ce cas, la recherche d'une mesure de probabilit invariante se ramne la rsolution d'un systme linaire de taille nie, que l'on peut, si ses dimensions restent raisonnables, rsoudre l'aide d'un ordinateur (Google utilise par exemple la mesure invariante de la chane de Markov dnie l'exercice 19
82 pour mesurer la popularit d'une page ouaibe, celle-ci tant rgulirement recalcule en rsolvant un systme linaire dont la taille tait, en 2002, de l'ordre de 109 109 ). On a galement le rsultat suivant (qui est galement une consquence des rsultats asymptotiques bass sur le thorme de renouvellement, que nous verrons plus loin) :
Preuve :
Soit ladite mesure de probabilit. L'invariance s'crit xS (x)pn (x, y) = (y). En sommant, on obtient que xS (x) n1 pn (x, y) = +. Rappelons toutes ns utiles que n1 pn (x, y) = Ex (N (y)). Or, pour x = y , Ex (N (y)) Ey (N (y)) + 1 (par exemple par couplage, ou alors, formule exacte de la proposition 8). Ainsi, xS (x)(Ex (N (y)) + 1) = +. Comme est une mesure de probabilit, on en dduit que Ex (N (y)) = +. Par consquent, p est rcurrent. Par unicit des mesures invariantes non-triviales, concide forcment avec cycle a cycle normalise 1. Par consquent, a est de masse nie, donc Ea (T1 (a)) est nie, et la chane est positivement rcurrente.
riante ,
Corollaire 15 Si p est un noyau irrductible possdant une loi de probabilit inva(x) = cycle (x) a . Ea (T1 (a))
Nous retrouverons cette formule de manire dirente dans la preuve par renouvellement des thormes limites. On retient, entre autres choses, de ce qui vient d'tre dit, que l'existence d'une loi de probabilit invariante quivaut (pour une chane irrductible) la rcurrence positive, la loi de probabilit invariante tant alors unique. Une question naturelle est alors de savoir si l'existence et l'unicit d'une mesure invariante non-triviale caractrisent la rcurrence, et la rponse est ngative, comme le montre l'exemple suivant.
N avec rexion en 0) On considre le noyau de transition sur N suivant : pour i 1, p(i, i 1) = p, p(i, i + 1) = 1 p, et
83
p(0, 1) = 1. On voit facilement en crivant les quations qu'il existe, une constante multiplicative prs, une unique mesure invariante non-triviale, donne par (i) =
pour i = 0 et (0) = p. Pour p > 1/2, la chane est transiente (par comparaison avec la marche simple non rchie, qui est transiente par la loi des grands nombres, et a donc une probabilit positive de ne jamais revenir en 0 en partant par la droite). Pour p < 1/2, la mesure obtenue est de masse nie, et on en dduit la rcurrence positive. Le cas p = 1/2 est rcurrent (comparaison avec la marche alatoire non-rchie, ou calcul direct).
1p p
i1
On peut en fait caractriser la rcurrence en considrant les mesures sous-invariantes plutt qu'invariantes. On obtient alors le rsultat suivant.
Preuve :
La preuve du fait que cycle est l'unique mesure non-triviale sous-invariante dans a le cas rcurrent a dj t faite plus haut. Inversement, supposons que p est transient, et considrons le renvers dans le temps de p par rapport cycle , dni par la formule a cycle 3.11. Comme a n'est que sous-invariante, la formule donnant, p ne dnit plus un noyau de transition, mais un sous-noyau de transition. Plus prcisment, pour x = a, on a bien l'galit yS p(a, y) = Pa,p (T1 (a) < yS p(x, y) = 1, mais +) < 1. Pour remdier ce problme, on adjoint un tat S , en dnissant p(a, ) = 1 yS p(a, y), et l'on pose p(, ) = 1. On dnit bien ainsi un noyau de transition sur S {}. A prsent, considrons u S dirent de a (S doit tre inni pour qu'il puisse y avoir transience, donc on peut bien toujours trouver un tel u), et la fonction dnie sur S{} par gu (x) = Px,(T1 (u) < +) pour x = u, et gu (u) = 1. On vrie que gu p est sur-harmonique par rapport p. Qui plus est, gu n'est pas constante, car gu (u) = 1 tandis que, du fait de la prsence du point absorbant , Pa,(T1 (u) < +) < 1. On p vrie alors que cycle et la mesure dnie par (x) = gu (x)cycle (x) sont deux a a mesures non-triviales et sous-invariantes distinctes. Les arguments utiliss pour prouver la proposition prcdente permettent facilement de prouver la caractrisation "duale" suivante :
84 Pour une chane irrductible transiente il existe donc toujours au moins deux mesures sous-invariantes non-triviales. Pour ce qui est de l'existence et de l'unicit d'une mesure invariante non-triviale, toutes les situations sont possibles (pas de mesure invariante, une unique mesure invariante, plusieurs mesures invariantes), comme le montrent l'exercice 115, ainsi que les deux premiers exercices ci-dessous. Des conditions ncessaires et susantes concernant l'existence d'une mesure invariante pour les chanes transientes peuvent tre trouves dans les articles [26, 52].
vant : pour i 0, p(i, i + 1) = i , et p(i, 0) = 1 i , o 0 < i < 1 pour tout i. L'irrductibilit de la chane est immdiate. Partant de l'origine, la probabilit de ne jamais y revenir est gale au produit = + i . Par consquent, la chane est i=0 rcurrente si = 0, et transiente si > 0. Etudions l'existence de mesures invariantes non-triviales pour p. L'invariance s'crit, pour tout i 0, (i + 1) = i (i). Par consquent, p possde au plus une mesure invariante non-triviale, qui doit vrier (i) = i1 i (0). En 0, l'invariance s'crit (0) = + (i)(1 i ). Donc i=0 j=0 (0) = (0) + (1 i ) i1 i (avec la convention = 1), d'o, par tlescoj=0 i=0 page, (0) = (1 )(0). Par consquent, si > 0, il ne peut y avoir de mesure invariante non-triviale.
N sui-
noyau de transition sur Z suivant : pour tout i, p(i, i 1) = p, p(i, i + 1) = 1 p. La mesure constante est invariante par p. C'est galement le cas de la mesure dnie i par (i) = 1p . Pour p = 1/2, on a donc au moins deux mesures invariantes p non-triviales, et c'est galement une manire de dduire la transience. Au passage, on note que, sachant que le cas p = 1/2 est rcurrent, le fait que l'on ait trouv une mesure invariante de masse innie entrane automatiquement que la chane doit tre rcurrente nulle. alatoire sur le groupe Zd ? (Indication : utiliser la transformation de Fourier.) Qu'en conclure quant la rcurrence/transience ?
Exercice 118 (Marche alatoire simple avec (ou sans) biais sur Z) On considre le
Exercice 119 Peut-il exister des mesures de probabilit invariantes pour une marche
un processus de naissance et de mort irrductible sur N (voir l'exercice 107 pour les notations et les dnitions). 1) Montrer que l'on dnit une mesure invariante en posant
n
(n) :=
j=1
j1 . j
85
2) Montrer qu'il existe une probabilit invariante si et seulement si est de masse nie. Est-il surprenant que les j n'interviennent pas dans ce critre ? 2) Discuter la rcurrence nulle/positive dans le cas o j 0 et j est de la forme j = 1/2 + j avec j Aj u pour A, u > 0.
3.2.3 Rversibilit
Dnition 7 Etant donne un noyau p sur un ensemble ni ou dnombrable S , on
dit qu'une mesure positive sur S est rversible vis--vis de p si, pour tous x, y S ,
(x)p(x, y) = (y)p(y, x).
On dit que p est rversible lorsqu'il existe une mesure positive non-triviale rversible.
Preuve :
On crit que (p)(x) = yS (y)p(y, x). D'un autre ct, (x) = yS (x)p(x, y). La rversibilit signie donc que l'on a galit terme--terme entre ces deux sommes.
dessus, on appelle parfois en anglais la condition dnissant la rversibilit detailed balance condition, par opposition la condition dnissant l'invariance, qui n'est que la balance condition.
la notion vague d'quilibre associe une mesure de probabilit invariante. Si une mesure invariante est rversible, on observera, en initialisant la chane avec cette loi, autant de transitions en moyenne de x vers y que de y vers x, pour tout couple x, y d'lments de S . Lorsqu'une loi invariante n'est pas rversible, cette proprit n'est plus vrie, mais cela ne signie pas qu'il n'y a pas quilibre, puisque, en initialisant la chane avec cette loi, la probabilit d'observer un lment x donn est la mme, quelque soit le nombre de pas considr.
Z/nZ dnie, pour tout n 2 et 0 < p < 1, par la loi suivante des incrments : +1 avec probabilit p, 1 avec probabilit (1 p), +0 avec probabilit 1/2. Montrer que le noyau est rversible pour pour p = 1/2, et non-rversible pour p = 1/2.
86
peut conduire des systmes linaires diciles rsoudre. En revanche, la recherche d'une mesure rversible, si elle existe, est nettement plus facile, puisque l'on peut la calculer de proche en proche ! En particulier, pour un noyau irrductible, il ne peut exister au plus qu'une mesure rversible non-triviale, une constante multiplicative prs.
Exercice 122 Donner un exemple d'un noyau pour lequel il existe deux mesures
invariantes non-triviales distinctes dont l'une est rversible et l'autre ne l'est pas.
Voici maintenant quelques caractrisations simples, mais importantes, de la rversibilit d'un noyau.
n 2 et toute suite (x1 , . . . , xn ) S n vriant xn = x1 , on a l'identit : p(x1 , x2 ) p(xn1 , xn ) = p(xn , xn1 ) p(x2 , x1 ).
Le fait que la rversibilit entrane la condition est immdiat. Rciproquement, il sut de xer un point arbitrairement, disons a, et une valeur strictement positive arbitraire pour (a), puis d'tendre tout x de la manire suivante : tant donn x S , il existe par irrductibilit un chemin de probabilit strictement positive x1 , . . . , xn tel que x1 = a et xn = x. On pose alors
(x) := (a) p(x1 , x2 ) p(xn1 , xn ) . p(xn , xn1 ) p(x2 , x1 )
Preuve :
On vrie que est eectivement rversible. On note que, pour un noyau irrductible, la rversibilit entrane que p(y, x) > 0 ds que p(x, y) > 0. Cette remarque fournit un argument simple permettrant de montrer que certains noyaux ne sont pas rversibles.
est rversible si et seulement si le renvers dans le temps p de p par rapport est gal p.
Preuve :
Immdiat.
Corollaire 19 Si est une loi rversible pour p, alors, par rapport la probabilit
P , les lois de (X0 , . . . , Xn ) et de (Xn , . . . , X0 ) sont identiques.
87
est la loi invariante d'un noyau irrductible et positivement rcurrent, l'adjoint de p vu comme un oprateur linaire de L2 () dans lui-mme n'est autre que p. Dans ce contexte, la rversibilit de signie que p est un oprateur
Proposition 49 Si
auto-adjoint.
Pour vrier la rversibilit d'une marche alatoire sur un graphe, il sut par exemple de vrier le critre de la proposition 47 portant sur les boucles. D'autre part, tant donn un noyau irrductible p possdant une mesure rversible , on vrie qu'il sut de poser w(x, y) = (x)p(x, y) pour dnir une pondration correspondant p.
Preuve :
orient associ une pondration w, la mesure rversible non-triviale est fournie ( une constante multiplicative prs) par la formule
(v) :=
v ;{v,v }E
Exercice 124 Prouver que, dans le cas d'une marche alatoire sur un graphe non-
w({v, v }).
Quelle forme prend cette expression dans le cas d'une marche alatoire pour laquelle tous les poids sont gaux 1 ?
Les chanes de Markov rversibles forment une catgorie particulire de chanes de Markov, pour l'tude desquelles des techniques nombreuses et varies, exploitant de manire importante la rversibilit, peuvent tre utilises. Nous ne ferons pas un expos systmatique des techniques propres au cas rversible, renvoyant pour cela [1]. Pour ne mentionner que deux de ces techniques, citons l'analogie avec les rseaux lectriques, prsente par exemple de manire trs simple et trs claire dans le splendide petit ouvrage [17], et l'utilisation du caractre autoadjoint de l'action de l'oprateur p dans L2 .
88
ni ou dnombrable S , dont la loi invariante est note . Le but de cet exercice est de prouver l'identit suivante, valable pour tout x S , et tout n 1 :
P (T1 (x) = n) = (x)Px (T1 (x) n).
1) Vrier l'identit pour n = 1. Quelle identit obtient-on en sommant sur toutes les valeurs de n ? 2) Montrer que, pour tout n 2,
P (T1 (x) = n) =
y=x
3) En dduire que
P (T1 (x) = n) =
yS
puis que
P (T1 (x) = n) = P (T1 (x) = n 1) (x)Px (T1 (x) = n 1).
P (T1 (x) = n) =
j=n
5) Conclure.
Quelques consquences de l'exercice prcdent gurent dans l'exercice ci-dessous.
dessus. Utiliser le rsultat de cet exercice pour traiter les questions suivantes. 1) Donner un exemple de noyau positivement rcurrent pour lequel il existe un x vriant E (T1 (x)) = +. 2) Montrer que les conditions suivantes sont quivalentes : (i) Il existe x S tel que Ex (T1 (x)2 ) < + ; (ii) Il existe x S tel que E (T1 (x)) < + ; (iii) Pour tout x S , E (T1 (x)) < + ; (iv) Pour tout x S , Ex (T1 (x)2 ) < +. (Indication : pour (ii) (iii), utiliser le Corollaire 8.
Exercice 126 On se place sous les mmes hypothses que dans l'exercice 125 ci-
89
un ensemble S ni, on cherche prouver directement l'existence et l'unicit d'une mesure de probabilit invariante. 1) Soit le vecteur de RS dont toutes les coordonnes sont gales 1. Montrer que 1 p = . 1 1 2) En dduire l'existence d'un vecteur non-nul x = (xs )sS RS tel que xp = x. 3) Prouver que, pour un tel vecteur, le vecteur |x| := (|xs |)sS vrie galement |x|p = x. (Montrer d'abord que |x|p |x| coordonnes par coordonnes, puis sommer). 4) Conclure quant l'existence d'une probabilit invariante. 5) A prsent, considrons x = (xs )sS RS tel que px = x. En considrant s tel que xs = maxsS xs , montrer que toutes les coordonnes de x sont constantes. (C'est une version du principe du maximum.) Comparer le plan de cette preuve avec celle donne dans le cas gnral. pour tout i 1, p(i, i 1) = pi et p(i, i + 1) = 1 pi . Etudier les mesures invariantes de ce noyau (existence, unicit, nitude).
G = (V, E) telle
w(e)
est invariante.
transition p sur S , irrductible et positivement rcurrent. Montrer que, si p est invariant sous l'action de f , c'est galement le cas de la loi invariante de p.
Considrons un ensemble ni S et un noyau de transition irrductible p sur S . Il existe donc une unique loi invariante sur S . Considrons prsent le graphe orient G = (V, E) obtenu en posant V = S et E = {(x, y); p(x, y) > 0}. Etant donn x S , un sous-graphe T de G sera appel arbre couvrant de G enracin en x s'il ne contient pas de cycles et si chaque lment de V \ {x} est le sommet initial d'une et une seule arte de T . Nous noterons T (x) l'ensemble des arbres couvrants enracins en x, et T := xS T (x) l'ensemble de tous les arbres couvrants de G. A tout T T , on associe un poids p(T ) dni de la manire suivante :
p(T ) :=
(x,y)E(T )
Exercice 131 (Thorme arbre-matrice pour les chane de Markov, d'aprs [3])
p(x, y),
90
o E(T ) dsigne l'ensemble des artes de T . L'objectif de cet exercice est d'tablir la remarquable formule suivante pour la loi invariante de p : pour tout x S ,
(x) =
T T (x) p(T ) T T
p(T )
Plusieurs preuves de ce rsultat existent. Celle qui suit fournit une interprtation probabiliste intressante. On considre (voir l'exercice 112) le prolongement d'une chane de Markov (Xn )n0 de loi initiale et de noyau p en une chane de Markov (Xn )nZ . On dnit ensuite pour tout n 0 une variable alatoire Tn valeurs dans T de la manire suivante. La racine de Tn est choisie gale Xn . Pour x S , on dnit Sn (x) := sup{k n 1; Xk = x}, et les artes prsentes dans Tn sont exactement les artes de la forme (XSn (x) , XSn (x)+1 ), x dcrivant S . 1) Montrer que Tn est bien dni, et mesurable par rapport la tribu engendre par les (Xi )<in . 2) Montrer que l'on passe de Tn Tn+1 de la manire suivante : on ajoute l'arte (Xn , Xn+1 ) et l'on supprime l'unique arte issue de Xn+1 . (Faire un dessin !) En appelant Yn l'extrmit de cette arte supprime, montrer que (Xn , Xn+1 ) est l'unique arte de Tn+1 se terminant en Xn+1 et que l'on peut atteindre partir de Yn en suivant les artes de Tn+1 3) Quelle est la loi de Xn+1 conditionnellement T0 , . . . , Tn ? 4) Montrer que la suite (Tn )n0 est une chane de Markov, irrductible sur T . Nous noterons q son noyau de transition. 5) On dnit le noyau de transition q sur T de la manire suivante : partant d'un arbre T enracin en x, q (T, ) est la loi de l'arbre obtenu en choisissant un sommet y selon la loi p(x, ), puis en ajoutant T l'arte (x, y) et en supprimant l'unique arte se terminant en x et que l'on peut atteindre partir de y en suivant les artes de T . Montrer que, pour tous T, T T ,
p(T )q(T, T ) = p(T )q (T , T ).
6) En dduire que la loi invariante de q est, une constante multiplicative prs, gale p, et que q est le noyau renvers dans le temps de q par rapport cette loi. 7) Conclure.
pas d'autres pices, en choisissant uniformment au hasard chaque pas l'une des positions autorises par sa rgle de dplacement (deux cases le long d'un axe, une le long de l'autre). 1) Montrer que la suite des positions occupes par le cavalier constitue une chane de Markov irrductible.
91
2) Montrer que cette chane est rversible. Quelle est sa loi invariante ? 3) En dduire la moyenne du temps de retour du cavalier en son point de dpart.
Exercice 133 Montrer que la chane de Markov associe l'urne d'Ehrenfest (voir
l'exercice 16) est rversible. Quelle est la loi invariante associe ?
Exercice 134 Montrer que la chane de Markov dcrite dans l'exercice 18 est rversible. Quelle est la loi invariante associe ?
On considre une marche alatoire sur un arbre de Galton-Watson enracin. Rappelons qu'un arbre de Galton-Watson est construit de la manire suivante : tant donne une loi de reproduction sur N, on attribue d'abord la racine un nombre alatoire d'enfants de loi , qui forment le premier niveau de l'arbre. Ensuite, tant donn le nme niveau de l'arbre, on attribue indpendamment chaque sommet de ce niveau un nombre alatoire d'enfants de loi , pour former le n + 1-me niveau. Un tel arbre alatoire tant construit, on considre ensuite la marche alatoire sur le graphe correspondant, obtenue en attribuant chaque arte un poids constant gal 1. Il s'agit donc d'une marche alatoire en milieu alatoire, le milieu alatoire tant fourni par la structure alatoire de l'arbre sur lequel la marche volue. Notons T l'arbre de Galton-Watson alatoire considr, et (Xn )n0 la marche alatoire sur T correspondante, initialise en la racine. Si x dsigne un sommet de T , nous noterons T (x) l'arbre obtenu en dplaant la racine de T en x. Avec cette notation, la notion d'environnement vu de la marche est donne par la suite d'arbres alatoires (T (Xn ))n0 . Nous noterons T l'ensemble des arbres localement nis (i.e. pour lesquels chaque sommet possde un nombre ni d'enfants enracins), deux arbres tant considrs comme identiques s'ils ne dirent que par un r-tiquetage des sommets prservant la racine, muni de la tribu engendre par les sous-arbres nis issus de la racine. 1) Montrer que la suite de variables alatoires (T (Xn ))n0 est une chane de Markov sur T . (Attention : on ne travaille pas conditionnellement la ralisation de T , mais en tenant compte de l'ala engendrant T et de celui engendrant la marche.) 2) On dnit une probabilit Q sur T de la manire suivante : on attribue la racine un nombre alatoire d'enfants de loi + dnie par + (n) := (n + 1) pour tout n N, puis on continue la construction comme pour l'arbre de Galton-Watson T , en utilisant la loi pour gnrer les nombres d'enfants de tous les sommets issus de la racine. Montrer1 que Q est rversible pour (T (Xn ))n0 .
Attention : il faut d'abord trouver la gnralisation adquate de la rversibilit dans le cas d'un espace mesurable gnral.
1
92
3) Supposons que l'esprance de est infrieure ou gale 1. L'arbre T est donc ni avec probabilit 1. Quelle est la loi stationnaire de la marche alatoire conditionnellement T ? Comment ce rsultat se compare-t-il au rsultat de la question prcdente ?
(Xn )n0 est une chane irrductible et positivement rcurrente, montrer que, pour tout p 1, c'est galement le cas de la chane (Zn )n0 := (Xn , , Xn+p )n0 (en dnissant convenablement l'espace d'tats). Comment s'exprime la loi invariante associe en fonction de celle de (Xn )n0 ?
Exercice 136 Si
Exercice 137 Le but de cet exercice est de montrer que, si (Xn )n0 est une chane
de Markov irrductible positivement rcurrente, la suite des lois des Xn est tendue, c'est--dire que, pour tout > 0, il existe un sous-ensemble ni A S tel que, pour tout n, P (Xn Ac ) . (Ici, ce sont les sous-ensembles nis de S qui jouent le rle des partie compactes dans la dnition de la tension.) Nous noterons p le noyau de transition de la chane, et la loi invariante. 1) En utilisant l'invariance de , montrer que, pour tout > 0, on peut trouver un sous-ensemble ni A S tel que, pour tout x S , et tout n 0, x (x)pn (x, Ac ) . 2) Montrer que, pour tout x S , et tout n 0, P (Xn Ac ) P (T1 (x) n) + /(x). 3) Conclure.
Preuve :
Comme est invariante, pn = , et l'on voit que, pour tout , on dispose de A tel que x (x)pn (x, Ac ) pour tout n, d'o, en xant x, pn (x, Ac ) /(x) pour tout n. Ainsi, en utilisant la proprit de Markov, on voit que P (Xn Ac ) P (T1 (x) n) + pn (x, Ac ). La conclusion en rsulte.
Chapitre 4
Fonctionnelles additives : loi des grands nombres
Etant donne une fonction f de S dans R, et une chane de Markov (Xn )n0 , on parle de fonctionnelle additive de la chane pour dsigner les sommes partielles de la forme Sn (f ) = f (X0 )+. . .+f (Xn ). La connaissance du comportement asymptotique de quantits du type Sn (f ) lorsque n tend vers l'inni fournit de prcieux renseignements sur les proprits en temps longs des trajectoires de la chane. Pour prendre un exemple trs simple, si f = 1A est la fonction indicatrice d'un sous-ensemble A S , Sn (f ) n'est autre que le nombre de visites de l'ensemble A eectues par la chane au cours des n premiers pas. Nous verrons que, dans le cas d'une chane positivement rcurrente, le comportement asymptotique des fonctionnelles additives prsente un certain nombre de points communs (mais galement des dirences !) avec celui des sommes de variables alatoires i.i.d.
Les thormes suivants montrent que, lorsque f est une fonction intgrable par rapport la loi invariante de la chane, on obtient un comportement comparable celui fourni par la loi des grands nombres usuelle pour les sommes de variables alatoires i.i.d. intgrables.
94
Thorme 9 Si
p est un noyau irrductible et positivement rcurrent de loi invariante , alors, pour tout f L1 (), et toute loi initiale , on a
n+
lim
Sn (f ) = (f ), P p.s. n
On notera que le rsultat ci-dessus est valable quelle que soit la loi initiale . En revanche, le rsultat suivant suppose que la loi initiale est prcisment la loi invariante.
Thorme 10 Si
p est un noyau irrductible et positivement rcurrent de loi in(f variante , alors, pour tout f L1 (), on a convergence de Snn ) vers (f ) dans L1 (P ), autrement dit,
n+
lim E
Sn (f ) (f ) n
= 0.
La comparaison avec la loi des grands nombres habituelle pour les sommes de variables alatoires i.i.d., dont les deux thormes ci-dessus constituent une gnralisation, explique la ncessit de poser une hypothse telle que l'intgrabilit de f par rapport . Une extension simple, mais utile du thorme 10 est fournie par le corollaire suivant.
= g , g tant borne suprieurement (par exemple si est support ni), on a galement convergence dans L1 (P ), soit
n+
Corollaire 20 Si
lim E
Sn (f ) (f ) n
= 0.
Exercice 138 Prouver que le corollaire ci-dessus est eectivement une consquence
du thorme 10.
4.2 Preuves
Nous prsenterons deux approches distinctes permettant de prouver le thorme 9. La premire est base sur la dcomposition de renouvellement des trajectoires obtenue en considrant les portions de trajectoires sparant les retours successifs en un point donn. La seconde s'appuie sur la thorie ergodique. Auparavant, expliquons comment le thorme 10 se dduit du thorme 10.
On note d'abord que f (Xn ) L1 (P ) pour tout n, compte-tenu du fait que la loi de Xn sour P est , et ce, quelle que soit la valeur de n. Ensuite, on procde par troncature. Pour M 0, posons
fM (x) := f (x)1(|f (x)| M ).
95
D'aprs le thorme 9, on a convergence presque sre de n1 Sn (fM ) vers (fM ), presque srement par rapport P . Comme fM est une fonction borne, la suite (n1 Sn (fM ))n0 est elle-mme borne, et, par consquent, converge galement vers (fM ) dans L1 (P ). On note ensuite que
|Sn (f fM )| Sn (|f fM |).
Compte-tenu de l'invariance de , on a E (|f fM |(Xn )) = (|f fM |), et l'on dduit de ce qui prcde que, pour tout n,
|E Sn (f fM )| (n + 1)(|f fM |).
Le thorme de convergence domine entranant le fait que limM + (|f fM |) = 0, on en dduit que n1 Sn (f fM ) et (f fM ) tendent vers zro dans L1 (P ) lorsque n tend vers l'inni, ce qui achve la preuve.
Li (f ) :=
j=Ti (a)
f (Xj ).
(avec la convention max = 0). Pour tout n T1 (a), on peut alors crire une dcomposition de renouvellement de Sn (f ), sous la forme
T1 (a)1 Rn 1 n
Sn (f ) =
j=0
f (Xj ) +
i=1
Li (f ) +
j=TRn (a)
f (Xj ).
(4.1)
On sait que, quelle que soit la loi initiale, la suite Li (f ), i 1 est constitue de v.a. i.i.d. de mme loi que celle de la variable T1 (a)1 f (Xj ) sous Pa . j=0
96
Ea
j=0
f (Xj ) = cycle (f ). a
Preuve :
f (Xj ) Ea
T1 (a)1
|f (Xj )| .
Ea
j=0
j=0
|f (Xj )| =
yS
|f (y)|Ea
T1 (a)1
1(Xj = y) .
j=0
Par consquent,
Ea
T1 (a)1
j=0
En utilisant le fait que est proportionnelle cycle et que f L1 (), on obtient a T1 (a)1 l'intgrabilit de f (Xj ) par rapport Pa . L'identit annonce se dduit j=0 alors par le mme calcul que ci-dessus. Nous allons maintenant prouver le thorme 9 en tudiant sparment le comportement de chacun des trois termes qui constituent la dcomposition de renouvellement (4.1). Pour commencer, on a, en utilisant simplement le fait que P (T1 (a) < +) = 1, le fait que
n+
lim
= 0, P p.s.
Le premier "terme de bord" de la dcomposition peut donc tre nglig. Ensuite, en utilisant le fait que la suite (Ti+1 (a) Ti (a))i1 est i.i.d. et de mme loi que T1 (a) sous Pa , et le fait que Ea (T1 (a)) < + d'aprs la rcurrence positive, on obtient, en appliquant la loi des grands nombres, que
TK (a) = Ea (T1 (a)), P p.s. K+ K lim
(4.2)
D'autre part, en notant que l'ingalit n Ti (a) entrane que Rn i, on voit facilement que, lorsque n tend vers l'inni,
n+
lim Rn = +, P p.s.
97
n TRn +1 (a) TRn (a) . Rn Rn Rn En utilisant (4.2) et le fait que Rn tend vers l'inni avec probabilit 1 sous P , on
En partant de l'ingalit, valable par dnition, TRn (a) n TRn +1 (a), on obtient que, pour tout n 1,
dduit que
n+
lim
Enn, le lemme 21 et la loi des grands nombres nous permettent d'tablir que
M +
lim
M i=1 Li (f )
= cycle (f ), P p.s. a
lim
Rn i=1 Li (f )
Il nous reste montrer que l'on peut ngliger le second "terme de bord" de la dcomposition. Pour cela, notons la majoration
n
lim
Rn 1 i=1 Li (|f |)
n |
n+
= lim
Rn i=1 Li (|f |)
n+
= 0, P p.s.
ductibles positivement rcurrentes partir des arguments employs dans la preuve du thorme donne ci-dessus. 1) En reprenant l'argumentation de la preuve ci-dessus, montrer (sans utiliser les preuves donnes au chapitre prcdent) que, pour une chane irrductible positivement rcurrente, toute loi invariante est ncessairement tre proportionnelle cycle . a 2) De mme, reprendre l'argumentation de la preuve ci-dessus pour montrer que, pour une chane irrductible positivement rcurrente, cycle /Ea (T1 (a)) est une loi de a probabilit invariante.
On note en particulier que l'exercice ci-dessus fournit une autre justication l'expression de la loi invariante en termes de cycle que celle qui rsulte de la preuve a donne dans le chapitre prcdent.
Exercice 139 Cet exercice propose de reprouver des rsultats sur les chanes irr-
98
Par consquent, d'aprs le thorme ergodique de Birkho, lorsque n tend vers l'inni n1 Sn (f ) converge presque srement et dans L1 (P ) vers l'esprance de f X0 conditionnelle la tribu des invariants de sous l'action de . Nous allons montrer qu'un ensemble (mesurable) invariant est ncessairement de probabilit gale 0 ou 1, i.e. que dnit une action ergodique sur (S N , HN , P ), ce qui conclura la preuve lorsque la loi initiale est gale . Si A est un tel ensemble invariant, (x0 , x1 , . . . , ) A est quivalent au fait que (x1 , x2 , . . .) A. Par consquent, pour tout k, P (A|Fk ) = P ((k )1 (A)|Fk ) = PXk (A). Si P (A) = 0, il existe x tel que Px (A) > 0. Pour un texl x, on a donc que P (A|Fk ) Px (A)1(Xk = x). D'aprs le thorme de Lvy (voir [18, 49]), P (A|Fk ) 1(A) P presque srement lorsque k tend vers l'inni. Or, par rcurrence de la chane, on voit que, avec probabilit 1 sous P , lim inf k+ (1(Xk = x)) = 1. Par consquent, 1(A) = 1 P p.s. Comme est propre, on voit que la convergence p.s. sous entrane la convergence p.s. sous pour toute loi initiale .
4.3 Exercices
La loi des grands nombres pour les fonctionnelles additives prsente dans ce chapitre implique une importante proprit de rgularit des trajectoires, comme expliqu dans l'exercice suivant.
brable S , que l'on suppose irrductible et positivement rcurrent, dsignant sa loi invariante, et une loi initiale quelconque sur S . 1) Montrer que, pour tout A S ,
n+
lim
card {0 i n; Xi A}
n
= (A) P p.s.
n+
lim
= (x0 )
i=0
99
3) En dduire que, pour une chane rversible, la proportion asymptotique de transitions d'un tat x vers un tat y le long d'une trajectoire est gale la proportion de transitions de y vers x.
Exercice 141 Quelle mthode de simulation la loi des grands nombres pour les fonctionnelles additives suggre-t-elle pour estimer la valeur de (f ) ?
Cet exercice propose de prouver diverses identits intressantes reliant loi invariante et temps d'atteintes. Dans toute la suite, on suppos donn un noyau de transition p dni sur un ensemble S ni ou dnombrable, irrductible et positivement rcurrent. 1) Soit T un temps d'arrt de (Fn )n0 (sur l'espace canonique des trajectoires). On suppose que, pour un x S , on a Ex (T ) < + et XT = x Px p.s. Etant donn y S , on dnit NT (y) comme le nombre de visites en y avant le temps T , ou, plus formellement, NT (y) := card{0 j T 1; Xj = y}. Montrer qu'alors, pour tout y S , on a
Ex (NT (y)) = (y)Ex (T ).
2) Quelle relation obtient-on en posant T := T1 (y) ? 3) Prouver la relation suivante : pour tous x, y S tels que x = y ,
Px (T1 (y) < T1 (x)) = 1 . (x) (Ex (T1 (y)) + Ey (T1 (x)))
(Indication : choisir un T appropri et appliquer le rsultat du 1).) 4) Prouver la relation suivante : pour tous x, y, z S tels que x, y, z sont deux--deux distincts,
Px (T1 (y) < T1 (z)) = Ex (T1 (z)) + Ez (T1 (y)) Ex (T1 (y)) . Ey (T1 (z)) + Ez (T1 (y))
Exercice 143 (Marche alatoire dans un milieu priodique) On considre un noyau de transition p sur Z d vriant la proprit de priodicit suivante : il existe des entiers 1 , . . . , d > 0 tel que, pour tous x, y Zd , et tous u1 , . . . , ud Z,
p(x + (u1 1 , . . . , ud d ), y + (u1 1 , . . . , ud d )) = p(x, y).
On suppose en outre que, pour tout x Zd , la loi de X1 sous Px possde une esprance nie, ou, plus explicitement, que yZd |y|p(x, y) < +. Montrer qu'il existe v Rd tel que, pour tout x Zd ,
n+
lim
Xn = v, Px p.s. n
100
p sur N dni de la manire suivante : p(0, 1) = 1 et, pour tout n 1, p(n, i) = P (Z = i), o Z dsigne une variable alatoire de loi binomiale de paramtres 2n et 1/2. 1) Montrer que p est irrductible et apriodique. 2) Posons f (x) = x pour x N. Calculer la fonction pf . En dduire que p est
rcurrent. 3) Prouver qu'il existe une constante C 0 telle que, pour tout n 0,
2 E0 (Xn ) Cn2 .
(Indication : on peut raisonner par rcurrence.) 4) Considrons une variable alatoire X 0 telle que 0 < E(X 2 ) < +. Prouver l'ingalit suivante :
P X 1 E(X) 2 1 E(X)2 . 4 E(X 2 )
1 (Indication : que peut-on dire de E X1 X 2 E(X) ?) 5) Montrer que, si p est positivement rcurrent, il doit exister une constante c > 0 telle que pour tout n 0,
E0 (Xn ) cn.
6) En faisant la synthse des questions prcdentes, montrer, en raisonnant par l'absurde, que p est rcurrent nul.
Chapitre 5
Comportement asymptotique de la loi de
Xn
Le rsultat fondamental concernant le comportement asymptotique de la loi de Xn lorsque n tend vers l'inni est prsent dans les deux thormes suivants, le premier traitant du cas rcurrent positif, tandis que le second traite les cas transient et rcurrent nul.
alors, en dsignant par la loi invariante de la chane, on a, pour toute loi initiale , la convergence en loi suivante : pour tout A S ,
n+
On constate donc que l'inuence du point de dpart X0 sur la loi de Xn s'estompe mesure que le nombre de pas eectus par la chane grandit : on dit que la chane oublie son point de dpart.
Thorme 12 Si Si
p est un noyau irrductible et apriodique, rcurrent nul ou transient, alors, on a, pour toute loi initiale , et tout x S ,
n+
lim P (Xn = x) = 0.
102 On note que l'on ne peut avoir une formulation du rsultat ci-dessus du type : pour tout A S , limn+ P (Xn A) = 0 ! Cette limite est cependant ralise lorsque A est, par exemple, un sous-ensemble ni de S . En revanche, les deux formulations (avec x S ou avec un sous-ensemble gnral A S ) sont quivalentes dans le cas o la limite est une loi de probabilit, comme expliqu dans l'exercice suivant.
S , et l'on suppose qu'il existe une mesure de probabilit sur S telle que, pour tout x S, lim n (x) = (x).
n+
Exercice 145 On se donne une suite de lois n sur un ensemble ni ou dnombrable
1) Montrer que la suite (n )n0 est tendue. (Indication : pour > 0 donn, choisir A tel que (A) 1 .) 2) En dduire que, pour tout B S ,
n+
chane de Markov irrductible et apriodique sur un ensemble ni ou dnombrable S , la suite (Xn )n0 est tendue si et seulement si elle suite converge en loi vers une mesure de probabilit. pour une chane de Markov irrductible et apriodique : l'existence d'une probabilit invariante entrane la rcurrence positive ; il ne peut exister plus d'une probabilit invariante.
Exercice 147 Montrer comment dduire des thormes 11 et 12 les faits suivants,
Les deux thormes ci-dessus concernent le comportement asymptotique des lois de probabilit pn . Dans le cas ergodique tout au moins, on peut en dduit simplement le rsultat suivant, en termes d'action du noyau sur les fonctions.
Thorme 13 Si
p est un noyau ergodique de loi invariante , on a le rsultat suivant : pour tout 1 q < +, et f Lq (),
n+
lim pn f = (f ),
Preuve :
Sans perte de gnralit, nous prouverons le rsultat pour toute f Lq () telle que (f ) = 0. On se rappelle d'abord que, pour tout x S , pn f (x) = Ex (f (Xn )).
Xn
xA |f (x)| / q (x)
103
.
Ensuite, pour tout > 0, il existe un ensemble ni A tel que Ecrivons
Nous allons montrer sparment la convergence dans Lq () des deux termes du membre de droite de l'galit ci-dessus. L'ingalit de Jensen entrane que
(x) |Ex (f (Xn )1(Xn A))|q /
xS xS
|f (x)|q (x) .
f (x)(x).
Qui plus est, A tant un ensemble ni, f est borne sur A, et le thorme de convergence domine permet de conclure que
q n+
lim
f (x)(x)
= 0.
xS
f (x)(x)
xA / xA /
|f (x)| (x)
on en dduit que
f (x)(x)
xA 1/q
104
1 , E(1 )
avec la convention 1/ + = 0.
Xn
105
Exercice 149 Lire une preuve analytique du thorme de renouvellement, par exemple
dans [20] (XIII,11), ou, pour une version plus gnrale (non limite au cas discret), [21] (XI).
n 1,
Supposons donc la chane rcurrente. On note que pour toute loi initiale , et
P (Xn = x) = P (n T1 (x) {0, T2 (x) T1 (x), T3 (x) T1 (x), . . .}).
Posons
a(k, x) = Px (k {0, T1 (x), T2 (x), T3 (x), . . .}).
On note que, en utilisant le caractre i.i.d. de la suite (Ti+1 (x)Ti (x))i1 par rapport la probabilit Px , et en posant x :=loi de probabilit de T1 (x) sous Px , i.e. x (n) = Px (T1 (x) = n), on peut rcrire, pour tout k 0,
+
a(k, x) =
i=0
xi (k),
(5.1)
ou i dsigne le produit de convolution itr i fois, et o l'on pose, pour i = 0, 0 := . 0 Grce la proprit forte de Markov applique T1 (x), on obtient l'identit fondamentale suivante
P (Xn = x) = E (a(n T1 (x), x)).
D'aprs le thorme du renouvellement appliqu la suite dnie par i = Ti (x) Ti1 (x), (avec la convention T0 (x) = 0) qui est i.i.d. sous Px , la condition sur le p.g.c.d. tant exactement la condition d'apriodicit de la chane, on a limn+ a(n T1 (x), x) = 1/EPx (T1 (x)). Le thorme de convergence domine permet de conclure que limn+ P (Xn = x) = (x). Ceci sut prouver le thorme 12 dans le cas
rcurrent nul. Pour prouver le thorme 11 dans le cas ergodique, il nous faut tendre la limite valable pour tout x une limite valable pour tout sous-ensemble A S , pas forcment ni. Cette extension est par exemple une consquence de l'exercice 145 (mais c'est aussi une consquence de la tension de la suite de lois (P (Xn = ))n0 , que l'on sait tablir simplement en utilisant la rcurrence positive, voir l'exercice 137). On note que l'on retrouve grce cette preuve, la formule liant la mesure invariante et l'esprance du temps de retour en un point. On note que, pour prciser la vitesse de convergence dans la preuve ci-dessus, on doit chercher la fois prciser la vitesse de convergence dans le thorme de
106 renouvellement, et disposer d'un contrle sur la dcroissance de la queue de la variable T1 (x). Ce point de vue est illustr dans l'exercice suivant. Voir [36] pour plus de dtails sur cette question.
positivement rcurrent sur un ensemble ni ou dnombrable S , et l'on xe a S . 1) Montrer que, pour tous x, y S , et n 0, on a la reprsentation suivante de Px (Xn = y) :
n j
ty (j).
3) Montrer que limn+ |Px (Xn = y) (y)| = 0 en analysant sparment chacun des termes de l'ingalit ci-dessus. De quelles informations a-t-on besoin pour contrler la vitesse de convergence ?
On dit que dV T (, ) est la distance en variation totale entre et , et l'on note que 0 dV T (, ) 1.
dV T dnit une
Xn
107
Exercice 151 Prouver la proposition ci-dessus. Proposition 52 Etant donne deux mesures de probabilit et sur S , on a l'identit
dV T (, ) = 1 2 |(x) (x)|.
xS
Preuve :
On introduit l'ensemble B = {x : (x) (x)}, et l'on vrie qu'il ralise le maximum dans le supremum dnissant dV T . On voit donc que dV T dnit une distance sur les mesures de probabilits sur S , vues comme un sous-ensemble de l'espace norm 1 (S). Une manire dirente d'crire cette distance, dans le cas particulier o est une mesure propre (ce qui sera toujours le cas lorsque est la loi invariante d'un noyau irrductible) est la suivante :
dV T (, ) = 1/2
xS
|(x)/(x) 1|(x),
et dV T (, ) apparat donc comme la norme (au facteur 1/2 prs) dans L1 () de la fonction x ((x)/(x) 1).
en variation totale lorsque S est ni ou dnombrable, mais que l'on a seulement une implication dans le cadre des espaces de probabilit gnraux (en prenant le sup sur tous les vnements A de la tribu considre pour dnir dV T ).
L'exercice ci-dessus montre donc que, qualitativement, convergence en loi et convergence en variation totale sont quivalentes (sur un espace ni ou dnombrable). Cependant, contrler la distance en variation totale fournit une information quantitative que ne contient pas le simple fait de savoir que la convergence en loi a lieu. L'un des principes de base de l'approche par couplage est le suivant : pour prouver que deux lois de probabilit sur S , disons 1 et 2 , sont proches, on fabrique sur un mme espace de probabilit deux variables alatoires, disons Z1 et Z2 , de lois respectives 1 et 2 , de telle manire que la probabilit que les deux variables alatoires en question soient proches ait une valeur proche de 1. Si l'on choisit simplement comme notion de proximit entre lments de S l'galit entre lments (ce qui est loisible sur un ensemble S dnombrable gnral sur lequel on ne suppose pas donne une structure particulire), on obtient un contrle sur la distance en variation totale entre 1 et 2 , comme le prcise la proposition suivante.
S quivaut la convergence
108
Z1 et Z2 sont deux variables alatoires dnies sur un mme espace de probabilit (, F, P ), de lois respectives 1 et 2 , alors dV T (1 , 2 ) P (Z1 = Z2 ).
Proposition 53 Si
(5.2)
Preuve :
On crit que
Par consquent,
|1 (A) 2 (A)| E(|1(Z1 A) 1(Z2 A)|).
A prsent, on note que, si l'vnement Z1 = Z2 , 1(Z1 A) 1(Z2 A) = 0. D'autre part, on a toujours que |1(Z1 A) 1(Z2 A)| 1. Le rsultat s'ensuit. De manire intressante, il est toujours possible de fabriquer un couplage ralisant l'galit dans l'ingalit prouve ci-dessus. On en dduit une interprtation de la distance en variation totale en termes de couplage.
sur l'ensemble des paires de v.a. valeurs dans S , dnies sur un mme espace de probabilit (, F, P ) et telles que la loi de X est et la loi de X est .
Exercice 155 Si
1 et 2 sont deux mesures de probabilit sur S , 1 s + et si f : S R est une fonction telle que f Ls (1 ) Ls (2 ), montrer que l'on a |E1 (f (X0 )) E2 (f (X0 ))| ||f ||Ls (1 ) + ||f ||Ls (2 ) [dV T (, )]1/r ,
o r est l'exposant conjugu de s. (Indication : appliquer la reprsentation par couplage de la distance en variation totale, et utilise les ingalits de Hlder et Minkowski.)
Xn
109
mme espace de probabilit et valeurs dans S , et si T est une v.a. valeurs dans N et dnie sur ce mme espace de probabilit, on dit que T est un temps de couplage 1 2 de X 1 et X 2 si, pour tout n, on a n T Xn = Xn .
Preuve :
1 2 Il sut de vrier que le couplage que l'on obtient entre Xn et Xn que l'on obtient 1 = X 2 ) P (T > n). est tel que P (Xn n
Exercice 156 Justier le fait qu'il est toujours possible de trouver un espace de
1 3 probabilit (, F, P ) et deux suites (Xn )n0 et (Xn )n0 vriant les proprits cidessus.
1 3 2 Dnissons ensuite T = inf{n : Xn = Xn }, et dnissons pour tout n Xn par 2 1 2 3 Xn = Xn pour n T et Xn = Xn pour n > T . 2 Lemme 22 La suite (Xn )n0 est une chane de Markov de loi intiale et de noyau 1 2 de transition p, et T est un temps de couplage de (Xn )n0 et (Xn )n0 .
110
1 3 A prsent, remarquons que la suite (Xn , Xn )n0 est une chane de Markov sur S S , de noyau de transition p p dni par p p((x1 , x2 ), (y1 , y2 )) = p(x1 , y1 )p(x2 , y2 ), et que T n'est autre que le temps de premire atteinte de l'ensemble D := {(x, x); x S} par cette chane.
p.
Etant donns (x1 , x2 ) et (y1 , y2 ) dans S S , l'irrductibilit de p entrane l'existence de a1 1 et a2 1 tels que pa1 (x1 , y1 ) > 0 et pa2 (x2 , y2 ) > 0. Notre but est de trouver m1 , m2 0 tel que pm1 (y1 , y1 ) > 0, pm2 (y2 , y2 ) > 0, et a1 +m1 = a2 +m2 . Par 1 apriodicit de p, il existe d1 , . . . , d11 1, et u1 , . . . , u11 Z tels que pdj (y1 , y1 ) > 0 1 1 k k pour tout 1 j k1 , et u1 d1 + +u11 d11 = 1. De mme, il existe d2 , . . . , d22 1, et 1 1 1 k k k 2 u2 , . . . , u22 Z tels que pdj (y1 , y1 ) > 0 pour tout 1 j k2 , et u2 d2 + + u22 d22 = 1 1 1 k k k 1. On vrie que, en choisissant m1 := a2 (u1 d1 + + u11 d11 ) + Kd1 d11 d2 d22 1 1 1 k k k 1 k et m2 := a1 (u2 d2 + + u22 d22 ) + Kd1 d11 d2 d22 , pour un entier K susament 1 1 1 k k k 1 k grand (de manire compenser les valeurs ventuellement ngatives de uj en faisant i apparatre un facteur positif devant chaque dj ), on parvient au rsultat recherch. i
Preuve :
p est rcurrent nul et p p est transient, et un exemple o p est rcurrent nul et p p est rcurrent. (Indication : essayer des marches alatoires simples sur Zd .) Est-il possible que pp soit rcurrent positif dans
Xn
111
Mais, par dnition, P,pp (Xn = (x, x)) = (P,p (Xn = x))2 , et l'on a donc que, pour tout x S ,
n+
ce qui est la conclusion du thorme 12. Supposons maintenant que p p est rcurrent. En reprenant la dnition de T 1 3 avec des chanes (Xn )n0 et (Xn )n0 issues respectivement de deux lois initiales et quelconques, on en dduit de la rcurrence de p p le fait que T est ni P,pp presque srement, d'o, en appliquant la proposition 55, le fait que, pour toutes lois initiales et ,
n+
(5.3)
A prsent, xons arbitrairement a S , et considrons la mesure cycle . Comme a p est suppos rcurrent nul, cette mesure est invariante pour p (et donc propre), et de masse innie. Etant donn x S , donnons-nous un sous-ensemble ni A S contenant x. On a donc 0 < cycle (A) < +, et il est possible de dnir une mesure a de probabilit sur S en posant
A (x) =
cycle (x) a , cycle (A) a
x A,
A (x) = 0, x A. /
Pour un x x, du fait que cycle est de masse innie, on peut choisir A tel que a cycle a cycle (A) soit arbitrairement grand, disons, tel que A (x) = cycle (x) . En applia a (A) quant (5.3) pour contrler |P (Xn = x) PA (Xn = x), on en dduit que
lim sup P (Xn = x) ,
n+
ce qui conclut la preuve. Remarquons que, dans la section prcdente, nous n'avons pas fourni de preuve du thorme du renouvellement. Ayant maintenant tabli par couplage les thormes 11 et 12, nous pouvons les utiliser an de donner une preuve du thorme du renouvellement sous la forme que nous avons nonce dans la section prcdente.
112
Exercice 160 Soit une variable alatoire valeurs dans N telle que le pgcd des
lments du support de S soit gal 1. 1) Montrer que, pour toute variable alatoire, il est possible de construire une chane de Markov apriodique et rcurrente sur N telle que la loi de T1 (0) sous la probabilit P0 est la loi de . 2) En utilisant les thormes 11 et 12, en dduire le thorme du renouvellement nonc dans la section prcdente.
gomtrique, et que la convergence a donc lieu vitesse au moins exponentielle. Montrer que l'on peut mme tablir une borne indpendante de la loi initiale. Montrer que, gnriquement, la vitesse de la convergence est eectivement exponentielle.
Exercice 162 Montrer sur un exemple que, lorsque S est inni, il n'existe pas tou-
jours de borne uniforme vis--vis de la loi initiale pour la convergence en variation totale.
Nous avons vu que, pour tout temps de couplage entre deux versions de la chane dont l'une est initialise selon la loi invariante , l'autre l'tant selon une loi quelconque , on a l'ingalit dV T (P (Xn = ), ) P (T > n). Dans le cas d'une chane
Xn
113
de Markov ergodique sur un ensemble S ni, on peut en fait prouver qu'il existe toujours un temps de couplage tel qu'il y ait galit dans l'ingalit ci-dessus. Un tel temps de couplage est donc minimal, en ce sens que tout autre temps de couplage T doit vrier que P (T > n) P (T > n), autrement dit, tout temps de couplage est minor stochastiquement par T . Pour une preuve de ce rsultat, dont l'intrt est essentiellement thorique, voir [34]. Notons qu'en partant simplement de l'existence d'un couplage, tel que celui dni dans la preuve du thorme, il est possible d'obtenir des informations qualitatives sur la vitesse d'oubli de la condition initiale en variation totale. En considrant le couplage partir de (x, y) S S , on constate que
dV T (x pn , y pn ) P (T > n)
et que
P (T > n) < +
n=0
car p p est positivement rcurrent. Nous pouvons reformuler ceci sous la forme d'une proposition.
x, y S ,
dV T (x pn , y pn ) < +.
n=0
Nous verrons dans le chapitre suivant que cette proprit n'est pas toujours vrie si l'on considre + dV T (x pn , ). On peut en tout cas noter que le fait que T soit n=0 d'esprance nie si l'on part non pas d'une loi concentre en un point (en l'occurrence (x, y)), mais d'une loi dont le support est potentiellement inni telle que x , n'est pas a priori une consquence de la rcurrence positive de p p. Nous aurons l'occasion par la suite d'utiliser les notations :
d1 (n) := sup dV T (pn (x, ), ),
xS
et
d1 (n) := sup dV T (pt (x, ), pt (y, )) = (pn ).
x,yS
114
(Xn )n0 de loi invariante est une variable alatoire T telle que : (i)) T est un temps d'arrt par rapport une famille de tribus (Gn ) de la forme Gn := (X0 , . . . , Xn , Z), o Z est une variable alatoire indpendante de (Xk )k0 (on autorise donc les vnement de la forme T = n dpendre de X0 , . . . , Xn
et d'une randomisation indpendante de toute la chane) ; (ii) P (T < +) = 1 ; (iii) P (XT = x|T = n) = (x).
En d'autres termes, la proprit (iii) signie que XT est distribu selon la loi et est de plus indpendant de la valeur de T . D'un point de vue algorithmique, un tel temps fournit une rponse la question : combien de pas d'une chane de Markov ergodique doit-on simuler avant d'atteindre la loi invariante avec une prcision satisfaisante. En eet, en simulant un nombre (alatoire !) de pas gal T , on obtient une variable alatoire distribue exactement selon cette loi stationnaire. Cette approche est la base de l'algorithme de simulation parfaite de Fill que nous dcrirons plus bas. Pour l'instant, expliquons comment l'existence d'un temps stationnaire fort permet de prouver la convergence vers la loi invariante. Nous avons vu prcdemment le lien troit entre couplage et distance en variation totale. Dans le contexte des temps stationnaires forts, la notion approprie de distance entre lois s'avre tre celle de distance en sparation :
Attention : cette dnition n'est pas symtrique en et , et donc la terminologie est trompeuse car elle ne correspond pas une vritable distance. On vrie que 0 sp.(, ) 1, et que l'on a l'ingalit suivante :
P (T > n).
Preuve :
On crit que P (Xn = x) = P (Xn = x, T n) + P (Xn = x, T > n). En partant de la dnition d'un temps stationnaire fort, on vrie facilement que (XT +i )i0
Xn
115
est une chane de Markov de noyau de transition p et de loi , indpendante de T . On en dduit que P (Xn = x, T n) = (x)(1 P (T > n)), d'o le fait que P (Xn = x)/(x) 1 P (T > n), ce qui conclut la preuve. Comme pour les temps de couplage vis--vis de la distance en variation totale, il existe galement un temps stationnaire fort minimal, au sens o celui ralise l'galit dans l'ingalit ci-dessus, et donc au sens o il minore stochastiquement tous les autres temps stationnaires forts.
Proposition 59 Pour toute loi initiale sur S , il existe une chane de Markov de
noyau de transition p et de loi initiale possdant un temps stationnaire fort T tel que l'on ait, pour tout n 0, sp.(pt , ) = P (T > n).
Preuve :
Voir [7].
La construction de ce temps stationnaire fort permet en particulier de retrouver la convergence en loi de la chane vers sa loi stationnaire. Nous avons vu que la distance en sparation domine de manire gnrale la distance en variation totale. Dans le contexte de la comparaison des temps (de couplage et stationnaires forts), on a le rsultat suivant.
Preuve :
1 Partons d'un temps stationnaire fort T , et notons (Xn )n0 la chane de Markov 1 issue de la loi initiale correspondante. Ensuite, partant de XT , fabriquons indpen1 damment de ce qui prcde une trajectoire XT =: Y0 , . . . , YT selon le noyau renvers dans le temps de p par rapport . On vrie alors que la suite de variables alatoires 2 2 1 2 (Xn )n0 dnie pour 0 n T par Xn := YnT , et pour n > T par Xn := Xn est une chane de Markov de noyau de transition p issue de la loi stationnaire , et que 1 2 T est un temps de couplage entre (Xn )n0 et (Xn )n0 .
Citons prsent quelques proprits gnrales de la distance en sparation dans le contexte des chanes de Markov.
116
Preuve :
rversible, pour
Preuve :
p2t (x, y) = (y) pt (x, z)pt (z, y) = (y) (z)
zS
zS
zS
d'o
p2t (x, y) (y) min(p (x, z), (p (y, z))
zS z t t
On vrie ensuite facilement (pensez l'ensemble B ) que 1 dV T (pt (x, ), pt (y, )). Le rsultat s'ensuit.
zS
Proposition 64 La fonction t dsp. (t) est sous-multiplicative (et donc en particulier dcroissante).
Preuve :
On crit que pt (x, y) = (1 dsp. (t))(y) + dsp. (t)qt (x, y), et l'on vrie que qt est un noyau de transition pour lequel est invariante. On obtient alors en calculant que pt+s (x, y) = (1 dsp. (t)dsp. (s))(y) + dsp. (t)dsp. (s) zS qs (x, z)qt (z, y), d'o le fait que pt+s (x, y) (1 dsp. (t)dsp. (s))(y), ce qui conclut la preuve. Ainsi, on peut par exemple utiliser sp. = inf{t; dsp. (t) 1/2} pour dnir un temps de relaxation pour la distance en sparation. Pour intressante qu'elle soit en thorie, la construction de temps stationnaires forts analysables n'est possible que dans des cas trs particuliers, possdant de fortes proprits de symtrie. Voici deux exemples simples et croquignolets (cits par [7]).
Xn
117
Z/2a Z
(voir [15]).
On considre la marche alatoire sur Z/2a Z dont les pas sont +1, 0 ou 1 avec une probabilit de 1/3 pour chacun. Clairement, il s'agit d'une chane de Markov irrductible et apriodique dont la loi stationnaire est la loi uniforme. En dnissant T1 = 0 et, pour i = 1, . . . , a 1, Ti comme le premier instant postrieur Ti1 o l'on se trouve distance 2ai1 de XTi1 , on vrie par rcurrence (en utilisant la symtrie du problme) que, conditionnellement la valeur de Ti , la v.a. XTi est uniformment distribue sur son support, qui, pour i = a1, est l'ensemble des points distance impaire de X0 . En dnissant Ta comme le premier instant postrieur Ta1 o l'on fait un pas gal 0 ou +1, on voit que Ta est un temps stationnaire fort pour la chane. Nous discuterons dans un autre chapitre les conclusions quantitatives qui peuvent tre tires des temps stationnaires forts introduits ci-dessus.
118 l'oprateur linaire p (sur des espaces prciser) puissent jouer un rle important dans cette tude. Dans le cas o S est ni, on peut par exemple appliquer p la thorie classique de Perron-Frobenius des matrices positives, pour tablir les proprits de base du spectre, comme nous le verrons ci-dessous, et en dduire le comportement asymptotique de pn . Dans le cas o S est inni, l'tude des proprits spectrales de p (en faisant agir p sur des espaces convenables) est galement intressante, mais fait appel une sophistication technique bien plus grande, et ncessite des hypothses supplmentaires sur le noyau considr. Dans le cas rversible, on note que l'action de p sur L2 () est auto-adjointe, et il est donc possible d'utiliser la thorie gnrale des oprateurs continus auto-adjoints sur les espaces de Hilbert, cette thorie (faisant appel la notion de mesure spectrale) tant prsente par exemple dans [11, 47]. Dans ce qui suit, nous nous contenterons de prsenter la thorie dans le cas o S est un ensemble ni.
toutes les valeurs propres (dans C) de p sont de module infrieur ou gal 1 ; 1 est valeur propre de p ; si p est irrductible, la multiplicit (gomtrique et algbrique) de 1 est gale 1, le sous-espace propre associ ( droite) tant celui des fonctions constantes, et gauche celui des mesures complexes invariantes ; si p est irrductible et apriodique, 1 est l'unique valeur propre de module 1.
Preuve :
On note qu'en ce qui concerne le spectre (valeurs propres, multiplicits algbriques et gomtriques), une matrice et sa transpose ont les mmes caractristiques. On peut donc indiremment tudier l'action droite ou gauche de p. On vrie d'abord que |f p| |f |, o, pour f : S C, |f | = xS |f (x)|. On en dduit que toutes les valeurs propres complexes de p sont de module 1. Le fait que 1 soit valeur propre se voit en vriant que la fonction constante gale 1 est xe par l'action de p. Le fait que la multiplicit gomtrique de 1 soit gale 1 si p est
Xn
119
irrductible se vrie en considrant f : S C telle que pf = f , ce que l'on ramne, en considrant parties relles et imaginaires sur lesquelles p agit sparment, une fonction f valeurs relles, puis en introduisant s tel que f (s ) = maxsS f (s) et en vriant que ncessairement, f (s) = f (s ) pour tout s tel que p(s , s) > 0, grce l'invariance de f sous l'action de p, puis en itrant. En appelant la probabilit invariante, on note que l'ensemble des fonctions F0 des fonctions f vriant sS f (s)(s) = 0 est stable par p, et constitue un supplmentaire de l'ensemble des fonctions constantes. On voit alors que 1 ne peut tre valeur propre de p restreint F0 , ce qui prouve que 1 est galement de multiplicit algbrique gale 1. (On peut aussi considrer les mesures complexes de masse nulle en lieu et place de F0 , et considrer l'action gauche.) Considrons maintenant un nombre complexe de module 1, et supposons l'existence d'une mesure complexe non-nulle telle que p = , p tant suppos irrductible et apriodique. Nous allons prouver que l'galit suivante a lieu pour tout x S et n 1 :
(y)pn (y, x) =
yS yS
(5.4)
n n Notons d'abord que, pour x x, yS |(y)|p (y, x). Or, yS (y)p (y, x) par hypothse, p = , d'o le fait que yS (y)pn (y, x) = n (x). On en dduit n (x)pn (y, x) = |(x)|, et, en sommant, que xS yS (y)p (y, x) = n xS |(x)|. Par ailleurs, xS yS |(y)|p (y, x) = xS |(x)|. On en dduit l'galit (5.4). Celle-ci entrane en particulier que (x) := |(x)| dnit une mesure positive non-triviale invariante pour p, qui est donc propre. Par consquent, (x) = 0 pour tout x S . A prsent, rappelons qu'une galit de la forme |x1 + + xk | = |x1 | + + |xk |, o x1 , . . . , xk C, quivaut au fait que tous les xi non-nuls possdent le mme argument (Pour k = 2, c'est le cas d'galit dans l'ingalit de Cauchy-Schwarz, et le cas gnral s'en dduit par rcurrence). Considrons donc x S , et n 1 tel que pn (x, x) > 0. On voit que les arguments de yS (y)pn (y, x) = n (x) et de pn (x, x)(x) doivent tre gaux, ce qui entrane que n = 1. En utilisant le fait que la chane est apriodique, on en dduit que ncessairement = 1, ce qui conclut la yS
que
preuve.
priode d, ses valeurs propres de module 1 sont ncessairement des racines dmes de l'unit.
Le thorme prcdent entrane prsent automatiquement le thorme 11 : il sut par exemple d'eectuer une rduction de Jordan, pour constater que, partant
120 d'une loi initiale quelconque , P (Xn = ) converge, lorsque n tend vers l'inni, vers la projection de sur le sous-espace propre associ la valeur propre 1 en ayant pris comme supplmentaire les mesures signes de masse nulle. On retrouve le fait qualitatif que la convergence vers la loi stationnaire a lieu vitesse exponentielle, et l'on constate que la connaissance du spectre de p, ou tout au moins de la distance de Spec(p) \ {1} au cercle unit de C, conditionne la vitesse de convergence. Nous avons donn une preuve du thorme prcdent utilisant le fait que la matrice associe p est stochastique. Si l'on considre seulement des matrices positives, le thorme de Perron-Frobenius, dont il existe direntes versions, montre que certaines des proprits ci-dessus demeurent valables, condition d'tre convenablement adaptes. Nous citons ci-dessous, sans donner de preuve, une version du thorme de Perron-Frobenius que nous aurons l'occasion d'utiliser. Rappelons qu'une matrice carre A = (axy ) indexe par S S coecients dans R est dite positive si ses coecients sont tous positifs ou nuls, et irrductible si, pour tous x, y S , il existe (n) (n) n 0 tel que axy > 0, o An =: (axy ).
Thorme 16 Soit
R telle que > 0;
toute autre valeur propre de A possde un module ; il existe un vecteur propre de A associ dont toutes les coordonnes sont strictement positives ; la multiplicit gomtrique de est gale 1.
Exercice 163 Prouver le thorme ci-dessus (ou aller en lire une preuve).
5.6 Thorie L2
5.6.1 Gnralits
Dans toute cette partie p dsigne un noyau ergodique de loi invariante . On rappelle que l'action de p sur les fonctions envoie L2 () dans lui-mme, et que l'adjoint de p pour le produit scalaire de L2 () n'est autre que le noyau renvers dans le temps p. Dans ce contexte, la distance entre deux fonctions est mesure par la 2 1/2 , et la convergence vers la norme de L2 (), i.e. ||f g||2 := xS (f (x) g(x)) loi stationnaire pourra par exemple tre mesure sur les fonctions de L2 (), par ||pn f (f )||2 , qui n'est autre que l'cart-type de f (Xn ) sous P . On peut galement dnir une distance L2 entre pn et par la formule xS |(x)/(x) 1|2 (x) (avec la convention 0/0 = 1), mais, dans le cas o S est inni, il se peut que cette distance prenne une valeur innie. Notez que le fait que / (vue comme une
Xn
121
fonction sur S ) se trouve dans L2 () signie que (vue comme une fonction sur S ) se trouve dans L2 (1/). On peut alors poser d2 (t) := supxS
t 2 yS |p (x, y)/(y) 1| (y) xS 1/2
, et l'on
1/2
vrie que, par convexit, pour toute loi initiale , d2 (t). Par ailleurs, on voit que l'on a l'ingalit
2dV T (, ) =
xS
1/2
(x)|(x)/(x) 1|
xS
|(x)/(x) 1| (x)
D'autre part, on vrie que p est, comme p, ergodique de loi invariante , et que (p)/ = p(/). Par consquent, la convergence de pn vers peut tre analyse dans notre contexte en tudiant la convergence dans L2 () de l'action de pn sur les fonctions. Nous nous restreindrons donc aborder le problme du point de vue de l'action sur les fonctions. On se rappelle au passage que la suite (||pn f (f )||2 )n0 est dcroissante du fait que la norme de l'action de p de L2 dans lui mme est de norme 1.
Il s'agit d'une forme quadratique sur L2 () (on vrie facilement qu'elle est bien dnie, du fait que pf et f sont dans L2 ()). La forme de Dirichlet reprsente donc une mesure de la variation locale de f : partant d'un lment de S choisi selon la loi invariante , on mesure dans L2 la variation de f lorsque l'on fait un pas de la chane. On vrie que Ep (f, f ) = Ep (f, f ). Partant d'un noyau p, nous allons considrer le noyau ppar. sur S (par. pour paresseux) dni par ppar. (x, y) := (1/2)p(x, y) si x = y , et ppar. (x, x) := 1/2 + 1/2p(x, x). On vrie que ppar. est galement ergodique, et possde galement pour loi invariante. En outre, ppar. est rversible si et seulement si p l'est.
L2 (),
d'o
ppar. f (x) = (1/2)
yS
(5.5)
yS
yS
p(x, z) (x) ,
et donc que
||ppar. f ||2 (1/4) 2
xS
yS
(5.6)
f (y)2 (y),
Xn
123
soit nalement
||f ||2 = (1/2) 2
x,yS
(5.7)
Ce rsultat montre en particulier que la suite ||(ppar. )n f (f )||2 n1 est d2 croissante. De manire plus intressante, notons que, si l'on dispose d'une ingalit du type Ep (f, f ) ||f (f )||2 , o > 0 on obtient des bornes exponentielles quantita2 tives sur la convergence vers la stationnarit. Une telle ingalit est appele ingalit de Poincar ; elle borne la variation L2 globale d'une fonction, soit ||f (f )||2 , en 2 termes d'une somme de variations L2 locales, soit Ep (f, f ). Nous verrons plus loin comment obtenir des ingalits de Poincar dans certaines situations. Dans le cas o S est ni, une telle ingalit existe toujours, car on vrie facilement que, si Ep (f, f ) = 0, f doit tre une fonction constante, et donc on doit avoir f = (f ). On conclut ensuite en utilisant l'homognit de Ep (f, f ) et ||f (f )||2 2 pour se ramener la sphre unit de L2 (), et un argument de compacit. Nous verrons plus bas des techniques permettant de prouver ce type d'ingalit dans certains cas. Si cette ingalit vous parat mystrieuse, vous pouvez noter que, en considrant une version en temps continu de la mme chane, possdant exactement le mme noyau de transision, et des taux de sauts constants gaux 1, la forme de Dirichlet apparat de manire plus naturelle : on a en eet l'identit
d ||pt f (f )||2 = 2Ep (f, f ), 2 dt
qui suggre, par ailleurs, que l'ingalit de la proposition ci-dessus perd un facteur 4 par rapport ce qui devrait tre l'ordre de grandeur correct, un facteur 2 s'expliquant par le caractre paresseux de la chane considre, un autre facteur 2 demeurant inexpliqu.
124 orthonorme (pour le produit scalaire de L2 ()) et que ses valeurs propres sont des nombres rels. Cependant, hormis dans de rares cas, il est dicile, voire impossible de calculer prcisment la diagonalisation d'un noyau rversible. Un exemple remarquable, dans le cas des marches alatoires sur le groupe symtrique est fourni par [16] (voir galement [14]), dans lequel l'analyse de Fourier sur le groupe symtrique (utilisant la thorie des reprsentations) est mise contribution.
Proposition 66 Pour une chane rversible, la forme de Dirichlet possde l'expression alternative suivante :
Ep (f, f ) =< (I p)f, f >L2 () .
Preuve :
Par dnition, < (I p)f, f >= x,yS (x)p(x, y)f (x)(f (x) f (y)). Ceci se rcrit < (I p)f, f >= x,yS (y)p(y, x)f (y)(f (y) f (x)), et, par rversibilit, se rcrit encore < (I p)f, f >= x,yS (x)p(x, y)f (y)(f (y) f (x)). En crivant < (I p)f, f > comme la demi-somme de la permire et de la dernire expression, on obtient la formule annonce. On note au passage qu'il est facile de vrier que la valeur propre 1 est de multiplicit 1 dans ce contexte, en notant qu'une fonction f vriant pf = f doit annuler la forme de Dirichlet d'aprs l'expression ci-dessus, ce qui entrane trs facilement le fait que f doit tre constante, en utilisant la dnition de Ep (f, f ). Dans le cas o S est ni, on a, en se rappelant que la valeur propre 1 est associe aux fonctions constantes et le fait que toutes les valeurs propres sont relles et infrieures ou gales 1 (et d'ailleurs > 1), la caractrisation classique suivante :
inf{1 Spec(p); < 1} = inf Ep (f, f ) ; < f, 1 >= 0, f L2 () . ||f ||2 2
Ou, en termes plus probabilistes, en notant que Ep (f, f ) n'est pas modie par l'ajout f d'une constante, et en notant que < f, 1 >= xS f (x)(x),
sup{ Spec(p); < 1} = inf Ep (f, f ) ; f L2 () . V ar (f )
(Cette caractrisation a encore un sens dans le cadre plus gnral de la dcomposition spectrale en dimension innie.) On voit alors qu'une ingalit de Poincar entrane une borne sur la distance 1 du spectre de p. On voit que le fait de considrer le noyau ppar. = 1/2(I + p) permet de n'avoir que des valeurs propres entre 0 et 1 et que, par consquent, l'ingalit de Poincar entrane une borne sur le trou spectral de ppar. , ce qui claire quelque peu les rsultats de la partie prcdente, dans le cas o p est rversible.
Xn
125
= 0. Pouvez-vous tudier
< f, 1 >= 0, f L2 ()
Dnition 13 Etant donnes deux mesures de probabilit et sur S , tant propre, on appelle entropie relative de par rapport la quantit dnie par
H(|) :=
xS
(x) log
(x) = (x)
xS
(x) (x)
(x).
Comme est borne infrieurement, on voit que H(|) est toujours bien dnie. Comme est convexe, l'ingalit de Jensen permet de voir que
H(|)
xS
= (1) = 0.
De plus, tant strictement convexe, l'galit H(|) = 0 entrane donc automatiquement que (y) = (z) pour tous y, z S , d'o le fait que = . (y) (z) On note que H(|) ne dnit pas une distance, car elle n'est pas symtrique vis--vis de et . L'entropie relative peut tre compare la distance en variation totale grce l'ingalit importante suivante (dite de Csiszr-Kullback-Pinsker) :
Proposition 67
2dV T (, ) (H(|))1/2 .
126
Preuve :
Posons f (x) := 1(x)/(x). On a par dnition H(|) = ((1+f ) log(1+f )). En notant que (f ) = 0, on a encore H(|) = ((1+f ) log(1+f )f ). A prsent, on utilise l'ingalit, valable pour tout u 0, (1 + u) log(1 + u) u u2 /2(1 + u/3)1 , d'o l'on tire que H(|) (f 2 /2(1 + f /3)1 ) = (f 2 /2(1 + f /3)1 )(1 + f /3). Par Cauchy-Schwarz, on en tire que H(|) (1/2)(f )2 . On retrouve en particulier le fait que H(|) 0, avec galit si et seulement si = . Donnons-nous prsent un noyau ergodique p sur S . Par convexit, on a que, pour toute loi initiale ,
H(pn |) sup H(pn (x)|).
xS
Une proprit fondamentale de l'entropie dans le contexte des chanes de Markov est la suivante :
Preuve :
On crit que
H(p|) =
xS
(x)
yS
(y)p(y, x) (x)
On rcrit que
H(p|) =
xS
yS
(x)
On voit rapparatre le noyau renvers dans le temps p, qui permet d'obtenir que, par convexit de ,
H(p|)
xS
(x)
yS
Par stricte convexit, on dduit que l'galit dans l'ingalit ci-dessus entrane que, pour tout x, (y) = (z) pour tous y, z S tels que p(y, x) > 0 et p(z, x) > 0. Le (y) (z) fait que = s'en dduit par irrductibilit et apriodicit. Dans le cas o S est ni, on peut redmontrer a minima le thorme 11 de la manire suivante. On note d'abord que l'ensemble des lois de probabilits sur S est
Xn
127
compact (pour la topologie hrite de celle de RS ). En vertu de la proposition cidessus, la suite (H(pn |))n0 est dcroissante, et minore par zro. Appelons h sa limite. Considrons maintenant une sous-suite convergente de (pn )n0 , et notons 1 sa limite. On vrie facilement que H(1 |) = h. De plus, on a galement le fait que (pn+1 )n0 converge vers 1 p. Mais on doit galement avoir que H(1 p|) = h. Conclusion : 1 p = 1 , et donc 1 = .
Exercice 166 Peut-on utiliser un tel argument bas sur la stricte convexit avec les
distances prcdemment introduites ?
transition sur S suppos irrductible et apriodique. La loi invariante de p est note . Pour tout x S , on note T (x) := inf{n 0; Xn = x} en se plaant sur l'espace canonique des trajectoires, et avec la convention inf = +. L'objectif principal de cet exercice est d'tablir les deux identits suivantes, valables pour tous x, y S :
(x)E (T (x)) = Z(x, x), (y)Ex (T (y)) = Z(y, y) Z(x, y),
Exercice 167 Dans tout cet exercice, S dsigne un ensemble ni, et p un noyau de
(5.8) (5.9)
o
Z(x, y) :=
1) Expliquer pourquoi la srie dnissant Z(x, y) est absolument convergente pour tous x, y S . Montrer que, pour tout x S ,
Z(x, y) = 0.
yS
(5.10)
2)
avec la convention inf = +. Montrer que S0 est presque srement ni sous Px , et que Ex (S0 ) < +. Montrer ensuite que
Ex (card {0 j S0 1; Xj = x}) = (x)Ex (S0 ).
(Indication : utiliser par exemple une dcomposition de renouvellement base sur S0 .) 3) Dduire de la question prcdente que
n0 1
128
avec la convention inf = +. Montrer que S0 est presque srement ni sous Py , et que Ey (S0 ) < +. Montrer ensuite que
Ey (card {0 j S0 1; Xj = y}) = (y)Ey (S0 ).
(Indication : utiliser par exemple une dcomposition de renouvellement base sur S0 .) 6) En dduire que
Ey (card {0 j T (x) 1; Xj = y}) +
n0 1
pn (x, y)
n=0
est gal
(y) (Ey (T (x)) + n0 + E (T (y))) ,
(5.11)
8) Dduire (5.9) de ce qui prcde. 9) Soit N la matrice indexe par S S dnie par N (x, y) := (y), soit I la matrice identit indexe par S S . En voyant p comme la matrice indexe par S S dnie par p(x, y), montrer que I (p N ) est inversible et que
Z + N = (I (p N ))1 .
En dduire comment calculer numriquement les valeurs Z(x, y) partir de la connaissance du noyau p. 10) Peut-on gnraliser ce qui prcde au cas d'une chane ergodique sur un ensemble S dnombrable ? Quelles sont les obstructions ventuelles ?
Chapitre 6
Une premire approche quantitative de l'ergodicit pour la distance en variation totale
Dans ce chapitre, nous discutons d'une premire famille d'approches pour quantier plus prcisment l'ergodicit d'une chane de Markov pour la distance en variation totale. Cette approche est "quantitative" au sens o elle s'intresse la vitesse de convergence d'une chane vers sa loi stationnaire, mais elle ne donne de cette vitesse qu'une caractrisation plutt qualitative, tant davantage destine dlimiter des grandes classes de comportement asymptotique, plutt qu' fournir des bornes nonasymptotiques explicites sur l'cart la stationnarit. Des exemples de telles bornes non-asymptotiques seront donns dans un chapitre ultrieur. Dans tout ce chapitre, p dsigne un noyau ergodique sur un ensemble ni ou dnombrable S , tant la loi invariante.
et tudier quand la somme de celle-ci est nie. Le thorme suivant fournit plusieurs caractrisations de cette proprit, et, lorsque l'une des conditions quivalentes ci-dessus est vrie, on dit que p est ergo-
dique de degr 2.
130
dV T (x pn , ) < +;
(vii) On a
(x)
xS
dV T (x pn , )
n=0
< +.
Une consquence immdiate de (vii) est qu'il existe une suite cn de nombres positifs satisfaisant + cn < + et telle que, pour tout x S , et tout n 0, n=0
dV T (x pn , ) cn . (x)
On dispose donc en quelque sorte d'une borne uniforme sur la vitesse de convergence de dV T (x pn , ) vers zro lorsque n tend vers l'inni, module par la valeur de (x). L'quivalence de (i)-(ii)-(iii)-(iv) fait l'objet de l'exercice 126, et rsulte assez facilement de l'identit tablie par l'exercice 125.
avec la convention inf = +, n0 tant un entier x. On montre comme dans l'exercice (qui est formul dans le cas o l'espace est ni, mais l'adaptation au cas positivement rcurrent sur un espace dnombrable ne pose pas de problme), que S0 est presque srement ni sous Px , que Ex (S0 ) < +, et que
n0 1
o () = Px (Xn0 = ). Rcrivons
E (T (x)) =
yS
131
Par ergodicit de p, on a, pour tout y S , la convergence limn0 + Px (Xn0 = y) = (x). Le lemme de Fatou entrane donc que
n0 +
lim inf
lim inf
Cette ingalit prouve automatiquement que (v) (ii). On note que la preuve ci-dessus montre en fait que l'existence d'un x tel que (x)] < +, qui est moins forte que (v), sut entraner (ii), et se trouve donc en fait quivalente aux autres proprits mentionnes dans le thorme. La preuve ci-dessus sut galement montrer, (voir la premire question de l'exercice 126), qu'il existe bel et bien des exemples de chanes ergodiques pour lesquels (v) n'est pas vrie. Nous allons maintenant prouver que l'une quelconque des proprits quivalentes (i)-(ii)-(iii)-(iv) entrane (vii), en utilisant l'approche par couplage pour contrler la vitesse de convergence en variation totale. Nous commenons par introduire et tudier un objet qui nous sera utile dans l'analyse du temps de couplage correspondant. Considrons une suite S1 , S2 , . . . de variables alatoires i.i.d. valeurs dans {1, 2, . . .}. Pour tout n 1, notons
n0 1 n n=0 |p (x, x)
Zn := S1 + + Sn ,
Il est clair que Ht est une variable alatoire presque srement nie. On dnit le noyau de transition q sur N par
q(t, s) := P (Ht = s).
Pour expliquer l'utilit de q , considrons deux suites de variables alatoires i.i.d. indpendantes et de mme loi que S1 , soit S1 , S2 , . . . et S1 , S2 , . . ., et dnissons rcursivement une suite de variables alatoires (Wn )n0 par W0 := 0, W1 := t, puis, rcursivement, pour tout n 0,
W2n+2 := inf{S1 , S1 + S2 , . . .} [W2n+1 , +[ ,
132 et tout n 1,
W2n+1 := inf{t + S1 , t + S1 + S2 , . . .} [W2n , +[ .
Proposition 69 La suite (Ln )n1 est une chane de Markov de noyau de transition
q.
Preuve :
En notant que q(t, 0) = P (s (inf{S1 , S1 + S2 , . . .}), et en appliquant le thorme du renouvellement, nous en dduisons que
t+
(6.1)
Par ailleurs, pour tout t N donn, grce notre hypothse sur le support de la loi de S1 , nous pouvons prouver qu'il existe d1 , . . . , da et e1 , . . . , eb tous dans le support de S1 et tels que t+d1 + +da = e1 + +eb . On en dduit, au vu de la proposition 69, qu'il existe m 1 tel que
q m (t, 0) > 0.
Preuve :
En dcomposant selon la valeur du plus grand Zi strictement infrieur t, on voit facilement que
+
P (Ht u) =
0at1 =0
P (Z = a, S
+1
t a + u).
133
En notant (x) := P (S1 x), le caractre i.i.d. des (Si ) entrane que
P (Z = a, S
+1
t a + u) = P (Z = a)(t a + u).
P (Z = a) = E
=0 =0
1(Z = a)
1,
P (Ht u)
0at1
(t a + u) =
b=1
(u + b).
E(Ht ) + 1
u=0 b=1
Dnissons
K := inf{k 2; Lk = 0},
avec la convention inf = +. Au vu de la proposition 70, on dduit facilement que, sous les hypothses de la proposition, K est presque srement ni, et mme qu'il existe une constante c ne dpendant pas de t telle que
E(K) c < +.
E(S1 ) < + et que pgcd({i N; P (S1 = i) > 0}) = 1, il existe une constante C ne dpendant pas de t telle que E(WK W1 ) C.
Preuve :
WK W1 =
k=1
(Wk+1 Wk ),
d'o
E(WK W1 ) =
134 A prsent, observons que, d'aprs sa dnition, l'vnement K > k est mesurable par rapport (W0 , . . . , Wk ), tandis que, conditonnellement (W0 , . . . , Wk ), la loi de Wk+1 Wk n'est autre que q(Ln1 , ). On en dduit que
+
E(WK W1 )
sup E(Hs )
s1 k=1
P (K > k))
sup E(Hs ) c.
s1
La proposition 71 montre ensuite que sups1 E(Hs ) < +. Considrons le couplage employ dans 5.3, dont la loi du temps de couplage est 1 3 celle du premier temps d'atteinte T de la diagonale par la chane (Xn , Xn )n0 lorsque la loi initiale est la loi produit . Considrons x S , et dnissons
1 1 2 3 B0 := inf{n 0; Xn = x}, B0 := inf{n 0; Xn = x}.
On note que les implications restantes formules dans le thorme 17 sont soit triviales, soit rsultent de celles dj prouves ci-dessus. Nous renvoyons par exemple [40, 9, 36] pour plus d'informations ainsi que des rfrences sur la notion d'ergodicit de degr 2.
135
mtriquement ergodique.
Le thorme suivant fournit plusieurs caractrisations de cette proprit, et, lorsque l'une des conditions quivalentes ci-dessus est vrie, on dit que p est gop sur un ensemble
suivantes : (i) Il existe x S tel que T1 (x) possde une queue sous-gomtrique sous Px ; (ii) Pour tout x S , la queue de T1 (x) est sous-gomtrique sous Px ; (iii) Il existe x S , 0 < r < 1 et A 0 tel que, pour tout n 0,
dV T (pn (x, ), ) Arn ;
(iv) Pour tout x S , il existe 0 < r < 1 et A 0 tel que, pour tout n 0,
dV T (pn (x, ), ) Arn ;
Une consquence immdiate de (v) est qu'il existe 0 < r < 1, A 0 tels que, pour tout x S , et tout n 0,
dV T (x pn , ) Arn . (x)
On peut donc en quelque sorte choisir uniformment par rapport x la vitesse de convergence exponentielle de dV T (x pn , ) vers zro lorsque n tend vers l'inni, module par la valeur de (x).
136
Proposition 73 La variable possde une queue sous-gomtrique si et seulement Proposition 74 La somme de deux variables alatoires queue sous-gomtrique
Proposition 75 Soit (Yi )i1 une suite de variables alatoires dnies sur un espace
Pour 0 < < c2 , on a, en utilisant une intgration par parties, le fait que
exp(t)Q(Yi t|Hi1 )dt 1 + c1 (c2 )1 .
E(exp(Yi )|Hi1 ) 1 +
0
On en dduit que
E(exp((Y1 + + Yn ))) (1 + c1 (c2 )1 )n .
137
si bien que
Q(Y1 + + Yn nt) exp(n(t + log(1 + c1 (c2 )1 ))).
En choisissant assez petit, on obtient le rsultat. Nous allons commencer par prouver que (i)(vi). La preuve consiste, comme dans la section prcdente, obtenir une borne sur le temps de couplage. Au lieu de la proposition 71, nous utiliserons la proposition suivante.
ment le cas pour q(t, ), uniformment par rapport t, ou, plus prcisment : il existe f, h > 0 tels que, pour tout t 0, et tout s 0,
q(t, s) f exp(hs).
Supposons que, pour tout x 0, P (S1 x) a exp(bx) Nous allons montrer, avec les notations de la section prcdente, qu'il existe f > 0 tel que, pour tout s 0,
P (Ht k) f exp(bk).
(6.2)
P (Ht u)
0at1
(t a + u) =
w=1
(u + w).
et l'on a donc
t
P (Ht u) exp(bu)
w=1
exp(bw) f exp(bu),
en posant f =
t w=1 exp(bw)
= exp(b)(1 exp(b))1 .
138
Supposons donc que, pour tout x 0, P (S1 x) a exp(bx), et crivons WK sous la forme
K1 k=0
Preuve :
WK W1 :=
(Wk+1 Wk ).
D'autre part, du fait que la suite (Wj )j est croissante et que, par dnition, k m , on a
P (WK W1 k, K m) P (Wm W1 k) P (Wm W1 m).
La proposition en rsulte.
Preuve de (i)(v):
On reprend l'argument de la preuve donne dans la section prcdente, pour la partie du thorme 17 armant l'implication (i)-(ii)-(iii)-(iv) (vii). On obtient ainsi que
1 2 T max(B0 , B0 ) + WK W1 .
La proposition 77 entrane que WK W1 possde une queue sous-gomtrique. D'autre part, l'identit tablie dans l'exercice 125 montre que, si T1 (x) possde une queue sous-gomtrique par rapport Px , c'est galement le cas par rapport P . On arrive la conclusion annonce. Le fait que (v) (iv), (v) (iii), (ii) (i) est immdiat.
La preuve prsente ici reprend la preuve donne dans [36] du thorme de Kendall sur le renouvellement (p. 358). Cette preuve est base sur des considrations
139
d'analyse complexe1 , et il ne semble pas exister de preuve faisant appel des considrations plus probabilistes, par exemple par couplage. Supposons (iii) vrie. On en dduit facilement que la srie entire
+
F (z) :=
n=1
U (z) :=
n=0
Px (Xn = x)z n ,
dont le rayon de convergence est ncessairement 1, vu que les coecients sont des probabilits. Dans le disque {|z| < 1}, on a l'galit
F (z) = (1 z)U (z) 1.
(6.3)
P (z) :=
n=0
Grce l'identit (5.1), on vrie que l'on a, dans le disque {|z| < 1}, l'identit
U (z) = (1 P (z))1 .
On en dduit alors de (6.3) que, sur {|z| < 1}, (1 z)(1 P (z))1 = 1 + F (z), d'o
P (z) = (z + F (z))(F (z) + 1)1 .
(6.4)
Nous avons vu que F est analytique sur {|z| < r0 }. Par consquent, pour tout 0 < < r0 1, 1 + F (z) ne peut avoir qu'un nombre ni de zros dans {|z| < r0 } (sauf tre identiquement nulle, mais nous allons voir que ce n'est pas le cas). Montrons qu'aucun de ces zros ne peut appartenir {|z| 1}. Par l'absurde, soit z0 un tel zro. Notons que ncessairement z0 = 1, car 1 + F (1) = (x). Par consquent, lorsque z z0 en restant dans {|z| < 1}, z + F (z) z0 + F (z0 ) = z0 1 = 0, et donc |P (z)| + d'aprs (6.4). Mais P est borne sur {|z| 1}, car ses coecients sont des probabilits. Contradiction. Par consquent, toujours d'aprs (6.4), il existe r1 > 1 tel que P soit analytique sur {|z| < r1 }, ce qui prouve (i). La preuve prsente ci-dessus montre en fait que, si l'on dispose d'un x pour lequel la proprit nonce dans (iii) est vrie, la proprit nonce dans (i) est vrie pour le mme x. En utilisant le fait que (i) entrane (v), et que (v) entrane que la proprit nonce dans (ii) est vrie pour tout x, on en dduit que (i) entrane (ii). On conclut ainsi la preuve des quivalences contenues dans le thorme 18.
1
140
Exercice 171 Donner une preuve lmentaire que (i) entrane (ii), en utilisant
l'identit tablie dans l'exercice 125 et la stratgie du Corollaire 8.
Nous renvoyons par exemple [45, 36] pour plus de dtails sur la notion d'ergodicit gomtrique.
vers zro par rapport x, lorsque n tend vers l'inni. Avant d'noncer un thorme de caractrisation de cette proprit, nous commenons par tablir quelques rsultats relatifs aux proprits de contraction du noyau p vis--vis de la distance en variation totale. Ceci est naturel, puisque nous nous intressons la convergence de p vers un point xe, savoir la loi invariante.
Proprits de contraction de p Dnition 14 On dnit, pour tout noyau de transition p, le coecient de Dobrushin de p par (p) = supx,yS dV T (p(x, ), p(y, )).
On vrie immdiatement que 0 (p) 1.
Exercice 172 On note que (p) s'exprime de manire explicite en termes des probaProposition 78 Si p et q sont deux noyaux de transition, on a (pq) (p)(q). Preuve :
Facile avec l'interprtation par couplage de la distance en variation totale (voir par exemple [1]). On peut galement donner une preuve lmentaire (voir par exemple [7]).
Preuve :
Idem.
141
Exercice 174 Donner les dtails de la preuve de la proposition. Corollaire 25 Le coecient de Dobrushin est le coecient de contraction de p vu comme une application de l'ensemble des mesures de probabilit sur S dans lui mme, muni de la distance en variation totale. Plus explicitement :
(p) := sup
1 =2
dV T (1 p, 2 p) . dV T (1 , 2 )
et
d1 (n) := sup dV T (pt (x, ), pt (y, )) = (pn ).
x,yS
Exercice 176 Prouver la proposition ci-dessus. Caractrisations de l'ergodicit uniforme Thorme 19 Etant donn un noyau de transition ergodique
S ni ou dnombrable, de loi invariante , il y a quivalence entre les proprits p sur un ensemble
suivantes : (i) Il existe x S tel que supyS Ey (T1 (x)) < + ; (ii) Il existe x S et > 1 tels que supyS Ey (T1 (x) ) < + ; (iii) On a
n+ xS
142
(v) On a
n+
lim (pn ) = 0;
(vii) Il existe n 1 pour lequel supxS dV T (pn (x, ), ) < 1/2 ; (viii) Il existe n 1 pour lequel (pn ) < 1 ; (ix) Il existe n 1 tel que pn vrie la condition de Doeblin, i.e. il existe une mesure de probabilit sur S et > 0 telle que pn (x) (x) pour tout x S .
L'implication (i) (v) se prouve en reprenant la stratgie de preuve par couplage employ dans la preuve de l'implication (i)-(ii)-(iii)-(iv) (vii) du Thorme 17. On obtient ainsi une borne uniforme sur l'esprance du temps de couplage uniforme vis-vis du point de dpart (y1 , y2 ) S 2 . La proprit de sous-multiplicativit nonce dans la proposition 80 montre que (v) et (vi) sont quivalentes. En utilisant l'ensemble des proprits nonces dans la proposition, on dduit l'quivalence entre (iii), (iv), (v), (vi), (vii), et (viii). Inversement, (iii) permet de voir qu'il existe un x et un n tels que inf zS Pz (Xn = x) > 0. On en dduit facilement le fait qu'il existe une borne sous-gomtrique uniforme en le point de dpart pour la queue de T1 (x), ce qui n'est autre que (ii). On a par ailleurs videmment que (ii) entrane (i). On obtient ainsi l'quivalence entre les proprits (i) (viii). Il reste donc traiter le cas de (ix). Le fait que (ix) implique (viii) est une consquence de l'interprtation que l'on peut donner de (ix) en termes de couplage. Sous (ix), on peut fabriquer une famille de variables (Zx )xS et une variable Y valeurs dans S , de telle sorte que, pour tout x S , Zx suit la loi pn (x, ), tandis que Y est de loi , et telles que la probabilit que l'on ait Zx = Y pour tout x S soit suprieure ou gale . Inversement, (iii) implique facilement (ix) : il sut de choisir x S , puis n tel que
sup dV T (pn (y, ), ) (x)/2,
yS
Exercice 177 Faire en dtail les preuves esquisses ci-dessus. Exercice 178 Prouver (sans faire appel au thorme ci-dessus) que, pour une chane
de Markov ergodique sur un ensemble S ni, il existe n tel que (pn ) < 1. Donnez un exemple o (p) = 1 (et donc n = 2 au minimum). Donner galement un exemple de chane ergodique avec S inni et pour laquelle (pn ) = 1 pour tout t.
143
On retrouve en particulier, grce cet exercice le rsultat qualitatif dj obtenu en tudiant la queue du temps de couplage T introduit dans la partie prcdente : dans le cas d'un ensemble ni, la convergence en loi d'une chane ergodique vers sa loi stationnaire a toujours lieu vitesse exponentielle.
(Indication : utiliser le lemme classique sur les suites sous-additives.) 2) Montrer que l'on a galement
1 log d1 (n) = r. n+ n lim 3) Donner un exemple pour lequel il existe t 0 tel que d1 (t) = 0 (et donc en particulier r = +). (Indication : faire une tentative avec un espace deux tats.)
Ainsi, on peut par exemple, dans le cas o le noyau est uniformment ergodique, (par exemple dans le cas ergodique avec S ni), utiliser V T = inf{t; d1 (t) e1 } pour estimer la vitesse de convergence en variation totale, et dnir un temps de relaxation en variation totale permettant des comparaisons entre chanes direntes, et possdant une interprtation immdiate en termes de contrle de la vitesse de convergence.
144
Chapitre 7
Fonctionnelles additives : thorme de la limite centrale
La situation est un peu plus complexe pour le thorme de la limite centrale que pour la loi des grands nombres, et nous prsenterons trois approches, bases respectivement sur le renouvellement, les martingales et l'quation de Poisson, et la mthode de Nagaev en exploitant les proprits spectrales. Nous renvoyons par exemple [9, 36, 45] pour plus d'informations. Nous reprenons dans cette section les notations dnies dans la partie sur la loi des grands nombres. Donnons-nous donc f : S R, un noyau de transition irrductible et positivement rcurrent p de loi invariante , et une loi initiale quelconque. Nous nous restreindrons essentiellement des fonctions f vriant
(f ) = 0, (f 2 ) < +,
(7.1)
et notre objectif sera donc de prouver des thormes limites armant que, sous P , on a la convergence en loi suivante lorsque n tend vers l'inni :
n
n1/2
i=0
loi
(7.2)
o v 0 (avec la convention N (0, v) = 0 ). Notons qu'une condition telle que (7.1) n'est pas ncessaire pour que la proprit ci-dessus ait lieu. Un exemple trs simple (quoique dans un cas dgnr) est le suivant : partant d'une suite de v.a. i.i.d. valeurs relles (Yn )n0 , on fabrique la chane (Xn )n0 = (Yn , Yn+1 )n0 , dont on vrie facilement qu'elle est ergodique. On pose ensuite f (x, y) := y x, et l'on voit que l'on a toujours un thorme de la limite centrale (dgnr, avec v = 0) pour f applique la chane (Xn )n0 , car n1/2 Sn (f ) tend vers zro en probabilit. On peut pourtant facilement choisir la loi de (Y0 ) de telle manire que f ne soit pas intgrable (et l'on n'a donc alors mme
146 pas f L1 () !). Nous verrons galement qu'une condition telle que (7.1) n'est pas non plus susante en gnral. Commenons par un rsultat prliminaire montrant que l'on peut, pour prouver un thorme de la limite centrale, choisir la loi initiale notre guise.
Proposition 81 Si une limite telle que (7.2) a lieu pour une loi initiale donne,
Preuve :
Pour le voir lorsqu'il y a apriodicit, il sut par exemple de considrer un couplage entre deux versions de la chane tel que celui dni dans la preuve par couplage du Thorme 11, et de constater que la dirence entre les deux sommes renormalises que l'on considre tend vers zro avec probabilit 1. Lorsqu'il y a priodicit, on dcompose en classes et l'on se ramne l'argument prcdent en considrant un itr apriodique du noyau de dpart.
T1 (a)1
2 f (Xi ) < +.
f (Xi ) = 0, Ea
i=0
(7.3)
Alors, lorsque n tend vers l'inni, on a, pour toute loi initiale , la convergence en loi n
n1/2
i=0
loi
o
v= Ea
Ea (T1 (a))
On notera que, sous rserve que f soit intgrable par rapport , la premire cycle hypothse du thorme signie que (f ) = 0 (en se rappelant que = Eaa 1 (a)) ). (T De fait, si f est intgrable par rapport , la loi des grands nombres pour les fonctionnelles additives montre que l'on doit avoir (f ) = 0 pour esprer obtenir un TCL. Notons que la condition (f 2 ) < + se traduit par
Ea
i=0 T1 (a)1
f 2 (Xi ) < +,
ce qui n'est pas du tout la mme chose que la deuxime hypothse du thorme.
147
que la variance asymptotique soit gale 0 sans que f soit une fonction constante. Ceci tant, une variance nulle signie que T1 (a)1 f (Xi ) = 0 avec probabilit 1 sous i=0 Pa , ce qui restreint tout de mme la classe des fonctions f pouvant donner lieu une variance nulle ! Par ailleurs, l'exemple trs simple donn prcdemment montre que la variance de la gaussienne obtenue la limite dans le TCL n'est pas ncessairement gale (f 2 ), comme une analogie nave avec la loi des grands nombres pourrait le faire croire : la dpendance entre les termes successifs de la chane fait que la variance limite n'est pas en gnral identique celle que l'on obtiendrait si les variables alatoires (f (Xi ))i0 taient i.i.d.
Dans cette preuve, nous travaillerons sous la probabilit Pa , ce qui est licite car nous avons vu que l'on pouvait choisir arbitrairement la loi initiale sous laquelle travailler pour prouver un thorme de la limite centrale dans notre contexte. Nous reprenons les notations dj employe dans le chapitre sur la loi des grands nombres, savoir n
Sn (f ) =
j=0
f (Xj ),
Li (f ) =
j=Ti (a)
f (Xj ),
On reprend la dcomposition dj utilise pour prouver la loi des grands nombres, qui se simplie quelque peu par le fait de travailler sous Pa :
Rn 1 n
Sn (f ) =
i=0
Li (f ) +
j=TRn (a)
f (Xj ).
(7.4)
n1/2
j=TRn (a)
f (Xj )
tend vers zro en probabilit lorsque n tend vers l'inni, et il nous sura d'tablir ensuite le TCL pour
Rn 1 i=0
1/2
Li (f ).
148 En eet, rappelons que, si une suite (Zn )n0 de variables alatoires relles converge en loi vers une loi limite , il en va de mme de toute suite de la forme
(Zn + Vn )n0
telle que Vn tende vers zro en probabilit lorsque n tend vers l'inni. (Pour le voir, passer par exemple par la transforme de Fourier.) Nous utiliserons alors le fait suivant : si une suite de variables alatoires (Zn )n0 est tendue, et si ( n )n0 est une suite (dterministe) tendant vers zro, alors
( n Zn )n0
tend vers zro en probabilit lorsque n tend vers l'inni. Commenons donc par prouver le rsultat gnral suivant.
f (Xj )
n0
est tendue.
On note que cette preuve ne fait aucune hypothse sur f , et amliore donc celle donne dans la preuve de la loi des grands nombres, qui utilisait le fait que (|f |) < +. En particulier, on voit que, dans la loi des grands nombres, les termes de bord peuvent toujours tre ngligs, que f soit intgrable sous ou non. Partons de l'ingalit
n n
Preuve :
f (Xj )
j=TRn (a) j=TRn (a)
|f (Xj )| .
A prsent,
Pa
j=TRn (a) n
|f (Xj )| t =
n k=0
Pa
n j=k
Pa
n j=k
|f (Xj )| t, Xk = a, Xk+1 = a, . . . , Xn = a .
149
|f (Xj )| t =
n k=0
Pa (Xk = a)Pa
nk j=0
entrane l'vnement
T1 (a)
j=0
|f (Xj )| t
+ m=0
Pa
T1 (a)
t = 0. D'autre part,
t, T1 (a) > m
de conclure que
> m) < + car Ea (T1 (a)) < + par hypothse. Le thorme de convergence domine (appliqu la mesure de dnombrement sur N) permet donc Pa
m=0 j=0 T1 (a)
+ t+
lim
et donc que
t+ n0
lim sup P
f (Xj ) t = 0.
n 0
n1/2
j=TRn (a)
f (Xj )
150 tend vers zro en probabilit. Il nous reste donc prouver le thorme de la limite centrale pour
Rn
1/2 i=1
Li (f ).
et l'on peut donc appliquer le thorme de la limite centrale pour les v.a.i.i.d. centres et de carr intgrable
k
k 1/2
i=0
Li (f )
lorsque k tend vers l'inni, mais le fait que Rn soit alatoire et certainement pas indpendante des Li (f ) ne nous permet pas de faire k = Rn dans la limite correspondante et d'en dduire le rsultat directement, comme cela tait possible dans la preuve de la loi des grands nombres, dans laquelle on pouvait considrer le comportement asymptotique presque sre des suites qui intervenaient. Nous utilisons donc l'argument un peu plus sophistiqu qui suit. D'aprs la preuve par renouvellement donne dans la partie sur la loi des grands nombres, on a la convergence suivante :
n+
o = (Ea (T1 (a)))1 . Par consquent, pour tout 0 < < 1 et que, pour tout n assez grand,
Pa (1 ) n1 Rn (1 + ) 1 .
En utilisant le fait que les Li (f ) sont i.i.d., centres, et de carr intgrable sous Pa , on voit facilement que la suite (G1 )k0 dnie par k
n +k
G1 k
:=
j= n +1
Lj (f )
est une martingale, et que l'ingalit maximale pour les martingales (voir par exemple [49, 18], ou le mmento sur les martingales donn dans ces notes) entrane que, pour tout t 0,
n +1
Pa
max
k=0
G1 tn1/2 k
t2 n1 Ea
G1n
+1
= kE(|L1 (f )|2 ),
151
Pa
max
k=0
G1 tn1/2 k
n j= n k
En dnissant G2 := k
n +1
Pa
max
k=0
G2 tn1/2 k
Posons alors
Rn
Lj (f ) ,
dn := n1/2
j=0
Lj (f )
j=0
G1 + max k
k=0
n +1
G2 . k
On obtient maintenant facilement le fait que dn tend vers zro en probabilit lorsque n tend vers l'inni. On conclut en appliquant le thorme de la limite centrale pour n les suites i.i.d. centres de carr intgrable n 1/2 i=0 Li (f ). De manire remarquable, il est possible de prouver une rciproque au thorme que nous venons de prouver.
T1 (a)1
2 f (Xi ) < +.
f (Xi ) = 0, Ea
i=0
On note que le rsultat est en fait plus fort qu'une simple rciproque, puisqu'il ne suppose que la tension pour en dduire les hypothses du thorme 20. Par consquent, au vu des deux thormes 20 et 21, la tension de la suite
n1/2 Sn (f )
n1
entrane automatiquement la validit du thorme de la limite centrale. En particulier, on ne peut avoir de loi limite autre que gaussienne dans notre contexte. Qui plus est, le thorme de la limite centrale peut toujours tre obtenu grce l'approche par renouvellement. On obtient galement que la validit de l'hypothse 7.3 pour un
152 preuve directe de ce dernier fait peut tre trouve dans [10]. Le plan de la preuve du thorme 21 est le suivant : on prouve d'abord que la suite
n
a S entrane sa validit pour tout a S , ce qui n'est pas vident a priori. Une
n1/2
i=0
Li (f )
n1
Thorme 22 Soit (Zn )n0 une suite de variables alatoires i.i.d. Alors la suite
n1/2 (Z0 + + Zn )
n1
2 Le fait que les hypothses E(Z0 ) < + et E(Z0 ) = 0 entranent la tension de la suite
n1/2 (Z0 + + Zn )
n1
est une consquence immdiate du thorme de la limite centrale pour les variables alatoires i.i.d. centres de carr intgrable. Pour la rciproque, considrons une suite de variables alatoires (Zn )n0 indpendante de (Zn )n0 , et de mme loi. Posons, pour tout i 0,
Wi = Zi Zi ,
On note que la suite (Yi )i0 est une suite de variables alatoires indpendantes bornes, et vriant donc E(Yi2 ) < +. De plus, la dnition de Wi entrane que Wi et Wi ont la mme loi, ce qui entrane que l'on a ncessairement E(Yi ) = 0. On peut donc appliquer le thorme de la limite centrale pour les variables alatoires i.i.d. centres de carr intgrable pour dduire que, lorsque n tend vers l'inni, la loi de
n1/2 (Y0 + + Yn )
Par ailleurs, observons que, toujours en vertu de la dnition symtrique de Wi , pour tout i, on a l'identit en loi suivante :
(Yi , Wi 1(|Wi | > K)) = (Yi , Wi 1(|Wi | > K)).
loi
153
On en dduit que
n n n n
Yi ,
i=0 i=0
Wi 1(|Wi | > K)
loi
Yi ,
i=0 i=0
Wi 1(|Wi | > K) .
P
i=0
Yi t,
i=0
=P
i=0
Yi t,
i=0
On en dduit que
n n n
P
i=0
Yi t,
i=0
Wi 1(|Wi | > K) 0
(1/2)P
i=0
Yi t .
P
i=0
Wi t
(1/2)P
i=0
Yi t
(7.5)
et
n1/2 (Z0 + + Zn )
n1
n1/2 (Y0 + + Yn ),
on en dduit que l'on peut faire en sorte que, pour n assez grand,
n
P
i=0
Yi t
1/3
154 (il sut de choisir K de telle sorte que la variance limite soit assez grande, et l'on peut s'approcher aussi prs que l'on veut de 1/2). Mais l'ingalit (7.5) entrane alors que
n
P
i=0
Wi t
2 ce qui conduit une contradiction. On en dduit que E(W0 ) < +. En conditionnant par un vnement de la forme a Z0 b de probabilit non-nulle, on en dduit 2 que E(Z0 ) < +. A prsent, on sait que E(|Z0 |) < +, et l'on doit ncessairement avoir E(Z0 ) = 0, sans quoi la loi forte des grands nombres contredit manifestement l'hypothse sur la tension de la loi de
n1/2 (Z0 + + Zn )
n0
Comme dans la preuve du thorme 20, nous xons a S , et nous nous plaons sous la probabilit Pa . L'hypothse du thorme nous permet de prouver la tension de (n1/2 (Sn (f )))n1 sous Pa , en utilisant un argument semblable celui qui permet de prouver la proposition 81. Nous allons en dduire la tension sous Pa de la suite
n
n1/2
i=0
Li (f )
n1
Li (f )
n1
= n1/2 ST
(a)1 (f )
n1
(a)1 (f )
2M n1/2
(a)1 (f )
2M n1/2 , Rn n
La loi des grands nombres dj utilise dans la preuve du thorme 20 entrane que
n+
lim Pa (Rn n ) = 0.
155
D'autre part,
Pa ST
n
(a)1 (f )
2M n1/2 , Rn n
Pa
1kRn
max
Dnissons
:= inf Tk (a); k 1, STk (a)1 (f ) 2M n1/2
(avec la convention inf = +). On constate que est un temps d'arrt de la chane (Xi )i0 tel que X = a si < +, et que
{ n} =
1kRn
max
{ n}
i=
f (Xi ) M n1/2
|Sn (f )| M n1/2 .
Pa
i=
f (Xi ) M n1/2 F
= PXu
i=0
f (Xi ) M n1/2
En utilisant le fait que X = a si < +, on en dduit que le membre de droite de l'identit prcdente est suprieur ou gal
c :=
0mn1
min
Pa |Sm (f )| M n1/2 .
max
c Pa |Sn (f )| M n1/2 .
La tension de la suite
n1/2 (Sn (f ))
n1
max
(a)1 (f )
n1
est tendue. Donnons prsent quelques exemples de situations dans lesquelles il est possible de vrier les hypothses du TCL tel que nous l'avons nonc prcdemment.
Preuve :
T1 (a)1 Il est immdiat que |f |(Xj ) T1 (a) sup |f |. Ensuite, l'ergodicit de j=0 degr 2 entrane le fait que Ea (T1 (a)2 ) < +. On en dduit que
Ea
T1 (a)1
2 |f (Xj )| < +.
j=0
2 f (Xj ) < +
que
f (Xj ) = (f ) = 0.
Ea
T1 (a)1
j=0
Il se trouve que la proposition ci-dessus admet une rciproque (voir [9] pour une preuve) : si le TCL a lieu pour toutes les fonctions bornes, alors on doit avoir ergodicit de degr 2.
Proposition 83 Si f
L2+ () pour un
Preuve :
On a
T1 (a)1 T1 (a)1
f (Xj )
j=0 j=0
|f (Xj )| .
157
2 |f (Xj )| =
i,j0
Posons
ui := Ea |f |2+ (Xi )1(T > i)
En choisissant s > 1 tel que 1/(2 + ) + 1/(2 + ) + 1/s + 1/s = 1, l'ingalit de Hlder entrane que, pour tous i, j 0,
Ea (|f |(Xi )1(T > i)|f |(Xj )1(T > j)) ui
1/(2+ ) 1/(2+ ) uj Pa (T
On en dduit que
j=0 T1 (a)1
2 |f (Xj )|
+ 1/(2+ ) ui Pa (T i=0
> i)
1/s
Or, d'aprs l'hypothse que f L2+ (), et en se rappelant que = voit que
+ +
on
Ea |f |
i=0
2+
ci < +.
Par ailleurs, l'ergodicit gomtrique entrane que Pa (T > i) tend exponentiellement rapidement vers zro lorsque i +. Toujours d'aprs l'ingalit de Hlder,
+ 1/(2+ ) ci Pa (T i=0 + 1/(2+ ) + 1/u
> i)
1/s
i=0
ci
i=0
Pa (T > i)
u/s
2 |f (Xj )| < +.
La preuve s'achve comme celle de la proposition prcdente. On peut construire des contre-exemples cette proposition dans le cas o l'on suppose seulement le fait que f L2 () (voir par exemple [24, 6]). En revanche on a toujours un TCL lorsque f L2 () si l'on suppose en plus que pk est uniformment ergodique, ou la rversibilit (voir [45]).
158
alors, lorsque n tend vers l'inni, on a, pour toute loi initiale , la convergence en loi
n
n1/2
i=0
loi
o
v = (g 2 ) ((pg)2 ) = E (g(X1 ) pg(X0 ))2 < +.
La preuve du thorme s'appuie sur le thorme de la limite centrale pour les martingales, dont nous donnons ici la version qui nous sera utile (voir par exemple [18, 49]) pour une preuve et des noncs plus gnraux.
Thorme 24 Soit
vriant les conditions suivantes : M0 = 0 ; 2 pour tout n 0, E(Mn ) < + ; on a la convergence en probabilit suivante :
n n+
(Mn )n0 une martingale par rapport une ltration (Fn )n0
lim n
1 k=1
lim n
1 k=1
Alors, lorsque n tend vers l'inni, on a, pour toute loi initiale , la convergence en loi
n1/2 Mn N (0, v).
loi
Nous ne donnerons pas de preuve de ce rsultat, mais au moins une petite ide (trs grossire) de preuve, an que le rsultat n'apparaisse pas comme trop mystrieux.
159
Preuve (esquisse):
Pour R, on introduit
Cn := exp(in1/2 Mn ), Gn () :=
1kn
et
() = exp(2 v 2 /2).
lim Gn () = ().
En utilisant que Gn () tend en probabilit vers () = 0 lorsque n tend vers l'inni, on en dduit que
n+
o l'absence de terme d'ordre 1 en s'explique par le fait que, par la proprit de martingale, E(Mk Mk1 |Fk1 ) = 0. En ngligeant les termes d'erreurs, on en conclut que
Gn ()
1kn
puis que
n
Gn ()
1kn
exp (2 /2)
k=1
160 d'o l'on dduit le rsultat, condition de pouvoir convenablement contrler les termes d'erreur que nous avons ngligs.
On note que la nitude de v sous l'hypothse que g L2 (), ainsi que l'identit donnant une seconde expression de v , sont immdiates. Partant de la relation f = g pg , on peut crire que
n
f (X0 ) + + f (Xn ) =
i=0
g(Xi ) pg(Xi ),
d'o
f (X0 ) + + f (Xn ) = g(X0 ) pg(Xn ) + Mn ,
(7.6)
o l'on a pos
Mn :=
n1
g(Xi+1 ) pg(Xi ).
i=0
On constate que (Mn )n est une martingale par rapport la ltration naturelle de la chane (Fn )n0 . Avant d'appliquer le thorme de la limite centrale pour les martingales Mn , expliquons comment contrles les deux termes de bord apparaissant dans l'quation (7.6) On a videmment que n1/2 g(X0 ) tend p.s. vers zro lorsque n tend vers l'inni. Quant n1/2 pg(Xn ), on lui rgle son compte en utilisant par exemple le fait que, comme par hypothse ((pg)2 ) < +, on a la loi des grands nombres pour
n1 (pg)2 (X0 ) + + (pg)2 (Xn )
(On peut galement par exemple partir sous la loi et utiliser le fait que la loi de pg(Xn ) ne dpend alors pas de n.) Il reste vrier que l'on peut appliquer le TCL pour les martingales Mn . On vrie que
E ((g(Xi+1 ) pg(Xi ))2 |Fi ) = p(g 2 )(Xi ) (pg(Xi ))2 .
En appliquant la loi des grands nombres la fonctionnelle additive obtenue avec la fonction h dnie par
h(x) := p(g 2 )(x) (pg(x))2 ,
lim n
1 i=0
161
1 i=0
tend presque srement vers zro, pour tout > 0. On rapplique pour cela la loi des grands nombres la fonctionnelle additive obtenue en prenant avec la fonction hc dnie par
hc (x) := Ex (g(X1 ) pg(X0 ))2 1((g(X1 ) pg(X0 ))2 c) ,
lim n
1 i=0
Comme
(hc ) = E (((g(X1 ) pg(X0 ))2 1((g(X1 ) pg(X0 ))2 c)),
lim (hc ) = 0,
ce qui permet de conclure. Etant donne f L2 () telle que f puisse se mettre sous la forme g pg , o g L2 (), on voit que f doit ncessairement vrier (f ) = 0. Une bonne question est donc, tant donne f L2 () telle que (f ) = 0, y a-t-il existence (et, pourquoi pas, unicit) de solutions de l'quation de Poisson associe f ? Notons que nous ne sommes pas dans le cadre de l'quation de Poisson avec frontire absorbante tudi dans un chapitre antrieur. Concernant l'unicit, nous avons le rsultat suivant :
Preuve :
On a alors p(g1 g2 ) = g1 g2 . En itrant, on en dduit que pn (g1 g2 ) = g1 g2 . La loi des grands nombres applique g1 g2 entrane alors que g1 g2 = (g1 g2 ).
g=
k=0
pk f.
162 Lorsque la srie ci-dessus converge au sens de L2 (), on obtient eectivement une solution de l'quation tudie. On obtient ainsi la proposition ci-dessous.
f L2 (), si + pk f converge dans L2 (), alors k=0 en notant g la somme de la srie, on a f = g pg .
G(x, y) =
Celle-ci dire de celles tudies dans le chapitre d'introduction la thorie du potentiel dans le cas sans frontire, par la soustraction de , et l'objet dni (formellement) ci-dessus est appel potentiel rcurrent. Il permet, condition que la convergence de la chane vers sa loi stationnaire soit susamment rapide, d'obtenir un objet pouvant jouer le rle d'une fonction de Green, alors mme que la srie + pn (x, y) n=0 possde toujours une valeur innie. Nous avons en fait dj rencontr cet objet dans l'exercice 167. Mentionnons que l'approche du thorme de la limite centrale base sur l'quation de Poisson a donn lieu l'important rsultat de Kipnis et Varadhan (voir [29]), qui, dans le cas rversible, fournit un thorme de la limite centrale pour des chanes de Markov ergodiques valeurs dans des espaces d'tats gnraux. La preuve de ce rsultat repose galement sur l'utilisation de la thorie spectrale de l'oprateur auto-adjoint associ l'action du noyau sur L2 (). Notons que cette approche permet de traiter les deux exemples vus dans la partie prcdente.
163
> 0 donn, satisfait (f ) = 0, et si p
Proposition 87 Si
est gomtriquement ergodique, alors les hypothses de la proposition 85, et donc du thorme 23, sont satisfaites.
f L2+ () pour un
Preuve :
Grce au rsultat de l'exercice 155 appliqu avec 1 = pk (x, ) et 2 = .on ob1/2 tient que, pour tout x S , |pk f (x)| (pk |f |2 (x))1/2 + ||f ||L2 () dV T (x pk , ) . On en dduit que
|pk f (x)|2 (x)
xS xS
D'aprs nos hypothses, il est clair que k0 xS ||f ||2 2 () dV T (x pk , )(x) < +. L D'autre part, en appliquant l'ingalit de Hlder, on en dduit que
(pk |f |2 (x))dV T (x pk , )(x)
xS
(p |f | (x))
xS
1+ /2
(x)
xS
dV T (x p , )
1+2/
(x)
Ensuite, en utilisant l'ingalit (pk |f |2 (x))1+ /2 pk |f |2+ (x), on peut conclure que la srie n pn f converge normalement dans L2 ().
v=
Ea (T1 (a))
164
f L2 (), si
+ k k=0 p f
(g 2 ) ((pg)2 ) = V (f (X0 )) + 2
k=1
(rappelons-nous que (f ) = 0). Un calcul facile obtenu en dveloppant le carr, utilisant la stationnarit de , montre que
n
V n1/2 Sn (f ) = c(0) + 2
k=1
(1 k/n)c(k).
Si la srie
+ k=1 ck
lim V n
1/2
Sn (f ) = c(0) + 2
k=1
ck ,
et l'on retrouve alors l'expression de la variance obtenue dans la proposition prcdente. On note que celle-ci fait apparatre le terme que l'on aurait eu si les (f (Xi ))i0 taient i.i.d., savoir c(0), auquel s'ajoutent des termes de covariance lis la dpendance existant entre ces variables.
Preuve :
et les thormes 20 et 21 entranent donc la validit du TCL. Un problme est que l'on ne peut pas garantir en gnral que, lorsque la proposition ci-dessus s'applique, la variance asymptotique dans le TCL (celle de la gaussienne) est eectivement gale la limite de la variance des sommes partielles. Il est
165
pour cela ncessaire d'ajouter des hypothses. Nous avons vu dans la partie prcdente que, si + pk f converge dans L2 (), alors c'est eectivement le cas. C'est k=1 donc ce qui se produit dans les deux exemples que nous avons donns (ergodicit de degr 2 + fonction borne, ou ergodicit gomtrique + fonction de L2+ ()). Il est en fait possible (voir [9]) de prouver le rsultat plus fort suivant :
Proposition 90 Si la srie
2
+ k=1 c(k)
Nous retiendrons que, de manire gnrale, les hypothses permettant d'obtenir le TCL portent sur la rapidit de la convergence de pk vers l'quilibre, de manire assez analytique dans cette partie, de manire plus implicite dans l'approche par renouvellement. Notons qu'il est galement possible d'obtenir des principes d'invariance, c'est-dire la convergence en loi des trajectoires renormalises vers un mouvement brownien. Pour une discussion plus dtaille des liens entre l'existence d'un TCL et les direntes expressions possibles de la variance, nous renvoyons [25].
166
Chapitre 8
Critres de drive
Les critres de drive drift criteria en anglais, encore appels critres de fonctions de Lyapounov fournissent l'un des outils utiliss en pratique pour tudier le comportement en temps long des chanes de Markov. Ils ont l'avantage de ne faire appel qu' une analyse un pas des transitions de la chane. Notons l'analogie troite entre les thormes qui suivent et ceux qui ont cours dans le contexte des fonctions de Lyapounov associes aux quations direntielles. Nous ne prsentons ici que les exemples les plus simples de ces critres, dont il exsite de nombreux ranements. Nous renvoyons [36, 19] ou encore [7], pour plus de dtails et des exemples d'utilisation de ces critres.
8.1
ou dnombrable S , et supposons qu'il existe une fonction V : S R vriant les proprits suivantes : (i) pour tout x S , V (x) 0 ; (ii) V n'est pas constante sur S ; (iii) pour tout x S , Ex (V (X1 )) < + ; (iv) pour tout x S , Ex (V (X1 ) V (X0 )) 0 ; (v) il existe C 0 tel que, pour tout x S , Ex |V (X1 ) V (X0 )| C . Alors la chane est soit transiente, soit rcurrente nulle.
Preuve :
(V (Xi+1 ) V (Xi )) ,
168 soit
V (XT1 (x) ) = V (X0 ) +
i=0
Ey
i=0
=
i=0
et le fait que
Ey (V (Xi+1 ) V (Xi )|Fi ) 0
car T1 (x) > i est un vnement de Fi . Or, avec probabilit 1 sous Py , on a V (X0 ) = V (y), et, en utilisant la rcurrence suppose, V (XT1 (x) ) = V (x). On dduit donc de cette positivit le fait que V (x) V (y) pour tous x et y , donc V doit tre constante. Contradiction.
et V (i) = i montre que les hypothses (i) (iv) ne susent pas assurer la nonrcurrence positive.
Critres de drive
169
Preuve :
On remarque que les hypothses entranent automatiquement que Ey (V (Xn )) < + pour tous y et n. Ce rsultat a en fait dj t vu : V est une fonction surharmonique positive non-constante sous Px , ce qui est impossible si la chane est rcurrente. Pour la rciproque, on suppose qu'il y a transience, et l'on xe un point a et on prend la fonction dnie par V (x) := Px (T1 (a) < +) si x = a, et V (a) := 1.
(iv) pour tout K , l'ensemble {x S; V (x) K} est ni. Alors la chane est rcurrente.
Considrons y S \ C . On remarque que l'hypothse entrane facilement que Ey (V (Xn )) < + pour toutn. Posons T1 (C) = inf{n 0; Xn C} (avec la convention habituelle inf = +). On pose
Yn = V (Xn )1(T1 (C) > n).
Preuve :
Comme T1 (C) est un temps d'arrt, l'vnement {T1 (C) > n} est mesurable par rapport Fn , et l'on a donc
Ey (V (Xn+1 )1(T1 (C) > n)|Fn ) = Ey (V (Xn+1 ))|Fn )1(T1 (C) > n).
et donc le fait que (Yn ) est une surmartingale positive par rapport (Fn ), pour la probabilit Py .Par le thorme de convergence des surmartingales, Yn tend donc avec probabilit 1 (sous Py ) vers une limite (a priori alatoire) nie lorsque n tend vers l'inni, et donc, sur l'vnement {T1 (C) = +}, V (Xn ) tend avec probabilit 1 vers une limite nie. Par ailleurs, si nous supposons le noyau transient, l'hypothse (iv) entrane que, pour tout entier K l'ensemble, ni d'aprs nos hypothses, {x S; V (x) K} n'est visit qu'un nombre ni de fois par la chane, et par consquent on doit avoir limn+ V (Xn ) = + avec probabilit 1. En revenant (Yn ), on constate donc que l'vnement {T1 (C) = +} doit donc avoir une probabilit nulle sour Py , y pouvant tre choisi arbitrairement hors de l'ensemble C . Par irrductibilit de la chane, et en utilisant le fait que C est un ensemble ni, on en dduit facilement que la chane est rcurrente (en cas de doute, regarder la preuve du thorme suivant), d'o une contradiction. On conclut donc nalement que p est transient.
on peut seulement supposer que V est borne infrieurement, quitte lui ajouter une constante.
Preuve :
On remarque que l'hypothse entrane automatiquement que Ey (V (Xn )) < + pour tous y et n. On reprend les notations utilises dans la preuve du thorme prcdent. D'aprs celui-ci, on sait dj qu'il y a rcurrence. On vrie facilement que les hypothses entranent le fait que, pour x C , Ex (Yn+1 ) Ex (Yn ) Px (T1 (C) > /
Critres de drive
171
n). On en dduit facilement en itrant et en utilisant la positivit de Y , que Ex (Y0 ) n i=0 Px (T1 (C) > i), d'o le fait que Ex (T1 (C)) V (x)/ .
d'o
Ex (T1 (C)) 1 +
y C /
la dernire expression tant nie grce l'hypothse (ii). On obtient ainsi une borne explicite sur Ex (T1 (C)) en termes de V et . On conclut ensuite la rcurrence positive de la faon suivante. Partant de y C , dnissons une suite de temps alatoires par 0 := 0 et, pour tout i 0, i+1 := inf{n i + 1; Xn C}. On vrie facilement que les i sont des temps d'arrt, et que la suite (Xi )i0 est une chane de Markov sur l'ensemble C , irrductible car la chane de dpart l'est, et donc positivement rcurrente du fait que C est ni. Pour x C , appelons H(y) := inf{i 1; Xi = y}. Nous savons donc que Ey (Hy ) < +. Pour tout k 0, posons Sk := k+1 k . Notons que l'on a l'identit
H(y) +
T1 (y) = H(y) =
k=0
Sk =
k=0
A prsent, notons que l'vnement H(y) > k est mesurable par rapport la tribu Fk . Par consquent, la proprit forte de Markov applique l'instant k entrane que
Ex (Sk 1(H(y) > k)) M Px (H(y) > k),
o
M := sup Ex (T1 (C)),
xC
en utilisant le fait que Xk C . D'aprs ce qui prcde, Ex (T1 (C)) < + pour tout x S , et C est un ensemble ni, donc M < +. On en dduit que Ex (T1 (y)) + M k=0 Px (H(y) > k) = M Ey (H(y)) < +. Pour la rciproque, on prend a S , et l'on pose V (x) = Ex (T1 (a)) pour x = a, V (a) = 0, et C = {a}.
172
Preuve :
Notons que la positivit de V impose que 1. On reprend les notations prcdentes, en posant cette fois
Yn = n V (Xn )1(T1 (C) > n), 0
et, par consquent, pour tout n 0, Ex (Yn ) Ex (Y0 ) V (x). En utilisant l'hypothse (i), on en dduit que, pour tout n 0,
n Px (T1 (C) > n) V (x), 0
p(x, y)
d'o
Ex (T1 (C)) +
y C /
T1 (y) = H(y) =
k=0
Sk .
Critres de drive
173
En utilisant le fait que (Xi )i0 est une chane de Markov sur un ensemble ni, on dduit que, pour y C , H(y) possde une queue sous-gomtrique sous Py . Ensuite, pour tout k, la proprit forte de Markov entrane que Ey (Sk |Fk ) = EXk (T1 (C) ). Or, en vertu de ce qui prcde, C tant un ensemble ni, supxC Ex (T1 (C) ) < +. Au vu de ce rsultat, et des estimations prcdentes, on constate que l'on peut appliquer la proposition 75 la suite (Sk )k0 . A prsent, pour tout > 0, nous pouvons crire que, par la borne de la runion,
Py (T1 (y) n) Py (H(y) n) + Py
k=0 n
S k n .
Comme H(y) possde une queue sous-gomtrique, Py (H(y) n) est exponentiellement petit en n pour tout > 0, tandis que le lemme ci-dessus nous montre n que Py ( k=0 Sk n) est exponentiellement petit en n pourvu que soit sufsament petit. On en dduit que, pour tout y S , il existe a, b > 0 tels que Py (T1 (y) n) a exp(bn), ce qui prouve le rsultat. Pour prouver la rciproque, on considre un point a tel que T1 (a) possde une queue sous-gomtrique sous Pa . On utilise le thorme 18 et le rsultat de l'exercice 125, qui entrane facilement l'existence de r > 1 tel que Ex (rT1 (a) ) < + pour tout x S . On pose alors V (x) = Ex (rT1 (a) ), pour x = a, V (a) = 1, et C = {a}.
174
Chapitre 9
Principe des mthodes de Monte-Carlo par chanes de Markov
On dsigne par le nom gnrique de mthodes de Monte-Carlo par chanes de Markov (ou Markov Chain Monte Carlo, souvent abrg en MCMC, en anglais les mthodes consistant simuler une loi de probabilit partir d'une chane de Markov ergodique de loi invariante . Le principe de base de la mthode est le suivant : en simulant n pas de la chane, avec n susamment grand, on s'attend ce que Xn fournisse une variable alatoire approximativement distribue selon la loi . Alternativement, la loi des grands nombres entrane que n1 Sn (f ) fournit une approximation de (f ).
176 ment que la loi simuler n'est connue qu' une constante multiplicative prs. Cependant, les mthodes MCMC peuvent tre mises en uvre dans diverses situations o la probabilit de rejet obtenue par cette mthode directe est prohibitivement petite, permettant en quelque sorte une approche progressive de la loi simuler n'entranant que des probabilits de rejet raisonnables chaque pas.
Mthodes MCMC
177
178 nulle d'tre slectionn par ce mcanisme de transition, qui laisse donc S0 stable. On vrie par ailleurs aisment le caractre irrductible et apriodique du noyau ainsi obtenu sur S0 , ainsi que la rversibilit de par rapport celui-ci.
Chapitre 10
Appendice : Mmento sur les martingales
Dans cet appendice, nous rcapitulons brivement les dnitions et les proprits relatives aux martingales que nous aurons l'occasion d'utiliser dans ce cours. Attention ce qui suit omet plusieurs rsultats et notions importants, car nous nous contentons de mentionner ce dont nous avons explicitement besoin. Les ouvrages classiques sur la thorie des probabilits contiennent en gnral un chapitre (ou plus) consacr aux martingales, et la lecture d'un tel chapitre est vivement recommande. Mentionnons par exemple [18, 49, 53].
(Mn )n0 dnie sur un espace de probabilit (, F, P ) est une martingale par rapport une ltration (Fn )n0 de F (c'est--dire une famille de sous-tribus de F telle que, pour tous n m, Fn Fm ) si, pour tout n 0, les conditions suivantes sont vries :
180
la ltration (Fn )n0 , et que (Mn )n0 est une martingale pour cette ltration (resp. sous-martingale, resp. sur-martingale), alors la suite (MT n )n0 est galement une martingale (resp. sous-martingale, resp. sur-martingale) pour cette ltration. (Avec la notation usuelle : a b = min(a, b).)
Corollaire 30 Si
(Mn )n0 est une martingale pour cette ltration (resp. sous-martingale, resp. surmartingale), alors E(XT ) = E(X0 ) (resp. , resp. ).
Si (Mn )n0 est une martingale, on a, pour tout p > 1, et tout n 0, l'ingalit
0kn
max |Mk |
E (|Mn |p ) . p
une sur-martingale ou une sous-martingale, telle que supn0 E|Mn | < +, alors, avec probabilit 1, la limite M+ := limn+ Mn existe dans R, et E|M+ | < +.
(Mn )n0 est une martingale positive, ou une sur-martingale positive.
Chapitre 11
Appendice : Mmento sur la thorie ergodique
Dans cet appendice, nous rcapitulons brivement les dnitions et les proprits relatives la thorie ergodique que nous aurons l'occasion d'utiliser dans ce cours. Attention ce qui suit omet plusieurs rsultats et notions importants, car nous nous contentons de mentionner ce dont nous avons explicitement besoin. Voir par exemple [18, 49] pour une introduction la thorie, et par exemple [41] pour une prsentation plus approfondie. L'objet de base de la thorie est la donne d'un espace probabilis (, F, P ) muni d'une application mesurable T : S S qui prserve la probabilit P , c'est--dire que la mesure-image de P par T est gale P .
I l'ensemble des sous-ensembles invariants de F , et l'on vrie qu'il constitue une sous-tribu de F .
Dnition 17 On dit que T est ergodique lorsque I est triviale pour P , i.e. P (A)
{0, 1} pour tout A I .
Etant donne une variable alatoire X dnie sur (, F, P ) et valeurs relles, dnissons la variable Sn (X) par
n
Sn (X) :=
i=0
X T i,
o T i dsigne la fonction obtenue en composant i fois par T . Le thorme fondamental que nous utiliserons est le suivant, connu sous le nom de thorme ergodique de Birkho.
182
X dnie sur (, F, P ) et
lim
On voit en particulier que, si T est ergodique, la limite dans le thorme cidessus n'est autre que E(X), et est donc gale une constante (alors que E(X| I) est gnriquement une variable alatoire).
Bibliographie
[1] D. J. Aldous and J. A. Fill. Reversible Markov Chains and Random Walks on Graphs. Book in preparation. Drafts available at http ://[Link]/users/aldous/RWG/[Link]. [2] David Aldous and Persi Diaconis. Shuing cards and stopping times. Amer. Math. Monthly, 93(5) :333348, 1986. [3] V. Anantharam and P. Tsoucas. A proof of the Markov chain tree theorem. Statist. Probab. Lett., 8(2) :189192, 1989. [4] William J. Anderson. Continuous-time Markov chains. Springer Series in Statistics : Probability and its Applications. Springer-Verlag, New York, 1991. An applications-oriented approach. [5] Vlad Stefan Barbu and Nikolaos Limnios. Semi-Markov chains and hidden semiMarkov models toward applications, volume 191 of Lecture Notes in Statistics. Springer, New York, 2008. Their use in reliability and DNA analysis. [6] Richard C. Bradley, Jr. Information regularity and the central limit question. Rocky Mountain J. Math., 13(1) :7797, 1983. [7] Pierre Brmaud. Markov chains, volume 31 of Texts in Applied Mathematics. Springer-Verlag, New York, 1999. Gibbs elds, Monte Carlo simulation, and queues. [8] Olivier Capp, Eric Moulines, and Tobias Rydn. Inference in hidden Markov models. Springer Series in Statistics. Springer, New York, 2005. With Randal Douc's contributions to Chapter 9 and Christian P. Robert's to Chapters 6, 7 and 13, With Chapter 14 by Gersende Fort, Philippe Soulier and Moulines, and Chapter 15 by Stphane Boucheron and Elisabeth Gassiat. [9] Xia Chen. Limit theorems for functionals of ergodic Markov chains with general state space. Mem. Amer. Math. Soc., 139(664) :xiv+203, 1999. [10] Kai Lai Chung. Markov chains with stationary transition probabilities. Second edition. Die Grundlehren der mathematischen Wissenschaften, Band 104. Springer-Verlag New York, Inc., New York, 1967.
184 [11] John B. Conway. A course in functional analysis, volume 96 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1990. [12] Amir Dembo and Ofer Zeitouni. Large deviations techniques and applications, volume 38 of Applications of Mathematics (New York). Springer-Verlag, New York, second edition, 1998. [13] P. Diaconis and D. Freedman. de Finetti's theorem for Markov chains. Ann. Probab., 8(1) :115130, 1980. [14] Persi Diaconis. Group representations in probability and statistics. Institute of Mathematical Statistics Lecture NotesMonograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988. [15] Persi Diaconis and James Allen Fill. Strong stationary times via a new form of duality. Ann. Probab., 18(4) :14831522, 1990. [16] Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete, 57(2) :159179, 1981. [17] Peter G. Doyle and J. Laurie Snell. Random walks and electric networks, volume 22 of Carus Mathematical Monographs. Mathematical Association of America, Washington, DC, 1984. [18] Richard Durrett. Probability : theory and examples. Duxbury Press, Belmont, CA, second edition, 1996. [19] G. Fayolle, V. A. Malyshev, and M. V. Men shikov. Topics in the constructive theory of countable Markov chains. Cambridge University Press, Cambridge, 1995. [20] William Feller. An introduction to probability theory and its applications. Vol. I. Third edition. John Wiley & Sons Inc., New York, 1968. [21] William Feller. An introduction to probability theory and its applications. Vol. II. Second edition. John Wiley & Sons Inc., New York, 1971. [22] James Allen Fill. An interruptible algorithm for perfect sampling via Markov chains. Ann. Appl. Probab., 8(1) :131162, 1998. [23] Xavier Guyon. Random elds on a network. Probability and its Applications (New York). Springer-Verlag, New York, 1995. Modeling, statistics, and applications, Translated from the 1992 French original by Carenne Ludea. [24] Olle Hggstrm. On the central limit theorem for geometrically ergodic Markov chains. Probab. Theory Related Fields, 132(1) :7482, 2005. [25] Olle Hggstrm and Jerey S. Rosenthal. On variance conditions for Markov chain CLTs. Electron. Comm. Probab., 12 :454464 (electronic), 2007. [26] T. E. Harris. Transient Markov chains with stationary measures. Proc. Amer. Math. Soc., 8 :937942, 1957.
185
[27] Mark Jerrum. Counting, sampling and integrating : algorithms and complexity. Lectures in Mathematics ETH Zrich. Birkhuser Verlag, Basel, 2003. [28] Ioannis Karatzas and Steven E. Shreve. Brownian motion and stochastic calculus, volume 113 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1991. [29] C. Kipnis and S. R. S. Varadhan. Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions. Comm. Math. Phys., 104(1) :119, 1986. [30] Yevgueniy Kovchegov. Mixing times via super-fast coupling. [Link]/0609568. [31] Thomas M. Liggett. Stochastic interacting systems : contact, voter and exclusion processes, volume 324 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1999. [32] Thomas M. Liggett. Interacting particle systems. Classics in Mathematics. Springer-Verlag, Berlin, 2005. Reprint of the 1985 original. [33] Torgny Lindvall. On Strassen's theorem on stochastic domination. Electron. Comm. Probab., 4 :5159 (electronic), 1999. [34] Torgny Lindvall. Lectures on the coupling method. Dover Publications Inc., Mineola, NY, 2002. Corrected reprint of the 1992 original. [35] Russell Lyons, Robin Pemantle, and Yuval Peres. Ergodic theory on GaltonWatson trees : speed of random walk and dimension of harmonic measure. Ergodic Theory Dynam. Systems, 15(3) :593619, 1995. [36] S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability. Communications and Control Engineering Series. Springer-Verlag London Ltd., London, 1993. [37] Ravi Montenegro and Prasad Tetali. Mathematical aspects of mixing times in markov chains. volume 1 :3 of Foundations and Trends in Theoretical Computer Science, pages 237354. NOW Publishers, 2006. [38] B. Morris and Yuval Peres. Evolving sets, mixing and heat kernel bounds. Probab. Theory Related Fields, 133(2) :245266, 2005. [39] J. R. Norris. Markov chains, volume 2 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 1998. Reprint of 1997 original. [40] Esa Nummelin. General irreducible Markov chains and nonnegative operators, volume 83 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1984.
186 [41] Karl Petersen. Ergodic theory, volume 2 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1989. Corrected reprint of the 1983 original. [42] James Gary Propp and David Bruce Wilson. Exact sampling with coupled Markov chains and applications to statistical mechanics. In Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), volume 9, pages 223252, 1996. [43] D. Revuz. Markov chains, volume 11 of North-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, second edition, 1984. [44] Daniel Revuz and Marc Yor. Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, third edition, 1999. [45] Gareth O. Roberts and Jerey S. Rosenthal. Geometric ergodicity and hybrid Markov chains. Electron. Comm. Probab., 2 :no. 2, 1325 (electronic), 1997. [46] L. C. G. Rogers and David Williams. Diusions, Markov processes, and martingales. Vol. 1. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 2000. Foundations, Reprint of the second (1994) edition. [47] Walter Rudin. Functional analysis. International Series in Pure and Applied Mathematics. McGraw-Hill Inc., New York, second edition, 1991. [48] Laurent Salo-Coste. Lectures on nite Markov chains. In Lectures on probability theory and statistics (Saint-Flour, 1996), volume 1665 of Lecture Notes in Math., pages 301413. Springer, Berlin, 1997. [49] A. N. Shiryaev. Probability, volume 95 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1996. Translated from the rst (1980) Russian edition by R. P. Boas. [50] Frank Spitzer. Principles of random walks. Springer-Verlag, New York, second edition, 1976. Graduate Texts in Mathematics, Vol. 34. [51] Hermann Thorisson. Coupling, stationarity, and regeneration. Probability and its Applications (New York). Springer-Verlag, New York, 2000. [52] William Veech. The necessity of Harris' condition for the existence of a stationary measure. Proc. Amer. Math. Soc., 14 :856860, 1963. [53] David Williams. Probability with martingales. Cambridge Mathematical Textbooks. Cambridge University Press, Cambridge, 1991. [54] D. B. Wilson. Web Site for Perfectly Random Sampling with Markov Chains. http ://[Link]/exact/.