Оценка Чернова (Keyutg Cyjukfg)

Перейти к навигации Перейти к поиску

Оценка Чернова даёт экспоненциально убывающие оценки вероятности больших отклонений сумм независимых случайных величин. Эти оценки являются более точными, чем оценки, полученные с использованием первых или вторых моментов, такие как неравенство Маркова или неравенство Чебышёва, которые дают лишь степенной закон убывания. Вместе с тем оценка Чернова требует, чтобы случайные величины были независимы в совокупности — условие, которое ни неравенство Маркова, ни неравенство Чебышёва не требуют, хотя неравенство Чебышёва требует попарную независимость случайных величин.

Оценка Чернова имеет отношение к неравенствам Бернштейна[англ.] и неравенству Хёфдинга, которые ей исторически предшествуют.

Основной случай

[править | править код]

Основной случай оценки Чернова для случайной величины достигается применением неравенства Маркова к etX [1]. Для каждого

Когда X является суммой n случайных величин X1, ... ,Xn, для любого

В частности, оптимизируя по t и предполагая, что Xi независимы, мы получаем

(1)

Аналогично

и, таким образом,

Конкретные значения оценок Чернова получаются вычислением для конкретных величин .

Пусть X1, ..., Xn — независимые случайные величины Бернулли, сумма которых X, и каждая равна 1 с вероятностью . Для переменной Бернулли верно:

следовательно,

Для всякого при и получаем

,

и общий случай оценки Чернова даёт[2]:64

Вероятность одновременного свершения более чем n/2 событий {Xk = 1} в точности равна:

Нижнюю оценку этой вероятности можно вычислить с помощью неравенства Чернова:

