Неравенство типа Чернова для попарно независимых случайных величин

Неравенства типа Чернова используются, чтобы показать, что вероятность того, что сумма независимых случайных величин значительно отклоняется от ожидаемого значения, экспоненциально мала в ожидаемом значении и отклонении. Существует ли неравенство типа Чернова для любой суммы попарно независимых случайных величин? Другими словами, есть ли результат, который показывает следующее: вероятность того, что сумма попарно независимых случайных величин отклонится от ожидаемого значения, экспоненциально мала по ожидаемому значению и отклонению?

Парной независимости недостаточно для черновского типа, связанного с ожиданием.

Это следует из того факта , что существует -размер выборочных пространств по п 0-1 случайных величин, где все переменные являются попарно независимы, и каждая переменная является равномерным (это 1 с вероятностью 1 / 2 ). Таким образом, ожидаемое значение их суммы n / 2 . Но поскольку существует только р о л у ( п ) возможные события в выборочном пространстве, даже вероятность того, что сумма точно определенное значение v составляет по меньшей мере 1 $poly(n)$$n$$1$$1/2$$n/2$$poly(n)$$v$ (следовательно, оно не может быть больше 1 / e x p ( n ) ).$1/poly(n)$$1/exp(n)$

Ссылка на эту примерную конструкцию пространства приведена на стр. 11-12 в этом обзоре .

Если у вас есть попарная независимость, то вы можете ограничить дисперсию суммы и, таким образом, получить границу концентрации, используя неравенство Чебышева.

В книге Дубхаши-Панконези есть все результаты такого рода . Одной из стандартных ссылок такого рода является работа Шмидта, Зигеля и Шринивасана 1993 года под названием (достаточно уместно) « Границы Чернова-Хеффдинга для приложений с ограниченной независимостью »