pp. 479-488 479

R6sultats et applications de la th6orie

Robert C O H E N *

des grandes d6viations

R6sum6

Cet article pr~sente les rOsultats de la th~orie des grandes dOviations dans des cas d fort potentiel d'appli- cations. Ces r~sultats permettent dYvaluer la vitesse de convergence vers zkro de probabilitks dYv~nements rares. .4 titre de comparaison, on donne le rOsultat du thOorbme de la limite centrale. Une application est propos~e en dernibre partie, pour une suite de variables al~atoires de loi de Poisson.

Mots el6s : Th6orie probabilit6, Grand 6cart, Suite variable al6atoire, Th6or6me central limite, Loi Poisson, Application t616communication.

LARGE DEVIATIONS T H E O R Y RESULTS AND A P P L I C A T I O N S

Abstract

This paper summarizes the results of the theory of large deviations and presents some applications to the most practical situations. These results concern the convergence toward zero of the probability of rare events. The central limit result is given for refer- ence. The last part is devoted to the case of Poisson distributed sequence of random variables.

Key words : Probability theory, Large deviation, Random variable sequence, Central limit theorem, Poisson law, Tele- communication application.

Sommaire

Introduction.

I. Th~orie des grandes d~viations.

II. Th~orbme de la limite centrale.

III . Application.

Conclusion.

Bibliographie (14 r~f.).

I N T R O D U C T I O N

Bien que r6cente, la th6orie des grandes d6viations recouvre, b, notre avis, un champ d'applications assez vas te ; en particulier dans le domaine des t616communications oh elle s'illustre sur des pro- bl6mes divers. Elle permet en effet de connaitre le comportement asymptotique de grands syst6mes stochastiques.

Dans le premier paragraphe, nous exposons les r6sultats de la th6orie des grandes d6viations que nous particularisons ~. des situations ~t fort potentiel d'applications. L'originalit6 de ce paragraphe, qui se veut un expos6 de synth6se, est de montrer la coh6rence des applications possibles des r6sultats de cette th6orie.

La loi des grands nombres nous assure que la moyenne empirique d 'une suite de variables al6atoires ind6pendantes, 6quidistribu6es et int6grables, converge presque sfirement vers la moyenne th6orique (l'esp6- rance). Si ces variables al6atoires sont de moment d 'ordre deux fini, alors le th6or6me de la limite centrale affirme qu 'une certaine fonction affine de la moyenne empirique (transformant cette der- ni6re en une variable al6atoire centr6e i.e. de moyenne nulle, et r6duite i.e. de variance 6gale 5. un) converge en loi vers une variable al6atoire de loi normale (loi gaussienne centr6e et r6duite).

D'apr6s ces th6or6mes classiques, la probabilit6 que les variables al6atoires concern6es prennent des valeurs dans des ensembles qui ne contiennent pas l 'esp6rance est faible. I1 y a grande d6viation en ce sens que la moyenne empirique 6viterait, avec une probabilit6 non nulle, un voisinage fix6 de la moyenne. La question est donc d'6valuer la vitesse de convergence vers z6ro de la probabilit6 de cet 6v6nement.

Le r6sultat de type grandes d6viations pour une suite de variables al6atoires ind6pendantes, 6qui- distribu6es et de moments exponentiels finis, est le suivant : la probabilit6 que la moyenne empirique prenne ses valeurs hors d 'un intervalle centr6 sur

* CNET/PAA/TIM, 38-40, rue du g6n6ral Leclerc, F-92131 Issy-les-Moulineaux.

1/10 ANN. T~L1ECOMMUN., 43, n ~ 9-10, 1988

480 R. C O H E N . - THI~ORIE DES G R A N D E S D I ~ V I A T I O N S

l'esp6rance est exponentiellement vers z6ro, avec un exposant n6gatif proportionnel au nombre de variables al6atoires consid6r6es dans la moyenne empirique.

C'est dans l'interpr6tation des termes de la th6orie que l 'on peut trouver mati6res ~t applications : sta- tistique, fiabilit6, m6canique, algorithmes de simu- lation, dimensionnement des r6seaux, ...

Le second paragraphe reprend le th6orSme de la limite centrale, th6orSme asymptotique plus connu que la th6orie des grandes d6viations.

Dans le dernier paragraphe, on applique les r6sul- tats de la th6orie des grandes d~viat!ons pour les variables al6atoires ind6pendantes daii~ le cas oh celles-ci suivent une loi de Poisson. L'exemple propos6 dans le domaine des t616communications concerne les secondes erron6es (secondes avec erreurs ou secondes gravement erron6es) sur une liaison num6rique. Si l 'on consid6re que l 'apparition de secondes erron6es par unit6 de temps suit une loi de Poisson, les for- mules obtenues sont riches d'informations. On a en effet des formules analytiques d6terminant la vitesse de convergence vers la vraie moyenne du nombre de secondes erron~es, la dur6e de la p6riode d'observation de la liaison permettant d'obtenir une pr6cision donn6e sur cette vraie moyenne.

Cet article est extrait de (*) et [5; ch. 4].

I. THI~ORIE DES GRANDES DI~VIATIONS

I1 peut paraitre paradoxal de s'int6resser ~. des 6v6nements rares alors que d 'une certaine fagon la th6orie des probabilit6s tend h les n6gliger. Rares mais de mesures non nulles, leur 6tude permet de connaltre le comportement de syst6mes stochastiques avec une probabilit6 par cons6quent proche de 1.

Le probl6me des grandes d6viations et son impor- tance peut ~tre bien compris par l '&ude de la question qui a motiv6 le d6veloppement de la th6orie [6] et qui concerne la loi des grands nombres et le th6or6me de la limite centrale.

Soit (X,) une suite de variables al6atoires ind6- pendantes et 6quidistribu6es, d'esp6rance m :

s . = Z x k , k = l

et, s .

S n ~ B n

�9 Loi des grands nombres :

si E(Ix, 1) < + o0 alors S, converge sfirement vers m, n tendant vers l'infini.

presque

(*) COHEN (R.). Quelques applications de la th6orie des grandes d6viations ~ la transmission num&ique. NT/PAA/TIM/ oRt/pu/1719. Mars 1986.

�9 Th6or6me de la limite centrale :

