Оглавление
- 1 Чернов связан
- 1.1 Граница Чернова
- 1.2 История и свойства
- 1.3 Применение и оценки
- 1.4 Логарифм и функции
- 1.5 Нижние границы и суммы
- 1.6 Приложения
- 1.7 Вероятность правильных предположений
- 1.8 Оценка Чернова для матричнозначных случайных величин
- 1.9 Теорема без учета зависимости от размеров
- 1.10 Вариант отбора проб
- 1.11 Доказательства
- 1.12 Полный текст статьи:
- 2 Граница Чернова
Чернов связан
-
Граница Чернова
- Экспоненциально уменьшающаяся верхняя граница хвостовой части случайной величины
- Основана на производящей функции момента
- Минимальная из всех экспоненциальных оценок образует границу Чернова
-
История и свойства
- Названа в честь Германа Черноффа и Харальда Крамера
- Более четкая граница, чем конечные оценки
- Требует независимости случайных величин
-
Применение и оценки
- Используется для сумм независимых случайных величин
- Применяется для доказательства неравенств Хеффдинга, Беннета и Макдиармида
- Общая оценка Чернова достигается применением неравенства Маркова
-
Логарифм и функции
- Логарифм двусторонней оценки Чернова известен как функция скорости
- Функция скорости эквивалентна преобразованию Лежандра-Феншеля
- Граница Чернова достигает максимума в среднем и инвариантна относительно трансляции
-
Нижние границы и суммы
- Нижние границы можно получить с помощью неравенства Пейли-Зигмунда
- Для сумм независимых случайных величин оценка Чернова сводится к произведению функций создания момента
-
Приложения
- Балансировка наборов данных и маршрутизация пакетов
- Используется в теории вычислительного обучения для оценки надежности алгоритмов
- Применяется для форсирования рандомизированных алгоритмов
-
Вероятность правильных предположений
- Вероятность более n/2 правильных предположений равна вероятности суммы независимых случайных величин Бернулли, равных 1 с вероятностью p, быть больше n/2.
- Вероятность по крайней мере 1 − δ через мультипликативную границу Чернова.
-
Оценка Чернова для матричнозначных случайных величин
- Рудольф Альсведе и Андреас Винтер ввели оценку Чернова для матричнозначных случайных величин.
- Для независимых матричнозначных случайных величин с E[M] = 0 и ‖M‖ ≤ γ почти наверняка, отклонение от 0 ограничено ε с вероятностью, пропорциональной логарифму d1 + d2.
-
Теорема без учета зависимости от размеров
- Для случайной симметричной вещественной матрицы M с ‖E[M]‖ ≤ 1 и ‖M‖ ≤ γ почти наверняка, если каждый элемент на носителе M имеет не более ранга r, то отклонение от 0 ограничено ε с вероятностью, пропорциональной r.
-
Вариант отбора проб
- Оценка Черноффа может быть использована для определения вероятности того, что большинство в популяции станет меньшинством в выборке.
- Для общей совокупности A и подгруппы B, относительный размер подгруппы в выборке (|B∩S|/|S|) можно оценить с помощью доли d.
-
Доказательства
- Мультипликативная форма: для независимых случайных величин Бернулли с вероятностью pi = 1, используя (1) с a = (1 + δ)μ, получаем желаемый результат.
- Теорема Чернова–Хеффдинга (аддитивная форма): для q = p + ε, используя математический анализ, получаем нижнюю границу.
- Симметричный случай: для случайной величины Yi = 1 − Xi, применяем то же доказательство.