Выборка обратного преобразования

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

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

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

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

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

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

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

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

Для любой случайной величины случайная величина имеет то же распределение , что и , где – обобщенная обратная функция кумулятивного распределения и равномерна на . ^[4] ${\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}$

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

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

Примеры

• В качестве примера предположим, что у нас есть случайная величина и кумулятивная функция распределения. ${\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}}$

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

Случайные числа _yi генерируются из равномерного распределения между 0 и 1, т.е. Y ~ U(0, 1). Они изображаются в виде цветных точек на оси Y. Каждая из точек отображается в соответствии с x=F ^-1 (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 слабо монотонны и непрерывны справа ): ^[7] ${\displaystyle F}$ ${\displaystyle F^{-1}}$

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

Утверждение: если является однородной случайной величиной, то ее CDF является ее CDF. ${\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) в рамках структуры полиномиального расширения хаоса. Это позволяет нам генерировать любое количество выборок Монте-Карло всего лишь с несколькими инверсиями исходного распределения с независимыми выборками переменной, для которой инверсии доступны аналитически, например, стандартной нормальной переменной. ^[8]

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

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

Рекомендации

1. Университет Аалто, Н. Хивонен, Вычислительные методы в обратных задачах. Двенадцатая лекция https://noppa.tkk.fi/noppa/kurssi/mat-1.3626/luennot/Mat-1_3626_lecture12.pdf ^{[ постоянная мертвая ссылка ]}
2. Люк Деврой (1986). Генерация неравномерных случайных переменных (PDF) . Нью-Йорк: Springer-Verlag. Архивировано из оригинала (PDF) 18 августа 2014 г. Проверено 12 апреля 2012 г.
3. «R: Генерация случайных чисел» .
4. МакНил, Александр Дж.; Фрей, Рюдигер; Эмбрехтс, Пол (2005). Количественный риск-менеджмент . Принстонская серия по финансам. Издательство Принстонского университета, Принстон, Нью-Джерси. п. 186. ИСБН 0-691-12255-5.
5. Штайнбрехер, Дьёрдь; Шоу, Уильям Т. (19 марта 2008 г.). «Квантильная механика». Европейский журнал прикладной математики . 19 (2). дои : 10.1017/S0956792508007341. S2CID  6899308.
6. Арридж, Саймон; Маасс, Питер; Октем, Озан; Шенлиб, Карола-Бибиан (2019). «Решение обратных задач с использованием моделей, управляемых данными». Акта Нумерика . 28 : 1–174. дои : 10.1017/S0962492919000059 . ISSN  0962-4929. S2CID  197480023.
7. Люк Деврой (1986). «Раздел 2.2. Инверсия путем численного решения задачи F(X) = U» (PDF) . Генерация неоднородной случайной переменной . Нью-Йорк: Springer-Verlag.
8. LA Grzelak, JAS Witteveen, M. Suarez и CW Oosterlee. Стохастический сэмплер Монте-Карло: высокоэффективная выборка из «дорогих» распределений. https://ssrn.com/abstract=2529691