Границы Чернова и Хёфдинга: хвост, который убывает как экспонента

Если ты объяснишь, откуда в оценке берётся экспонента, выберешь между формами Чернова и Хёфдинга и посчитаешь размер выборки для заданных точности и надёжности - листай до «Теперь сам».

Как думаешь, сколько человек нужно опросить

Нужно узнать, какая доля из 100 миллионов пользователей включила тёмную тему, с точностью до одного процентного пункта. Ошибиться сильнее разрешено в 5% случаев.

Попробуй угадать до чтения: какую часть пользователей придётся проверить - 10%, 1%, 0,1%? Ответ - 18 445 человек, меньше двух сотых процента. И для миллиарда пользователей нужно столько же: размер совокупности в формулу не входит вовсе.

На что это похоже

Суп и ложка. Чтобы понять, достаточно ли соли в кастрюле, хватает одной ложки - и для кастрюли на три литра, и для котла на триста. Важно одно: суп должен быть перемешан, то есть ложка должна быть случайной частью целого. От размера котла точность пробы не зависит, от размера ложки - зависит.

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

Механизм: неравенство Маркова для экспоненты

Чебышёв получился, когда Маркова применили к квадрату отклонения. Квадрат растёт быстрее самой величины, поэтому оценка вышла сильнее. Следующий шаг - взять функцию, которая растёт ещё быстрее: экспоненту e^(tX) с каким-нибудь t > 0; здесь e ≈ 2,718 - основание натурального логарифма. Она неотрицательна, и событие X ≥ a - то же самое, что e^(tX) ≥ e^(ta):

P(X ≥ a) = P(e^(tX) ≥ e^(ta)) ≤ E[e^(tX)] / e^(ta)

Почему именно экспонента. Пусть X = X₁ + … + Xₙ. Экспонента превращает сумму в произведение: e^(tX) = e^(tX₁) · e^(tX₂) · … · e^(tXₙ). А ожидание произведения независимых величин равно произведению ожиданий:

E[e^(tX)] = E[e^(tX₁)] · E[e^(tX₂)] · … · E[e^(tXₙ)]

Справа стоит n множителей. Знаменатель e^(ta) тоже можно разложить на n равных частей, и при подходящем t на каждое слагаемое приходится множитель меньше единицы. Оценка получает вид «число меньше единицы в степени n» - это и есть экспоненциальное убывание. Остаётся подобрать t, при котором оценка наименьшая; после подбора получаются формулы из правила. Для суммы независимых величин «0 или 1» их называют границами Чернова, для среднего независимых величин из ограниченного отрезка - границей Хёфдинга.

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

Правило

Пусть X - сумма независимых величин, каждая из которых равна 0 или 1, и μ = E[X]. Тогда

• P(X ≥ (1 + δ) · μ) ≤ e^(−μδ²/3) при 0 < δ ≤ 1;
• P(X ≤ (1 − δ) · μ) ≤ e^(−μδ²/2) при 0 < δ < 1;
• P(X ≥ R) ≤ 2^(−R) при R ≥ 6μ.

Граница Хёфдинга: если X̄ - среднее n независимых величин со значениями от 0 до 1 и общим ожиданием p, то P(|X̄ − p| ≥ ε) ≤ 2 · e^(−2nε²). Чтобы ошибка не превышала ε с вероятностью не меньше 1 − δ, достаточно n ≥ ln(2/δ) / (2ε²) наблюдений.

Разбор: четыре оценки одного хвоста

Тысяча бросков монеты, отклонение числа орлов от 500 на t и больше. Точная вероятность считается сложением: вероятность ровно k орлов получается из вероятности k − 1 орла умножением на (n − k + 1) / k. Рядом три оценки: Чебышёва n / (4t²), Чернова с δ = t / 500 в обе стороны и Хёфдинга с ε = t / 1000. Числа крошечные, поэтому печатаются их десятичные логарифмы, округлённые до десятых: −2.8 означает число около 10⁻²·⁸, между 0,001 и 0,002.

В программе впервые подключён модуль math: math.exp(x) - это e в степени x, math.log(x) - натуральный логарифм, math.log10(x) - десятичный.

import math

n = 1000
veroyatnost = [0.5 ** n]
for k in range(1, n + 1):
    veroyatnost.append(veroyatnost[k - 1] * (n - k + 1) / k)

for t in [50, 100, 150]:
    tochno = 0
    for k in range(n + 1):
        if abs(k - n / 2) >= t:
            tochno = tochno + veroyatnost[k]
    chebyshev = n / 4 / t ** 2
    delta = t / (n / 2)
    chernov = 2 * math.exp(-(n / 2) * delta ** 2 / 3)
    hoeffding = 2 * math.exp(-2 * t ** 2 / n)
    stroka = [t]
    for x in [chebyshev, chernov, hoeffding, tochno]:
        stroka.append(round(math.log10(x), 1))
    print(stroka)

[50, -1.0, -0.4, -1.9, -2.8]
[100, -1.6, -2.6, -8.4, -9.6]
[150, -2.0, -6.2, -19.2, -20.8]

Те же величины без логарифма, с одной-двумя значащими цифрами:

отклонение    Чебышёв    Чернов        Хёфдинг       точно
50            0,1        0,38          0,013         0,0017
100           0,025      0,0025        4 · 10⁻⁹      3 · 10⁻¹⁰
150           0,011      6 · 10⁻⁷      6 · 10⁻²⁰     2 · 10⁻²¹

