Метод Бокса — Мюллера

Метод Бокса — Мюллера — это алгоритм, предназначенный для генерации стандартных нормально распределённых случайных чисел на основе равномерно распределённых случайных чисел. Метод был предложен в 1958 году британским математиком Джорджем Боксом и американским статистиком Мервином Мюллером. Он широко применяется в статистическом моделировании, методах Монте-Карло, компьютерной графике и других областях, где требуется имитация случайных процессов с нормальным (гауссовским) распределением. Основное преимущество метода заключается в его простоте и эффективности: для получения двух независимых нормально распределённых случайных величин требуется всего два равномерно распределённых числа.

История

До появления метода Бокса — Мюллера генерация нормально распределённых случайных чисел была сложной задачей. Использование центральной предельной теоремы (суммирование большого числа равномерно распределённых величин) требовало значительных вычислительных ресурсов, а преобразование равномерного распределения в нормальное с помощью обратной функции распределения (квантильной функции) было затруднено из-за отсутствия аналитического выражения для функции ошибок (erf).

В 1958 году Джордж Бокс и Мервин Мюллер опубликовали статью «A Note on the Generation of Random Normal Deviates» в журнале The Annals of Mathematical Statistics. В ней они предложили метод, основанный на полярном преобразовании двух независимых равномерно распределённых случайных величин. Этот метод позволял получать пару независимых стандартных нормальных величин без необходимости вычисления обратной функции распределения, что делало его значительно быстрее и точнее по сравнению с существовавшими подходами.

Впоследствии метод был усовершенствован: в 1969 году Джордж Марсалья и Т. А. Брей предложили так называемый «полярный метод» (Marsaglia polar method), который устранил использование тригонометрических функций, заменив их на операции выборки и отбрасывания, что повысило вычислительную эффективность.

Алгоритм

Метод Бокса — Мюллера основан на преобразовании двух независимых случайных чисел, равномерно распределённых на интервале (0, 1], в два независимых стандартных нормально распределённых числа (с математическим ожиданием 0 и дисперсией 1). Существует две основные формы алгоритма: тригонометрическая и полярная.

Тригонометрическая форма (классическая)

1. Генерируются два независимых случайных числа \( u_1 \) и \( u_2 \) из равномерного распределения на интервале (0, 1].
2. Вычисляются:

\[ z_0 = \sqrt{-2 \ln u_1} \cdot \cos(2\pi u_2) \] \[ z_1 = \sqrt{-2 \ln u_1} \cdot \sin(2\pi u_2) \]

1. Величины \( z_0 \) и \( z_1 \) являются независимыми стандартными нормально распределёнными случайными числами.

Математическое обоснование: преобразование переводит равномерное распределение на единичном квадрате в нормальное распределение на плоскости через полярные координаты. Радиус \( r = \sqrt{-2 \ln u_1} \) следует распределению Рэлея, а угол \( \theta = 2\pi u_2 \) — равномерному распределению на \([0, 2\pi)\).

Полярная форма (Марсальи — Брея)

Этот вариант позволяет избежать вычисления тригонометрических функций, заменяя их на более быстрые операции:

1. Генерируются два независимых случайных числа \( u_1 \) и \( u_2 \) из равномерного распределения на интервале (-1, 1].
2. Вычисляется \( s = u_1^2 + u_2^2 \).
3. Если \( s \geq 1 \) или \( s = 0 \), пара отбрасывается и генерируется новая (процедура отбрасывания).
4. Если \( 0 < s < 1 \), вычисляется:

\[ z_0 = u_1 \cdot \sqrt{\frac{-2 \ln s}{s}} \] \[ z_1 = u_2 \cdot \sqrt{\frac{-2 \ln s}{s}} \]

1. Величины \( z_0 \) и \( z_1 \) являются независимыми стандартными нормальными числами.

Вероятность принятия пары (то есть попадания точки \((u_1, u_2)\) внутрь единичного круга) составляет \(\pi/4 \approx 0.785\), что делает метод эффективным, хотя и требует отбрасывания примерно 21% пар.

Математическое обоснование

