Как сгенерировать случайное число из указанного дискретного распределения? - PullRequest
9 голосов
/ 17 ноября 2010

Допустим, у нас есть некоторое дискретное распределение с конечным числом возможных результатов. Можно ли сгенерировать случайное число из этого распределения быстрее, чем в O (logn), где n - число возможных результатов?

Как сделать это в O (logn):
- Создать массив с кумулятивной вероятностью (Array [i] = Вероятность того, что случайное число будет меньше или равно i)
- Генерировать случайное число из равномерного распределения (обозначим его через k)
- Найти наименьшее i такое, что k - это наше случайное число.

1 Ответ

6 голосов
/ 21 ноября 2010

Метод псевдонима Уокера может рисовать выборку за постоянное наихудшее время, используя несколько вспомогательных массивов размера n, которые необходимо предварительно вычислить. Этот метод описан в главе 3 книги Деврой по сэмплированию и реализован в функции R sample (). Вы можете получить код из исходного кода R или этой ветки . Бумага 1991 от Vose претендует на снижение стоимости инициализации.

Обратите внимание, что ваш вопрос не является четко определенным, если вы не укажете точную форму ввода и сколько случайных чисел вы хотите нарисовать. Например, если входные данные представляют собой массив, дающий вероятность каждого результата, тогда ваш алгоритм не является O (log n), потому что он требует сначала вычисления кумулятивных вероятностей, что занимает O (n) времени из входного массива.

Если вы намереваетесь взять много образцов, тогда стоимость создания одного образца не так важна. Вместо этого важна общая стоимость генерации m результатов и требуемая пиковая память. В связи с этим метод псевдонимов очень хорош. Если вы хотите сэмплировать все сразу, используйте алгоритм O (n + m), опубликованный здесь , а затем перемешайте результаты.

...