Было предложено объединить эту статью с интегральным преобразованием вероятности . ( Обсудить ) Предлагается с декабря 2020 года. |
Выборка с обратным преобразованием (также известная как выборка с инверсией , обратное интегральное преобразование вероятности , метод обратного преобразования , преобразование Смирнова или золотое правило [1] ) является основным методом выборки псевдослучайных чисел , то есть для генерации номеров выборки при случайным образом из любого распределения вероятностей с учетом его кумулятивной функции распределения .
Выборка с обратным преобразованием берет однородные выборки числа от 0 до 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] и если имеет кумулятивное распределение , то случайная величина имеет то же распределение, что и .
Интуиция [ править ]
From , мы хотим сгенерировать с помощью CDF. Мы предполагаем, что это строго возрастающая функция, что обеспечивает хорошую интуицию.
Мы хотим увидеть, сможем ли мы найти какое-нибудь строго монотонное преобразование , такое, что . Мы будем иметь
где последний шаг использовал то, когда равномерно на .
Итак, мы должны быть обратной функцией , или, что то же самое,
Следовательно, мы можем генерировать из
Метод [ править ]
Проблема, которую решает метод выборки с обратным преобразованием, заключается в следующем:
- Пусть - случайная величина , распределение которой можно описать кумулятивной функцией распределения .
- Мы хотим сгенерировать значения, которые распределяются в соответствии с этим распределением.
Метод выборки с обратным преобразованием работает следующим образом:
- Сгенерируйте случайное число из стандартного равномерного распределения в интервале , например, из
- Найдите обратную величину желаемой функции CDF, например .
- Вычислить . Вычисленная случайная величина имеет распределение .
Выражаясь по-другому, случайная величина имеет распределение (или является распределенной ) при наличии непрерывной однородной переменной в и обратимой кумулятивной функции распределения .
Может быть дана трактовка таких обратных функций как объектов, удовлетворяющих дифференциальным уравнениям. [4] Некоторые такие дифференциальные уравнения допускают явные решения в виде степенных рядов, несмотря на их нелинейность. [ необходима цитата ]
Примеры [ править ]
- В качестве примера предположим, что у нас есть случайная величина и кумулятивная функция распределения.
- Чтобы выполнить инверсию, мы хотим решить для
- Отсюда мы будем выполнять шаги один, два и три.
- В качестве другого примера мы используем экспоненциальное распределение с для x ≥ 0 (и 0 в противном случае). Решая y = F (x), получаем обратную функцию
- Это означает, что если мы возьмем некоторые из a и вычислим, это имеет экспоненциальное распределение.
- Идея проиллюстрирована на следующем графике:
- Обратите внимание, что распределение не изменится, если мы начнем с 1-y вместо y. Поэтому для вычислительных целей достаточно сгенерировать случайные числа y в [0, 1], а затем просто вычислить
Доказательство правильности [ править ]
Пусть F - непрерывная кумулятивная функция распределения , и пусть F −1 - ее обратная функция (с использованием точной нижней грани, поскольку CDF слабо монотонны и непрерывны справа ): [5]
Утверждение: Если U является равномерной случайной переменной на (0, 1) , то есть F в качестве КОР.
Доказательство:
Усеченное распределение [ править ]
Выборка с обратным преобразованием может быть просто расширена на случаи усеченного распределения на интервале без затрат на выборку отклонения: можно следовать тому же алгоритму, но вместо генерации случайного числа, равномерно распределенного между 0 и 1, генерировать равномерно распределенное между и , и потом снова бери .
Уменьшение количества инверсий [ править ]
Чтобы получить большое количество выборок, нужно выполнить такое же количество инверсий распределения. Один из возможных способов уменьшить количество инверсий при получении большого количества выборок - это применение так называемого стохастического коллокационного сэмплера Монте-Карло (SCMC-сэмплер) в рамках структуры полиномиального хаоса . Это позволяет нам генерировать любое количество выборок Монте-Карло с помощью всего лишь нескольких инверсий исходного распределения с независимыми выборками переменной, для которой инверсии доступны аналитически, например стандартной нормальной переменной. [6]
См. Также [ править ]
- Интегральное преобразование вероятности
- Копула , определяемая с помощью интегрального преобразования вероятностей.
- Функция квантиля для явного построения обратных функций CDF.
- Функция обратного распределения для точного математического определения распределений с дискретными компонентами.
Ссылки [ править ]
- ^ Университет Аалто, Н. Хивёнен, Вычислительные методы в обратных задачах. Двенадцатая лекция https://noppa.tkk.fi/noppa/kurssi/mat-1.3626/luennot/Mat-1_3626_lecture12.pdf [ постоянная мертвая ссылка ]
- ^ Люк Devroye (1986). Генерация неоднородной случайной величины (PDF) . Нью-Йорк: Springer-Verlag.
- ^ https://stat.ethz.ch/R-manual/R-devel/library/base/html/Random.html
- ^ Штайнбрехер Г., Шоу, WT (2008). Квантильная механика. Европейский журнал прикладной математики 19 (2): 87–112.
- ^ Люк Devroye (1986). «Раздел 2.2. Инверсия путем численного решения F ( X ) = U » (PDF) . Генерация неравномерной случайной величины . Нью-Йорк: Springer-Verlag.
- ^ LA Grzelak, JAS Witteveen, М. Суарес, и CW Oosterlee. Сэмплер Монте-Карло со стохастической коллокацией: высокоэффективный отбор образцов из «дорогих» распределений. https://ssrn.com/abstract=2529691