Неравенство Йенсена: цена среднего и средняя цена

Если проверяешь выпуклость и направление знака до подстановки среднего, листай до «Теперь сам».

Как думаешь, сколько стоит средний запрос

Половина пакетов имеет размер два, половина восемь. Средний размер пять. Если обработка пакета размера x стоит x², цена среднего размера равна 25, а средняя цена - 34. Программа, рассчитывающая мощность сервера по квадрату среднего размера, систематически недооценивает работу. Причина в нелинейности, а не в плохом измерении среднего.

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

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

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

Функция выпукла, если f(t·a+(1-t)·b) ≤ t·f(a)+(1-t)·f(b) при 0≤t≤1. Если случайная величина принимает a с вероятностью t, а b с вероятностью 1-t, слева стоит функция ожидания, справа ожидание функции. Для конечного числа исходов применяем то же рассуждение последовательно, объединяя группы с их вероятностями. Для общего распределения нужны условия существования соответствующих ожиданий.

Производная не входит в определение. Если функция дважды дифференцируема на интервале, достаточная проверка выпуклости - неотрицательная вторая производная на всём интервале. У x² она равна двум. У log x на положительных числах вторая производная отрицательна, поэтому логарифм вогнут и знак противоположен.

Дисперсия - ожидаемый квадрат отклонения от среднего; обозначается Var(X). Для квадрата есть более точное равенство: E[X²]=(E[X])²+Var(X). Дисперсия неотрицательна, отсюда сразу следует нужная граница. Но для произвольной выпуклой функции нельзя просто дописать дисперсию: добавка зависит от самой функции и распределения.

Правило

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

Разбор: две нагрузки с одним средним

from fractions import Fraction
from math import log, sqrt


def expectation(values, probabilities, f):
    return sum(p * f(x) for x, p in zip(values, probabilities))


def report(values, probabilities):
    mean = expectation(values, probabilities, lambda x: x)
    mean_square = expectation(values, probabilities, lambda x: x*x)
    variance = mean_square - mean*mean
    assert variance >= 0
    print("Среднее:", mean)
    print("Квадрат среднего:", mean * mean)
    print("Средний квадрат:", mean_square)
    print("Дисперсия:", variance)


half = Fraction(1, 2)
report([5], [Fraction(1)])
report([2, 8], [half, half])
print("Логарифм среднего:", f"{log(5):.6f}")
print("Средний логарифм:", f"{(log(2)+log(8))/2:.6f}")
for loads in ([2, 2, 2], [0, 2, 4], [0, 0, 6]):
    total = sum(x*x for x in loads)
    lower = Fraction(sum(loads) ** 2, len(loads))
    assert total >= lower
    print(list(loads), total, lower)
print("Корень среднего:", f"{sqrt(5):.6f}")
print("Средний корень:", (sqrt(1) + sqrt(9)) / 2)

Среднее: 5
Квадрат среднего: 25
Средний квадрат: 25
Дисперсия: 0
Среднее: 5
Квадрат среднего: 25
Средний квадрат: 34
Дисперсия: 9
Логарифм среднего: 1.609438
Средний логарифм: 1.386294
[2, 2, 2] 12 12
[0, 2, 4] 20 12
[0, 0, 6] 36 12
Корень среднего: 2.236068
Средний корень: 2.0

Оба первых распределения имеют среднее пять. В постоянном случае квадратичная цена 25, при разбросе - 34. Код использует рациональные числа, поэтому различие не вызвано округлением. Последние строки показывают противоположное направление для логарифма: его значение на среднем больше среднего логарифмов.

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

Разбор: балансировка по корзинам

Пусть m элементов распределены по n корзинам с загрузками xᵢ. Выбери равновероятно одну корзину. Её средняя загрузка m/n, поэтому Σ xᵢ² ≥ m²/n. Это детерминированная граница для любой раскладки: случайность введена лишь как способ усреднить фиксированный набор чисел. Если стоимость обработки корзины квадратична, выравнивание загрузок минимизирует суммарную цену, насколько позволяют целочисленные значения.

При целочисленной нагрузке равенство достигается только если все загрузки одинаковы, что возможно, когда m делится на n. Иначе минимум дают размеры, отличающиеся на единицу. Йенсен по-прежнему верен, просто граница может быть не точной для целого ответа.

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

Нельзя переставлять ожидание и нелинейную функцию как равенство. Нельзя также говорить «Йенсен всегда увеличивает»: у логарифма знак обратный. И условие выпуклости нельзя вывести из одного красивого графика на коротком отрезке, если случайная величина принимает значения за его пределами.

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

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

Теперь сам

Величина принимает 1 и 9 с вероятностью половина. Сравни E[X²] и (E[X])². Что изменится для sqrt(X)?