Jeudi 12 Décembre 2024
Rechercher 🔍

Inégalité d'Azuma - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
- Introduction - Énoncé courant - Principe de Maurey - Énoncé général

Introduction

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é courant

Un des énoncés les plus courants est

Inégalité d'Azuma — Soit une martingale \scriptstyle\ M=(M_t)_{0\le t\le m}\ par rapport à une filtration \scriptstyle\ \mathcal{F}=(\mathcal{F}_0=\{\Omega,\varnothing\}\subset\mathcal{F}_1\subset\mathcal{F}_2\subset\dots\subset\mathcal{F}_m)\ et vérifiant

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

Alors, pour tout \scriptstyle\ \lambda>0,\

\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 \scriptstyle\ \mathcal{F}_0=\{\Omega,\varnothing\}\ entraine que \scriptstyle\ M_0=\mathbb{E}[M_m].\

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 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é

Soit deux ensembles A et B et soit \scriptstyle\ \Omega=A^B\ l'ensemble des applications de B dans A. On se donne une une filtration \scriptstyle\ \mathcal{B}\ =\ (B_0=\varnothing\,\subset\,B_1\,\subset\,B_2\,\subset\dots\subset\,B_m=B).\

Définition — Une application \scriptstyle\ X\,:\,\Omega\rightarrow\mathbb{R}\ est dite \scriptstyle\ \mathcal{B} -lipshitzienne si, pour tout \scriptstyle\ t\in[\![1,m]\!]\ et pour tout \scriptstyle\ (\omega,\tilde\omega)\in\,\Omega,\ 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\}.

Autrement dit, si les deux applications coincident à l'intérieur de \scriptstyle\ B_{t-1}\ et à l'extérieur de \scriptstyle\ B_{t}\ (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 \scriptstyle\ \Omega\ muni d'une structure \scriptstyle\ (\Omega,\mathcal{A},\mathbb{P})\ d'espace probabilisé telle que les images \scriptstyle\ (\omega(b))_{b\in B}\ forment une famille de variables aléatoires indépendantes. On suppose également que la variable aléatoire réelle X, définie sur \scriptstyle\ (\Omega,\mathcal{A},\mathbb{P})\ , est \scriptstyle\ \mathcal{B} -lipshitzienne. Alors, pour tout \scriptstyle\ \lambda>0,\

\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}

On considère la filtration filtration \scriptstyle\ \mathcal{F}=(\mathcal{F}_0=\{\Omega,\varnothing\}\subset\mathcal{F}_1\subset\mathcal{F}_2\subset\dots\subset\mathcal{F}_m)\ définie, pour \scriptstyle\ 1\le t\le m,\ par

\mathcal{F}_t=\sigma\left(\omega(b)\ |\ b\in B_{t}\right).

Pour \scriptstyle\ 0\le t\le m,\ on pose

M_t=\mathbb{E}\left[X\left|\ \mathcal{F}_t\right.\right].

Ainsi \scriptstyle\ \left(M_t\right)_{0\le t\le m}\ est une martingale, et \scriptstyle\ M_0=\mathbb{E}\left[X\right],\ \scriptstyle\ M_m=X.\ Pour pouvoir appliquer l'inégalité d'Azuma, il ne reste plus qu'à démontrer que "les différences sont bornées". Pour cela on note, pour \scriptstyle\ 1\le t\le m,

  • \scriptstyle\ \omega_{1} la restriction de \scriptstyle\ \omega à \scriptstyle\ C_{1}=B_{t-1},\
  • \scriptstyle\ \omega_{2} la restriction de \scriptstyle\ \omega à \scriptstyle\ C_{2}=B_{t}\backslash B_{t-1},\
  • \scriptstyle\ \omega_{3} la restriction de \scriptstyle\ \omega à \scriptstyle\ C_{3}=B_{t}^{c},\ voir figure ci-dessus.

Comme les \scriptstyle\ C_{i},\ \scriptstyle\ 1\le i\le 3,\ forment une partition de B, il en résulte, d'une part, que \scriptstyle\ \omega est en correspondance bijective avec le triplet \scriptstyle\ (\omega_{1},\,\omega_{2},\, \omega_{3})\ , d'autre part qu'en vertu du lemme de regroupement le triplet \scriptstyle\ (\omega_{1},\,\omega_{2},\, \omega_{3})\ est un triplet de variables aléatoires indépendantes. Notons \scriptstyle\ \mathbb{P}_{i}\ la loi de probabilité de \scriptstyle\ \omega_{i},\ qui est une mesure de probabilité sur \scriptstyle\ A^{C_{i}}.\ On a alors

