Обратное преобразование выборки

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

Выборка с обратным преобразованием (также известная как инверсионная выборка , обратное интегральное преобразование вероятности , метод обратного преобразования или преобразование Смирнова ) — это базовый метод выборки псевдослучайных чисел , т. е. генерации случайных чисел выборки из любого распределения вероятностей с учетом его кумулятивной функции распределения .

Выборка обратного преобразования берет равномерные выборки числа от 0 до 1, интерпретируемые как вероятность, а затем возвращает наименьшее число, такое что для кумулятивной функции распределения случайной величины. Например, представьте, что это стандартное нормальное распределение со средним значением ноль и стандартным отклонением единица. В таблице ниже показаны выборки, взятые из равномерного распределения, и их представление в стандартном нормальном распределении. ${\displaystyle u}$ ${\displaystyle x\in \mathbb {R} }$ ${\displaystyle F(x)\geq u}$ ${\displaystyle F}$ ${\displaystyle F}$

Выборка обратного преобразования для нормального распределения

Мы случайным образом выбираем долю площади под кривой и возвращаем число в домене таким образом, что именно эта доля площади находится слева от этого числа. Интуитивно, мы вряд ли выберем число в дальнем конце хвостов, потому что в них очень мало площади, которая потребовала бы выбора числа, очень близкого к нулю или единице.

С вычислительной точки зрения этот метод включает вычисление квантильной функции распределения — другими словами, вычисление кумулятивной функции распределения (CDF) распределения (которая отображает число в области в вероятность между 0 и 1) и затем инвертирование этой функции. Это является источником термина «обратная» или «инверсия» в большинстве названий этого метода. Обратите внимание, что для дискретного распределения вычисление CDF в общем случае не слишком сложно: мы просто складываем отдельные вероятности для различных точек распределения. Однако для непрерывного распределения нам необходимо интегрировать функцию плотности вероятности (PDF) распределения, что невозможно сделать аналитически для большинства распределений (включая нормальное распределение ). В результате этот метод может быть вычислительно неэффективным для многих распределений, и предпочтительны другие методы; однако это полезный метод для построения более общеприменимых выборок, таких как те, которые основаны на выборке с отклонением .

Для нормального распределения отсутствие аналитического выражения для соответствующей функции квантиля означает, что другие методы (например, преобразование Бокса–Мюллера ) могут быть предпочтительнее с точки зрения вычислений. Часто бывает так, что даже для простых распределений метод выборки обратного преобразования может быть улучшен: ^[1] см., например, алгоритм зиккурата и выборка отклонения . С другой стороны, можно аппроксимировать функцию квантиля нормального распределения чрезвычайно точно, используя полиномы умеренной степени, и на самом деле метод, позволяющий это сделать, достаточно быстр, чтобы выборка инверсии теперь стала методом по умолчанию для выборки из нормального распределения в статистическом пакете R. [ ^2]

Официальное заявление

Для любой случайной величины случайная величина имеет такое же распределение , как и , где — обобщенная обратная функция кумулятивного распределения и является равномерной на . ^[3] ${\displaystyle X\in \mathbb {R} }$ ${\displaystyle F_{X}^{-1}(U)}$ ${\displaystyle X}$ ${\displaystyle F_{X}^{-1}}$ ${\displaystyle F_{X}}$ ${\displaystyle X}$ ${\displaystyle U}$ ${\displaystyle [0,1]}$

Для непрерывных случайных величин обратное вероятностное интегральное преобразование действительно является обратным вероятностному интегральному преобразованию , которое утверждает , что для непрерывной случайной величины с кумулятивной функцией распределения случайная величина равномерна на . ${\displaystyle X}$ ${\displaystyle F_{X}}$ ${\displaystyle U=F_{X}(X)}$ ${\displaystyle [0,1]}$

График метода инверсии от до . Справа внизу мы видим регулярную функцию, а слева вверху — ее инверсию. ${\displaystyle x}$ ${\displaystyle F(x)}$