si ~2 = var(X1) < + oo alors ~Jh-(S.--m)/~ con- verge en loi vers la loi gaussienne centr6e, r6duite, not6e N(0,1).

D'apr6s ces th6or6mes classiques, les 6v6nements (4-n(S, - - m)[~ > a} et (S, > a}, pour a > m, sont rares, et la question est de connaitre, ou plut6t d'6valuer la vitesse de convergence vers z6ro des probabilit6s de ces 6v6nements. Cependant, au lieu d'6tudier les 6carts de S, vis4t-vis de a, on s'int6resse aux 6carts de S, vis4t-vis de na. Et il y a grandes d6viations en ce sens que S, 6viterait a lor~)avec une probabilit6 non nulle, un voisinage de la moyenne m dont la taille ne tendrait pas vers z6ro avec n.

Plus pr6cis6ment, on obtient un r6sultat du type :

�9 Principe des grandes d6viations :

si E(exp(tX1)) < -t- ~ , pour t dans un intervalle de ~,, alors on a : P(S, > a q- 8) _~ exp(-- nh(a, 8) ) pour une fonction h convenable.

L'int6r& du th6orSme de la limite centrale, est de fournir une majoration d'6v6nements ind6pehdante de la loi ~ des variables al6atoires Xk 6tudi6es ; mais c'est l~t aussi sa limite en ce sens que la majo- ration doit ~tre suffisamment large pour 8tre valable pour toute loi. Les r6sultats des grandes d6viations tiennent compte de la loi ~t des variables al6atoires 6tudi6es, la majoration est donc plus fine que celle du th6or6me de la limite centrale, mais la contre- partie est justement la connaissance n6cessaire qu'ils impliquent de la loi ~.

De tels r6sultats permettent d'6tudier dans un cadre plus g6n6ral les quantit6s suivantes associ6es ~. la suite de processus (X" ( t ) ) :

