Чернофф рассчитывается для взвешенных сумм

14

Рассмотрим , где lambda_i> 0 и Y_i распределены как стандартная нормаль. Какие границы концентрации можно доказать на X как функцию (фиксированных) коэффициентов lambda_i?Иксзнак равноΣяλяYя2

Если все лямбда_i равны, то это граница Чернова. Единственный другой результат, о котором я знаю, - это лемма из статьи Ароры и Каннана («Изучение смесей произвольных гауссианов», STOC'01, лемма 13), которая доказывает концентрацию вида , т. е. оценка зависит от суммы квадратов коэффициентов.проб(Икс<Е[Икс]-T)<еИксп(-T2/(4Σяλя2)

Доказательство их леммы аналогично обычному доказательству границы Чернова. Существуют ли другие «канонические» такие границы или общая теория, в которых функции лямбда-элементов таковы, что их большая величина обеспечивает хорошую экспоненциальную концентрацию (здесь функция была просто суммой квадратов)? Может быть, какая-то общая мера энтропии?

Более стандартная ссылка на лемму Арора-Каннана также была бы полезна, если бы она существовала.

Томас
источник
Как далеко вы продвинулись в воспроизведении их границ? Этот конкретный случай экспоненциального метода mgf, кажется, требует некоторых умных границ и анализа случая.
Томас Але

Ответы:

14

Книга Дубхаши и Панконези собирает вместе много таких границ, более многочисленных, чем можно перечислить здесь. Если вам трудно сразу получить доступ, есть онлайн-обзор границ Черноффа, проведенных Чунгом и Лу.

Суреш Венкат
источник
Спасибо, это выглядит очень хорошо. В частности, теорема 3.5 обзора Чунга и Лу, похоже, идентична лемме Арора-Каннана, которую я сформулировал. Наличие суммы lambda_i ^ 2 кажется естественным, поскольку это просто дисперсия X.
Томас
Связь между Чунгом и Лу мертва. Тем не менее, интернет-архив имеет это: web.archive.org/web/20070714095538/http://… . Название: «Неравенства концентрации и неравенства Мартингейла: обзор», авторы - Фан Чунг и Линьюань Лу.
Jbapple