Три наблюдения. Первое: при удвоении отклонения Чебышёв улучшается вчетверо, а у Хёфдинга вчетверо вырастает показатель экспоненты; на отклонении 150 между ними семнадцать порядков. Второе: в первой строке форма Чернова проиграла Чебышёву. Упрощённая формула с тройкой в знаменателе грубовата у самого среднего и становится выгодной на больших отклонениях. Третье: для монеты Хёфдинг лучше Чернова на всех трёх строках и отстаёт от точного значения всего на порядок-полтора.

Выбор формы зависит от того, где лежит среднее. Когда p около половины, как у монеты, берут Хёфдинга. Когда события редкие и μ мало по сравнению с n, Хёфдинг почти ничего не даёт, а формы Чернова работают, потому что в них стоит μ, а не n.

Разбор: размер выборки и то, от чего он не зависит

Формула n ≥ ln(2/δ) / (2ε²) для четырёх пар «точность, допустимая вероятность промаха», а затем проверка: 45 опросов по 2050 человек при истинной доле 0,37.

import math
import random

def razmer(eps, delta):
    return math.ceil(math.log(2 / delta) / (2 * eps ** 2))

print(razmer(0.03, 0.05), razmer(0.01, 0.05), razmer(0.01, 0.001), razmer(0.001, 0.05))

random.seed(9)
dolya = 0.37
n = razmer(0.03, 0.05)
oprosov = 45
hudshee = 0
promahov = 0
for opros in range(oprosov):
    za = 0
    for chelovek in range(n):
        if random.random() < dolya:
            za = za + 1
    oshibka = abs(za / n - dolya)
    hudshee = max(hudshee, oshibka)
    if oshibka > 0.03:
        promahov = promahov + 1
print(n, round(hudshee, 4), promahov)

2050 18445 38005 1844440
2050 0.0232 0

math.ceil(x) округляет вверх до целого. random.random() возвращает случайное дробное число от 0 до 1, и условие < dolya истинно с вероятностью 0,37. Из 45 опросов ни один не ошибся больше чем на три пункта; худшая ошибка - 2,3 пункта. Формула обещала не больше 5% промахов и выполнила обещание с запасом.

Первая строка показывает, сколько стоит каждое требование. Точность ε входит в квадрате: перейти от трёх пунктов к одному - в девять раз больше наблюдений, от одного к 0,1 - в сто раз. Надёжность δ стоит под логарифмом: уменьшить вероятность промаха с 5% до 0,1%, в пятьдесят раз, стоит всего вдвое больше наблюдений. Надёжность дёшева, точность дорога.

Граница - независимость наблюдений. Формула верна для выборки, в которой каждый человек выбран случайно и отдельно от остальных. Две тысячи сотрудников одного офиса, две тысячи запросов одной сессии, две тысячи строк лога подряд - это одна ложка с поверхности: слагаемые зависимы, и гарантия исчезает, хотя число наблюдений то же.

Что ломается без этого

Берут выборку, пропорциональную данным. «Проверим 1% строк» на миллиарде строк - десять миллионов проверок там, где хватило бы двадцати тысяч, а на десяти тысячах строк - сто проверок там, где их мало.

Применяют оценку к зависимым событиям. Отказы серверов в одной стойке, ошибки в запросах одного клиента. Экспоненциальная оценка получена перемножением ожиданий и без независимости неверна; для таких случаев остаётся Чебышёв или оценка объединения.

Путают направление и диапазон. Форма с δ²/3 работает только до δ = 1, то есть до удвоенного среднего. Для превышения в десять раз есть третья форма, 2^(−R).

Ждут от Хёфдинга пользы на редких событиях. Если ошибка случается в одном запросе из миллиона, то «доля с точностью 1%» бессмысленна: сама доля в десять тысяч раз меньше допуска.

Зачем это в работе

Мониторинг по выборке. Трассировку запросов включают для одного из тысячи, и долю медленных оценивают по этой выборке. Формула говорит, сколько трасс нужно накопить, прежде чем доле можно верить, и почему редкую ошибку выборка в 0,1% может не увидеть вовсе.

Сравнение двух версий. Сколько пользователей нужно в каждой группе, чтобы заметить разницу в один пункт, - это тот же расчёт: точность ε должна быть заметно меньше искомой разницы.

Анализ рандомизированных алгоритмов. Утверждения вида «глубина рекурсии быстрой сортировки не превышает c · log n с вероятностью 1 − 1/n²» доказываются границей Чернова, применённой к числу удачных разбиений на пути. Третья форма даёт короткую оценку для шаров и корзин: при средней загрузке один в корзине окажется 2 · log₂ n шаров и больше с вероятностью не выше 1/n², и по оценке объединения с вероятностью не меньше 1 − 1/n такой корзины нет ни одной.

Теперь сам

1. Монету бросают 10 000 раз. По границе Хёфдинга оцени вероятность того, что число орлов отличается от 5000 не меньше чем на 200. Используй e⁻⁸ ≈ 0,00034.
2. Сколько наблюдений нужно, чтобы оценить долю с точностью 0,05 и вероятностью промаха не больше 0,01? Используй ln 200 ≈ 5,3.
3. Сумма независимых индикаторов имеет среднее 300. Оцени вероятность того, что она не меньше 450.
4. К серверу обращается 1000 клиентов; каждый в данную секунду независимо шлёт запрос с вероятностью 0,002, так что в среднем приходит 2 запроса. Оцени вероятность, что за секунду придёт 20 и больше.
5. Точность опроса нужно улучшить вдвое, а вероятность промаха уменьшить в сто раз, с исходных 5%. Что из этого обойдётся дороже?