Неравенство Маркова: что обещает одно только среднее

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

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

Алгоритм со случайным выбором внутри работает в среднем 100 мс. Больше о нём ничего не известно: ни разброса, ни худшего случая.

Ответь себе до чтения: может ли он в половине запусков работать секунду и дольше? А в каждом десятом? В половине - не может: тогда одно только это слагаемое дало бы среднее не меньше 500 мс. В каждом десятом - может, и ровно на границе: 0,1 · 1000 = 100, если остальные запуски мгновенны. Больше из среднего не выжать, но и это уже гарантия.

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

Средняя зарплата в компании - 100 тысяч. Может ли каждый пятый получать миллион? Нет: одна эта пятая часть сотрудников уже дала бы в среднем 200 тысяч на человека, даже если остальные работают бесплатно. Не больше десятой части может получать миллион, не больше сотой - десять миллионов.

Довод держится на одном: зарплата не бывает отрицательной. Если бы кто-то мог «получать» минус десять миллионов, им можно было бы уравновесить сколько угодно миллионеров.

Механизм: большие значения тянут среднее вверх

Пусть X - неотрицательная величина и a - положительное число. Сравним X с более простой величиной: она равна a, когда X ≥ a, и нулю в остальных случаях.

исход:            X < a          X ≥ a
X                 не меньше 0    не меньше a
простая величина  0              a

На каждом исходе X не меньше простой величины - слева потому, что X неотрицательна, справа по условию. Значит и ожидание X не меньше. А простая величина - это a, умноженное на индикатор события X ≥ a, и её ожидание равно a · P(X ≥ a):

E[X] ≥ a · P(X ≥ a)        откуда        P(X ≥ a) ≤ E[X] / a

Деление здесь означает то же, что в примере с зарплатой: сколько раз порог a помещается в среднее. Если подставить a = k · E[X], получится форма, удобная для разговора: превысить среднее в k раз можно не чаще чем в 1/k случаев.

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

Правило

Для неотрицательной случайной величины X и любого a > 0: P(X ≥ a) ≤ E[X] / a. В другой записи, при E[X] > 0: P(X ≥ k · E[X]) ≤ 1/k. Оценка работает только вверх и только для неотрицательных величин; без дополнительных сведений о величине её нельзя усилить.

Разбор: насколько оценка далека от правды

Сбор коллекции из 30 вариантов, ожидание 30 · H₃₀ ≈ 119,8 попытки. Четыреста опытов; считаем долю тех, что заняли не меньше полутора, двух и трёх ожиданий. Рядом - то, что обещает Марков.

import random

def sobrat(n):
    est = [False] * n
    raznyh = 0
    pokupok = 0
    while raznyh < n:
        k = random.randrange(n)
        pokupok = pokupok + 1
        if not est[k]:
            est[k] = True
            raznyh = raznyh + 1
    return pokupok

random.seed(30)
n = 30
ozhidanie = 0
for i in range(1, n + 1):
    ozhidanie = ozhidanie + n / i

opytov = 400
kratnosti = [1.5, 2, 3]
dolshe = [0, 0, 0]
for opyt in range(opytov):
    t = sobrat(n)
    for k in range(3):
        if t >= kratnosti[k] * ozhidanie:
            dolshe[k] = dolshe[k] + 1
print(round(ozhidanie, 1))
for k in range(3):
    print(kratnosti[k], round(1 / kratnosti[k], 3), dolshe[k] / opytov)

119.8
1.5 0.667 0.07
2 0.5 0.0125
3 0.333 0.0

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

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

Разбор: величина, на которой оценка точна, и величина, на которой она неверна

Самая неудобная величина выглядит так. С вероятностью 0,9 она равна нулю, с вероятностью 0,1 - десяти.

E[X] = 0 · 0,9 + 10 · 0,1 = 1
P(X ≥ 10) = 0,1          оценка Маркова: E[X] / 10 = 0,1

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

Теперь граница применимости. Величина равна −1000 с вероятностью 0,5 и +1002 с вероятностью 0,5.

E[X] = −500 + 501 = 1
P(X ≥ 1002) = 0,5        «оценка Маркова»: 1 / 1002 ≈ 0,001

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

Вторая граница - направление. Оценки «X редко бывает намного меньше среднего» из одного среднего не получить: величина может равняться нулю с вероятностью 0,999 и миллиону с вероятностью 0,001.

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

Оценку читают как прогноз. «Вероятность не больше 50%» не значит «около 50%». В разборе было 1,25%. Марков - потолок, который у настоящих величин почти никогда не достигается.

Оценку применяют к знакопеременной величине. Отклонение от среднего X − E[X] бывает отрицательным, и неравенство к нему не относится. Его применяют к квадрату отклонения, который неотрицателен, - так получается неравенство ЧебышёваРазбирается в разделе 20, глава «Хвостовые оценки - Марков, Чебышёв, Чернов»: Дисперсия и неравенство Чебышёва: разброс как второе число из следующего урока.

Из среднего времени выводят «почти всегда быстро». Среднее 100 мс совместимо с тем, что каждый десятый запуск длится секунду. Единственное, что среднее запрещает, - слишком частые большие значения.

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

Главное применение - превращение ожидаемого времени в гарантированное. Пусть алгоритм всегда отвечает верно, а работает в среднем T шагов. Запустим его с будильником на 2T шагов. По Маркову он не успеет с вероятностью не больше 1/2. Если не успел - запустим заново, с новыми случайными числами. Вероятность не успеть k раз подряд не больше 1/2ᵏ: десять попыток, 20T шагов - и неудача реже одной на тысячу. Так алгоритм, который может надолго задуматься, превращается в алгоритм с твёрдым пределом времени и малой вероятностью отказа; подробнее об этих двух видах - в следующей главе.

Второе применение уже встречалось. Для счётчика плохих событий порог a = 1 даёт P(X ≥ 1) ≤ E[X]: ожидаемое число коллизий 0,001 означает, что коллизия случится не чаще одного раза на тысячу. Это неравенство Маркова в самой ходовой форме.

Третье - чтение метрик. Если среднее время ответа 20 мс, то дольше двух секунд длится не более 1% запросов: время, в которое укладываются 99% запросов, не больше ста средних. Оценка слабая, но она следует из единственного числа, которое есть на любом графике.

Теперь сам

1. Среднее число сравнений алгоритма - 2000. Оцени сверху вероятность, что сравнений окажется не меньше 10 000.
2. Ожидаемое число запросов, упавших за час, - 0,02. Что можно сказать о вероятности хотя бы одного падения?
3. Алгоритм всегда верен и работает в среднем 3 секунды. Его обрывают через 6 секунд и перезапускают. Сколько попыток гарантируют неудачу реже одной на миллион?
4. Величина X - баланс счёта, он бывает отрицательным; E[X] = 100. Можно ли утверждать, что P(X ≥ 1000) ≤ 0,1?
5. Про неотрицательную величину известно E[X] = 5. Придумай распределение, для которого P(X ≥ 50) = 0,1 ровно.