Конспект: хвостовые оценки - Марков, Чебышёв, Чернов

Понятия

Хвост распределения - вероятность значений, далёких от среднего. Хвостовая оценка - верхняя граница этой вероятности.

Дисперсия Var[X] = E[(X − μ)²] = E[X²] − μ² - среднее квадрата отклонения. Стандартное отклонение σ = √Var[X] - типичный размах в единицах самой величины.

Медиана - середина отсортированного списка. Медиана средних - замеры делят на группы, в каждой берут среднее, из средних берут медиану.

С высокой вероятностью - вероятность нарушения не больше 1/nᶜ.

Что унести

ОДНА ИДЕЯ, ТРИ СТУПЕНИ: неравенство Маркова, применённое
  к самой величине        → 1/t          знает среднее
  к квадрату отклонения   → 1/t²         знает дисперсию; хватает попарной независимости
  к экспоненте e^(tX)     → e^(−ct²)     сумма стала произведением; нужна полная независимость

ДИСПЕРСИЯ
индикатор с вероятностью p:  p(1 − p)                 Var[cX] = c² · Var[X]
независимые:  Var[X + Y] = Var[X] + Var[Y]            складываются квадраты: σ 3 и 4 дают 5, не 7
сумма n независимых:  среднее n·μ,  σ·√n              среднее n замеров:  σ/√n
кубик: 3,5 и σ = 1,71;   сто кубиков: 350 и σ = 17,1;   один кубик × 100: σ = 170,8
1000 бросков монеты: μ = 500, Var = 250, σ = 15,8
в 10 раз точнее - в 100 раз больше замеров

1000 БРОСКОВ, ОТКЛОНЕНИЕ ОТ 500 НА t И БОЛЬШЕ
t      Чебышёв    Чернов       Хёфдинг       точно
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⁻²¹
у самого среднего упрощённый Чернов слабее Чебышёва; p около 1/2 - Хёфдинг; редкие события - Чернов

РАЗМЕР ВЫБОРКИ:  n ≥ ln(2/δ) / (2ε²)        размер совокупности в формулу не входит
ε = 0,03, δ = 0,05 →  2 050          ε = 0,01, δ = 0,05  → 18 445
ε = 0,01, δ = 0,001 → 38 005         ε = 0,001, δ = 0,05 → 1 844 440
точность - в квадрате, надёжность - под логарифмом

УСИЛЕНИЕ ПОВТОРОМ, k независимых запусков
ошибка односторонняя p             хватит одного достоверного ответа     pᵏ
ошибка двусторонняя p < 1/2        большинство                           ≤ e^(−2k(1/2 − p)²)
числовая оценка, хороша с 3/4      медиана                               ≤ e^(−k/8)
оценка слабее 3/4                  среднее t штук, потом медиана средних

большинство, точный счёт:    k = 1      3        5        11       21
p = 0,1                      0,1    0,028    0,0086   0,0003   10⁻⁶
p = 0,25                     0,25   0,156    0,104    0,034    0,006
p = 0,4                      0,4    0,352    0,317    0,247    0,174

От ожидаемого времени к пределу времени. Алгоритм верен всегда и работает в среднем T. Обрываем на 2T: не успел с вероятностью не больше 1/2. Перезапускаем k раз: неудача не чаще 1/2ᵏ, время не больше 2Tk.

Оценка объединения с «высокой вероятностью». Каждая из n операций неудачна с вероятностью 1/n² - хоть одна неудачна с вероятностью не больше 1/n.

Азима: для скачков |ΔMᵢ|≤cᵢ двухсторонний хвост не больше 2 exp(-t²/(2Σcᵢ²)); независимые входы с влияниями dᵢ дают ограниченные разности 2 exp(-2t²/Σdᵢ²).

Локальная лемма: e·p·(d+1)≤1 гарантирует избегание событий при корректном графе зависимости. В независимой переменной модели Мозер-Тардош пересэмплирует все переменные выбранного нарушения.

Ловушки джокера

Прочитал оценку как прогноз. «Не больше 50%» у Маркова на деле было 1,25%. Оценка - потолок.

Применил Маркова к знакопеременной величине. Для −1000 и +1002 с равными шансами неравенство нарушено в пятьсот раз.

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

Усреднил зависимые замеры. Общая помеха не гасится: сто прогонов на одной перегруженной машине не точнее одного.

Взял выборку «1% от данных». Нужный размер не зависит от объёма данных: 18 445 наблюдений дают один пункт и на миллионе, и на миллиарде.

Посчитал pᵏ для двусторонней ошибки. Большинство из трёх при p = 1/4 - это 15,6%, а не 1,6%.

Усилил оценку средним. Десять оценок, девять около 100 и одна 5000: среднее 590, медиана около 100.

Повторил с тем же зерном. Одинаковые запуски повторяют одну и ту же ошибку.

Проверь себя

Почему Маркову нужна неотрицательность? Откуда в Чебышёве квадрат, а в Чернове экспонента? Почему размер выборки не зависит от размера совокупности? Когда трёх запусков достаточно, а когда нет? Что именно делает среднее и что - медиана в медиане средних?