Матожидание и линейность: среднее, которое складывается всегда

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

Как думаешь, чему равно среднее наименьшего из двух кубиков

Бросают два кубика и записывают два числа: меньшее из выпавших и большее. Среднее значение одного кубика - 3,5.

Попробуй угадать до чтения: среднее меньшего числа и среднее большего. И второй вопрос, на который можно ответить, не зная первых двух: чему равна сумма этих средних? Ответы - примерно 2,53 и 4,47, а сумма ровно 7. Первые два числа требуют счёта, третье получается в уме, и причина этого - главный инструмент всего раздела.

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

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

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

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

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

Распределение величины - таблица «значение и его вероятность». Для одного кубика: каждое из чисел от 1 до 6 с вероятностью 1/6.

Математическое ожидание, или матожидание, E[X] - сумма значений, умноженных на свои вероятности:

E[X] = x₁ · P(X = x₁) + x₂ · P(X = x₂) + …

кубик:  1·1/6 + 2·1/6 + 3·1/6 + 4·1/6 + 5·1/6 + 6·1/6 = 21/6 = 3,5

Почему умножение на вероятность: при N повторах значение x встретится примерно N · P(X = x) раз. Сумма всех выпавших чисел - около N · (x₁P₁ + x₂P₂ + …), а среднее арифметическое получается делением на N. Вероятности здесь - доли, с которыми значения входят в длинный ряд наблюдений.

То же ожидание можно считать не по значениям, а по исходам: пройти по всем карточкам в коробке и сложить число на карточке, умноженное на её вероятность. Из этой записи линейность видна сразу. Пусть на каждой карточке записаны два числа, X и Y:

E[X + Y] = сумма по исходам (X + Y) · P(исход)
         = сумма по исходам X · P(исход)  +  сумма по исходам Y · P(исход)
         = E[X] + E[Y]

Вторая строка - обычная перегруппировка слагаемых. Нигде не понадобилось знать, как X и Y связаны: они сидят на одной карточке, и сумму по карточкам можно собирать в любом порядке.

С произведением перегруппировка не проходит: X · Y на карточке не раскладывается в отдельные суммы. Равенство E[XY] = E[X] · E[Y] верно для независимых величин - тех, у которых значение одной не меняет распределения другой, - а для зависимых обычно нарушается.

Правило

Матожидание - сумма значений величины с весами-вероятностями: E[X] = Σ x · P(X = x), где знак Σ означает сумму по всем значениям x, которые величина может принять. Линейность: E[X + Y] = E[X] + E[Y] и E[c · X] = c · E[X] для любых величин, зависимых или нет, и для любого числа слагаемых. E[X · Y] = E[X] · E[Y] гарантировано только для независимых. Ожидание - не «самое вероятное значение»: оно может вообще не встречаться среди значений.

Разбор: наименьшее и наибольшее из двух кубиков

Перебор 36 исходов: сумма наименьших, сумма наибольших и сумма произведений.

summa_min = 0
summa_max = 0
summa_proizv = 0
for a in range(1, 7):
    for b in range(1, 7):
        summa_min = summa_min + min(a, b)
        summa_max = summa_max + max(a, b)
        summa_proizv = summa_proizv + min(a, b) * max(a, b)
print(summa_min, summa_max, summa_min + summa_max)
print(round(summa_min / 36, 4), round(summa_max / 36, 4), (summa_min + summa_max) / 36)
print(round(summa_proizv / 36, 4), round(summa_min / 36 * summa_max / 36, 4))

91 161 252
2.5278 4.4722 7.0
12.25 11.3048

E[min] = 91/36 ≈ 2,53, E[max] = 161/36 ≈ 4,47. Сумма ровно 7: наименьшее плюс наибольшее - это просто сумма двух кубиков, а её ожидание по линейности 3,5 + 3,5. Считать распределение суммы, в котором 11 значений с разными вероятностями, не пришлось.