�9 P( (X"( t )e B}), pour un ensemble B,

�9 P({v"(G) ~< T}),

�9 E['r"(G)],

oh z"(G) est le premier instant de sortie de l 'ouvert G, qu 'on peut caract6riser par :

":"(G) = inf(t ; X"(t) r G).

Les r6sultats s'6tendent aux lois empiriques des processus 6tudi6s. I1 faut cependant, dans un cas comme dans l'autre, d 'abord 6tudier les crit~res d'existence de telles fonctionnelles puis, proc6der leur identification.

La th6orie doit ses principales contributions [8], [9], [12] dont notre expos6 s'inspire.

1.1. Th~or~me.

Nous nous limitons aux cas oh les convergences vers z6ro des probabilit6s consid6r6es sont expo- nentielles en nous fixant pour but d 'en pr6ciser l'exposant.

ANN. T~L~COMMUN., 43, n ~ 9-10, 1988 2/10

R. C O H E N . -- THI~ORIE DES G R A N D E S DI~V1ATIONS 481

Ddfinition 1.

Soit {P, ; n e N } une suite de probabil i t6s sur un espace polonais (espace mdtrique, complet , sdparable) C, telle que P, tend vers ~ 0 , Xo ~ C, quand n tend vers l'infini.

On dira que la suite {P, ; n 6 N} satisfait au prin- cipe des grandes d6viations avec la fonctionnelle I si :

�9 I : C--->IR+,

�9 I est semicontinue inf6rieurement,

�9 Pour tout k < + 0% { x ~ C ; I(x) <~k} est un compac t de C.

�9 Pour tout ensemble ferm6 A de C avec Xo q~ A :

lira sup(l ]n)logP,(A) <~ - - inf I (x) .

�9 Pour tout ensemble ouvert G de C avec Xo q~ (3 :

1 - - inf I(x) <~ lim i n f - log P,(G) .

x ~ A n ~ o o I1

De plus, d6s que ces r6sultats sont valables, alors pour tout ensemble B tel que Xo ~ B et

inf{I(x) ; x ~ B ~ = inf{I(x) ; x ~ B},

o~t B ~ d6signe l ' intdrieur de B, et B sa fermeture, au sens topologique des termes :

1 (1) tim - l o g P.(B) = - - i n f I(x).

n--* cc F/ x~B

Remarque.

Il est possible de faire une approx imat ion qui permet d 'ut i l iser les thdor6mes de convergences lorsque, dans la prat ique, nous disposons d ' un 6chantillon de taille n << assez grand >>. Pour la loi des grands nombres , cela se t raduit pa r :

E(XO ~- S , .

Pour les grandes ddviations, nous obtenons :

1 - log P.(B) ~ - - inf I(x), n x~B

c'est-/l-dire :

(2) P,,(B) ~ e - " t,f{l~), ~n}.

On mont re alors le th6or6me suivant [12 ; Th. 2.6, p. 24] qui sert ~ calculer des int6grales asymptot iques /t l 'a ide de la seule fonct ion L

ThOorbme 1.

Si {P. ; n 6IN} satisfait au principe des grandes ddviations avec I alors, pour toute f o n c t i o n f c o n t i n u e bornde sur C, on a " I[S ] (3) lim - log exp (nf(x)) P. (dx)

n~oO H C

= s u p [ f (x) - - I(x)]. xE:C

C'es t en 6tudiant diverses situations particuli6res du principe des grandes d6viations que nous obtien- drons des rdsultats immddia tement exploitables. On parvient en effet dans beaucoup de cas ~ calculer explici tement la fonctionnelle L

1.2. Cas d'une suite de variables al~atoires .

Si I e s t

a) I est

b) I est

c) Pour compact .

L' idde dans un tel contexte est de ddfinir la suite de probabili t6s (P, ; n ~ N} en posan t pou r tout n :

P , (A) = Prob(S , e A), VA c C.

Nous aurons besoin de la t ransform6e de Cramer d 'une fonction, outil qui joue un r61e impor tan t dans la suite, et que nous ddfinissons.

D@nition 1.

On appelle duale ou t ransform6e de Cramer d 'une fonction ? semicontinue inf6rieurement (s.c.i.), convexe, 5. valeurs dans [1, + ~ [ , la fonct ion /, ddfinie pou r tout x de IR a pa r :

(4) l(x) = s u p ( < t , x > - - l o g q~(t)), t E~l.a

Off < . , . > est le produi t scalaire dans IRa. La fonct ion I pe rmet de re t rouver qo puisque :

log q~(t) = s u p ( < t , x > - - I(x)). xEp..a

On dit que I e t log ? sont conjugudes. Le lemme suivant se ddmontre faci lement [12;

lemme 3.3, p. 31].

Proposition 1.

duale de q~ alors :

posit ive et convexe.

semicontinue infdrieurement.

tout k ~ I R +, { x ~ I R a ; I (x )<~k} est

Soit X une variable al6atoire ~t valeurs dans IR a, de loi ~z ; si q~(t) = E~(exp< t, X > ) alors on a un rdsultat suppldmentaire sur I.

Lemme 1.

Si m- - - -E~(X) alors :

a) I(m) ---- O,

b) I e s t non ddcroissante sur Ira, q- oo[, I e s t non croissante sur ] - - 0% m].

Nous en ddduisons le thdor6me suivant :

Th~orbme 2.

Soit {2", ; n ~ N} une suite de variables al6atoires, inddpendantes, dquidistribudes de loi ~t, /t valeurs dans IR d, telle que qo(t) = E , ( e x p < t , ) ( 1 > ) < + oo pour tout r6el t. Le principe des grandes d6viations est v6rifi6 pour la suite {P, ; n ~ N} d6finie pour tou t n par :

P.(A) = P r o b ( S . ~ A ) , VA = I R a ,

3/10 ANN. TEL~COMMUN., 43, n ~ 9-10, 1988

482 R. COHEN. - THI~ORIE DES GRANDES DI~VIATIONS

avec la fonctionnelle I drfinie sur R d par :

I(x) = sup(<t , x > - - log q~(t) ). t�9

Si m = E~[X~], alors :

(5) P ( S , � 9 + 3, + ~ D e - n sup{(<t,m+8>-Iog q~(t)), t e ~ d}

Ddmonstration.

Elle rrsulte de la proposition 1. De fait, le rrsultat du throrrme 2 reste valable

pour des variables alratoires non nrcessairement indrpendantes, 6quidistribures.

Thdorbme 3.

Soit (Y, ; n �9 IN} une suite de variables alratoires /l valeurs dans IR a telle que :

a) % ( 0 = E(exp<t , I I ,>) < + ~ , pour tout t dans rc pay6 de IRa produit cartrsien d'intervalles de R du type : ] - - r~, rz[, avec r~ > 0 et rz > 0.

b) Vt �9 7~ : ( l /n) log %(t) -+ log q~(t), n --> + ~ .

c) (supp Z,) ~ @ q~ et (lim inf(1]n)(supp Z , ) ) ~ =~ Z , off (1/n)(supp Z~) est l 'homothrtique du support de Z~ et (A) ~ est l ' intrrieur de A.

Alors le principe des grandes drviations est vrrifi6 pour la suite {P, ; n �9 IN) drfinie pour tout n par :

P.(A) = Prob(S. ~ A), VA = IRa,

et la fonctionnelle I drfinie sur IR a par :

I(x) = sup(<t , x > - - log q~(t) ). tGRd

Si m----E~[X1] alors :

(6) P(g, �9 [m + 3, + 0o]) __ e - n sup{(<t,m+8 > --log r te~- d}

Ddmonstration.

La drmonstration de ce throrrme (cf. [1 ; p. 22] ou [12 ; th. 3.8, p. 35]) comme celle du throrrme 2 utilise les deux points importants suivants :

�9 un changement de probabilitr, en considrrant des lois P7 drfinies par :

dP~ = exp < t, Z , > dP. ~n( t )

�9 Pour n assez grand, on peut exhiber t ~" tel que :

1 nE~: , (Z . ) = a.

Le th6or~me 2 peut ~tre gdndralis6 au cas de variables aldatoires, inddpendantes, 6quidistribudes /t valeurs dans un espace de Banach C.

Th~orbme 4.

Soit (X. ; n �9 N} une suite de variables aldatoires, inddpendantes, 6quidistribudes de loi tz, /t valeurs dans un espace de Banach C, telle que :

E~(tl[xil lc ) < + o%

pour tout rrel t. Alors le principe des grandes ddviations est vrrifi6

pour la suite {P, ; n �9 IN} drfinie pour tout n par :

P,(A) ---- Prob(S, �9 A), VA ~ C,

avec la fonctionnelle I drfinie sur C par :

I(x) = sup(<t , x > - - l o g q0(t)), t EC*

off C* est le dual de C. Si

m ---- E~(XI),

alors :

(7) P ( S . � 9 + 3, + ~ D ~ e - n sup{(<t ra+8>-Iog q~(t))~ teC*}.

Ddmonstration (cf. [8]).

1.3. Cas des densit6s.

On peut dgalement prouver un type de rrsultat dquivalent pour des densitds, h condition cependant de prdciser la notion d'information, extension de la notion de duale.

D~finition 2.

Soit q~ une fonction de IR+, et soient P e t Q, deux mesu!'es de probabilitds. On appelle information, la quantitd :

= I Ee(~(dQ/de)) si Q ,~ P, (8) I(P, Q; ~?) ( + ~ sinon.

Cette valeur peut 6tre considrrre comme le montant moyen d'information pour discriminer P contre Q lorsque P e s t la vraie loi.

Nous prrsentons deux exemples. Le premier permet d 'une part de retrouver une notion bien connue en throrie des tests et d 'autre part, de bien comprendre le deuxirme exemple, qui jouera un r61e important dans la suite de l'exposr.

�9 Si q~ est drfini par 9(r) ---- (r - - 1)2/r, on retrouve la distance du Z 2 (khi-deux) qui est ~t la base du test du Z 2 :

I(P, Q) = z2(P, Q) -- E ( ( p - q)Z/q),

si p e t q sont les densitrs de P et Q respectivement.

�9 Quand q~(r) = - - log r, on obtient' l ' information de Kullback :

l Ee(log dP]dQ) siP ,~ Q, I(P, Q)=K(P, O ) = + ~ sinon

b. laquelle on rattache les notions de divergence et d'entropie. Remarquons que K(k, ~) = 0, pour route probabilit6 Z.

Nous focalisons maintenant notre attention sur les proprirtrs de cette dernirre en tant que fonction de son premier paramrtre : fixons nous une proba- bilit6 ~, et notons I~(7.) pour I(;~, ~).

ANN TELI~COMMUN., 43, n ~ 9-10, 1988 4/10

R. COHEN. - THI~ORIE DES GRANDES DI~VIATIONS

Lemme 2. a) I~(X) = sup{Ex(log u) - - log(Eu(u)) ; u ~ U},

off U est l'ensemble des fonctions continues, posi- tives, born6es et d'inverse born6 de C dans IR.

b) X-+I~(X) est convexe et semi-continue inf6- rieurement.

c) {X ~ P(C) ; l~(X) ~< k} est compact dans P(C), Vk e IR +, off P(C) est l'ensemble des probabilit6s sur C.

Ddmonstration. On pourra la trouver dans [1; prop. 2; p. 36].

Les propri6t6s dont jouissent les informations de Kullback ne sont pas 61oign6es de celles exig6es aux fonctionnelles dans le principe des grandes d6viations. Muni de ces outils on peut montrer (cf [8]) :

ThOorbme 5. Soit (X, ; n ~ N} une suite de variables al6atoires,

ind6pendantes, 6quidistribu6es de loi ~, sur un espace polonais C. Soit if(C) l'ensemble des pro- babilit6s sur C. Alors le principe des grandes d6via- tions est v6rifi6 pour la suite {P, ; n ~N} d6finie pour tout n par :

" ( A ) : P r ~ ' k = , VA e f t (C) ,

o/~ 8x est la masse de Dirac en x, avec la fonctionnelle I d6finie sur if(C) par :

I~(X) = E~ log ,

on a alors :

(9) " ( ~ k = ~ x ~ A ) -~e . . . . p{,~,z,, X~A}.

Remarque. lntroduisons la notation suivante pour le temps

d'occupation de A

1 " L,(A, o~) = -n k= - -~21)~A(Xk((D)= )'

Oia ZA est la fonction indicatrice de l'ensemble A, alors Vf : C -->~.

nk~=l = cof(Y) L . ( d y ) =- EL. ( f ) ,

ofa L.(dy) d6signe le temps &occupation quand )((to) = y e t <t A = dy >>. On peut alors exprimer la convergence empirique par :

i / ( y ) L,(dy) -+ icf(y ) ~t(dy).

La fonctionnelle I du th6or6me 2 pour les variables al6atoires ind6pendantes, 6quidistribu6es, devient alors un cas particulier de la pr6c6dente, ~ 6tant fix6, puisque :

483

I(x) = Inf E~ ~ l o g ~ ;

que : X e P ( C ) et Ez(f)---- x t . tels )