Интуиция

Из мы хотим сгенерировать с помощью CDF Мы предполагаем , что будет непрерывной, строго возрастающей функцией, что обеспечивает хорошую интуицию. ${\displaystyle U\sim \mathrm {Unif} [0,1]}$ ${\displaystyle X}$ ${\displaystyle F_{X}(x).}$ ${\displaystyle F_{X}(x)}$

Мы хотим посмотреть, сможем ли мы найти какое-то строго монотонное преобразование , такое, что . Мы будем иметь ${\displaystyle T:[0,1]\mapsto \mathbb {R} }$ ${\displaystyle T(U){\overset {d}{=}}X}$

${\displaystyle F_{X}(x)=\Pr(X\leq x)=\Pr(T(U)\leq x)=\Pr(U\leq T^{-1}(x))=T^{-1}(x),{\text{ for }}x\in \mathbb {R} ,}$

где последний шаг использовал то, что когда является равномерным на . ${\displaystyle \Pr(U\leq y)=y}$ ${\displaystyle U}$ ${\displaystyle [0,1]}$

Итак, мы должны быть обратной функцией , или, что то же самое ${\displaystyle F_{X}}$ ${\displaystyle T}$ ${\displaystyle T(u)=F_{X}^{-1}(u),u\in [0,1].}$

Таким образом, мы можем генерировать из ${\displaystyle X}$ ${\displaystyle F_{X}^{-1}(U).}$

Метод

Схема обратного преобразования выборки. Обратная функция может быть определена как . ${\displaystyle y=F_{X}(x)}$ ${\displaystyle F_{X}^{-1}(y)=\mathrm {inf} \{x|F_{X}(x)\geq y\}}$

Анимация того, как обратное преобразование выборки генерирует нормально распределенные случайные значения из равномерно распределенных случайных значений.

Проблема, которую решает метод выборки обратного преобразования, заключается в следующем:

• Пусть — случайная величина , распределение которой можно описать кумулятивной функцией распределения . ${\displaystyle X}$ ${\displaystyle F_{X}}$
• Мы хотим сгенерировать значения, которые распределены в соответствии с этим распределением. ${\displaystyle X}$

Метод выборки обратного преобразования работает следующим образом:

1. Сгенерировать случайное число из стандартного равномерного распределения в интервале , т.е. из ${\displaystyle u}$ ${\displaystyle [0,1]}$ ${\displaystyle U\sim \mathrm {Unif} [0,1].}$
2. Найдите обобщенную обратную функцию искомого CDF, т.е. . ${\displaystyle F_{X}^{-1}(u)}$
3. Вычислить . Вычисленная случайная величина имеет распределение и, следовательно, тот же закон, что и . ${\displaystyle X'(u)=F_{X}^{-1}(u)}$ ${\displaystyle X'(U)}$ ${\displaystyle F_{X}}$ ${\displaystyle X}$

Выражаясь по-другому, при заданной кумулятивной функции распределения и равномерной переменной случайная величина имеет распределение . ^[3] ${\displaystyle F_{X}}$ ${\displaystyle U\in [0,1]}$ ${\displaystyle X=F_{X}^{-1}(U)}$ ${\displaystyle F_{X}}$

В непрерывном случае может быть дана обработка таких обратных функций как объектов, удовлетворяющих дифференциальным уравнениям. ^[4] Некоторые такие дифференциальные уравнения допускают явные решения в виде степенных рядов , несмотря на их нелинейность. ^[5]

Примеры

• В качестве примера предположим, что у нас есть случайная величина и кумулятивная функция распределения ${\displaystyle U\sim \mathrm {Unif} (0,1)}$

${\displaystyle {\begin{aligned}F(x)=1-\exp(-{\sqrt {x}})\end{aligned}}}$

Для того чтобы выполнить инверсию, нам нужно решить ${\displaystyle F(F^{-1}(u))=u}$

