Inégalité de concentration

théorie

Dans la théorie des probabilités, les inégalités de concentration fournissent des bornes sur la probabilité qu'une variable aléatoire dévie d'une certaine valeur (généralement l'espérance de cette variable aléatoire). Par exemple, la loi des grands nombres établit qu'une moyenne de variables aléatoires i.i.d. est, sous réserve de vérifier certaines conditions, proche de leur espérance commune. Certains résultats récents vont plus loin, en montrant que ce comportement est également vérifié par d'autres fonctions de variables aléatoires indépendantes[1].

Inégalités basiques

modifier

Inégalité de Markov

modifier

Cette inégalité indique la probabilité qu'une variable aléatoire à valeurs positives dépasse une certaine valeur, autrement dit elle permet de majorer la queue d'une loi de probabilité. En particulier, la probabilité qu'elle dépasse des valeurs de plus en plus grandes est de plus en plus faible. Si est une variable aléatoire réelle qu'on suppose presque sûrement positive alors

Ce résultat possède un corollaire qui généralise ce résultat à toute fonction croissante et positive :

Inégalité de Bienaymé-Tchebychev

modifier

Cette inégalité indique comment une variable dévie de sa moyenne. En particulier, la probabilité qu'une variable aléatoire dévie d'une valeur de plus en plus grande de sa moyenne est de plus en plus faible. On la démontre grâce à l'inégalité de Markov. Soit une variable aléatoire admettant un moment d'ordre deux alors

On peut généraliser cela à une variable aléatoire admettant un moment d'ordre  :

Inégalité de Chernoff

modifier

Cette inégalité permet de majorer la queue d'une loi de probabilité au même titre que l'inégalité de Markov. Elle ressemble à cette dernière mais donne une borne exponentielle.

Soit une variable aléatoire dont la fonction génératrice est finie. Alors

est la transformée de Cramér définie par

Inégalité de Bennett

modifier

Cette inégalité majore la fonction génératrice des cumulants d'une somme de variables aléatoires indépendantes majorées centrées et majore en conséquence d'après l'inégalité de Chernoff la probabilité que cette somme dévie avec une quantité donnée. Soient des variables i.i.d. de variance finie et tels que presque-sûrement pour tout et . On pose et . Pour tout ,

pour . En appliquant l'inégalité de Chernoff on obtient en particulier que pour tout ,

pour .

Inégalités de la variance

modifier

Inégalité d'Efron-Stein

modifier

Cette inégalité borne la variance d'une fonction générale d'une variable aléatoire[1]. Soient des variables indépendantes (pas nécessairement identiquement distribuées) et tels que pour tout . En posant et alors

Inégalités du processus empirique

modifier

Inégalité DKW

modifier

Cette inégalité borne la probabilité que la fonction de répartition empirique diffère uniformément de la fonction de répartition de la variable aléatoire étudiée.

Soient des variables i.i.d. de fonction de répartition . On note la fonction de répartition empirique basée sur l'échantillon , c'est-à-dire

Alors l'inégalité d'un côté est donnée par :

Cette inégalité a pour conséquence l'inégalité des deux côtés suivante (qui n'a pas de conditions sur ) :

Inégalité de Borell

modifier

Cette inégalité donne une borne exponentielle pour la concentration d'un processus stochastique gaussien[2]. Soit un processus gaussien stochastique séparable indexé par un espace semi-métrique . On note le supremum et on suppose que le processus est centré, i.e. pour tout . On note le supremum de la variance du processus et la médiane de la variable . Pour tout ,

Inégalité de Bousquet

modifier

L'inégalité de Bousquet donne la concentration du processus empirique indexé par des classes de fonctions bornées[3]. Soient des variables aléatoires réelles i.i.d. indexés par . On suppose que les variables sont centrées et majorées par 1, i.e. et pour tout et . On note . Alors pour tout ,

pour , avec . En optimisant la fonction , on obtient en particulier

Inégalité de Talagrand

modifier

Cette inégalité donne également une borne exponentielle pour la concentration du processus empirique indexé par des classes de fonctions[4]. Soient des variables i.i.d. à valeurs dans un espace , une fonction une fonction mesurable, et le processus empirique . Si est une classe de fonctions mesurables définies sur à valeurs réelles vérifiant certaines conditions d'entropie métrique alors pour tout ,

et .

Références

modifier
  1. a et b (en) Olivier Boucheron, Gabor Lugosi et Pascal Massart, Concentration inequalities: A Nonasymptotic Theory of Independence, OUP Oxford, 496 p. (ISBN 019876765X)
  2. (en) Christer Borell, « The Brunn-Minkowski inequality in Gauss space », Inventiones mathematicae, vol. 30, no 2,‎ , p. 207–216 (ISSN 0020-9910 et 1432-1297, DOI 10.1007/BF01425510, lire en ligne, consulté le )
  3. (fr + en) Olivier Bousquet, « A Bennett Concentration Inequality and Its Application to Suprema of Empirical Processes », Académie des sciences,‎ , p. 1-11
  4. (en) M. Talagrand, « Sharper Bounds for Gaussian and Empirical Processes », The Annals of Probability, vol. 22, no 1,‎ , p. 28–76 (ISSN 0091-1798 et 2168-894X, DOI 10.1214/aop/1176988847, lire en ligne, consulté le )