Inégalité d'Azuma

L’inégalité d'Azuma, parfois appelée inégalité d'Azuma-Hoeffding, est une inégalité de concentration concernant les martingales dont les accroissements sont bornés. C'est une généralisation de l'inégalité de Hoeffding, une inégalité de concentration ne concernant, elle, que les sommes de variables aléatoires indépendantes et bornées.

Énoncé courantModifier

Un des énoncés les plus courants est

Inégalité d'Azuma — Soit une martingale   par rapport à une filtration   et vérifiant

 

Alors, pour tout  

 

Notons que le choix   entraine que  

Énoncé généralModifier

Un énoncé plus général (McDiarmid, Théorème 6.7) est le suivant

Théorème — Soit une martingale   par rapport à une filtration   Supposons qu'il existe une suite   de variables aléatoires et une suite   de constantes telles que, pour tout  

  •   soit  -mesurable ;
  •  

Alors, pour tout  

 

L'énoncé courant, donné à la section précédente, est obtenu en spécialisant l'énoncé général aux choix  

Principe de MaureyModifier

Le principe de Maurey a été énoncé pour la première fois par Maurey dans une note aux Comptes rendus de l'Académie des Sciences en 1979, et découvert plus tard, semble-t-il indépendamment, par Harry Kesten, en théorie de la percolation. Il est d'usage fréquent en théorie des graphes aléatoires, dans l'analyse des algorithmes randomisés, et en théorie de la percolation. Il est parfois appelé method of bounded differences ou MOBD.

ÉnoncéModifier

Soit deux ensembles A et B et soit   l'ensemble des applications de B dans A. On se donne une filtration  

Définition — Une application   est dite  -lipshitzienne si, pour tout   et pour tout   on a l'implication :

 

Autrement dit, si les deux applications coïncident à l'intérieur de   et à l'extérieur de   (i.e. dans les zones vertes et bleues de la figure ci-dessous), alors X varie peu de l'une à l'autre.

 
Principe de Maurey et condition de Lipschitz.

Théorème — On suppose   muni d'une structure   d'espace probabilisé telle que les images   forment une famille de variables aléatoires indépendantes. On suppose également que la variable aléatoire réelle X, définie sur  , est  -lipshitzienne. Alors, pour tout  

 

Application à un modèle d'urnes et de boulesModifier

Dans cet exemple, l'intérêt d'une inégalité de concentration précise est de justifier une méthode statistique de comptage approximatif[1] pouvant servir, par exemple, à déceler une attaque de virus informatique.

Une inégalité de concentrationModifier

On jette m boules au hasard dans n boîtes, expérience probabiliste dont un événement élémentaire   est décrit par une application de   dans   :   est le numéro de la boîte dans laquelle est rangée la boule numéro k. Ainsi les   sont bien des variables aléatoires indépendantes, et, accessoirement, des variables aléatoires uniformes. Considérons l'application X, qui, à une distribution   de m boules dans n boîtes, associe le nombre   de boîtes vides à la fin de cette distribution   On peut calculer l'espérance de X aisément à l'aide d'une décomposition de X en somme de variables de Bernoulli. On trouve alors que

 

Pour le choix   l'application X est  -lipshitzienne : en effet, si, d'une distribution à une autre, seule la place de la boule n°t change (  est réduit au seul élément t ), alors le nombre de boîtes vides varie d'au plus une unité. Ainsi, en vertu du principe de Maurey,

 

Une inégalité plus précise[2] est obtenue en appliquant la forme générale de l'inégalité d'Azuma.

Un problème de comptage approchéModifier

Il s'agit d'estimer le nombre m d'utilisateurs différents, identifiés, à un nœud du réseau, par l'entête du paquet de données qu'ils envoient. L'idée est qu'une attaque de virus ne se traduit pas par une augmentation décelable du volume du trafic (le gros du volume étant fourni, par exemple, par des téléchargements de fichiers, lesquels sont scindés en nombreux paquets qui ont tous le même entête, caractérisant le même utilisateur), mais par une augmentation drastique du nombre d'utilisateurs différents, à cause d'un envoi massif et concerté de mails (tous de petit volume, comparés à des téléchargements).

