Войти
алгоритм зиккурата - это алгоритм для выборки псевдослучайных чисел. Принадлежащий к классу алгоритмов отбраковки выборки, он основан на базовом источнике равномерно распределенных случайных чисел, обычно от генератора псевдослучайных чисел , а также на предварительно вычисленных таблицах. Алгоритм используется для генерации значений из монотонно убывающего распределения вероятностей. Его также можно применить к симметричным унимодальным распределениям, таким как нормальное распределение, путем выбора значения из одной половины распределения, а затем случайного выбора половины значение считается взятым из. Он был разработан Джорджем Марсалья и другими в 1960-х годах.
Типичное значение, полученное с помощью алгоритма, требует только генерации одного случайного значения с плавающей запятой и одного случайного индекса таблицы, за которым следует один поиск по таблице, одна операция умножения и одно сравнение. Иногда (в 2,5% случаев, в случае нормального или экспоненциального распределения при использовании типичных размеров таблиц) требуются дополнительные вычисления. Тем не менее, этот алгоритм в вычислительном отношении намного быстрее, чем два наиболее часто используемых метода генерации нормально распределенных случайных чисел, полярный метод Марсальи и преобразование Бокса – Мюллера, которые требуют как минимум одного логарифм и вычисление одного квадратного корня для каждой пары сгенерированных значений. Однако, поскольку алгоритм зиккурата сложнее реализовать, его лучше всего использовать, когда требуется большое количество случайных чисел.
Термин «алгоритм зиккурата» восходит к статье Марсальи с Вай Ван Цанг в 2000 году; он назван так потому, что концептуально основан на покрытии распределения вероятностей прямоугольными сегментами, сложенными в порядке убывания размера, в результате чего получается фигура, напоминающая зиккурат .
. Алгоритм Зикгурата, используемый для генерации выборочных значений с нормальное распределение. (Для простоты показаны только положительные значения.) Розовые точки - это изначально равномерно распределенные случайные числа. Требуемая функция распределения сначала сегментируется на равные области «А». Один слой i выбирается случайным образом однородным источником слева. Затем случайное значение из верхнего источника умножается на ширину выбранного слоя, и результат проверяется по x, чтобы увидеть, в какую область среза оно попадает с 3 возможными результатами: 1) (слева, сплошная черная область) образец четко под кривой и передается непосредственно на выход; 2) (правая, вертикальная полоска) значение выборки может находиться под кривой и должно быть проверено в дальнейшем. В этом случае генерируется случайное значение y в выбранном слое и сравнивается с f (x). Если меньше, точка находится под кривой и выводится значение x. Если нет (третий случай), выбранная точка x отклоняется, и алгоритм перезапускается с начала. Алгоритм зиккурата - это алгоритм отбраковки выборки; он случайным образом генерирует точку в распределении, немного превышающую желаемое распределение, а затем проверяет, находится ли сгенерированная точка внутри желаемого распределения. Если нет, он пытается снова. Для случайной точки под кривой плотности вероятности ее координата x представляет собой случайное число с желаемым распределением.
Распределение, из которого выбирает алгоритм зиккурата, состоит из n областей равной площади; n - 1 прямоугольник, покрывающий основную часть желаемого распределения, поверх непрямоугольного основания, включающего хвост распределения.
Учитывая монотонно убывающую функцию плотности вероятности f (x), определенную для всех x ≥ 0, основание зиккурата определяется как все точки внутри распределения и ниже y 1 = f (x 1). Он состоит из прямоугольной области от (0, 0) до (x 1, y 1) и (обычно бесконечного) хвоста распределения, где x>x 1 (и y < y1).
Этот слой (назовем его слоем 0) имеет область A. Поверх этого добавьте прямоугольный слой шириной x 1 и высотой A / x 1, поэтому у него также есть область A. Верх этого слоя находится на высоте y 2 = y 1 + A / x 1 и пересекает функцию плотности на точка (x 2, y 2), где y 2 = f (x 2). Этот слой включает в себя каждую точку функции плотности между y 1 и y 2, но (в отличие от базового слоя) также включает такие точки, как (x 1, y 2), которые не находятся в желаемом распределении.
Затем сверху накладываются дополнительные слои. Чтобы использовать предварительно вычисленную таблицу размера n (обычно n = 256), выбирают x 1 так, чтобы x n = 0, что означает, что верхний блок, слой n - 1, достигает пика распределения точно в точке (0, f (0)).
Слой i простирается по вертикали от y i до y i + 1 и может быть разделен по горизонтали на две области: (обычно большую) часть от 0 до x i + 1, который полностью содержится в желаемом распределении, и (небольшая) часть от x i + 1 до x i, которая содержится только частично.
Игнорируя на мгновение проблему уровня 0 и учитывая однородные случайные величины U 0 и U 1 ∈ [0,1), алгоритм зиккурата может быть описывается как:
Шаг 1 представляет собой выбор координаты y с низким разрешением. Шаг 3 проверяет, находится ли координата x в пределах желаемой функции плотности, не зная больше о координате y. Если это не так, на этапе 4 выбирается координата y с высоким разрешением, а на этапе 5 выполняется проверка отклонения.
В случае близко расположенных слоев алгоритм завершается на шаге 3 очень большую часть времени. Однако для верхнего слоя n - 1 этот тест всегда терпит неудачу, потому что x n = 0.
Слой 0 также можно разделить на центральную область и край, но край это бесконечный хвост. Чтобы использовать тот же алгоритм для проверки, находится ли точка в центральной области, сгенерируйте фиктивный x 0 = A / y 1. Это будет генерировать точки с x < x1 с правильной частотой, и в редких случаях, когда выбран слой 0 и x ≥ x 1, используйте специальный резервный алгоритм для выбора точки в случайный из хвоста. Поскольку резервный алгоритм используется реже одного раза из тысячи, скорость не имеет значения.
Таким образом, алгоритм полного зиккурата для односторонних распределений:
Конечно, для двустороннего распределения результат должен быть инвертирован в 50% случаев. Часто это удобно сделать, выбрав U 0 ∈ (−1,1) и на шаге 3 проверив, | x | < xi + 1.
Поскольку алгоритм зиккурата генерирует только большинство выходных данных очень быстро и требует резервного алгоритма всякий раз, когда x>x 1, он всегда сложнее, чем прямая реализация. Алгоритм отката, конечно, зависит от распределения.
Для экспоненциального распределения хвост выглядит так же, как тело распределения. Один из способов - вернуться к наиболее элементарному алгоритму E = −ln (U 1) и позволить x = x 1 - ln (U 1). Другой - вызвать алгоритм зиккурата рекурсивно и добавить к результату x 1.
Для нормального распределения Марсалья предлагает компактный алгоритм:
Поскольку x 1 ≈ 3,5 для типичных размеров таблиц, тест на шаге 3 почти всегда проходит успешно.
Алгоритм может быть эффективно выполнен с предварительно вычисленными таблицами x i и y i = f (x i), но есть некоторые модификации, чтобы сделать его еще быстрее:
Можно сохранить всю таблицу предварительно вычисленной или просто включить значения n, y 1, A и реализацию f ( y) в исходном коде и вычислить оставшиеся значения при инициализации генератора случайных чисел.
Как описано ранее, вы можете найти x i = f (y i) и y i + 1 = y i + A / x i. Повторить n - 1 раз для слоев зиккурата. В конце у вас должно получиться y n = f (0). Конечно, будет некоторая ошибка округления, но это полезный тест на работоспособность, чтобы убедиться, что она достаточно мала.
При фактическом заполнении значений таблицы просто предположите, что x n = 0 и y n = f (0), и примите небольшую разницу в слое n - Площадь 1 как ошибка округления.
Учитывая начальное (предположение) x 1, вам нужен способ вычисления площади t хвост, для которого x>x 1. Для экспоненциального распределения это просто e, а для нормального распределения, предполагая, что вы используете ненормализованное f (x) = e, это √π / 2 erfc (x / √2). Для более неудобных распределений может потребоваться численное интегрирование.
Имея это в руках, из x 1 вы можете найти y 1 = f (x 1), площадь t в хвост, а площадь базового слоя A = x 1y1+ t.
Затем вычислите серии y i и x i, как указано выше. Если y i>f (0) для любого i < n, then the initial estimate x1 было слишком низким, что привело к слишком большой области A. Если y n< f(0), then the initial estimate x1было слишком большим.
Учитывая это, используйте алгоритм поиска корня (например, метод деления пополам ), чтобы найти значение x 1, которое дает y n − 1 как можно ближе к f (0). В качестве альтернативы ищите значение, которое делает площадь самого верхнего слоя, x n − 1 (f (0) - y n − 1), как можно ближе к желаемому значению A. насколько возможно. Это экономит одну оценку f (x) и на самом деле представляет наибольший интерес.
| journal =() Описывает опасности использования младших разрядов генератора целых случайных чисел. для выбора номера слоя.[W] Когда поддержание чрезвычайно высокого статистического качества является первым приоритетом, и с учетом этого ограничения также желательна скорость, метод Зикгурата часто будет наиболее подходящим выбором.Сравнение нескольких алгоритмов для генерации Гауссовские случайные числа.
