Оценка Чернова даёт экспоненциально убывающие оценки вероятности больших отклонений сумм независимых случайных величин. Эти оценки являются более точными, чем оценки, полученные с использованием первых или вторых моментов, такие как неравенство Маркова или неравенство Чебышёва, которые дают лишь степенной закон убывания. Вместе с тем оценка Чернова требует, чтобы случайные величины были независимы в совокупности — условие, которое ни неравенство Маркова, ни неравенство Чебышёва не требуют, хотя неравенство Чебышёва требует попарную независимость случайных величин.
Оценка Чернова имеет отношение к и неравенству Хёфдинга, которые ей исторически предшествуют.
Основной случай
Основной случай оценки Чернова для случайной величины достигается применением неравенства Маркова к Этот метод был впервые применён Сергеем Бернштейном в доказательствах, связанных с .. Для каждого
Когда является суммой случайных величин , для любого
В частности, оптимизируя по t и предполагая, что независимы, мы получаем
(1)
Аналогично
и, таким образом,
Конкретные значения оценок Чернова получаются вычислением для конкретных величин .
Пример
Пусть — независимые случайные величины Бернулли, сумма которых , и каждая равна 1 с вероятностью . Для переменной Бернулли верно:
следовательно,
Для всякого при и получаем , и общий случай оценки Чернова даёт
Вероятность одновременного свершения более чем n/2 событий } в точности равна:
Нижнюю оценку этой вероятности можно вычислить с помощью неравенства Чернова:
В самом деле, обозначая , мы получаем мультипликативную форму оценки Чернова (см. ниже или Corollary 13.3 in Sinclair's class notes):
Этот результат допускает разнообразные обобщения, как отмечено ниже. Можно отметить несколько форм оценок Чернова: исходную аддитивную форму (даёт оценку для абсолютной ошибки) или более практичную мультипликативную форму (ограничивает ошибку по отношению к среднему).
Аддитивная форма (оценка для абсолютной ошибки) Следующая Теорема была доказана Василием Хёфдингом.
Теорема Чернова — Хёфдинга. Пусть — независимые одинаково распределённые случайные величины, принимающие значения Положим и . Тогда
где
Это расхождение Кульбака — Лейблера между случайными величинами, имеющими бернуллиево распределение с параметрами x и y соответственно. Если то
Более простая оценка получается ослаблением этой теоремы, используя неравенство , которое следует из выпуклости и того факта, что
Этот результат является частным случаем неравенства Хёфдинга. В некоторых случаях используются оценки
более сильные при .
Мультипликативная форма (оценка для относительной ошибки)
Мультипликативная оценка Чернова. Пусть — независимые случайные величины, принимающие значения Их сумму обозначим , математическое ожидание этой суммы обозначим μ. Тогда для всякого
Аналогичным образом можно показать, что для любого
На практике вышеприведённая формула часто оказывается громоздкой, поэтому используются более слабые, но удобные оценки
которые получаются с помощью неравенства из списка логарифмических неравенств. Или ещё более слабое неравенство
Приложения
Оценки Чернова имеют приложения в уравновешивании множеств и маршрутизации пакетов в разреженных сетях.
Проблема уравновешения множества возникает при проектировании статистического эксперимента. Как правило, при проектировании статистического эксперимента с заданными в этом эксперименте свойствами участников нам необходимо разделить участников на две непересекающиеся группы так, чтобы каждое свойство было, насколько это возможно, сбалансировано между двумя группами. См. также информацию в Probability and Computing: Randomized Algorithms and Probabilistic Analysis .
Оценки Чернова также используются для достижения жестких границ в задачах маршрутизации с использованием перестановок. Это уменьшает перегруженность при маршрутизации в разреженных сетях. См. подробнее в Probability and Computing: Randomized Algorithms and Probabilistic Analysis .
Также оценки Чернова находят применение в теории вычислительного обучения для доказательства того, что обучающий алгоритм аппроксимационно по вероятности корректен. То есть с высокой вероятностью этот алгоритм имеет малую ошибку на достаточно большом наборе тренировочных данныхM. Kearns, U. Vazirani. An Introduction to Computational Learning Theory. Chapter 9 (Appendix), pages 190-192. MIT Press, 1994..
Оценки Чернова могут быть эффективно использованы для оценки "уровня робастности" приложения/алгоритма посредством исследования его пространства возмущений при помощи рандомизации.C.Alippi: "Randomized Algorithms" chapter in Intelligence for Embedded Systems. Springer, 2014, 283pp.
Матричная оценка и использовали оценки Чернова для случайных величин с матричными значениями. Следующую версию неравенства можно найти в работе Троппа.
Пусть — случайные величины с матричными значениями такие, что и . Обозначим оператор нормы матрицы . Если неравенство почти наверное выполнено для всех , то для каждого
Чтобы заключить, что отклонение от 0 ограничено величиной с высокой вероятностью, нам нужно выбрать (количество образцов) пропорциональным логарифму . В общем случае зависимость от неочевидна: например, возьмём диагональную случайную матрицу знаков размерности . Оператор нормы суммы независимых образцов является в точности максимальным отклонением среди независимых случайных блужданий длины . Для того, чтобы достичь фиксированную границу максимального отклонения с постоянной вероятностью, должно логарифмически возрастать вместе с .
Следующая теорема получена в предположении, что имеет низкий ранг, для того, чтобы избежать зависимости от размерности.
Теорема без зависимости от размерности Пусть и ─ случайная симметрическая вещественная матрица с и почти наверное. Предположим, что каждый элемент носителя имеет ранг самое большее . Положим
Если почти наверное, то
где — это независимые одинаково распределенные копии .
Теорема для не полностью случайных матриц Анкит Гарг, Инь Тат Ли, Чжао Сонг и получили оценки типа Чернова для сумм матричнозначных случайных величин, семплированных с помощью случайного блуждания экспандера.
Расмус Кинг и Чжао Сонг получили оценки типа Чернова для сумм матриц лапласианов случайных деревьев.
Вариант семплинга Следующий вариант оценки Чернова можно использовать для оценки вероятности того, что большинство популяции станет в выборке меньшинством и наоборот.; lemma 6.1
Предположим, имеется общая популяция и подпопуляция . Обозначим относительный размер подпопуляции () через .
Допустим, мы выбираем целое кисло и случайную выборку размера . Обозначим относительный размер подпопуляции () через .
Тогда для каждой доли :
В частности, если ─ это большинство в (то есть, ), то мы можем оценить сверху вероятность того, что останется большинством в взяв Посмотреть графики: граница как функция от r с меняющимся k и граница как функция от k с меняющимся r .:
Эта оценка, разумеется, не является точной. Например, если , то мы получаем тривиальную оценку .
Доказательства
Теорема Чернова-Хёфдинга (аддитивная форма) Пусть . Взяв в формуле (1), получаем:
Теперь, зная что , имеем
Таким образом, мы можем легко вычислить минимум, используя технику дифференцирования:
Приравнивая полученное выражение к нулю и разрешая уравнение относительно , получаем
так что
Следовательно,
Поскольку , то мы видим, что , так что наша оценка удовлетворяется по . Получив , мы можем вернуться в предыдущие уравнения и найти
Теперь мы имеем желаемый результат, поскольку
Для завершения доказательства в симметрическом случае мы попросту определим случайную величину , применим к ней точно такое же доказательство и присоединим результат к нашей оценке.
Мультипликативная форма Положим . Согласно формуле (1),
Третья строчка следует из того, что принимает значение с вероятностью и значение 1 с вероятностью . Это идентично вычислениям выше в доказательстве аддитивной формы.
Переписав как и вспомнив, что (если , то неравенство строгое), мы положим . Тот же результат можно получить, напрямую заменяя в уравнении для оценки Чернова на .Обратитесь к приведенному выше доказательству.
Таким образом,
Если мы просто положим , так что для , то сможем подставить это в последнее выражение и найти
,
что и требовалось доказать.
См. также
Неравенство концентрации меры
Ссылки
Дальнейшее чтение
Категория:Вероятностные неравенства