\begin{align} \mathbb{E}\left[X\left|\ \mathcal{F}_t\right.\right](\omega) &=\int_{A^{C_{3}}} X(\omega_{1},\,\omega_{2},\, w_{3}) \mathbb{P}_{3}(dw_{3}), \\ &=\int_{A^{C_{3}}} \left(\int_{A^{C_{2}}} X(\omega_{1},\,\omega_{2},\, w_{3}) \mathbb{P}_{2}(dw_{2})\right)\mathbb{P}_{3}(dw_{3}). \\ \mathbb{E}\left[X\left|\ \mathcal{F}_{t-1}\right.\right](\omega) &=\int_{A^{C_{3}}} \left(\int_{A^{C_{2}}} X(\omega_{1},\,w_{2},\, w_{3}) \mathbb{P}_{2}(dw_{2})\right)\mathbb{P}_{3}(dw_{3}). \end{align}

Ainsi

\begin{align} \left|M_t(\omega)-M_{t-1}(\omega)\right| &=\left|\int_{A^{C_{3}}} \left(\int_{A^{C_{2}}} \left(X(\omega_{1},\omega_{2},\, w_{3})-X(\omega_{1},\,w_{2},\, w_{3}) \right)\mathbb{P}_{2}(dw_{2})\right)\mathbb{P}_{3}(dw_{3})\right| \\ &\le\int_{A^{C_{3}}} \left(\int_{A^{C_{2}}} \left|X(\omega_{1},\omega_{2},\, w_{3})-X(\omega_{1},\,w_{2},\, w_{3}) \right|\mathbb{P}_{2}(dw_{2})\right)\mathbb{P}_{3}(dw_{3}). \end{align}

Mais les deux triplets \scriptstyle\ (\omega_{1},\omega_{2},\, w_{3})\ et \scriptstyle\ (\omega_{1},\,w_{2},\, w_{3})\ déterminent deux applications de B dans A qui ne diffèrent qu'au niveau de leurs restrictions à \scriptstyle\ C_{2}=B_{t}\backslash B_{t-1},\ (leurs restrictions sont \scriptstyle\ \omega_{2}\ et \scriptstyle\ w_{2},\ respectivement). Ainsi, X étant \scriptstyle\ \mathcal{B} -lipshitzienne,

\left|X(\omega_{1},\omega_{2},\, w_{3})-X(\omega_{1},\,w_{2},\, w_{3}) \right|\le 1.

Par conséquent

\left|M_t(\omega)-M_{t-1}(\omega)\right|\le 1.

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 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 \scriptstyle\ \omega\ est décrit par une application de \scriptstyle\ B=[\![1,m]\!]\ dans \scriptstyle\ A=[\![1,n]\!]\  : \scriptstyle\ \omega(k)\ est le numéro de la boite dans laquelle est rangée la boule numéro k. Ainsi les \scriptstyle\ \omega(k)\ sont bien des variables aléatoires indépendantes, et, accessoirement, des variables aléatoires uniformes. Considérons l'application X, qui, à une distribution \scriptstyle\ \omega\ de m boules dans n boites, associe le nombre \scriptstyle\ X(\omega)\ de boites vides à la fin de cette distribution \scriptstyle\ \omega.\ 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

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

Pour le choix \scriptstyle\ B_{t}=[\![1,t]\!],\ l'application X est \scriptstyle\ \mathcal{B} -lipshitzienne : en effet, si, d'une distribution à une autre, seule la place de la boule n°t change ( \scriptstyle\ B_t\backslash B_{t-1}= \{t\}\ est réduit au seul élément t ), alors le nombre de boites vides varie 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 est obtenue en appliquant la 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 noeud 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 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 noeud du réseau, l'utilisateur b émetteur du paquet est reconnu à l'aide de l'entête \scriptstyle\ \mathcal{E}_{b}\ du paquet de données (une suite de longueur L de 0 et de 1). Cette entête \scriptstyle\ \mathcal{E}_{b}\ est hachée, i.e. transformée en un nombre \scriptstyle\ U(\mathcal{E}_{b})\ 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 \scriptstyle\ \left(\mathcal{E}_{b}\right)_{1\le b\le m}\ et, après hachage de ces entêtes, produisent une suite \scriptstyle\ \left(U_{b}\right)_{1\le b\le m}\ de m variables aléatoires indépendantes et uniformes sur l'intervalle [0,1]. Par contre \scriptstyle\ \ell\ paquets émis par le même utilisateur b produisent \scriptstyle\ \ell\ fois la même entête \scriptstyle\ \mathcal{E}_{b}\ , et \scriptstyle\ \ell\ hachages successifs de cette entête produisent une suite de \scriptstyle\ \ell\ 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 une nouvelle entête reçue fait partie de la liste des entêtes déjà récoltées. 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. 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° \scriptstyle\ \lceil nU\rceil\ 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 engendré et la même case n° \scriptstyle\ \lceil nU\rceil\ 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ées \scriptstyle\ (U_{b})_{1\le b\le m}\ 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 boites et de boules évoqué à la section précédente. L' assure que, pour n et m assez grands, avec une forte probabilité, l'approximation de \scriptstyle\ \mathbb{E}[X]\ par X, c'est-à-dire :