Третья строка - про произведение. Наименьшее, умноженное на наибольшее, равно произведению двух кубиков, а они независимы, так что его ожидание 3,5 · 3,5 = 12,25. Произведение же ожиданий 2,53 · 4,47 = 11,30. Не совпало: наименьшее и наибольшее зависимы. Если наименьшее равно шести, наибольшее обязано быть шестью.

Разбор: ожидание - не прогноз одного броска

Среднее арифметическое в серии из N бросков одного кубика; для каждого N серия начинается заново:

import random

random.seed(7)
for broskov in [10, 100, 1000, 10000]:
    summa = 0
    for i in range(broskov):
        summa = summa + random.randint(1, 6)
    print(broskov, round(summa / broskov, 3))

10 3.1
100 3.38
1000 3.429
10000 3.482

Среднее подходит к 3,5 медленно: в серии из тысячи бросков отклонение ещё 0,07. А в одном броске 3,5 не выпадает никогда. Ожидание описывает сумму многих повторов и ничего не обещает одному.

Граница понятия видна на лотерее. Билет стоит 100 рублей, с вероятностью одна миллионная выигрывает 50 миллионов. Ожидаемый выигрыш 50 000 000 / 1 000 000 = 50 рублей, ожидаемый итог - минус 50. Но ни один покупатель не получит минус 50: почти все получат минус 100, один - плюс 49 999 900. Когда величина почти всегда мала и изредка огромна, ожидание честно усредняет и плохо описывает то, что увидит отдельный человек. У алгоритмов так бывает со временем работы, и поэтому одного ожидания мало: в следующей главе к нему добавится оценка того, как далеко от ожидания уходят значения.

Ещё одно следствие определения - ожидаемая цена поиска. Линейный поиск в списке из n элементов, искомый стоит на случайном месте, все места равновозможны. Число сравнений - место элемента, каждое значение от 1 до n с вероятностью 1/n:

E = 1·1/n + 2·1/n + … + n·1/n = (1 + 2 + … + n) / n = (n + 1) / 2

Для тысячи элементов 500,5 сравнения. Это «в среднем по входам»: оценка верна, пока места и правда равновозможны.

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

Ожидание как гарантия. «В среднем запрос занимает 20 мс» не мешает одному из ста занимать две секунды. Среднее время и время, в которое укладываются 99% запросов, - разные числа, и по первому второе не восстановить.

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

Ожидание функции вместо функции от ожидания. E[X²] не равно E[X]². Для кубика E[X²] = (1 + 4 + 9 + 16 + 25 + 36) / 6 = 15,17, а 3,5² = 12,25. Алгоритм, который тратит X² шагов на вход размера X, в среднем стоит E[X²], и подставить средний размер в формулу - занизить цену.

Среднее по неверному распределению. (n + 1) / 2 для линейного поиска получено при равновозможных местах. Если ищут чаще то, что лежит в конце, ожидание другое. Формула ожидания всегда содержит предположение о вероятностях, и проверять надо его.

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

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

Так получены оценки, уже встречавшиеся в курсе: ожидаемая длина цепочки в хеш-таблице, ожидаемое число коллизий n² / 2m в парадоксе дней рождения, ожидаемое время быстрого выбора. Там они были приняты коротким рассуждением; следующий урок показывает приём целиком.

Теперь сам

1. Величина принимает значение 0 с вероятностью 0,9 и значение 100 с вероятностью 0,1. Чему равно её ожидание и может ли она принять значение, равное ожиданию?
2. Бросают 10 кубиков. Чему равно ожидание суммы?
3. X - число на кубике, Y = 7 − X - число на противоположной грани. Чему равны E[X + Y] и E[X · Y]? Равно ли второе E[X] · E[Y]?
4. Запрос обслуживает быстрый сервер (10 мс) с вероятностью 0,8 и медленный (200 мс) с вероятностью 0,2. Чему равно ожидаемое время?
5. Искомый элемент с вероятностью 1/2 стоит на первом месте списка из 100 элементов, а иначе на любом из остальных 99 мест с равной вероятностью. Чему равно ожидаемое число сравнений линейного поиска?