§3. Показательный датчик без логарифмов: фокус фон Неймана

Формула из §1 $x = -\ln(1-y)$ хороша всем, кроме одного: в ней логарифм, а компьютер считает его не бесплатно. Фон Нейман придумал, как получить показательный закон вообще без логарифмов — одними сравнениями чисел. Звучит как развод, но работает железно.

Таблица и нисходящие серии

Представь таблицу независимых равномерных на $[0,1]$ чисел, читаем её по строкам:

В каждой строке смотрим, как долго числа идут на убыль с самого начала. Номер числа, которое первым оказалось больше предыдущего и оборвало спад, обозначим $K_i$:

Это ровно «нисходящая серия» из задачи 2 главы 2, где мы получили $\mathbf{M}K = e$. Теперь назовём строку успехом, если $K_i$ чётное, и неудачей, если нечётное.

Рецепт

Утверждение 2. Пусть $\nu$ — число неудач до первого успеха. Тогда величина $\nu + \eta_{(\nu+1)1}$ — число неудачных строк плюс первое число успешной строки — распределена по показательному закону с параметром $\lambda = 1$.

То есть алгоритм совсем детский:

1. Тянешь строку: первое число запоминаешь, дальше тянешь числа, пока они убывают.
2. Спад оборвался на чётном номере — успех: ответ равен «сколько было неудач» плюс «первое число этой строки».
3. Оборвался на нечётном — неудача: счётчик неудач +1, тянешь новую строку.

Ни одного логарифма, только сравнения «больше-меньше». Целую часть ответа даёт счётчик неудач, дробную — первое число строки.

Почему это работает

Разберём по кирпичикам. Сначала поймём, с какой вероятностью серия держится долго и при этом первое число не больше $y$:

Почему так: все $n$ чисел должны попасть на отрезок $[0, y]$ (шанс $y^n$) и встать строго по убыванию — а из $n!$ равновероятных порядков нужный ровно один. Отсюда вероятность, что серия оборвалась ровно на $n$-м числе:

Складываем по чётным $n = 2, 4, 6, \dots$ — получается знакопеременный ряд, который сворачивается в знакомую экспоненту:

При $y = 1$ это вероятность успеха: $p = 1 - e^{-1} \approx 0{,}632$, а неудачи — $q = e^{-1} \approx 0{,}368$. Строки независимы, поэтому

А теперь финальный аккорд — свойство самого показательного закона. Возьмём $\tau \sim \text{Exp}(1)$ и разрежем на целую часть $[\tau]$ и дробную $\{\tau\}$. Оказывается (это утверждение 3, его проверим в задачах), они независимы: целая часть распределена геометрически, $\mathbf{P}([\tau] = i) = q^i p$, а дробная имеет функцию распределения $\frac1p(1 - e^{-x})$ на $[0,1]$. Значит

— ровно то же, что у нашей пары «число неудач» и «первое число успешной строки». Совпали законы целой и дробной частей, значит совпали и суммы: $\nu + \eta_{(\nu+1)1}$ распределено как $\tau$. Вот и весь фокус.

По-дворовому: счётчик неудач — это «сколько целых часов прождал», а первое число удачной строки — «сколько ещё минут сверху». Склеил — получил честное время ожидания по показательному закону.

Покрути виджет: гистограмма датчика ложится на $e^{-x}$, а счётчик внизу показывает, что логарифмов ноль, а равномерных уходит около $4{,}3$ на каждое число.

Откуда $4{,}3$: в строке в среднем $\mathbf{M}K = e \approx 2{,}72$ числа, а строк на один успех уходит в среднем $1/p \approx 1{,}58$. Перемножаем: $2{,}72 \cdot 1{,}58 \approx 4{,}30$.

Код датчика целиком:

Цена фокуса — чисел тратится больше (около 4,3 вместо одного у обратной функции). Выгоден он там, где логарифм дорог, а равномерные числа дешёвые. В следующем параграфе — другой подход: логарифм оставить, но считать его один раз на целую пачку чисел.

Проверь себя