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. Un des énoncés les plus courants est Notons que le choix entraine que Un énoncé plus général (McDiarmid, Théorème 6.7) est le suivant L'énoncé courant, donné à la section précédente, est obtenu en spécialisant l'énoncé général aux choix 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. Soit deux ensembles A et B et soit l'ensemble des applications de B dans A. On se donne une filtration 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. 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. 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.