Дисперсия и неравенство Чебышёва: разброс как второе число

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

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

Ты замеряешь время работы функции. Один замер шумит: то 95 мс, то 110, типичный промах - около 10 мс. Ты усредняешь 10 независимых замеров, и типичный промах среднего - уже около 3 мс.

Попробуй угадать до чтения: сколько замеров нужно, чтобы точность стала 0,3 мс, в десять раз лучше? Сто? Ответ - тысяча. Точность среднего улучшается как корень из числа замеров, и за каждый следующий знак приходится платить в сто раз больше.

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

Два стрелка, оба в среднем попадают в центр мишени. У первого пробоины лежат кучно, в кружке с монету. У второго разбросаны по всей мишени, просто промахи вправо уравновешены промахами влево. Среднее у них одинаковое, и оно ничего не говорит о том, куда попадёт следующий выстрел.

Нужно второе число - насколько далеко от центра в среднем ложатся пробоины. Причём расстояния надо как-то усреднить так, чтобы промах влево и промах вправо не погасили друг друга.

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

Пусть μ = E[X]. Отклонение X − μ в среднем равно нулю: плюсы гасят минусы. Чтобы не гасили, его возводят в квадрат.

Дисперсия - ожидание квадрата отклонения: Var[X] = E[(X − μ)²]. Если раскрыть квадрат, получится удобная для счёта запись: E[X² − 2μX + μ²] = E[X²] − 2μ · μ + μ² = E[X²] − μ². Стандартное отклонение σ - корень из дисперсии. Корень нужен, чтобы вернуться к исходным единицам: если X измеряется в миллисекундах, дисперсия - в квадратных миллисекундах, а σ снова в миллисекундах.

Почему квадрат, а не модуль. Модуль тоже неотрицателен, но у квадрата есть свойство, которого у модуля нет: для независимых величин дисперсия суммы равна сумме дисперсий. Раскроем скобки для двух величин со средними, равными нулю:

E[(X + Y)²] = E[X²] + 2 · E[X · Y] + E[Y²]
                       └── для независимых E[X · Y] = E[X] · E[Y] = 0
            = Var[X] + Var[Y]

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

Отсюда закон корня. Сумма n независимых одинаковых величин имеет среднее n · μ и дисперсию n · σ², то есть стандартное отклонение σ · √n. Среднее растёт как n, разброс как √n: относительный разброс σ√n / (nμ) при μ ≠ 0 убывает как 1/√n. Для среднего арифметического n замеров то же самое: его стандартное отклонение σ / √n.

Теперь оценка хвоста. Величина (X − μ)² неотрицательна, и к ней применимо неравенство Маркова с порогом a²:

P(|X − μ| ≥ a) = P((X − μ)² ≥ a²) ≤ E[(X − μ)²] / a² = Var[X] / a²

Это неравенство Чебышёва. Оно сильнее Маркова, потому что знает больше: не только среднее, но и разброс. И, в отличие от Маркова, работает в обе стороны от среднего.

Правило

Var[X] = E[(X − μ)²] = E[X²] − μ², σ = √Var[X]. Для независимых величин Var[X + Y] = Var[X] + Var[Y]; у индикатора события с вероятностью p дисперсия p(1 − p). Неравенство Чебышёва: P(|X − μ| ≥ a) ≤ Var[X] / a², или P(|X − μ| ≥ k · σ) ≤ 1/k². Среднее n независимых замеров имеет стандартное отклонение σ / √n.

Разбор: дисперсия кубика и суммы ста кубиков

srednee = 0
for x in range(1, 7):
    srednee = srednee + x / 6

dispersiya = 0
for x in range(1, 7):
    dispersiya = dispersiya + (x - srednee) ** 2 / 6
print(srednee, round(dispersiya, 4), round(dispersiya ** 0.5, 3))

n = 100
print(n * srednee, round(n * dispersiya, 1), round((n * dispersiya) ** 0.5, 2))

3.5 2.9167 1.708
350.0 291.7 17.08

У одного кубика среднее 3,5 и стандартное отклонение 1,7 - почти половина среднего. У суммы ста кубиков среднее 350, а стандартное отклонение 17: меньше 5% от среднего. Кубиков стало в сто раз больше, разброс вырос в десять раз.

Чебышёв для суммы ста кубиков: отклониться от 350 на 52 и больше (это чуть больше трёх σ) можно с вероятностью не больше 1/9. Поэтому сумма лежит строго между 298 и 402 с вероятностью не меньше 8/9, хотя возможные значения идут от 100 до 600.

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

Число орлов в тысяче бросков - сумма тысячи индикаторов с p = 1/2. Дисперсия каждого 1/4, суммы - 250, σ ≈ 15,8. Три тысячи серий по тысяче бросков; чтобы уложиться в шаги, броски делаются пачками: random.getrandbits(50) возвращает число из 50 случайных битов, а bit_count() считает в нём единицы - это 50 бросков монеты одной командой.