1.4 . C a s d ' u n e c h a i n e d e M a r k o v .

Les th60r6mes pr6c6dents comportaient l'hypo- th6se d'ind6pendance sur la suite {Xk; k e N ) . Dans ce paragraphe, nous 6tablissons un r6sultat similaire de grandes d6viations lorsque la d6pen- dance est markovienne. Cette d~pendance est carac- t6ris6e par la probabilit6 de transition Q de la chaine, ce qui explique la diff6rence de traitement (l'usage d'une fonctionnelle I du type information de Kull- back) par rapport au cas des variables al6atoires ind6pendantes. Avant d'~noncer ce th~or~me, nous pr6cisons quelques notations et hypoth6ses.

Notations. La chaine de Markov [11] est ~ valeurs dans l'espace

m6trique E, muni de sa filtration bor61ienne g et de la probabilit6 de transition Q(.,.).

On note C(E) l'ensemble des fonctions continues sur E h valeurs r6elles, C+(E) l'ensemble des fonc- tions de C(E) strictement positives.

~(E) d6signe l'ensemble des probabilit6s sur (E, ~;), et ~2(E) d6signe l 'ensembk des probabilit6s sur (E • E, ~; | g).

Si X' est un 616ment de ff2(E) de lois marginales Xl, X2, on note pour X ~P(E) :

