Une extension de Chernoff lié

Je cherche une référence (pas une preuve, que je peux faire) à l'extension suivante de Chernoff.

Laissez sont des variables aléatoires booléennes, pas nécessairement indépendantes . Au lieu de cela, il est garanti que P r ( X i = 1 | C ) < p pour chaque i et chaque événement C qui ne dépend que de { X j | j ≠ i } .$X_1,..,X_n$$Pr(X_i=1|C)<p$$i$$C$$\{X_j|j\neq i\}$

Naturellement, je veux une borne supérieure sur .$\Pr\left(\sum_{i\in[n]}X_i>(1+\lambda)np\right)$

Merci d'avance!

Ce que vous voulez, c'est la borne de Chernoff généralisée, qui ne suppose que pour tout sous-ensemble S d'indices variables. Cette dernière découle de votre hypothèse, car pour S = { i 1 , … , i | S | } , P ( ⋀ i ∈ S X i ) = P ( X i 1 = 1 ) P $P(\bigwedge_{i\in S} X_{i}) \leq p^{|S|}$$S=\{i_1,\ldots,i_{|S|}\}$ Impagliazzo et Kabanets ont récemment donné une preuve alternative de la liaison de Chernoff, y compris celle généralisée. Dans leur article, vous pouvez trouver toutes les références appropriées aux travaux antérieurs:

Les éléments les plus proches dont je suis conscient dans la littérature sont les extensions des limites de Chernoff à des variables aléatoires corrélées négativement, par exemple voir ceci ou cela . Formellement, votre condition pourrait être satisfaite sans la corrélation négative, mais l'idée est similaire.

Parce que votre généralisation n'est pas difficile à prouver, il se peut que personne n'ait pris la peine de l'écrire.

Une référence alternative pourrait être le lemme 1.19 dans B. Doerr, Analyse de l'heuristique de recherche aléatoire: outils de la théorie des probabilités, Théorie de l'heuristique de recherche aléatoire (A. Auger et B. Doerr, éd.), World Scientific Publishing, 2011, pp. 1- 20.

$X_i=1$$p_i$$X_1, \dots, X_{i-1}$$X_1, \ldots, X_n$$Y_1, \ldots, Y_n$$p_1, \ldots, p_n$, respectivement. La preuve est élémentaire et le résultat est naturel, donc je suppose que personne n'a ressenti le besoin de l'écrire.