${\displaystyle {\begin{aligned}F(F^{-1}(u))&=u\\1-\exp \left(-{\sqrt {F^{-1}(u)}}\right)&=u\\F^{-1}(u)&=(-\log(1-u))^{2}\\&=(\log(1-u))^{2}\end{aligned}}}$

Отсюда мы выполним шаги один, два и три.

• В качестве другого примера мы используем экспоненциальное распределение с для x ≥ 0 (и 0 в противном случае). Решая y=F(x), мы получаем обратную функцию ${\displaystyle F_{X}(x)=1-e^{-\lambda x}}$

${\displaystyle x=F^{-1}(y)=-{\frac {1}{\lambda }}\ln(1-y).}$

Это означает, что если мы возьмем некоторое число из a и вычислим Это имеет экспоненциальное распределение. ${\displaystyle y_{0}}$ ${\displaystyle U\sim \mathrm {Unif} (0,1)}$ ${\displaystyle x_{0}=F_{X}^{-1}(y_{0})=-{\frac {1}{\lambda }}\ln(1-y_{0}),}$ ${\displaystyle x_{0}}$

Идея проиллюстрирована на следующем графике:

Случайные числа y _i генерируются из равномерного распределения между 0 и 1, т. е. Y ~ U(0, 1). Они изображены в виде цветных точек на оси y. Каждая из точек отображается в соответствии с x=F ⁻¹ (y), что показано серыми стрелками для двух точек-примеров. В этом примере мы использовали экспоненциальное распределение. Следовательно, для x ≥ 0 плотность вероятности равна , а кумулятивная функция распределения равна . Следовательно, . Мы видим, что при использовании этого метода многие точки оказываются близкими к 0, и только несколько точек оказываются с высокими значениями x — как и ожидается для экспоненциального распределения. ${\displaystyle \varrho _{X}(x)=\lambda e^{-\lambda \,x}}$ ${\displaystyle F(x)=1-e^{-\lambda \,x}}$ ${\displaystyle x=F^{-1}(y)=-{\frac {\ln(1-y)}{\lambda }}}$

Обратите внимание, что распределение не изменится, если мы начнем с 1-y вместо y. Поэтому для вычислительных целей достаточно сгенерировать случайные числа y в [0, 1], а затем просто вычислить

${\displaystyle x=F^{-1}(y)=-{\frac {1}{\lambda }}\ln(y).}$

Доказательство правильности

Пусть будет кумулятивной функцией распределения , а будет ее обобщенной обратной функцией (используя инфимум , поскольку CDF слабо монотонны и непрерывны справа ): ^[6] ${\displaystyle F}$ ${\displaystyle F^{-1}}$

${\displaystyle F^{-1}(u)=\inf \;\{x\mid F(x)\geq u\}\qquad (0<u<1).}$

Утверждение: Если — равномерная случайная величина , то имеет в качестве своей функции распределения. ${\displaystyle U}$ ${\displaystyle [0,1]}$ ${\displaystyle F^{-1}(U)}$ ${\displaystyle F}$

Доказательство:

${\displaystyle {\begin{aligned}&\Pr(F^{-1}(U)\leq x)\\&{}=\Pr(U\leq F(x))\quad &(F{\text{ is right-continuous, so }}\{u:F^{-1}(u)\leq x\}=\{u:u\leq F(x)\})\\&{}=F(x)\quad &({\text{because }}\Pr(U\leq u)=u,{\text{ when }}U{\text{ is uniform on }}[0,1])\\\end{aligned}}}$

Усеченное распределение

Выборку с обратным преобразованием можно просто распространить на случаи усеченных распределений на интервале без затрат на выборку с отклонением: можно следовать тому же алгоритму, но вместо генерации случайного числа, равномерно распределенного между 0 и 1, сгенерировать равномерно распределенное между и , а затем снова взять . ${\displaystyle (a,b]}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle F(a)}$ ${\displaystyle F(b)}$ ${\displaystyle F^{-1}(u)}$

