Выборка с обратным преобразованием

Было предложено объединить эту статью с интегральным преобразованием вероятности . ( Обсудить ) Предлагается с декабря 2020 года.

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

Выборка с обратным преобразованием берет однородные выборки числа от 0 до 1, интерпретируемых как вероятность, а затем возвращает наибольшее число из области распределения, такое что . Например, представьте, что это стандартное нормальное распределение с нулевым средним и единичным стандартным отклонением. В таблице ниже показаны образцы, взятые из равномерного распределения, и их представление в стандартном нормальном распределении.${\ displaystyle u}$${\ displaystyle x}$${\ Displaystyle P (X)}$${\ Displaystyle P (- \ infty <X <x) \ leq u}$${\ Displaystyle P (X)}$

Преобразование однородного образца в нормальный

${\ displaystyle u}$	${\ Displaystyle F ^ {- 1} (и)}$
.5	0
0,975	1,95996
0,995	2,5758
.999999	4,75342
1-2 ^ {- 52}	8,12589

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

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

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

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

Определение [ править ]

Интегральная вероятность преобразование состояния , что , если это непрерывная случайная величина с функцией распределения , то случайная величина имеет равномерное распределение на [0, 1]. Обратное интегральное преобразование вероятности - это как раз обратное этому: в частности, если имеет равномерное распределение на [0, 1] и если имеет кумулятивное распределение , то случайная величина имеет то же распределение, что и .${\ displaystyle X}$ ${\ displaystyle F_ {X}}$${\ Displaystyle Y = F_ {X} (X)}$${\ displaystyle Y}$${\ displaystyle X}$${\ displaystyle F_ {X}}$${\ Displaystyle F_ {X} ^ {- 1} (Y)}$${\ displaystyle X}$

График техники инверсии от до . В правом нижнем углу мы видим обычную функцию, а в левом верхнем - ее инверсию.${\ displaystyle x}$${\ Displaystyle F (х)}$

Интуиция [ править ]

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

Мы хотим увидеть, сможем ли мы найти какое-нибудь строго монотонное преобразование , такое, что . Мы будем иметь${\ Displaystyle Т: [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}(x)}$
3. Вычислить . Вычисленная случайная величина имеет распределение .${\displaystyle X=F_{X}^{-1}(u)}$${\displaystyle X}$${\displaystyle F_{X}(x)}$

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

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

Примеры [ править ]

• В качестве примера предположим, что у нас есть случайная величина и кумулятивная функция распределения.${\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 ^-1 (y), что показано серыми стрелками для двух примерных точек. В этом примере мы использовали экспоненциальное распределение. Следовательно, для x ≥ 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).}$

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

Пусть F - непрерывная кумулятивная функция распределения , и пусть F ⁻¹ - ее обратная функция (с использованием точной нижней грани, поскольку CDF слабо монотонны и непрерывны справа ): ^[5]

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

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

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

${\displaystyle {\begin{aligned}&\Pr(F^{-1}(U)\leq x)\\&{}=\Pr(U\leq F(x))\quad &({\text{applying }}F,{\text{ to both sides}})\\&{}=F(x)\quad &({\text{because }}\Pr(U\leq y)=y,{\text{ when U 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-сэмплер) в рамках структуры полиномиального хаоса . Это позволяет нам генерировать любое количество выборок Монте-Карло с помощью всего лишь нескольких инверсий исходного распределения с независимыми выборками переменной, для которой инверсии доступны аналитически, например стандартной нормальной переменной. ^[6]

См. Также [ править ]

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

Ссылки [ править ]