Как сделать выборку из полиномиального распределения?

Question

Предположим, что у меня есть набор вероятностей [0,1, 0,6, 0,2, 0,1]. Я хочу попробовать местоположения из этого набора вероятностей. например, когда я пробую, я должен получить местоположение 1 довольно часто, чем другие местоположения. Я знаю, что могу реализовать это в Matlab (используя команду mnrnd) или других языках. Тем не менее, я хотел бы знать детали алгоритма c. Я хотел бы знать очень простой алгоритм, который можно использовать для выборки из полиномиального распределения.

Answer 1

Метод грубой силы

Создайте массив, содержащий кумулятивные вероятности, в вашем случае cdf = [0.1, 0.7, 0.9, 1.0]. Сгенерируйте U, равномерное (0,1) случайное значение. Выберите первый индекс так, чтобы cdf[i] <= U. Для небольшого числа результатов это может быть выполнено с помощью линейного поиска (O (n)) или с помощью бинарного поиска (O (log n)), если число результатов велико.

Метод псевдонима

Таблица псевдонимов требует, чтобы вы использовали условную вероятность для построения таблицы первичных элементов и значений псевдонимов таким образом, чтобы для каждой пары первичный / псевдоним общая вероятность была одинаковой. Затем вы используете одно случайное число, чтобы выбрать столбец в таблице (с равной вероятностью), и второе значение, чтобы сделать биномиальный выбор между основным и псевдонимом. Время выполнения составляет O (1) после создания таблицы, что требует O (n) усилий. См. Wikipedia для подробностей или rubygems для реализации Ruby. Обратите внимание, что для каждого результата требуется две формы, так что это не инверсия, и вы не можете делать забавные трюки, такие как генерация антитеза c вариантов .