\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à, en fonction de X et de n, qui sont connus : on choisit comme approximation de r le nombre \scriptstyle\ -\ln(X/n).\ 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.

Énoncé général
- Introduction - Énoncé courant - Principe de Maurey - Énoncé général
miniature
Une étoile dévorée à pleine vitesse par... un trou noir ? 🌟
miniature
Cette astuce simple réduit la consommation d'alcool... des femmes 🍷
miniature
Découverte: la lumière transforme un isolant en métal 💡
miniature
Cet aliment à bannir nourrit les cancers 🍽️
miniature
Cette tablette de 3000 ans dévoile une écriture jusqu'alors inconnue ✍️
miniature
Découverte d'une chimie des océans refroidissant le climat 🌊
miniature
Le télescope James Webb, poussé à ses limites, découvre ces structures incroyablement anciennes 🔭
miniature
Le rôle surprenant de la grossesse contre la grippe A 🦠
miniature
Découverte d'une nouvelle espèce éteinte grâce à... un accélérateur de particules ⚛️
miniature
Une avancée prometteuse pour le déploiement des batteries sodium-ion 🔋
miniature
Voici comment et pourquoi le risque de cancer augmente... puis diminue avec l'âge 🧬
miniature
Le Soleil bientôt en "zone de combat": une période de turbulences extrêmes ☀️
miniature
1
Les rhumatismes plus douloureux par temps humide: vrai ou faux ? 🌧️
miniature
Ce nouveau type de moteur repousse les limites du vol supersonique ✈️
miniature
Poster sur les réseaux sociaux peut nuire à votre santé mentale 🧠
miniature
Une super-Terre entre Mars et Jupiter ? 🌎
miniature
Découverte impressionnante d'un fossile de crocodile géant 🐊
miniature
1
Cet accident en laboratoire pourrait transformer drastiquement la mémoire numérique ⚡
miniature
1
Un virage technologique révèle l'impact du diabète gestationnel 🩺
miniature
Insolite: ces loups butinent des fleurs ! Des grands carnivores pollinisateurs ? 🌼
miniature
1
Ce fin gilet robotisé soulage les tâches répétitives 🦾
miniature
Les équations d'Einstein invalidées ? 👀
miniature
Ce tatouage électronique se connecte à votre cerveau 🧠
miniature
Cette IA de Google prédit la météo mieux que jamais, et sur 15 jours ! 🌦️
miniature
Des plats au bœuf... sans bœuf ? 🥩
miniature
2
Ce moteur de recherche d'un nouveau genre bouscule nos habitudes 🔍
miniature
Pourquoi les cheveux bouclent-ils en fonction de la météo ? 🌦️
miniature
Découverte: d'autres univers plus propices à la vie que le notre 👽
miniature
Ces sons urbains qui minent notre santé mentale 🚗
miniature
La testostérone impacte-t-elle vraiment le désir sexuel des hommes ? 🔥
miniature
Des microalgues éliminent les métaux lourds: voici comment 🧪
miniature
1
Et voici un qubit mécanique ! 🖥️
miniature
Les lentilles de contact sont-elles vraiment sans danger ? 👁️
miniature
Dans la course à l'IA générative, Google lance son générateur de vidéos 🎥
miniature
4
Une zone oubliée du cerveau permet aux paralysés de marcher à nouveau 🧠
miniature
Cette astuce quotidienne ajoute 11 ans à votre vie 🕒
miniature
Révolutions, migrations des européens... les éruptions volcaniques ont influencé l'histoire 🌋
miniature
Soit l'énergie noire n'est pas constante, soit une seconde force inconnue est à l'œuvre... 🌀
miniature
Voici pourquoi l'alcool peut rendre agressif 🥂
miniature
Expérience inédite: ce laser projette une ombre visible 💥
miniature
Ce plat millénaire réduit significativement la graisse corporelle 🍽️
miniature
Les scientifiques trompés ? La Voie Lactée n'est PAS comme les autres galaxies 🔭
miniature
Pourquoi ce que pensent les autres de nous nous fait tant ruminer ? 🧠
miniature
De la vie découverte sur un échantillon de l'astéroïde Ryugu (oups) 👽
miniature
2
Des anomalies incompréhensibles de températures détectées simultanément presque partout sur Terre 🌡️
miniature
Cette planète, trop jeune pour exister, bouscule les lois de l'astronomie 🪐
miniature
Une montagne d'or découverte en Chine ⛏️
miniature
Cette simulation de l'Univers est totalement vertigineuse 🌀
miniature
1
Une pilule pourrait-elle imiter les bienfaits du yoga ? 🧘
miniature
Nous serions-nous trompés sur l'origine de l'écriture alphabétique ? ✍️
Page générée en 0.303 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise