Метод псевдонима
В вычислительной технике метод псевдонимов представляет собой семейство эффективных алгоритмов выборки из дискретного распределения вероятностей , опубликованных в 1974 году Аластером Дж. Уокером. [ 1 ] [ 2 ] То есть он возвращает целочисленные значения 1 ≤ i ≤ n в соответствии с некоторым произвольным дискретным распределением вероятностей p i . Алгоритмы обычно используют время предварительной обработки O ( n log n ) или O ( n ) , после чего случайные значения могут быть извлечены из распределения за время O (1) . [ 3 ]
Операция
[ редактировать ]Внутри алгоритм обращается к двум таблицам: вероятностей таблице U i и таблице псевдонимов K i (для 1 ≤ i ≤ n ). Чтобы получить случайный результат, бросают игральную кость , чтобы определить индекс i в двух таблицах. , Затем подбрасывают смещенную монету выбирая результат i с вероятностью U i или K i в противном случае (вероятность 1 - U i ). [ 4 ]
Более конкретно, алгоритм работает следующим образом:
- Сгенерируйте равномерную случайную величину 0 ≤ x < 1 .
- Пусть я = ⌊ nx ⌋ + 1 и y = nx + 1 − i . (Это делает i равномерно распределенным на {1, 2, ..., n }, а y равномерно распределенным на [0, 1) .)
- Если y < U i , верните i . Это предвзятый подбрасывание монеты.
- В противном случае верните K i .
Альтернативная формулировка таблицы вероятностей, предложенная Марсальей и др. [ 5 ] как и метод квадратной гистограммы , позволяет избежать вычисления y , вместо этого проверяя условие x < V i = ( U i + i − 1)/ n на третьем этапе.
Генерация таблиц
[ редактировать ]Распределение может быть дополнено дополнительными вероятностями p i = 0, чтобы увеличить n до удобного значения, например степени двойки .
Чтобы сгенерировать две таблицы, сначала инициализируйте U i = np i . При этом разделите записи таблицы на три категории:
- Группа «переполнения», где U i > 1 ,
- «Неполная» группа, где U i < 1 и K i не инициализирован, и
- «точно полная» группа, где U i = 1 или K i Инициализирована .
Если U i = 1 , соответствующее значение K i никогда не будет учитываться и не имеет значения, но значение K i = i является разумным. Это также позволяет избежать проблем, если вероятности представлены в виде чисел с фиксированной точкой , которые не могут точно представлять U i = 1 .
Если не все записи таблицы заполнены точно, повторите следующие шаги:
- Произвольно выберите переполненную запись U i > 1 и недостаточную запись U j < 1 . (Если один из них существует, то должен быть и другой.)
- Выделите неиспользуемое пространство в записи j для результата i , установив K j ← i .
- Удалите выделенное пространство из записи i, заменив U i ← U i - (1 - U j ) = U i + U j - 1 .
- Запись j теперь полностью заполнена.
- Назначьте запись i соответствующей категории на основе нового значения U i .
Каждая итерация перемещает по крайней мере одну запись в категорию «точно полная» (а последняя перемещает две), поэтому процедура гарантированно завершится не более чем через n -1 итераций. Каждая итерация может быть выполнена за время O (1) , поэтому таблицу можно настроить за время O ( n ) .
Все они [ 3 ] : 974 указывает, что ошибки округления с плавающей запятой могут привести к нарушению гарантии, упомянутой в шаге 1. Если одна категория опустошается раньше другой, для оставшихся записей U i может быть установлен в 1 с незначительной ошибкой. Решение, учитывающее плавающую запятую, иногда называют методом Уокера-Возе или методом псевдонима Восе .
Из-за произвольного выбора на шаге 1 структура псевдонима не уникальна.
Поскольку процедура поиска немного быстрее, если y < U i (поскольку с K i не нужно обращаться), одной из целей во время создания таблицы является максимизация суммы U i . Оптимальное выполнение этого оказывается NP-трудной задачей . [ 5 ] : 6 но жадный алгоритм достаточно близок к этому: грабить у самых богатых и отдавать самым бедным. То есть на каждом шаге выбирают наибольшее U i и наименьшее U j . Поскольку для этого требуется сортировка U i , это требует O ( n log n ) времени .
Эффективность
[ редактировать ]Хотя метод псевдонимов очень эффективен, если генерирование равномерного отклонения само по себе происходит быстро, бывают случаи, когда он далек от оптимального с точки зрения использования случайных битов. полной точности Это связано с тем, что он каждый раз использует случайную величину x , даже если требуется всего несколько случайных битов.
Один случай возникает, когда вероятности особенно хорошо сбалансированы, поэтому многие U i = 1 . Для этих значений i y K i не требуется, и создание является пустой тратой времени. Например, если p 1 = p 2 = 1 ⁄ 2 , то 32-битная случайная величина x может использоваться для генерации 32 выходных данных, но метод псевдонима сгенерирует только один.
Другой случай возникает, когда вероятности сильно несбалансированы, поэтому многие U i ≈ 0 . Например, если p 1 = 0,999 и p 2 = 0,001 , то в большинстве случаев для определения применимости случая 1 требуется всего несколько случайных битов. В таких случаях табличный метод, описанный Marsaglia et al. [ 5 ] : 1–4 является более эффективным. Если мы делаем много выборов с одинаковой вероятностью, нам в среднем может потребоваться гораздо меньше, чем один несмещенный случайный бит. Используя методы арифметического кодирования , мы можем приблизиться к пределу, заданному функцией двоичной энтропии .
Литература
[ редактировать ]- Дональд Кнут , Искусство компьютерного программирования , Том 2: Получисловые алгоритмы, раздел 3.4.1.
Реализации
[ редактировать ]- http://www.keithschwarz.com/darts-dice-coins/ Кейт Шварц: подробное объяснение, численно стабильная версия алгоритма Восе и ссылка на реализацию Java.
- https://jugit.fz-juelich.de/mlz/ransampl Йоахим Вуттке: Реализация в виде небольшой библиотеки C.
- https://gist.github.com/0b5786e9bfc73e75eb8180b5400cd1f8 Реализация Лиама Хуанга на C++
- https://github.com/joseftw/jos.weightedresult/blob/develop/src/JOS.WeightedResult/AliasMethodVose.cs C# реализация алгоритма Восе.
- https://github.com/cdanek/KaimiraWeightedList C# реализация алгоритма Восе без нестабильности с плавающей запятой.
Ссылки
[ редактировать ]- ^ Уокер, Эй Джей (18 апреля 1974 г.). «Новый быстрый метод генерации дискретных случайных чисел с произвольным распределением частот». Электронные письма . 10 (8): 127–128. Бибкод : 1974ElL....10..127W . дои : 10.1049/эл:19740097 .
- ^ Уокер, Аластер Дж. (сентябрь 1977 г.). «Эффективный метод генерации дискретных случайных величин с общими распределениями» . Транзакции ACM в математическом программном обеспечении . 3 (3): 253–256. дои : 10.1145/355744.355749 . S2CID 4522588 .
- ^ Jump up to: а б Восе, Майкл Д. (сентябрь 1991 г.). «Линейный алгоритм генерации случайных чисел с заданным распределением» (PDF) . Транзакции IEEE по разработке программного обеспечения . 17 (9): 972–975. CiteSeerX 10.1.1.398.3339 . дои : 10.1109/32.92917 . Архивировано из оригинала (PDF) 29 октября 2013 г.
- ^ «Дротики, кости и монеты: выборка из дискретного распределения» . KeithSchwarz.com . 29 декабря 2011 года . Проверено 27 декабря 2011 г.
- ^ Jump up to: а б с Марсалья, Джордж ; Цанг, Вай Ван; Ван, Цзинбо (12 июля 2004 г.), «Быстрая генерация дискретных случайных величин» (PDF) , Journal of Statistical Software , 11 (3): 1–11, doi : 10.18637/jss.v011.i03