Chernoff à destination des sommes pondérées

14

Considérons , où lambda_i> 0 et Y_i est distribué comme une normale standard. Quel type de limites de concentration peut-on prouver sur X, en fonction des coefficients (fixes) lambda_i?X=jeλjeOuije2

Si tous les lambda_i sont égaux, il s'agit d'une borne Chernoff. Le seul autre résultat que je connaisse est un lemme d'un article d'Arora et Kannan ("Learning mixtures of arbitrary Gaussians", STOC'01, Lemma 13), qui prouve la concentration de la forme , c'est-à-dire que la borne dépend de la somme des carrés des coefficients.Prob(X<E[X]-t)<eXp(-t2/(4jeλje2)

La preuve de leur lemme est analogue à la preuve habituelle de la liaison de Chernoff. Existe-t-il d'autres limites "canoniques", ou une théorie générale des fonctions des lambda_i telles que leur ampleur assure une bonne concentration exponentielle (ici, la fonction était simplement la somme des carrés)? Peut-être une certaine mesure générale de l'entropie?

Une référence plus standard pour le lemme Arora-Kannan serait également excellente, si elle existe.

Thomas
la source
Jusqu'où avez-vous réussi à reproduire leur reliure? Cet exemple particulier de la méthode mgf exponentielle semble nécessiter des limites intelligentes et une analyse de cas.
Thomas Ahle

Réponses:

14

Le livre de Dubhashi et Panconesi rassemble un grand nombre de ces limites, plus nombreuses que celles énumérées ici. Si vous trouvez cela difficile à accéder immédiatement, il y a une enquête en ligne sur les limites de Chernoff par Chung et Lu

Suresh Venkat
la source
Merci, cela semble très bien. En particulier, le théorème 3.5 de l'enquête Chung et Lu semble être identique au lemme Arora-Kannan que j'affirmais. Faire apparaître la somme des lambda_i ^ 2 est naturel car il s'agit simplement de la variance de X.
Thomas
Le lien Chung et Lu est mort. Cependant, Internet Archive l'a: web.archive.org/web/20070714095538/http://… . Le titre est «Inégalités de concentration et inégalités de martingale: une enquête» et les auteurs sont Fan Chung et Linyuan Lu.
jbapple