В самом деле, обозначая μ = np, мы получаем мультипликативную форму оценки Чернова (см. ниже или Corollary 13.3 in Sinclair's class notes)[3]:

Этот результат допускает разнообразные обобщения, как отмечено ниже. Можно отметить несколько форм оценок Чернова: исходную аддитивную форму (даёт оценку для абсолютной ошибки) или более практичную мультипликативную форму (ограничивает ошибку по отношению к среднему).

Аддитивная форма (оценка для абсолютной ошибки)

[править | править код]

Следующая Теорема была доказана Василием Хёфдингом[4].

Теорема Чернова — Хёфдинга. Пусть X1, ..., Xnнезависимые одинаково распределённые случайные величины, принимающие значения {0, 1}.
Положим p = E[X] и ε > 0. Тогда
где
Это расхождение Кульбака — Лейблера между случайными величинами, имеющими бернуллиево распределение с параметрами x и y соответственно. Если p1/2, то

Более простая оценка получается ослаблением этой теоремы, используя неравенство D(p + ε || p) ≥ 2ε2, которое следует из выпуклости D(p + ε || p) и того факта, что

Этот результат является частным случаем неравенства Хёфдинга. В некоторых случаях используются оценки

более сильные при p < 1/8.

Мультипликативная форма (оценка для относительной ошибки)

[править | править код]
Мультипликативная оценка Чернова. Пусть X1, ..., Xnнезависимые случайные величины, принимающие значения {0, 1}. Их сумму обозначим X, математическое ожидание этой суммы обозначим μ. Тогда для всякого

Аналогичным образом можно показать, что для любого

На практике вышеприведённая формула часто оказывается громоздкой[2], поэтому используются более слабые, но удобные оценки

которые получаются с помощью неравенства из списка логарифмических неравенств[5]. Или ещё более слабое неравенство

Приложения

[править | править код]

Оценки Чернова имеют приложения в уравновешивании множеств и маршрутизации пакетов в разреженных сетях.

Проблема уравновешения множества возникает при проектировании статистического эксперимента. Как правило, при проектировании статистического эксперимента с заданными в этом эксперименте свойствами участников нам необходимо разделить участников на две непересекающиеся группы так, чтобы каждое свойство было, насколько это возможно, сбалансировано между двумя группами. См. также информацию в Probability and Computing: Randomized Algorithms and Probabilistic Analysis Архивная копия от 16 апреля 2021 на Wayback Machine.

Оценки Чернова также используются для достижения жестких границ в задачах маршрутизации с использованием перестановок. Это уменьшает перегруженность при маршрутизации в разреженных сетях. См. подробнее в Probability and Computing: Randomized Algorithms and Probabilistic Analysis Архивная копия от 16 апреля 2021 на Wayback Machine.

Также оценки Чернова находят применение в теории вычислительного обучения для доказательства того, что обучающий алгоритм аппроксимационно по вероятности корректен. То есть с высокой вероятностью этот алгоритм имеет малую ошибку на достаточно большом наборе тренировочных данных[6].

Оценки Чернова могут быть эффективно использованы для оценки "уровня робастности" приложения/алгоритма посредством исследования его пространства возмущений при помощи рандомизации.[7]

Матричная оценка

[править | править код]

Рудольф Альсведе[англ.] и Андреас Винтер[англ.] использовали оценки Чернова для случайных величин с матричными значениями.[8] Следующую версию неравенства можно найти в работе Троппа.[9]

Пусть M1, ..., Mt — случайные величины с матричными значениями такие, что и . Обозначим оператор нормы матрицы . Если неравенство почти наверное выполнено для всех , то для каждого ε > 0

Чтобы заключить, что отклонение от 0 ограничено величиной ε с высокой вероятностью, нам нужно выбрать (количество образцов) пропорциональным логарифму . В общем случае зависимость от неочевидна: например, возьмём диагональную случайную матрицу знаков размерности . Оператор нормы суммы независимых образцов является в точности максимальным отклонением среди независимых случайных блужданий длины . Для того, чтобы достичь фиксированную границу максимального отклонения с постоянной вероятностью, должно логарифмически возрастать вместе с .[10]

Следующая теорема получена в предположении, что имеет низкий ранг, для того, чтобы избежать зависимости от размерности.

Теорема без зависимости от размерности

[править | править код]

Пусть 0 < ε < 1 и ─ случайная симметрическая вещественная матрица с и почти наверное. Предположим, что каждый элемент носителя имеет ранг самое большее . Положим

Если почти наверное, то

где M1, ..., Mt — это независимые одинаково распределенные копии .

Теорема для не полностью случайных матриц

[править | править код]

Анкит Гарг, Инь Тат Ли, Чжао Сонг и Нихил Шривастава[англ.][11] получили оценки типа Чернова для сумм матричнозначных случайных величин, семплированных с помощью случайного блуждания экспандера.

Расмус Кинг и Чжао Сонг[12] получили оценки типа Чернова для сумм матриц лапласианов случайных деревьев.

Вариант семплинга

[править | править код]

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

Предположим, имеется общая популяция и подпопуляция . Обозначим относительный размер подпопуляции () через .

Допустим, мы выбираем целое кисло и случайную выборку размера . Обозначим относительный размер подпопуляции () через .

Тогда для каждой доли :

В частности, если ─ это большинство в (то есть, ), то мы можем оценить сверху вероятность того, что останется большинством в взяв [14]:

Эта оценка, разумеется, не является точной. Например, если , то мы получаем тривиальную оценку .

Доказательства

[править | править код]

Теорема Чернова-Хёфдинга (аддитивная форма)

[править | править код]

Пусть q = p + ε. Взяв a = nq в формуле (1), получаем:

Теперь, зная что Pr(Xi = 1) = p, Pr(Xi = 0) = 1 − p, имеем

Таким образом, мы можем легко вычислить минимум, используя технику дифференцирования:

Приравнивая полученное выражение к нулю и разрешая уравнение относительно , получаем

так что

Следовательно,

Поскольку q = p + ε > p, то мы видим, что t > 0, так что наша оценка удовлетворяется по t. Получив t, мы можем вернуться в предыдущие уравнения и найти

Теперь мы имеем желаемый результат, поскольку

Для завершения доказательства в симметрическом случае мы попросту определим случайную величину Yi = 1 − Xi, применим к ней точно такое же доказательство и присоединим результат к нашей оценке.

Мультипликативная форма

[править | править код]

Положим Pr(Xi = 1) = pi. Согласно формуле (1),

Третья строчка следует из того, что принимает значение et с вероятностью pi и значение 1 с вероятностью 1 − pi. Это идентично вычислениям выше в доказательстве аддитивной формы.

Переписав как и вспомнив, что (если x > 0, то неравенство строгое), мы положим . Тот же результат можно получить, напрямую заменяя a в уравнении для оценки Чернова на (1 + δ)μ.[15]

Таким образом,

Если мы просто положим t = ln(1 + δ), так что t > 0 для δ > 0, то сможем подставить это в последнее выражение и найти

,

что и требовалось доказать.

  1. Этот метод был впервые применён Сергеем Бернштейном в доказательствах, связанных с неравенствами Бернштейна[англ.].
  2. 1 2 Mitzenmacher, Michael, & Upfal, Eli. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. — Cambridge University Press, 2005. — ISBN 978-0-521-83540-4. — doi:10.1017/CBO9780511813603.005. Архивная копия от 16 апреля 2021 на Wayback Machine
  3. Sinclair, Alistair Class notes for the course "Randomness and Computation" (Fall 2011). Дата обращения: 30 октября 2014. Архивировано из оригинала 31 октября 2014 года.
  4. Hoeffding, W. (1963). "Probability Inequalities for Sums of Bounded Random Variables" (PDF). Journal of the American Statistical Association. 58 (301): 13—30. doi:10.2307/2282952. JSTOR 2282952.
  5. Useful Inequalities. logarithm. Дата обращения: 13 мая 2020. Архивировано 19 августа 2020 года.
  6. M. Kearns, U. Vazirani. An Introduction to Computational Learning Theory. Chapter 9 (Appendix), pages 190-192. MIT Press, 1994.
  7. C.Alippi: "Randomized Algorithms" chapter in Intelligence for Embedded Systems. Springer, 2014, 283ppISBN 978-3-319-05278-6.
  8. Ahlswede, R.; Winter, A. (2003). "Strong Converse for Identification via Quantum Channels". IEEE Transactions on Information Theory[англ.]. 48 (3): 569—579. arXiv:quant-ph/0012127. doi:10.1109/18.985947. {{cite journal}}: Недопустимый |ref=harv (справка)
  9. Tropp, J. (2010). "User-friendly tail bounds for sums of random matrices". Foundations of Computational Mathematics. 12 (4): 389—434. arXiv:1004.4389. doi:10.1007/s10208-011-9099-z. {{cite journal}}: Недопустимый |ref=harv (справка)
  10. Magen, A.; Zouzias, A. (2011). "Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication". arXiv:1005.2724 [cs.DM].
  11. Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava. A Matrix Expander Chernoff Bound // Association for Computing MachineryNew YorkNYUnited States. — 2018. Архивировано 14 апреля 2021 года.
  12. Rasmus Kyng, Zhao Song. A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees // FOCS. — 2018. — 1 октября. Архивировано 22 апреля 2021 года.
  13. Goldberg, A. V. Competitive Auctions for Multiple Digital Goods // Algorithms — ESA 2001 / A. V. Goldberg, J. D. Hartline. — 2001. — Vol. 2161. — P. 416. — ISBN 978-3-540-42493-2. — doi:10.1007/3-540-44676-1_35.; lemma 6.1
  14. Посмотреть графики: граница как функция от r с меняющимся k Архивная копия от 4 января 2015 на Wayback Machine и граница как функция от k с меняющимся r Архивная копия от 4 января 2015 на Wayback Machine.
  15. Обратитесь к приведенному выше доказательству.

Дальнейшее чтение

[править | править код]