P2z(E) = {X' ~ p2(E) ; X 1 = X2 = X}.

Hypothbses. (H.1) la chalne de Markov est irr6ductible. (H.2) Les probabilit6s de transition {Q(x, dy); x e E} sont 6quivalentes ~ une mesure ~. :

Q(x, d y ) = Q(x, y) [~(dy).

(H.3) Propri6t6 de Feller :

Vf~ C(E), Of~ e(E),

o/1

Qf(x)=~ f(y)Q(x, y) ~x(dy). .E

(H.4) Sk E N* tel que : Vn > k, Vf~ C(E) e t f > 0, on a : Q"f> O, Q"f &ant d6finie par :

Q.(f) = Q(Q.-lf), avec QOf=f OU

(H'.4) E est compact.

Remarques. - - Les hypoth6ses (H.1) et (H'.4) impliquent qu'il

existe une unique probabilit6 invariante v pour cette chaine de Markov.

5/10 ANN. T~LI~COMMUN., 43, n ~ 9-10, 1988

484 R. COHEN. - THI~ORIE DES GRANDES DEVIATIONS

Par d6finition d'une chaine de Markov

Vf~ C(E), f >~ 0, V(n, k) ~ N ~,

Q ~ f ( x . ) = E ( f ( X . + k ) / X . ) .

Nous pouvons alors 6noncer le th6or6me :

ThOorbme 6.

Soit q; ~ C(E) et Y, ---- +(X,), sous les hypoth6ses (H.1) ~t (H'.4), le principe des grandes d6viations est v6rifi6 pour la s~ite {P, ; n ~]N} d6finie pour tout n par :

P,(A)---- P r o b ( ! ~ = 1 ~ Y * ~ A l X ~ VA~8,

avec la fonctionnelle I d6finie sur p2(E) | P(E) par :

I(7`', 7 ̀| Q ) = K(7`', 7 ̀| Q),

oh K est l 'information de Kullback, le supremum pour la majoration de la probabilit6 de l'6v6nement, 6rant pris sur l'ensemble :

A(A) = {7 ̀e P(E), 7 '̀ e P~,(E) ; E~(+(X) ) e A}.

Nous avons d o n c :

\ k = l e-n sup{K(X',X| (X',~,) cA(A)}.

Nous pouvons donner une forme, plus souple utiliser, ~t la fonctionnelle I e t de fait plus coh&ente avec la d6finition que nous avons donn6e des fonc- tionnelles I dans le principe des grandes d6viations :

PropriJtJs.

1) Inf{I(7`', ;~ | Q) ; (7`, 7`')6 A(A)} ----- Inf{h(a) ; a ~ A } , oh la fonction h est d6finie par :

h(a) = inf{I(7`', 7 ̀| a ) ; (7`, 7`')~ A({a})), de sorte que �9 (1 )

k = l

2) Par construction, h est positive, et semicontinue inf6rieurement.

3) Si v est la mesure invariante de la chalne de Markov, alors :

E~(+(X) ) = a <. h(a) = O.

Le th~orSme 6 s'6tend aux mesures empiriques des chatnes de Markov.

Th~orbme 7.

Soit {X. ; n ~IN} une chaine de Markov. Sous les hypotheses (H.1)/(H'.4) ou (H.1)/(H.4), le prin- cipe des grandes d6viations est v6rifi6 pour la suite {P . ; n ~ l } d~finie pour tout n par :

P.(A)-----Prob n ~A[Xo- - - -x , V A e S ,

avec la fonctionnelle I d6finie sur P(E) par :

I~(X) = sup )Ex log , u eC+( E

oh I~ est la notation pour I ~ , i.e. la chaine de Markov est issue de x.

( I ~ ) (12) P n 8~E AIX o = x -~ e . . . . p{I~(~),X~A}.

k = l

On peut &ablir le lien entre la fonctionnelle I du thdor6me 7, notde 17, pour la densitd de la ch~i~ne de Markov, et la fonctionnelle I du thdorSme 6, notde /6 , pour la chaine, de mSme qu'on avait 6tabli un lien entre les fonctionnelles des thdorSmes 2 e t 5.

Propri~t~s.

1) Pour tout 7 ̀ de P(E), il existe une probabilit6 de transition 0 pour laquelle :

�9 7 ̀ est invariante : 7`Q ----- 7 ,̀ �9 7` | O ' ~ 7̀ | Q,

�9 17(7`) = inf{16(7`', 7, | Q) ; 7 '̀ E p2(E)} ---- 16(7` | O, 7 ̀ | Q).

2) Si v e s t la mesure invariante de la chaine de Markov, alors :

E~(Q;(X) ) : a .~> h(a) : O.

3) S i v est la mesure invariante, alors 0 = Q, et I(X', v | Q ) : 0 ~ 7 ` ' = v | Q.

Remarque.

Quand 7 '̀ = v | Q sa seconde marginale vaut :

v Q ~ V.

1.5. Cas des diffusions.

Le lien entre les grandes d6viations et les petites perturbations est pr6cis6 et d6velopp6 dans [2]. Ici l'interpr6tation physique peut &re pr6cis6e : les grandes d6viations permettent de mesurer l'6cart d 'un processus X~' vis-b.-vis d'une position d'6quilibre X*, solution d'une 6quation non perturb6e.

On peut consid6rer le processus (X") solution de :

1 f(~ = f ( X T , n ~ ' ) '

comme le r6sultat d'une petite perturbation du sys- t6me d&erministe :

2(* = f ( X , , O) = ~(X, ) ,

oh ~ est un processus al6atoire d6fini sur le mSme espace (f~, A, P) que (X~) et X*, suppos6 en g6n6ral continu h droite et born&

Le principal outil pour montrer que :

Prob{lim m a x l X ~ - xYl = 0) = 1, n~oo [O,T]

ASN. T~L~COMMUN., 43, n ~ 9-10, 1988 6110

R. C O H E N . - THI~ORIE DES G R A N D E S DI~VIATIONS 485

est obtenu en consid6rant un tube de section l In centr6 sur la trajectoire t -+X~ (6ventuellement optimale relativement 5̀ une fonction de cofit J) .

Le lien est fait avec la formule de Feynman-Kac, puisque l'int6grale le long de cette trajectoire est la contribution principale pour certaines int6grales fonctionnelles.

Nous 6tudions le cas o/1 la perturbation ~;~ est gaussienne, et la fonction f du type :

f(x, y) = b(x) + ~(x)y.

Thdorbme 8.

Soit e~([0, T ] ; I R n) l'ensemble des fonctions X continues sur [0, T] 5̀ valeurs dans IR a, et telles que ) ( 0 = X.

Consid6rons la suite {P. ; n EN} de probabilit6s d6finies pour tout n comme la loi du processus X~' solution de l'6quation diff6rentielle stochastique suivante :

dX'~ = b(X~)dt 4- (l /~/-ff)e(XT)dB,, Xo = x,

off B est un mouvement brownien (la perturbation gaussienne est : ~ = [~, oia [3 est un bruit blanc tel que dBt = [3tdt), b et e 6tant lipchitziens.

Le principe des grandes d6viations est v6rifi6 avec la fonctionnelle d6,finie sur ex([0, T ] ; IRa) par :

(13) I ( r ) = (11~/2) •

i r < lit - - b( Y,), (***)- ~(Yt)(Y~ - - b(Y~) )>d t . o

On trouvera des r6sultats plus g6n6raux dans [9], notamment l'6tude de cas o/~ la perturbation ~ n'est plus gaussienne. Dans de tels cas on s'int6resse 6galement au d6veloppement en puissances de

(avec ~ = l[n) de X~. Sous certaines conditions de d6rivabilit6 de b et ~r, on montre [9; th 2.1, p. 52] que :

X~ = X~ ~ + ~ X ? ' + ... + ~X~ ~' + R}~+~'(~).

le processus (X(~)) 6tant ind6pendant de z, et

sup < tO,T]

avec P(C(~) < + oo) = 1.

1.6. Cas des rapports de vraisemblance.

Un autre domaine des probabilit6s est concern6 par la mesure d'ensembles : la statistique. Plus pr6cis6ment le chapitre des tests dont la formulation conduit b, pr6ciser les r6gions de rejet et d'accep- tation de l'hypoth~se test6e. Le test le plus classique pour discriminer une loi contre une autre est le test de Neyman-Pearson de deux lois.

Consid6rons deux lois Po et P~ de densit6s res- pectives par rappor t / t ix, P o e t p~ sur Ill, et un 6chan- tillon (IR, B(IR), Po)| N et(IR, B(IR), P~)N| de chacune

des lois. Les variables al6atoires que nous consi- d6rons (X,) sont d6finies, sur ces espaces canoniques, comme coordonn6es.

Le test de Neyman-Pearson de r6gion de rejet :

Rn : t ~k=l log P~ (Xg)P, >~na I

est le plus puissant possible de son niveau. Dans le choix de l'hypoth6se Ho : Po est la loi

de l'6chantillon contre H1 : P1 est la loi de l'6chan- tillon, deux erreurs sont possibles :

�9 rejeter Ho alors qu'elle est vraie (erreur de premi6re espSce) se fait avec une probabilit6 ~, = Po(R,) dite niveau du tes t ;

�9 accepter H1 alors qu'elle est fausse (erreur de deuxi6me espSce) se fait avec une probabilit6 f3, = PI(R~) dite puissance du test.

On a le r6sultat suivant :

Thdorbme 9.

Si les informations de Kullback K(Po, P~) et K(P1, Po) sont finies, pour tout

a ~ ]-- K(Po, PI) ; K(PI , Po)[,

on pose :

I(a) = sup at - - log e t q o g P ~ tEF, , R Pl /

on a alors :

(14)

et

(l /n)log e, - + - - I(a)

et (I/n) log ~ . - - - > a - I(a),

Po(R,) ~- e -"I~"), p I (R c) ~_ e-n(l(a)-a).

Ddmonstration : elle r~sulte de l'application du th6or6me fondamental des grandes d6viations (th6o- r6me 2 ) ; on pourra consulter [7].

II. THI~OREME DE LA LIMITE CENTRALE

Le th6or6me de la limite centrale permet de pr6- ciser le comportement, en loi, d 'une suite de variables al6atoires.

L'importance de ce th6or6me en statistique n'est plus 5̀ d6montrer.

ILl. Cas des suites de variables al~atoires ind~pendantes ~quidistribu~es (VALE) (~ connu).

Thdorbme 10 [11].

Soit {X. ; n ~ N} une suite de variables al6atoires ind6pendantes, de m~me loi Ex, de moyenne m finie,

7 /10 ANN. TI~L~COMMUN., 43, n ~ 9-10 , 1988

486 R. COHEN. - THI~ORIE DES G R A N D E S DI~VIATIONS

de variance O 2 finie, alors :

(15) L o i k / n ( S . - - m)lo] -+ N(0,1), n -+ + ~ ,

o/1 N(0, 1) d6signe la loi normale (gaussienne) centr6e rMuite.

Nous pouvons dire alors que, ind6pendamment de Or, il est possible d'6valuer les quantit6s de type suivant :

P(x/-n($.- m)/o <~ 8) _ P(Z <~ 8),

oh Z e s t une variable al6atoire de loi N(0, 1), puisque par d6finition :

I ~ P(Z <~ 8) ~_ e-~/2dx.

Bien stir les quantit~s du type suivant en d~coulent :

P ( I ~ / H ( s . - m)l* l < a) ~_ P ( I Z l < a),

et valent :

i s 1 ~.+8 1 " + - ~ e-x2/zdx= 2!o ~ ' ~ e-x2dx"

La loi N(0,1 ) 6tant tabul6e, on peut ainsi /t fix6 connaltre une valeur approch6e des probabilit6s pr6c6dentes.

La loi des grands nombres s'exprime alors pour toute fonction f mesurable par rapport ~ ~ :

1 f f(Xk) ---> I f(y)~(dy) E,(f) , n k = l t E

oh u est la mesure invariante de la chaine (une telle mesure existe sous nos hypotheses).

Nous avons alors :

Th~orbme 11.

Sous les hyp0th~ses pr6c6dentes, on a :

a) - E~ [f(X~) - - E ( f ( X 0 ) ] 2 _~ o t n -~ + oo n k=l

b) Si o 26]0, + o~[, alors, n - + + ~ :

(16) Pu (114 [f(Xk)--E(f(Xk))] < 8 -+

i s ( l i f t S ~ e-x212"'dx, - o o

pour toute loi initiale ~z de la chaine.

Un r6sultat analogue peut ~tre montr6 pour des processus, la convergence ayant alors lieu vers un mouvement brownien.

II.2. Cas des suites de VAIE (0 ineonnu).

Dans le cas oh l'6cart-type est inconnu, il est n6cessaire de l'estimer. L'estimation de if2 se fait par :

1 " ^ . = -~ X ( x~ - - '3 0 2 .

k = l

Alors [4; p. 135] la loi de la variable al6atoire ~ / n ( S , - m)]~, suit approximativement une loi de Student b. n - - 1 degr6s de libert6. Comme la fonction de r6partition F de cette loi est tabul6e, on a :

~/n _ 8 ) ~ F(8). P(-~7(S. - - m) <

II.3. Cas des chaines de Markov.

Nous reprenons les notations du paragraphe 1.3 et rajoutons les hypoth6ses n6cessaires ~t l'6tablis- sement du th6or6me de la limite centrale.

(H.I) La chaine de Markov {2",} est homo#ne .

(H.2) Elle n'admet qu'une classe r6currente.

(H.3) Si l'espace d'6tat E est d6nombrable :

Q(i,j) < + ~ ,

uniform6ment en i. Remarquons que l'hypothSse (H.3) est toujours

v6rifi6e pour une chaine ~ espace d'6tats finis.

ANN. TI~LI~COMMUN., 43, n ~ 9-10, 1988

III. APPLICATION

La loi de Poisson sert h mod61iser de nombreux ph6nom6nes, d 'oh son importance dans les appli- cations. C'est lh, la motivation de l'6tude qui suit.

L'une des applications possibles aux t616commu- nications est celle concernant l'apparition de secondes erron6es (secondes avec erreurs, ou bien secondes gravement erron6es [13]) sur une liaison num6rique pour laquelle les questions suivantes semblent de premier int6rSt :

�9 pOriode optimale d'observation. Quelle est la dur6e minimale d'observation de la liaison permettant de d6terminer la vraie moyenne du nombre de secondes erron6es par unit6 de temps /l partir de la moyenne empirique avec une pr6cision donn6e ?

�9 nombre minimal d'&~nements. Combien d'unit6s de temps avec secondes erron6es dolt-on ~bserver pour avoir cette pr6cision ?

�9 &aluation de la pr&ision. Avec quelle pr6cision la moyenne empirique 6value-t-elle la vraie moyenne 5. la fin d'une p6riode d'observation donn6e ?

L'application des r6sultats de la th6orie des grandes d6viations, dans notre cas du th6or~me 2, permet de r6pondre aux questions pr6c6dentes, en four- nissant des formes analytiques pour les param~tres concern6s.

Pour pouvoir utiliser ces r6sultats, il est indis- pensable de mod61iser l'exp6rience :

8/10

R. COHEN. - THI~ORIE DES GRANDES DI~VIATIONS 487

On consid~re que l 'unit6 de temps qui nous int6- resse dans l '6tude de la liaison num6rique est fix6e (minute ou heure), et que l ' appar i t ion des secondes erron6es pa r unit6 de temps suit une loi de Poisson de param6tre X. A la k-i+me unit6 de temps, ~t par t i r du d6but de l 'observa t ion de la liaison, on associe donc une variable al6atoire X~, et la probabil i t6 que la k-i6me unit6 de temps contienne j secondes erron6es est donn6e par "

P(X~ = j ) = e -x k~ j~

La dur6e d 'observat ion , qui correspond ~t un nombre d 'unit6s de temps, est la taille n de l '6chantil lon (x~ . . . . . x . ) .

On a la proposi t ion suivante :

Proposition 2.

Si X~ . . . . , 3(. sont n variables aldatoires ind6- pendantes de loi de Poisson de param6t re X, alors :

i) l 'esp6rance vaut �9 E(X,) = X,

ii) le m o m e n t exponentiel d ' o rd re t vaut : E(etX0 = exp(X(e t - 1)),

iii) la fonctionnelle I vaut :

I(x) = x l o g ( x / X ) - x + X.

Pour tout 3 > 0 :

a) P ( $ . e l X + 3, + oo[) ~ e -"ttx+*~ ~og.+~zx)-~,

b) P($ , e / - - 0% X - - 3[) ~ e -"t(z-a) l og (1 - -81~ . )+8] ,

c) e ( [ ~ . - xJ > 3) ~ e -""~+~' , o , . + ~ , - ~ + e - n [ ( X - 8) log(1 - 81~.) + 8]

DOmonstration.

i) et ii) sont des r6sultats classiques. Pour iii), la fonctionnelle I donn6e dans le th6or6me 2 est �9

I(x) = sup(tx - - log ~p(t) ), t e n

avec ~p(t) = E(etX).

En utilisant ii), on a :

I(x) = sup(tx - - X(e t - - 1) ). teN.

On v6rifie ais6ment que le m a x i m u m est atteint en t* ---- log(x/X), et en substi tuant cette valeur dans L il vient :

I(x) x log(x/X) - - x + x.

En vertu du th6orSme 2 et du lemme 1 point c), on a les r6sultats annonc6s en rempla~ant succes- sivement x par X + 3 et X - - 3 :

a) P ( S . e ]X + 3, + oQ[) ,-~ ,~-" l.r i(~) - - t, x~ ]X+ 8, + o0[ e - n[(?,+ 8) log(1 + 8 / ? , ) - 8]

b) P ( S . e ] - - 0% x - - 3[) _~ ~~ ,(~ = e - n [ ( ; ~ - 6 ) l o g ( 1 - ~ / ~ . ) + ~ ]

c) enfin, c o m m e

A = 1-- c~, X - - 3 [ et B = ]X -t- 3, + oo[

sont disjoints, le r~sultat d6coule de

P (A U B ) = P ( A ) + P ( B ) .

d) Pour mont re r ce point , il suffit de mont re r que le majoran t dans a) est sup6rieur au ma jo ran t dans b), ce qui revient /~ ordonner la valeur absolue des exposants dans l ' au t re sens. Si on pose ~ = ~k, il suffit de mont re r que :

(1 + 0t) log(1 + e) - - 0~ ~< (1 - - ~) log(1 - - e) + 0~.

C o m m e ~ ~< 1, il est 6quivalent de mont re r : cc ~k oo ~k

(1 + e) ~ ( - - 1)k-~-V+,~ (l - - e) ~2 ~-~< 2~. k = l k = l

Mais le membre de gauche est 6gal ~ :

2e + 2g=a ~: k - 1

0~k~

qui est bien inf6rieur b, 20~ car k - - 1 ~< 0.

Par cons6quent, le ma jo ran t dans la formule a) est plus grand que celui de la formule b), et la for- mule annonc6e en d6coule.

