§4. Быстрый показательный датчик: один логарифм на всю пачку

Компьютер считает $\ln x$ через разложение в ряд, и для приличной точности это около 20 арифметических операций. В серьёзных моделях — скажем, надёжность системы, где детали ломаются и чинятся в случайные моменты, — показательный датчик дёргают миллионы раз, глубоко внутри расчёта. Каждая сэкономленная операция там окупается. Идея этого параграфа: один логарифм на $n$ чисел вместо $n$ логарифмов.

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

Гамма-распределение

Величина $T$ имеет гамма-распределение с параметрами $\alpha > 0$ и $\lambda > 0$ (пишут $T \sim \Gamma(\alpha, \lambda)$), если её плотность

Тут $\Gamma(\alpha)$ — та самая гамма-функция Эйлера из главы 3 (обобщение факториала, $\Gamma(n) = (n-1)!$). Знакомый показательный закон — это частный случай при $\alpha = 1$. Моменты считаются в одну строку:

Лемма 1. Если $T_1 \sim \Gamma(\alpha_1, \lambda)$ и $T_2 \sim \Gamma(\alpha_2, \lambda)$ независимы, то $T_1 + T_2 \sim \Gamma(\alpha_1 + \alpha_2, \lambda)$.

Параметры $\alpha$ просто складываются. Главное следствие для нас: сумма $n$ независимых показательных величин $\tau_1 + \dots + \tau_n$ имеет закон $\Gamma(n, \lambda)$. По-дворовому: если ждать $n$ маршруток подряд, и каждую ждёшь показательное время, то общее время ожидания — гамма с $\alpha = n$.

Порядковые статистики

Расставим значения выборки $(\xi_1, \dots, \xi_n)$ по возрастанию: $\xi_{(1)} \le \xi_{(2)} \le \dots \le \xi_{(n)}$. Этот набор называют вариационным рядом, а сами $\xi_{(k)}$ — порядковыми статистиками. Крайние ты уже знаешь: $\xi_{(1)}$ — минимум, $\xi_{(n)}$ — максимум из §2.

Лемма 2. Если $\eta_1, \dots, \eta_n$ независимы и равномерны на $[0,1]$, то плотность вектора порядковых статистик $(\eta_{(1)}, \dots, \eta_{(n)})$ равна $n!$ на множестве $\{0 < x_1 < \dots < x_n < 1\}$ и нулю вне его.

Смысл: упорядоченные равномерные точки равномерно размазаны по «упорядоченной» части куба, а $n!$ берётся потому, что все $n!$ порядков исходных чисел равновероятны и схлопываются в один.

Расстояния между соседними точками, $\Delta_i = \eta_{(i)} - \eta_{(i-1)}$ (с краями $\eta_{(0)} = 0$, $\eta_{(n+1)} = 1$), называют равномерными спейсингами — это как случайно нарезать палку длины 1 на куски.

Лемма 3. Пусть $\tau_1, \dots, \tau_n$ — выборка из показательного закона и $S_i = \tau_1 + \dots + \tau_i$. Тогда вектор $(S_1/S_n, \dots, S_{n-1}/S_n)$ распределён так же, как порядковые статистики $n-1$ равномерного числа на $[0,1]$.

Вот это и есть ключ. Если отметить моменты прихода маршруток $S_1, S_2, \dots$ и поделить их на общее время $S_n$, то относительные моменты окажутся просто упорядоченными равномерными точками. И наоборот: случайно нарезал общее время равномерными разрезами — получил честные показательные интервалы.

Теорема о быстром датчике

Теорема 2. Пусть $\eta_1, \dots, \eta_{2n-1}$ независимы и равномерны на $[0,1]$; $\xi_1 < \dots < \xi_{n-1}$ — упорядоченные по возрастанию числа $\eta_{n+1}, \dots, \eta_{2n-1}$; $\xi_0 = 0$, $\xi_n = 1$. Тогда

$$\tau'_i = -\frac{1}{\lambda}\,(\xi_i - \xi_{i-1})\,\ln(\eta_1 \eta_2 \cdots \eta_n), \qquad i = 1, \dots, n,$$

— выборка из показательного закона с параметром $\lambda$.

Разберём по кирпичикам, что тут происходит:

• $-\tfrac1\lambda \ln(\eta_1 \cdots \eta_n) = \sum_{i=1}^n \bigl(-\tfrac1\lambda \ln \eta_i\bigr)$ — это сумма $n$ показательных чисел (каждое слагаемое — метод обратной функции), то есть общее время по закону $\Gamma(n, \lambda)$. Произведение равномерных и один логарифм вместо $n$.
• $\xi_1 < \dots < \xi_{n-1}$ — $n - 1$ равномерных разрезов, упорядоченных по возрастанию.
• $\xi_i - \xi_{i-1}$ — длины кусков, на которые разрезы режут отрезок $[0,1]$.
• Умножаем длины кусков на общее время — получаем $n$ интервалов. По лемме 3 это и есть независимые показательные числа.

Например, при $n = 2$:

По-дворовому: общак сначала посчитали одной суммой (один логарифм), а потом поделили случайными разрезами. Доли получились честные — как если бы каждый считал своё отдельно.

Где экономия и где подвох

Экономия: на $n$ показательных чисел уходит один логарифм. Подвох: равномерных нужно $2n - 1$ вместо $n$, а ещё $n - 1$ разрезов надо отсортировать. Чем больше $n$, тем дороже сортировка. Расчёты на компьютерах показали, что оптимум — около $n = 3$, и такой датчик работает примерно вдвое быстрее метода обратной функции.

Покрути виджет: при $n = 1$ это обычный метод обратной функции, при больших $n$ гистограмма остаётся на месте, а логарифмов на одно число становится $1/n$.

Проверим в коде, что числа действительно показательные: среднее должно быть $1/\lambda$, дисперсия $1/\lambda^2$. Заодно посчитаем, сколько логарифмов ушло.

В питоне выигрыша по скорости не увидишь — там логарифм вызывается из быстрой C-библиотеки и стоит копейки. Экономия ощутима в низкоуровневом коде, где каждая операция на счету.

Проверь себя