Inégalité de type Chernoff pour les variables aléatoires indépendantes par paire

Les inégalités de type Chernoff sont utilisées pour montrer que la probabilité qu'une somme de variables aléatoires indépendantes s'écarte significativement de sa valeur attendue est exponentiellement faible dans la valeur attendue et l'écart. Existe-t-il une inégalité de type Chernoff pour toute somme de variables aléatoires indépendantes par paire ? En d'autres termes, y a-t-il un résultat qui montre ce qui suit: la probabilité qu'une somme de variables aléatoires indépendantes par paire s'écarte de sa valeur attendue est exponentiellement petite dans la valeur attendue et l'écart?

L'indépendance par paire n'est pas suffisante pour une liaison de type Chernoff sur l'attente.

$poly(n)$$n$$1$$1/2$$n/2$$poly(n)$$v$$1/poly(n)$$1/exp(n)$

Pour une référence à cet exemple de construction d'espace, voir les pages 11-12 de cette enquête .

Si vous avez une indépendance par paire, vous pouvez alors limiter la variance de la somme et ainsi obtenir une concentration liée en utilisant l'inégalité de Tchebychev.

Il y a toutes sortes de résultats de ce genre dans le livre Dubhashi-Panconesi . Une référence standard de ce type est le travail de 1993 de Schmidt, Siegel et Srinivasan intitulé (de manière appropriée) " Limites de Chernoff-Hoeffding pour les applications avec une indépendance limitée "