Полярный метод Марсальи - Marsaglia polar method

Основную теорию можно резюмировать следующим образом:

Если ты равномерно распределена в интервале 0 ≤ты <1, то точка (cos (2πты), sin (2πты)) равномерно распределена по единичной окружностиИкс² + у² = 1, и умножив эту точку на независимую случайную переменную ρ с распределением

${displaystyle Pr (ho$

поставит точку

${displaystyle left (ho cos (2pi u), ho sin (2pi u) ight)}$

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

История

Эта идея восходит к Лаплас, кому Гаусс кредиты с обнаружением выше

${displaystyle I = int _ {- infty} ^ {infty} e ^ {- x ^ {2} / 2}, dx}$

извлекая квадратный корень из

${displaystyle I ^ {2} = int _ {- infty} ^ {infty} int _ {- infty} ^ {infty} e ^ {- (x ^ {2} + y ^ {2}) / 2}, dx , dy = int _ {0} ^ {2pi} int _ {0} ^ {infty} re ^ {- r ^ {2} / 2}, dr, d heta.}$

Преобразование в полярные координаты показывает, что θ равномерно распределен (постоянная плотность) от 0 до 2π и что радиальное расстояние р имеет плотность

${displaystyle re ^ {- r ^ {2} / 2}.,}$

(р² имеет соответствующий чи квадрат распределение.)

Этот метод создания пары независимых стандартных нормальных переменных путем радиального проецирования случайной точки на единичной окружности на расстояние, задаваемое квадратным корнем из переменной хи-квадрат-2, называется полярным методом генерации пары нормальных случайных величин. ,

Практические соображения

Прямое применение этой идеи,

${displaystyle x = {sqrt {-2ln (u_ {1})}} cos (2pi u_ {2}), quad y = {sqrt {-2ln (u_ {1})}} sin (2pi u_ {2}) }$

называется Преобразование Бокса – Мюллера, в котором вариация ци обычно генерируется как

${displaystyle {sqrt {-2ln (u_ {1})}},}$

но это преобразование требует функций логарифма, квадратного корня, синуса и косинуса. На некоторых процессорах косинус и синус одного и того же аргумента могут быть вычислены параллельно с помощью одной инструкции.^[5] В частности, для машин на базе Intel можно использовать инструкцию ассемблера fsincos или инструкцию expi (доступную, например, в D) для вычисления сложных

${displaystyle operatorname {expi} (z) = e ^ {iz} = cos (z) + isin (z) ,,}$

и просто разделите реальную и мнимую части.

Примечание: Чтобы явно вычислить комплексно-полярную форму, используйте следующие подстановки в общем виде:

Позволять ${displaystyle r = {sqrt {-2ln (u_ {1})}}}$ и ${displaystyle z = 2pi u_ {2}.}$ потом

${displaystyle re ^ {iz} = {sqrt {-2ln (u_ {1})}} e ^ {i2pi u_ {2}} = {sqrt {-2ln (u_ {1})}} влево [cos (2pi u_ {2}) + isin (2pi u_ {2}) ight].}$

Напротив, полярный метод здесь устраняет необходимость в вычислении косинуса и синуса. Вместо этого, решая точку на единичной окружности, эти две функции можно заменить на Икс и у координаты нормированные на ${displaystyle {sqrt {x ^ {2} + y ^ {2}}}}$ радиус. В частности, случайная точка (Икс, у) внутри единичной окружности проецируется на единичную окружность, задав ${displaystyle s = x ^ {2} + y ^ {2}}$ и формируя точку

${displaystyle left ({frac {x} {sqrt {s}}}, {frac {y} {sqrt {s}}} ight) ,,}$

что является более быстрой процедурой, чем вычисление косинуса и синуса. Некоторые исследователи утверждают, что условная инструкция if (для отклонения точки за пределами единичного круга) может замедлить выполнение программ на современных процессорах, оснащенных конвейерной обработкой и предсказанием ветвлений.^[6] Также эта процедура требует примерно на 27% больше оценок основного генератора случайных чисел (только ${displaystyle pi / 4approx 79 \%}$ генерируемых точек лежат внутри единичной окружности).

Затем эта случайная точка на окружности проецируется в радиальном направлении на необходимое случайное расстояние с помощью

${displaystyle {sqrt {-2ln (s)}} ,,}$

используя тот же s потому что s не зависит от случайной точки на окружности и равномерно распределен от 0 до 1.

Выполнение

Простая реализация в Ява используя среднее значение и стандартное отклонение:

частный статический двойной запасной;частный статический логический hasSpare = ложный;общественный статический синхронизированный двойной генерироватьГауссовский(двойной иметь в виду, двойной stdDev) {    если (hasSpare) {        hasSpare = ложный;        возвращаться запасной * stdDev + иметь в виду;    } еще {        двойной ты, v, s;        делать {            ты = Математика.случайный() * 2 - 1;            v = Математика.случайный() * 2 - 1;            s = ты * ты + v * v;        } пока (s >= 1 || s == 0);        s = Математика.sqrt(-2.0 * Математика.бревно(s) / s);        запасной = v * s;        hasSpare = истинный;        возвращаться иметь в виду + stdDev * ты * s;    }}

Не-потокобезопасный реализация в C ++ используя среднее значение и стандартное отклонение:

двойной генерироватьГауссовский(двойной иметь в виду, двойной stdDev) {    статический двойной запасной;    статический bool hasSpare = ложный;    если (hasSpare) {        hasSpare = ложный;        возвращаться запасной * stdDev + иметь в виду;    } еще {        двойной ты, v, s;        делать {            ты = (ранд() / ((двойной)RAND_MAX)) * 2.0 - 1.0;            v = (ранд() / ((двойной)RAND_MAX)) * 2.0 - 1.0;            s = ты * ты + v * v;        } пока (s >= 1.0 || s == 0.0);        s = sqrt(-2.0 * бревно(s) / s);        запасной = v * s;        hasSpare = истинный;        возвращаться иметь в виду + stdDev * ты * s;    }}

C ++ 11 GNU GCC libstdc ++ реализация std :: normal_distribution использует полярный метод Марсальи, как указано в здесь.

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