Chaque fois qu'un paquet de données est reçu à un nœud du réseau, l'utilisateur b émetteur du paquet est reconnu à l'aide de l'entête   du paquet de données (une suite de longueur L de 0 et de 1). Cet entête   est haché, i.e. transformé en un nombre   aléatoire uniforme sur l'intervalle [0,1] : cette transformation (la fonction de hachage) est conçue de telle sorte que m paquets émis par m utilisateurs différents produisent m entêtes différents   et, après hachage de ces entêtes, produisent une suite   de m variables aléatoires indépendantes et uniformes sur l'intervalle [0,1]. Par contre   paquets émis par le même utilisateur b produisent   fois la même entête  , et   hachages successifs de cet entête produisent une suite de   valeurs aléatoires identiques, toutes égales au même nombre tiré au hasard, une fois pour toutes, uniformément sur l'intervalle [0,1].

On reçoit un grand nombre (P) de paquets en un laps de temps très court. On dispose seulement de n cases mémoires et on veut compter le nombre m d'utilisateurs différents émetteurs de ces paquets. Par manque de place mémoire, il est impossible de stocker au fur et à mesure les entêtes des paquets déjà reçus, et par manque de temps il serait impossible de tester si un nouvel entête reçu fait partie de la liste des entêtes déjà récoltés. Un calcul exact de m est donc impossible. On se donne alors n cases, numérotées de 1 à n, considérées comme libres, ou bien occupées. Au départ toutes les cases sont considérées comme libres. À chaque paquet reçu, l'entête correspondant est haché, produisant un nombre U aléatoire uniforme sur [0,1], et la case n°  est marquée occupée, quel qu'ait été son statut antérieur. Qu'une entête apparaisse une fois ou 10 000 fois, le résultat sera le même : c'est, du fait de cet entête, le même nombre aléatoire U qui sera engendré et la même case n°  qui sera marquée occupée.

Ainsi l'état de l'ensemble des n cases après réception des P paquets ne dépend pas du volume P du trafic, mais uniquement de la suite des m entêtes hashés   correspondant aux m utilisateurs différents. Plus précisément, le nombre X de cases libres à la fin du processus a même loi que dans le problème de boîtes et de boules évoqué à la section précédente. L'inégalité de concentration assure que, pour n et m assez grands, avec une forte probabilité, l'approximation de   par X, c'est-à-dire :

 

est assez précise pour permettre de reconstituer le ratio r=m/n, et, partant de là, le nombre m d'utilisateurs différents, inconnu jusque-là, en fonction de X et de n, qui sont connus : on choisit comme approximation de r le nombre   Dans cette situation particulière, on sera satisfait si la précision de l'approximation permet de déceler un changement brutal de la valeur de m d'un moment à l'autre, changement annonciateur d'une attaque de virus : pour cela, une approximation grossière de m devrait suffire.

Voir aussiModifier

NotesModifier

  1. proposée par (en) Kyu-Young Whang et Ravi Krishnamurthy, « Query optimization in a memory-resident domain relational calculus database system », ACM Transactions on Database Systems (TODS), New York, NY, USA, ACM, vol. 15, no 1,‎ , p. 67–95 (ISSN 0362-5915, lire en ligne)
  2. (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge ; New York, Cambridge University Press (réimpr. 1997, 2000) (1re éd. 1995), 476 p. (ISBN 9780521474658), chap. 4 (« Tail inequalities »), p. 94–95, Théorème 4.18.

BibliographieModifier

  • (en) N. Alon et J. Spencer, The Probabilistic Method, New York, Wiley,
  • (en) K. Azuma, « Weighted Sums of Certain Dependent Random Variables », Tôhoku Math. Journ., vol. 19,‎ , p. 357–367
  • (ru) Sergei N. Bernstein, « [traduction] On certain modifications of Chebyshev's inequality », Doklady Akademii Nauk SSSR, vol. 17, no 6,‎ , p. 275–277
  • (en) C. McDiarmid, « On the method of bounded differences », London Math. Soc. Lectures Notes, Cambridge (UK), Cambridge Univ. Press, no 141 « Surveys in Combinatorics »,‎ , p. 148–188
  • (en) W. Hoeffding, « Probability inequalities for sums of bounded random variables », J. Amer. Statist. Assoc., vol. 58,‎ , p. 13–30
  • B. Maurey, « Constructions de suites symétriques », CR Acad. Sci. Paris, Série A–B, vol. 288,‎ , p. 679–681

Pour aller plus loinModifier

  • (en) S. Boucheron, G. Lugosi et P. Massart, « Concentration inequalities using the entropy method », Annals of Probability,‎

Pages liéesModifier