Пуассоновское приближение: пустые ящики и максимальная нагрузка

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

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

Сто запросов независимо назначили ста обработчикам. Среднее ровно один запрос на обработчик. Но часть простаивает, а часть получает несколько. Зная только среднее, нельзя оценить самый занятый обработчик. Начнём с одного ящика, затем отдельно разберём событие «хотя бы где-то большая нагрузка».

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

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

Механизм: биномиальная формула превращается в пуассоновскую

Для одного ящика ровно k шаров выбираются C(m,k) способами. Вероятность выбранных попаданий равна (1/n)ᵏ, непопаданий остальных - (1-1/n)ᵐ⁻ᵏ. Получается точная биномиальная вероятность. При большом m,n и фиксированном отношении m/n=λ первое произведение стремится к λᵏ/k!, второе - к e⁻λ. Здесь k фиксировано при предельном переходе; использовать приближение для растущего хвоста без оценки ошибки нельзя.

Индикатор пустоты каждого ящика имеет ожидание (1-1/n)ᵐ. Складывая ожидания, получаем число пустых без предположения независимости индикаторов. Загрузки разных ящиков при фиксированном числе шаров связаны: если в одном больше, другим остаётся меньше.

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

Правило

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

Разбор: сколько обработчиков простаивает

from math import comb, exp, factorial, e


def binomial_probability(m, n, k):
    return comb(m, k) * (1 / n) ** k * (1 - 1 / n) ** (m - k)


def poisson_probability(lam, k):
    return exp(-lam) * lam ** k / factorial(k)


print("n: точное ожидание пустых; n/e")
for n in (10, 100, 1000):
    exact = n * (1 - 1 / n) ** n
    print(n, f"{exact:.4f}", f"{n / e:.4f}")
print("k: биномиальная; Пуассон, m=n=100")
for k in range(6):
    exact = binomial_probability(100, 100, k)
    approx = poisson_probability(1, k)
    print(k, f"{exact:.6f}", f"{approx:.6f}")
print("Пустая доля при lambda=2:", f"{exp(-2):.6f}")
print("Верхние границы максимума для n=1000")
for k in (4, 6, 8, 10):
    upper = min(1, 1000 * (e / k) ** k)
    print(k, f"{upper:.6f}")
assert binomial_probability(1, 2, 2) == 0
assert poisson_probability(0.5, 2) > 0
print("Малый вход: приближение допускает невозможный исход")

n: точное ожидание пустых; n/e
10 3.4868 3.6788
100 36.6032 36.7879
1000 367.6954 367.8794
k: биномиальная; Пуассон, m=n=100
0 0.366032 0.367879
1 0.369730 0.367879
2 0.184865 0.183940
3 0.060999 0.061313
4 0.014942 0.015328
5 0.002898 0.003066
Пустая доля при lambda=2: 0.135335
Верхние границы максимума для n=1000
4 1.000000
6 1.000000
8 0.177679
10 0.002203
Малый вход: приближение допускает невозможный исход

Сравнение показывает сближение точного ожидания с n/e при m=n. В программе также выведены первые вероятности при среднем один. Это расчёт формул, не случайный опыт: значения воспроизводятся без зерна генератора. Пустых ящиков ожидается заметная доля, хотя средняя загрузка равна единице.

Разбор: от выбранного ящика к максимуму

При m=n вероятность X≥k для одного ящика можно оценить сверху как (e/k)ᵏ для k≥1. Для максимума применяем объединение событий по n ящикам: вероятность не больше n·(e/k)ᵏ. Чтобы она стала мала, величина k·log k должна обогнать log n. Отсюда масштаб log n / log log n.

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

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

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

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

Хеш-таблица с независимым равномерным распределением ключей может иметь много пустых цепочек и несколько длинных при средней длине один. Ожидание пустых помогает оценить использование памяти, хвост - риск длинного поиска, максимум - худший бакет. Реальная хеш-функция должна обеспечивать нужные свойства распределения; формулы не исправляют плохую функцию.

Теперь сам

В тысячу ящиков бросили две тысячи шаров. Чему приближённо равна доля пустых? Можно ли назвать загрузки ящиков независимыми?