§3. Метод Неймана: оставляем только то, что под графиком

Метод обратной функции требует посчитать $F^{-1}$. А если плотность хитрая и функцию распределения даже не выписать? Для этого фон Нейман придумал приём, который работает почти всегда: кидать точки и отбраковывать лишние. Его называют методом исключения.

Рецепт

Пусть величина $\xi$ живёт на отрезке $[a, b]$, а её плотность ограничена: $p_\xi(x) \le C$. Обведём график плотности прямоугольником $[a,b] \times [0, C]$ и будем кидать в него точки равномерно:

Пусть $\nu$ — номер первой точки, попавшей под график: $\nu = \min\{i : Y_i \le p_\xi(X_i)\}$. Выдаём её абсциссу $X_\nu$.

Утверждение 4. Величина $X_\nu$ распределена так же, как $\xi$.

По-дворовому: насыпал семки в коробку наугад, а потом выкинул все, что легли выше нарисованной кривой. Оставшиеся лежат гуще там, где кривая выше, — ровно как требует плотность.

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

Шанс, что одна точка ляжет под график, — это доля площади под кривой в площади прямоугольника. Площадь под плотностью равна 1, поэтому

Теперь разложим по номеру первой удачной точки (формула полной вероятности). «Остановились на $n$-й и её абсцисса $\le x$» значит: первые $n - 1$ точек промахнулись, а $n$-я легла под график левее $x$. Точки независимы, поэтому

По кирпичикам: $q^{n-1}$ — шанс первых $n-1$ промахов; дробь — доля площади под графиком левее $x$, то есть $p \cdot F_\xi(x)$. Остаётся геометрическая прогрессия:

Цена: сколько бросков уходит

Каждая точка удачна с шансом $p = \frac{1}{C(b-a)}$, поэтому на одно число в среднем уходит $\frac1p = C(b-a)$ бросков — ровно площадь прямоугольника. Отсюда правило: прямоугольник должен облегать график как можно плотнее. Поставил $C$ вдвое выше максимума плотности — бросков стало вдвое больше, половина работы в отходы.

Покрути виджет. Сверху видно, какие броски приняты (красные, под графиком) и какие выброшены (серые). Снизу гистограмма принятых ложится на плотность. Подними $C$ и смотри, как растёт доля отходов.

Метод в коде, на косом бета-распределении $B(2, 5)$ с плотностью $30x(1-x)^4$:

Расслоённый вариант

Если плотность то высокая, то низкая, один общий прямоугольник выйдет «дырявым» и бросков уйдёт много. Тогда отрезок $[a,b]$ режут на кусочки $\Delta_k$, и над каждым ставят свой прямоугольник высотой $C_k = \max_{x \in \Delta_k} p_\xi(x)$ — получается ступенчатая «крыша», плотно облегающая график.

Это смесь из §2: плотность раскладывается как $p_\xi(x) = \sum_k p_k f_k(x)$, где $p_k = \int_{\Delta_k} p_\xi(x)\,dx$. Метод суперпозиции в два хода:

1. Разыграть номер кусочка $k_0$ с вероятностями $p_k$.
2. Методом Неймана кидать точки в прямоугольник $\Delta_{k_0} \times [0, C_{k_0}]$ до первого попадания под график.

В среднем бросков уйдёт $\sum_k C_k |\Delta_k|$ — площадь ступенчатой крыши. При мелком разбиении она стремится к площади под графиком, то есть к 1: почти без отходов.

Так можно моделировать даже величину с бесконечным носителем. Например, показательную плотность $e^{-x}$ раскладывают на куски $[k, k+1)$ с весами $q^k p$, где $q = e^{-1}$ — ровно утверждение 3 из главы 4 про целую и дробную части.

А датчик фон Неймана из §3 главы 4 — это тот же метод исключения, только точки кидают не в прямоугольник, а в бесконечномерный куб, и «попадание под график» заменено событием «нисходящая серия оборвалась на чётном месте». Объём этого множества как раз $p = 1 - e^{-1}$.

Проверь себя