import random

random.seed(22)
opytov = 3000
porogi = [16, 32, 48, 64]
dalshe = [0, 0, 0, 0]
for opyt in range(opytov):
    orlov = 0
    for pachka in range(20):
        orlov = orlov + random.getrandbits(50).bit_count()
    otklonenie = abs(orlov - 500)
    for i in range(4):
        if otklonenie >= porogi[i]:
            dalshe[i] = dalshe[i] + 1

for i in range(4):
    t = porogi[i]
    print(t, round(250 / t ** 2, 4), round(dalshe[i] / opytov, 4))

16 0.9766 0.329
32 0.2441 0.047
48 0.1085 0.0037
64 0.061 0.0003

Столбцы: отклонение, оценка Чебышёва 250 / t², доля серий в опыте. Пороги выбраны около одного, двух, трёх и четырёх σ. Оценка верна во всех строках и при этом завышена: для четырёх σ она обещает «не чаще 6,104%», а случилось это в одной серии из трёх тысяч. Доля в опыте не равна точной вероятности: для редкого события 3000 серий дают слишком мало наблюдений.

Посчитаем точную вероятность отдельно в CPython. Из 2¹⁰⁰⁰ равновероятных последовательностей ровно comb(1000, j) содержат j орлов: выбираем позиции орлов. Событие |X − 500| ≥ 64 состоит из двух симметричных хвостов: X ≤ 436 и X ≥ 564. Достаточно сложить левый и удвоить:

from math import comb

hvost = 2 * sum(comb(1000, j) for j in range(437)) / 2 ** 1000
print(f"Чебышёв, %: {100 * 250 / 64 ** 2:.5f}")
print(f"Точно, %: {100 * hvost:.5f}")

Чебышёв, %: 6.10352
Точно, %: 0.00579

Чебышёв убывает как 1/t², а хвост этого распределения - гораздо быстрее. Следующий урок даёт оценку, которая это видит.

Теперь граница. Всё сказанное про √n требует независимости. Пусть вместо ста разных кубиков бросают один и умножают выпавшее число на сто. Среднее то же, 350. Но слагаемые теперь полностью зависимы, и стандартное отклонение равно 100 · 1,708 = 170,8 - в десять раз больше, чем у ста независимых. Ничего не усреднилось.

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

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

Складывают стандартные отклонения. У двух независимых величин с σ = 3 и σ = 4 сумма имеет σ = 5, а не 7: складываются квадраты, 9 + 16 = 25.

Ждут точности, пропорциональной числу замеров. Удвоение числа замеров уменьшает разброс среднего в 1,41 раза, а не вдвое.

Применяют закон корня к зависимым слагаемым. Запросы одного пользователя, замеры на одной машине, отказы дисков одной партии - у таких сумм разброс обычно больше, чем σ√n, и усреднение помогает меньше.

Сравнивают два средних без разброса. «Новая версия быстрее: 98 мс против 100» ничего не значит, пока неизвестно, что стандартное отклонение среднего меньше этих двух миллисекунд.

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

Замеры производительности. Чтобы различить 1% разницы при шуме одного замера в 5%, стандартное отклонение среднего должно быть заметно меньше 1%: 5% / √n < 0,5% даёт n > 100. Отсюда берутся «прогони сто раз», и отсюда же видно, что для различия в 0,1% прогонов нужно десять тысяч.

Планирование ёмкости. Нагрузка от N независимых пользователей имеет относительный разброс порядка 1/√N. Сервису на сто пользователей нужен запас в десятки процентов, сервису на миллион - в доли процента, пока пользователи действуют независимо. Распродажа или рассылка делает их зависимыми, и запас, посчитанный по корню, перестаёт спасать.

Вероятностные структуры данных. Оценка частоты в структуре count-minРазбирается в разделе 20, глава «Фильтр Блума, count-min, HyperLogLog»: Count-min: частоты миллиона ключей в таблице фиксированного размера и оценка числа различных элементов получаются как случайные величины с известным средним и дисперсией, а их точность доказывается неравенствами этой главы. Для сложения дисперсий там достаточно, чтобы величины были независимы попарно, - это требование к хеш-функциям заметно слабее полной независимости.

Теперь сам

1. Величина равна 0 с вероятностью 0,9 и 10 с вероятностью 0,1. Найди её среднее, дисперсию и σ.
2. Чему равно стандартное отклонение числа орлов в 400 бросках монеты?
3. По неравенству Чебышёва оцени вероятность того, что в 400 бросках число орлов отличается от 200 не меньше чем на 40.
4. Один замер имеет σ = 8 мс. Сколько независимых замеров нужно усреднить, чтобы σ среднего стала 1 мс?
5. Две независимые величины имеют дисперсии 16 и 9. Чему равно стандартное отклонение их суммы?