Метод Бокса — Мюллера использует свойство преобразования двумерного равномерного распределения в двумерное нормальное. Если \((X, Y)\) — пара независимых стандартных нормальных величин, то их совместная плотность равна: \[ f(x, y) = \frac{1}{2\pi} e^{-\frac{x^2 + y^2}{2}} \] В полярных координатах \((r, \theta)\): \[ f(r, \theta) = \frac{1}{2\pi} r e^{-\frac{r^2}{2}} \] Распределение радиуса \(r\) является распределением Рэлея с функцией плотности \(f(r) = r e^{-r^2/2}\), а угол \(\theta\) распределён равномерно на \([0, 2\pi)\). Преобразование \(r = \sqrt{-2 \ln u_1}\) и \(\theta = 2\pi u_2\) переводит равномерные \(u_1, u_2\) в требуемые распределения.

Применение

Метод Бокса — Мюллера широко используется в различных областях:

• Статистическое моделирование и методы Монте-Карло: для генерации случайных величин с нормальным распределением при оценке интегралов, моделировании случайных процессов (например, броуновского движения) и анализе рисков.
• Финансовая математика: для моделирования цен активов, расчёта опционов и оценки рисков (например, в модели Блэка — Шоулза).
• Компьютерная графика и симуляции: для генерации шума (например, нормально распределённого шума в текстурах), моделирования физических процессов (диффузия, теплопроводность) и анимации.
• Машинное обучение: для инициализации весов нейронных сетей, добавления шума в данные (аугментация) и генерации синтетических данных.
• Криптография: для генерации случайных чисел, используемых в криптографических протоколах (хотя в криптографии предпочитают аппаратные или детерминированные генераторы с гарантированной энтропией).

Преимущества и недостатки

Преимущества

• Простота реализации: алгоритм требует лишь базовых математических операций (логарифм, квадратный корень, тригонометрические функции или арифметические операции в полярной форме).
• Точность: метод даёт точное нормальное распределение (в отличие от аппроксимаций, основанных на центральной предельной теореме).
• Эффективность: для получения двух нормальных чисел требуется всего два равномерных числа (в тригонометрической форме) или в среднем 2.55 равномерных числа (в полярной форме с учётом отбрасывания).

Недостатки

• Вычислительная стоимость: вычисление логарифма и квадратного корня (а в тригонометрической форме — ещё и синуса/косинуса) может быть затратным на старых или ограниченных вычислительных системах. Полярная форма частично решает эту проблему.
• Зависимость от качества генератора равномерных чисел: если генератор равномерных чисел имеет дефекты (например, корреляцию или малый период), это может исказить распределение нормальных чисел.
• Необходимость отбрасывания в полярной форме: до 21% пар отбрасывается, что может снизить производительность в системах с жёсткими требованиями к скорости.

Сравнение с другими методами

• Метод обратного преобразования: требует вычисления обратной функции распределения нормального закона (квантильной функции), что обычно реализуется через аппроксимации (например, алгоритм Моро — Саса). Метод Бокса — Мюллера точнее и быстрее для многих приложений.
• Метод Зиггурата: более современный алгоритм, основанный на кусочно-линейной аппроксимации плотности нормального распределения. Он значительно быстрее метода Бокса — Мюллера, но сложнее в реализации.
• Центральная предельная теорема: суммирование 12 равномерных чисел даёт приближение к нормальному распределению, но оно неточно на хвостах распределения. Метод Бокса — Мюллера обеспечивает точное распределение.

Интересные факты

• Метод Бокса — Мюллера является одним из первых алгоритмов, специально разработанных для генерации нормальных случайных чисел на компьютерах.
• В 1976 году Джордж Марсалья и Т. А. Брей показали, что полярная форма метода может быть реализована без использования тригонометрических функций, что сделало её популярной в ранних компьютерных системах.
• Метод используется в стандартных библиотеках многих языков программирования, например, в numpy.random.randn (Python) и Math::Random (Perl), хотя в современных реализациях часто предпочитают метод Зиггурата.

Источники

• Box, G. E. P.; Muller, M. E. (1958). "A Note on the Generation of Random Normal Deviates". The Annals of Mathematical Statistics. 29 (2): 610–611.
• Marsaglia, G.; Bray, T. A. (1964). "A Convenient Method for Generating Normal Variables". SIAM Review. 6 (3): 260–264.
• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.
• Gentle, J. E. (2003). Random Number Generation and Monte Carlo Methods (2nd ed.). Springer.