Si ~[X est tr6s petit devant 1, alors on peut utiliser l ' app rox ima t ion suivante : log (1 + u)~_ u, pour u peti t devant 1 dans les expressions a), b) et c) de la proposi t ion pr6c6dente pour obtenir :

Corollaire 1.

Pour 3 > 0 , et 3 [X,~ 1, on a :

a) P (S , e ]X + 3, + oo[) ~ e -"(~2/x),

b) P ( S . e ] - - oo, k - - 3[) ~ e -"r

c) xl > = 2e -"(~:/x).

On est main tenant en mesure de r6pondre aux trois questions propos6es, en exploitant les fornmles de la proposi t ion 1 :

�9 la p6riode minimale d 'obse rva t ion n*. On se fixe la pr6cision 3 que l ' on d6sire avoir sur la vraie moyenne X g par t i r de la moyenne empirique S , , ainsi que la probabil i t6 [3 avec laquelle cette pr6cision est r6spect6e (i.e. ; P ( [ $ . - - X [ < 3 ) = [3). On a alors en utilisant la formule d) de la propos i t ion 1 :

1 - - [3 = P(ISn-- X I > 3) ~ 2 e -nttx+8) l~176

Soit, en expr imant n e n fonct ion des autres para- m6tres :

log(2/(1 - - [3)) n ~<

(X + ~) log(1 + ~/X) - - ~ "

D 'of i la p6riode opt imale n* d 'obse rva t ion

log(2/(1 - - [3))

(X + 8) log(1 + 8IX)- - 8"

9/10 ANN. TI~Lt~COMMUN., 43, n ~ 9-10, 1988

488 R. COHEN. - THEORIE DES GRANDES DEVIATIONS

Si 3 = 0~)`, on peut 6crire :

log(2/(1 - - ~) ) (17) n* =

)`[(1 + ~) log( l + : t ) - - ~ ] "

Si ~, ou de fagon 8quivalente 3/)`, est trSs petit, log(l + :~) _ :t, et :

(18) n* log(2/(1 - - ~)) )` l o g ( 2 / ( 1 - - ~ ) )

�9 l 'estimation du nombre S* d'6vSnements. Les paramStres fixes sont les mSmes que pr6c6demment. Mais cette fois on utilise le fait que S, - )`, en vertu de la loi des grands nombres. On a donc S, -~ n)`, et le nombre minimal d '6v6nements h observer pour avoir la pr6cision 3 d6sir6e est S , . = n*)` :

log(2/(1 - - [3) ) (19) S.* =

[(1 + :0 log(1 + ~ ) - - : ~ ] "

Si 0~ est petit,

(20) S . . log(2/(1 - - ~)) = ?2 log(2/(1 - - ~))

�9 probabilit6 de d6passer k fois la moyenne )`. I1 peut 8tre int6ressant de connMtre la probabilit6 avec laquelle S, est sup6rieur ou 6gal h k)`. En 6crivant 3 = (k - - 1))` dans la formule a) de la proposi t ion 1, il vient :

(21) P ( S , > k)`) ~ e -'xtk Iog(k)--k+l],

�9 6valuation de la pr6cision 3" h la fin d 'une p6riode &observat ion n. D'aprSs la formule (17) donnan t n* en fonct ion de ~, avec 3 ---- ~)`, on peut 6crire, s i n est donn6 et 3 fi estimer :

log(2/(1 - - [3) ) (22) (1 + 0t) log(1 + c t ) - 0c ---- ;qt

La solution 0~* fi cette 6quation peut 8tre obtenue, par la m6thode de Newton-Raphson , comme la limite de la suite ( ~ * ; n ~ 1 ) d6finie par :

~* +I * F(~* ) = ~. - - ~.,(~.) �9

[1] Ast6risque n ~ 68 : Grandes d6viations et applications statistiques. Soci6t6 math6matique de France. Coll. Ast6- risque (1979), 68, 200 p.

[2] AZENCOI'r (R.). Grandes d6viations et petites pertur- bations de syst6mes dynamiques. Ecole d'6t6 de Saint- Flour (aofit 1978). Lecture notes in mathematics, 774, Springer-Verlag.

[3] BECAM (D.), BRIGANT (P.), COHEN (R,). Mod61isation de la dispersion de la qualit6 en transmission num6rique. Globecom 1986, Houston, Texas, USA, 1-4 d6cembre 1986, IEEE, pp. 1610-1614.

[4] SACHS (L.). Applied statistics. Springer, 1984. [5] COHEN (R.). Mod61isation filtrage et contrSle de processus

stochastiques. Th6se de doctorat. ENST, Fr. (nov. 1987). 16] CRAMER (H.). Sur un nouveau th6or6me limite de la th6orie

des probabilit6s. Act. Sc. Ind. (1938), n ~ 736. [7] DACUNHA-CASTELLE (D.), DUFLO (M.). Probabilit6s et

statistiques. Masson (1983). [8] DONSKEa (M.), VARADHAN (S. R. S.). Asymptotic eva-

avec log(2/(1 - - ~))

F(x) = (1 + x) log(1 + x ) - - x - - Xn '

et F'(x) = log(1 + x).

La valeur optimale de 3 est donn6e par : 3" = 0~*)`. Si 3" est pressenti comme petit, alors la formule (18) donne :

(23) 3" = ~ / ) ` log(2/(ln - - [3)),

C O N C L U S I O N

On a montr6 la coh6rence des applications du r6sultat fondamental de la th6orie des grandes d6via- tions.

Dans l 'applicat ion que nous proposons , ce r6sultat pr6cise que la probabilit6 que la moyenne empirique S, soit dans un ensemble A ne contenant pas la vraie moyenne )`, est petite d ' o rd re ~A'~-'""(x), pour une fonctionnelle I que la th6orie permet d'identifier.

L 'appl icat ion est illustr6e par un exemple dans le domaine des t616communications. Les secondes erron6es par unit6 de temps sont mod61is6es par une loi de Poisson de paramStre )`. On peut alors, en utilisant la formule obtenue �9

P(I S. - - )`l < 3) = ~ ~< 2e -"t~+~) io~(,+at~)-81,

d6terminer le plus petit n donnan t la precision 3 d6sir6e de la moyenne empirique par rappor t ~. la vraie moyenne ou la plus petite valeur de :

k=,

conduisant h ce r~sultat ; s i n est fix6, on peut encore d~duire ce que sera 3.

Manuscri t re fu le 16 mars 1988, acceptd le 11 mai 1988.

BIBLIOGRAPHIE

luation of certain Markov process expectations for large time. Com. pure Appl. math I (1975), 28, pp. 1-4,7 ; Com. pure Appl. Math. 111 (1976), 29, pp. 389-4~il.

[9] FREmLIN (M. I.), WENTZELL (A. D.). Randoha pertur- bations of dynamical systems. Serie �9 Comp. Stud. Math., n ~ 260, Springer (1984).

[10] HAIME (A.). The Chernoff bound applied to error rate measurements. Australian Telecom. Res. (1981), 15, n ~ 2.

[11] NI~VEU (J.). Bases du calcul des probabilit6s. Masson (1964).

[12] STROOCK (D. W.). An introduction to the theory of large deviation. Serie : Universitext. Springer (1984).

[13] xxx : R6seaux num6riques, Syst6mes de transmission et 6quipement de multiplexage. C.C.LT.T., Gen6ve (1985), Livre rouge, fascicule 111.3, pp. 310-317.

[14] xxx : Interpr6tation de l'avis G821, et Valeur des para- m6tres de l'avis G821 ~_ mesurer sur une courte p6riode pour garantir les objectifs de qualit6 b. long terme. Rapport T/TR/TR3 (86) 30 C.E.P.T., Ath6nes (14/18 oct. 1985).

ANN. T~LI~COMMUN., 43, n ~ 9-10, 1988 10/10