Преобразование Бокса – Мюллера, автор Джордж Эдвард Пелхэм Бокс и Мервин Эдгар Мюллер, это метод выборки случайных чисел для генерации пар независимых, стандартных, нормально распределенных (нулевое ожидание, единица дисперсия ) случайных чисел, заданных источником равномерно распределенных случайных чисел. Фактически, этот метод впервые был упомянут в явной форме Раймондом Э. А. С. Пэли и Норбертом Винером в 1934 году.
Преобразование Бокса – Мюллера обычно выражается в двух формах. Основная форма, данная Боксом и Мюллером, берет две выборки из равномерного распределения на интервале [0, 1] и отображает их на две стандартные, нормально распределенные выборки. Полярная форма берет две выборки из другого интервала, [-1, +1], и отображает их в две нормально распределенные выборки без использования синусоидальных или косинусных функций.
Преобразование Бокса – Мюллера было разработано как более эффективная с вычислительной точки зрения альтернатива методу выборки обратного преобразования. Алгоритм зиккурата дает более эффективный метод для скалярных процессоров (например, старых ЦП), в то время как преобразование Бокса – Мюллера лучше для процессоров с векторными модулями (например, графические процессоры или современные процессоры).
Предположим, что U 1 и U 2 являются независимыми выборками, выбранными из равномерного распределения на единичном интервале (0, 1). Пусть
и
Тогда Z 0 и Z 1 являются независимыми случайными величинами со стандартным нормальным распределением .
Вывод основан на свойстве двумерного Декартова система, где координаты X и Y описываются двумя независимыми и нормально распределенными случайными величинами, случайные величины для R и Θ (показанные выше) в соответствующих полярных координатах также независимы и могут быть выражены как
и
Поскольку R является квадратом нормы стандартной двумерной нормальной переменной (X, Y), она имеет распределение хи-квадрат с двумя степенями свободы. В частном случае двух степеней свободы распределение хи-квадрат совпадает с экспоненциальным распределением , а приведенное выше уравнение для R представляет собой простой способ генерировать требуемую экспоненциальную переменную.
Полярная форма была сначала предложена Дж. Беллом, а затем модифицирована Р. Кнопом. Хотя было описано несколько различных версий полярного метода, здесь будет описана версия Р. Кнопа, потому что она наиболее широко используется, отчасти из-за ее включения в Числовые рецепты.
Учитывая u и v, независимые и равномерно распределенные в закрытом интервале [−1, +1], положим s = R = u + v. Если 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 в основной форме. Как показано на рисунке, значения и в базовой форме может быть заменен на коэффициенты и соответственно. Преимущество состоит в том, что можно избежать прямого вычисления тригонометрических функций. Это полезно, когда вычисление тригонометрических функций обходится дороже, чем одно деление, которое заменяет каждую из них.
Так же, как базовая форма дает два стандартных нормальных отклонения, так и этот альтернативный расчет.
и
Полярный метод отличается от базового метода тем, что он представляет собой тип отбраковки. Он отбрасывает некоторые сгенерированные случайные числа, но может быть быстрее, чем базовый метод, потому что его проще вычислить (при условии, что генератор случайных чисел относительно быстр) и он более устойчив в числовом отношении. Избегание использования дорогих тригонометрических функций увеличивает скорость по сравнению с базовой формой. Он отбрасывает 1 - π / 4 ≈ 21,46% от общего числа сгенерированных пар случайных чисел с равномерным распределением входных данных, то есть отбрасывает 4 / π - 1 ≈ 27,32% равномерно распределенных пар случайных чисел на каждую сгенерированную пару случайных чисел гауссова, что требует 4 / π ≈ 1,2732 входных случайных числа на каждое выходное случайное число.
Базовая форма требует двух умножений, 1/2 логарифма, 1/2 квадратного корня и одной тригонометрической функции для каждой нормальной переменной. На некоторых процессорах косинус и синус одного и того же аргумента могут быть вычислены параллельно с помощью одной инструкции. В частности, для машин на базе Intel можно использовать инструкцию ассемблера fsincos или инструкцию expi (обычно доступную из C как внутренняя функция ), чтобы вычислить комплексное
и просто разделите действительную и мнимую части.
Примечание: Для явного вычисления комплексно-полярной формы используйте следующие замены в общей форме:
Пусть и Тогда
Полярная форма требует умножения на 3/2, 1/2 логарифм, 1/2 квадратного корня и 1/2 деления для каждой нормальной вариации. Эффект заключается в замене одного умножения и одной тригонометрической функции на одно деление и условный цикл.
Когда компьютер используется для создания однородной случайной величины, он неизбежно будет иметь некоторые неточности, потому что существует нижняя граница того, насколько близки числа к нулю. Если генератор использует 32 бита на выходное значение, наименьшее ненулевое число, которое может быть сгенерировано: . Когда и равны этому, преобразование Бокса – Мюллера дает нормальное случайное отклонение, равное . Это означает, что алгоритм не будет генерировать случайные величины, превышающие 6,660 стандартных отклонений от среднего. Это соответствует пропорции потеряны из-за усечения, где - стандартное кумулятивное нормальное распределение. С 64 битами предел сдвигается до стандартных отклонений, для которых .
Стандартное преобразование Бокса – Мюллера генерирует значения из стандартного нормального распределения (т. Е. стандартных нормальных отклонений ) со средним 0 и стандартным отклонением 1. Реализация ниже в стандарте C ++ генерирует значения из любого нормального распределения со средним значением и дисперсией . Если является стандартным нормальным отклонением, то будет иметь нормальное распределение со средним значением и стандартным отклонением . Обратите внимание, что генератор случайных чисел был засеян, чтобы гарантировать, что новые псевдослучайные значения будут возвращены из последовательных вызовов функции generateGaussianNoise
.
#include#include #include double generateGaussianNoise (двойной mu, двойной сигма) {constexpr double epsilon = std :: numeric_limits :: epsilon (); constexpr double two_pi = 2.0 * M_PI; статический std :: mt19937 rng (std :: random_device {} ()); // Стандартный mersenne_twister_engine, засеянный rd () static std :: uniform_real_distribution <>runif (0.0, 1.0); двойной u1, u2; сделать {u1 = runif (rng); u2 = runif (rng); } while (u1 <= epsilon); auto z0 = sqrt(-2.0 * log(u1)) * cos(two_pi * u2); // auto z1 = sqrt(-2.0 * log(u1)) * sin(two_pi * u2); // not used here! return z0 * sigma + mu; }