Inégalité d'Azuma

L'inégalité d'Azuma, quelquefois nommée inégalité d'Azuma-Hœffding, est une inégalité de concentration concernant les martingales dont les accroissements sont bornés.



Catégories :

Probabilités - Inégalité

L'inégalité d'Azuma, quelquefois nommée inégalité d'Azuma-Hœffding, 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 Hœffding, une inégalité de concentration ne concernant, elle , que les sommes de variables aléatoires indépendantes et bornées.

Énoncé courant

Un des énoncés les plus courants est

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

\forall t\in[\![1,m]\!],\qquad \mathbb{P}(|M_t-M_{t-1}|\le 1)=1.

Alors, pour tout 0, \ " src="http ://upload. wikimedia. org/math/4/5/d/45d0c191abd0d30955636f22638d282c. png" />

\begin{align}
\mathbb{P}\left(M_m-\mathbb{E}[M_m]\ge \lambda\right)
&\le\exp\left(-\frac{\lambdaˆ2}{2m}\right),
\\
\mathbb{P}\left(M_m-\mathbb{E}[M_m]\le -\lambda\right)
&\le\exp\left(-\frac{\lambdaˆ2}{2m}\right),
\\
\mathbb{P}\left(\left|M_m-\mathbb{E}[M_m]\right|\ge \lambda\right)
&\le 2\exp\left(-\frac{\lambdaˆ2}{2m}\right).
\end{align}

Notons que le choix entraine que

Énoncé général

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

Théorème — Soit une martingale comparé à 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 0, \ " src="http ://upload. wikimedia. org/math/4/5/d/45d0c191abd0d30955636f22638d282c. png" />

\begin{align}
\mathbb{P}\left(M_m-\mathbb{E}[M_m]\ge \lambda\right)
&\le\exp\left(-\frac{2\lambdaˆ2}{\sum_{i=1}ˆm\ell_iˆ2}\right),
\\
\mathbb{P}\left(M_m-\mathbb{E}[M_m]\le -\lambda\right)
&\le\exp\left(-\frac{2\lambdaˆ2}{\sum_{i=1}ˆm\ell_iˆ2}\right),
\\
\mathbb{P}\left(\left|M_m-\mathbb{E}[M_m]\right|\ge \lambda\right)
&\le 2\exp\left(-\frac{2\lambdaˆ2}{\sum_{i=1}ˆm\ell_iˆ2}\right).
\end{align}

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

Principe de Maurey

Le principe de Maurey a été énoncé pour la première fois par Maurey dans une note au Compte 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 habituel habituel en principe des graphes aléatoires, dans l'analyse des algorithmes randomisés, et en théorie de la percolation. Il est quelquefois nommé method of bounded differences ou MOBD.

Énoncé

Soit deux ensembles A et B et soit la totalité des applications de B dans A. On se donne une une filtration

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

\left\{\omega_{|(B_{t}\backslash B_{t-1})ˆ{c}}\equiv\tilde\omega_{|(B_{t}\backslash B_{t-1})ˆ{c}})\right\}\quad\Rightarrow\quad\left\{\left|X(\omega)-X(\tilde\omega)\right|\le 1\right\}.

C'est à dire, si les deux applications coincident au sein de ainsi qu'hors de (i. e. dans les zones vertes et bleues de la figure ci-dessous), alors X fluctue peu de l'une à l'autre.

Principe de Maurey et condition de Lipschitz.

Théorème — On suppose pourvu d'une structure d'espace probabilisé telle que les images forment une famille de variables aléatoires indépendantes. On suppose aussi que la variable aléatoire réelle X, définie sur, est -lipshitzienne. Alors, pour tout 0, \ " src="http ://upload. wikimedia. org/math/4/5/d/45d0c191abd0d30955636f22638d282c. png" />

\begin{align}
\mathbb{P}\left(X-\mathbb{E}[X]\ge \lambda\right)
&\le\exp\left(-\frac{\lambdaˆ2}{2m}\right),
\\
\mathbb{P}\left(X-\mathbb{E}[X]\le -\lambda\right)
&\le\exp\left(-\frac{\lambdaˆ2}{2m}\right),
\\
\mathbb{P}\left(\left|X-\mathbb{E}[X]\right|\ge \lambda\right)
&\le 2\exp\left(-\frac{\lambdaˆ2}{2m}\right).
\end{align}

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

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 concentration

On jette m boules au hasard dans n boites, expérience probabiliste dont un évènement élémentaire est décrit par une application de dans  : est le numéro de la boite 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 boites, associe le nombre de boites vides à la fin de cette distribution On peut calculer l'espérance de X facilement avec une décomposition de X en somme de variables de Bernoulli. On trouve tandis que

\mathbb{E}[X]\ =\ n\left(1-\tfrac1n\right)ˆm.

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 boites vides fluctue d'au plus une unité. Ainsi, en vertu du principe de Maurey,

\begin{align}
\mathbb{P}\left(\left|X-n\left(1-\tfrac1n\right)ˆ{m}\right|\ge \lambda\right)
&\le 2\exp\left(-\frac{\lambdaˆ2}{2m}\right).
\end{align}

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é

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 traffic (le gros du volume étant apporté, par exemple, par des téléchargements de fichiers, lesquels sont scindés en nombreux paquets qui ont tous la 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 s'est vu consacré avec l'entête du paquet de données (une suite de longueur L de 0 et de 1). Cette entête est hachée, i. e. transformée 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érentes 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 cette entête produisent une suite de valeurs aléatoires semblables, toutes identiques 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 particulièrement court. On dispose uniquement 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 une nouvelle entête reçue est membre de la liste des entêtes déjà récoltées. Un calcul exact de m est par conséquent impossible. On se donne alors n cases, numérotées de 1 à n, reconnues comme libres, ou bien occupées. Au départ l'ensemble des cases sont reconnues comme libres. A chaque paquet reçu, l'entête correspondante est hachée, 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 cette entête, le même nombre aléatoire U qui sera génèré et la même case n° qui sera marquée occupée.

Ainsi l'état de la totalité des n cases après réception des P paquets ne dépend pas du volume P du trafic, mais seulement de la suite des m entêtes hashées correspondant aux m utilisateurs différents. Plus exactement, le nombre X de cases libres à la fin du processus a même loi que dans le problème de boites 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, autrement dit :

\frac{X}{n}\ \simeq\ \left(1-\tfrac1n\right)ˆ{m}\ \simeq\ eˆ{-m/n}

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à, selon X et de n, qui sont connus : on choisit comme approximation de r le nombre Dans cette situation spécifique, on sera satisfait si la précision de l'approximation sert à 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 aussi

Notes

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

Bibliographie

Pour aller plus loin,

Pages liées

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/In%C3%A9galit%C3%A9_d%27Azuma.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu