Преобразования Бокса-Мюллер , от Джорджа Эдварда Pelham Box и Мервин Эдгара Мюллера , [1] является случайным числом выборки способа генерации пара независимого , стандарта, нормально распределены (ноль ожидания , блок дисперсии ) случайных числа, учитывая источник равномерно распределенные случайные числа. Фактически, этот метод впервые явным образом был упомянут Раймондом Е.А. Пэли и Норбертом Винером в 1934 году [2].
Преобразование Бокса – Мюллера обычно выражается в двух формах. Основная форма, данная Боксом и Мюллером, берет две выборки из равномерного распределения на интервале [0, 1] и отображает их в две стандартные, нормально распределенные выборки. Полярная форма берет две выборки из другого интервала, [-1, +1], и отображает их в две нормально распределенные выборки без использования функций синуса или косинуса.
Преобразование Бокса – Мюллера было разработано как более эффективная с вычислительной точки зрения альтернатива методу выборки обратного преобразования . [3] алгоритм зиккурат дает более эффективный метод для скалярных процессоров (например , старые CPU), в то время как преобразование Box-Мюллер превосходит для процессоров с векторными единиц (например , графические процессоры или современные процессоры). [4]
Основная форма
Предположим, что U 1 и U 2 - независимые выборки, выбранные из равномерного распределения на единичном интервале (0, 1). Позволять
а также
Тогда Z 0 и Z 1 - независимые случайные величины со стандартным нормальным распределением .
Вывод [5] основан на свойстве двумерной декартовой системы , где координаты X и Y описываются двумя независимыми и нормально распределенными случайными величинами, случайными величинами для R 2 и (показанными выше) в соответствующих полярных координатах. координаты также независимы и могут быть выражены как
а также
Поскольку R 2 является квадратом нормы стандартной двумерной нормальной переменной ( X , Y ), он имеет распределение хи-квадрат с двумя степенями свободы. В частном случае двух степеней свободы распределение хи-квадрат совпадает с экспоненциальным распределением , а приведенное выше уравнение для R 2 представляет собой простой способ создания требуемой экспоненциальной переменной.
Полярная форма
Полярная форма была впервые предложена Дж. Беллом [6], а затем модифицирована Р. Кнопом. [7] Несмотря на то, что было описано несколько различных версий полярного метода, версия Р. Кнопа будет описана здесь, потому что она наиболее широко используется, отчасти из-за ее включения в числовые рецепты .
Для заданных u и v , независимых и равномерно распределенных на отрезке [−1, +1], положим s = R 2 = u 2 + v 2 . Если s = 0 или s ≥ 1 , отбросьте u и v и попробуйте другую пару ( u , v ). Поскольку u и v равномерно распределены и допускаются только точки внутри единичной окружности, значения s будут равномерно распределены и в открытом интервале (0, 1). Последнее можно увидеть, вычислив кумулятивную функцию распределения для s в интервале (0, 1). Это площадь круга с радиусом, деленное на . Отсюда мы находим, что функция плотности вероятности имеет постоянное значение 1 на интервале (0, 1). Точно так же угол θ, деленный наравномерно распределена в интервале [0, 1) и не зависит от s .
Теперь мы отождествляем значение s со значением U 1 ис U 2 в основной форме. Как показано на рисунке, значения а также в основном виде можно заменить на коэффициенты а также , соответственно. Преимущество состоит в том, что можно избежать прямого вычисления тригонометрических функций. Это полезно, когда вычисление тригонометрических функций обходится дороже, чем одно деление, заменяющее каждую из них.
Подобно тому, как базовая форма дает два стандартных нормальных отклонения, так и этот альтернативный расчет.
а также
Противопоставление двух форм
Полярный метод отличается от базового метода тем, что является разновидностью отбраковочного отбора проб . Он отбрасывает некоторые сгенерированные случайные числа, но может быть быстрее, чем базовый метод, потому что его проще вычислить (при условии, что генератор случайных чисел относительно быстр) и он более устойчив в числовом отношении. [8] Избегание использования дорогих тригонометрических функций увеличивает скорость по сравнению с базовой формой. [6] Он отбрасывает 1 - π / 4 ≈ 21,46% от общего количества сгенерированных пар случайных чисел с равномерным распределением, т. Е. Отбрасывает 4 / π - 1 ≈ 27,32% пар равномерно распределенных случайных чисел на каждую сгенерированную пару гауссовских случайных чисел, что требует 4 / π ≈ 1,2732 входных случайных числа на каждое выходное случайное число.
Базовая форма требует двух умножений, 1/2 логарифма, 1/2 квадратного корня и одной тригонометрической функции для каждой нормальной переменной. [9] На некоторых процессорах косинус и синус одного и того же аргумента могут быть вычислены параллельно с помощью одной инструкции. В частности, для машин на базе Intel можно использовать инструкцию ассемблера fsincos или инструкцию expi (обычно доступную из C в качестве встроенной функции ) для вычисления сложных
и просто разделите реальную и мнимую части.
Примечание: Чтобы явно вычислить комплексно-полярную форму, используйте следующие замены в общей форме,
Позволять а также потом
Полярная форма требует 3/2 умножения, 1/2 логарифма, 1/2 квадратного корня и 1/2 деления для каждой нормальной вариации. В результате одно умножение и одна тригонометрическая функция заменяются одним делением и условным циклом.
Усечение хвостов
Когда компьютер используется для создания однородной случайной величины, он неизбежно будет иметь некоторые неточности, потому что существует нижняя граница того, насколько близкие числа могут быть к 0. Если генератор использует 32 бита на выходное значение, наименьшее ненулевое число, которое может быть сгенерирован . Когда а также равны этому, преобразование Бокса – Мюллера дает нормальное случайное отклонение, равное . Это означает, что алгоритм не будет генерировать случайные величины, превышающие 6,660 стандартных отклонений от среднего. Это соответствует пропорции потеряно из-за усечения, где - стандартное кумулятивное нормальное распределение. С 64 битами предел сдвигается до стандартные отклонения, для которых .
Выполнение
Стандартное преобразование Бокса – Мюллера генерирует значения из стандартного нормального распределения ( т. Е. Стандартных нормальных отклонений ) со средним 0 и стандартным отклонением 1 . Реализация ниже в стандартном C ++ генерирует значения из любого нормального распределения со средним значением. и дисперсия . Если стандартное нормальное отклонение, то будет иметь нормальное распределение со средним и стандартное отклонение . Обратите внимание, что генератор случайных чисел был засеян, чтобы гарантировать, что новые псевдослучайные значения будут возвращаться из последовательных вызовов generateGaussianNoise
функции.
#include #include <пределы>#include <случайный>#include <служебная программа>std :: pair < двойной , двойной > generateGaussianNoise ( двойной mu , двойной сигма ) { constexpr двойной epsilon = std :: numeric_limits < двойной > :: epsilon (); constexpr double two_pi = 2.0 * M_PI ; // инициализируем генератор случайных однородных чисел (runif) в диапазоне от 0 до 1 static std :: mt19937 rng ( std :: random_device {} ()); // Стандартный mersenne_twister_engine, засеянный с помощью rd () static std :: uniform_real_distribution <> runif ( 0.0 , 1.0 ); // создаем два случайных числа, убедитесь, что u1 больше, чем epsilon double u1 , u2 ; сделать { u1 = runif ( rng ); u2 = runif ( rng ); } while ( u1 <= epsilon ); // вычисляем z0 и z1 auto mag = sigma * sqrt ( -2.0 * log ( u1 )); авто z0 = mag * cos ( two_pi * u2 ) + mu ; авто z1 = mag * sin ( two_pi * u2 ) + mu ; возврат std :: make_pair ( z0 , z1 ); }
Смотрите также
- Выборка с обратным преобразованием
- Полярный метод Марсальи , аналогичный преобразованию Бокса – Мюллера, который использует декартовы координаты вместо полярных координат.
Рекомендации
- Хоуз, Ли; Томас, Дэвид (2008). GPU Gems 3 - Эффективная генерация случайных чисел и приложение с использованием CUDA . ISBN Pearson Education, Inc. 978-0-321-51526-1.
- ^ Коробка, ГЭП; Мюллер, Мервин Э. (1958). «Заметка о генерации случайных нормальных отклонений» . Летопись математической статистики . 29 (2): 610–611. DOI : 10.1214 / АОМ / 1177706645 . JSTOR 2237361 .
- ^ Раймонд EAC Пэли и Норберт Винер преобразования Фурье в комплексной области, Нью-Йорк: Американское математическое общество (1934) §37.
- ^ Kloeden и Валик, численные решения стохастических дифференциальных уравнений , стр. 11-12
- ^ Хауэс & Thomas 2008 .
- ↑ Шелдон Росс, Первый курс теории вероятностей , (2002), стр. 279–281.
- ^ а б Белл, Джеймс Р. (1968). «Алгоритм 334: нормальные случайные отклонения» . Коммуникации ACM . 11 (7): 498. DOI : 10,1145 / 363397,363547 .
- ^ Кноп, Р. (1969). «Замечание по алгоритму 334 [G5]: Нормальные случайные отклонения» . Коммуникации ACM . 12 (5): 281. DOI : 10,1145 / 362946,362996 .
- ^ Эверетт Ф. Картер младший, Генерация и применение случайных чисел , Forth Dimensions (1994), Vol. 16, № 1 и 2.
- ^ Обратите внимание, что оценка 2 π U 1 засчитывается как одно умножение, потому что значение 2 π может быть вычислено заранее и использоваться повторно.
Внешние ссылки
- Вайсштейн, Эрик В. "Преобразование Бокса-Мюллера" . MathWorld .
- Как преобразовать равномерное распределение в распределение Гаусса (код C)