Уменьшение количества инверсий

Для получения большого количества выборок необходимо выполнить такое же количество инверсий распределения. Одним из возможных способов уменьшения количества инверсий при получении большого количества выборок является применение так называемого стохастического коллокационного Монте-Карло-сэмплера (SCMC-сэмплера) в рамках полиномиального хаотичного расширения. Это позволяет нам генерировать любое количество выборок Монте-Карло с помощью всего лишь нескольких инверсий исходного распределения с независимыми выборками переменной, для которой инверсии аналитически доступны, например, стандартной нормальной переменной. ^[7]

Реализации программного обеспечения

Существуют программные реализации, доступные для применения метода обратной выборки с использованием численных аппроксимаций обратной величины в случае, если она недоступна в закрытой форме. Например, аппроксимация обратной величины может быть вычислена, если пользователь предоставит некоторую информацию о распределениях, такую ​​как PDF ^[8] или CDF.

• Библиотека C UNU.RAN ^[9]
• R-библиотека Runuran ^[10]
• Выборка подпакета Python в scipy.stats ^{[11] [12]}

Смотрите также

• Вероятностное интегральное преобразование
• Копула , определяемая с помощью интегрального преобразования вероятности.
• Функция квантиля для явного построения обратных CDF.
• Обратная функция распределения для точного математического определения распределений с дискретными компонентами.
• Выборка с отклонением — еще один распространенный метод генерации случайных величин, не требующий инверсии функции распределения.

Ссылки

1. Люк Деврой (1986). Неоднородная генерация случайных величин (PDF) . Нью-Йорк: Springer-Verlag. Архивировано из оригинала (PDF) 2014-08-18 . Получено 2012-04-12 .
2. «R: Генерация случайных чисел».
3. Макнил, Александр Дж.; Фрей, Рюдигер; Эмбрехтс, Пол (2005). Количественное управление рисками . Princeton Series in Finance. Princeton University Press, Принстон, Нью-Джерси. С. 186. ISBN 0-691-12255-5.
4. Steinbrecher, György; Shaw, William T. (19 марта 2008 г.). "Квантильная механика". European Journal of Applied Mathematics . 19 (2). doi :10.1017/S0956792508007341. S2CID  6899308.
5. Арридж, Саймон; Маасс, Питер; Октем, Озан; Шёнлиб, Карола-Бибиан (2019). «Решение обратных задач с использованием моделей, управляемых данными». Acta Numerica . 28 : 1–174. doi : 10.1017/S0962492919000059 . ISSN  0962-4929. S2CID  197480023.
6. Люк Деврой (1986). "Раздел 2.2. Инверсия с помощью численного решения F(X) = U" (PDF) . Генерация неравномерных случайных величин . Нью-Йорк: Springer-Verlag.
7. LA Grzelak, JAS Witteveen, M. Suarez и CW Oosterlee. Стохастический коллокационный Монте-Карло-сэмплер: высокоэффективная выборка из «дорогих» распределений. https://ssrn.com/abstract=2529691
8. Дерфлингер, Герхард; Хёрманн, Вольфганг; Лейдольд, Йозеф (2010). «Генерация случайных величин с помощью численной инверсии, когда известна только плотность» (PDF) . ACM Transactions on Modeling and Computer Simulation . 20 (4). doi :10.1145/945511.945517.
9. "UNU.RAN - Универсальные генераторы случайных чисел с неоднородной последовательностью".
10. «Runuran: R-интерфейс для генераторов случайных величин «UNU.RAN». 17 января 2023 г.
11. «Генераторы случайных чисел (Scipy.stats.sampling) — Руководство SciPy v1.12.0».
12. Баумгартен, Кристоф; Патель, Тирт (2022). «Автоматическая генерация случайных величин в Python». Труды 21-й конференции «Python in Science» . С. 46–51. doi :10.25080/majora-212e5952-007.