Rejection sampling и Reservoir sampling

Разобрался на днях с двумя интересными алгоритмами про выборки.

Rejection sampling находил в задачах вроде «с помощью функции, которая гарантирует равновероятное выпадение целого числа в интервале [1...7], создайте функцию, которая делает тоже самое, но в интервале от [1...10]». Ещё такая же задача была однажды у меня на собесе в Яндексе: дана монетка с вероятностью выпадения орла/решки ½. С помощью этой монетки нужно смоделировать вероятность ⅓. Я интуитивно дошёл до решения и доказал, что это работает, но конкретно названия группы алгоритмов не знал.

Reservoir sampling про то, как смоделировать равновероятный выбор элемента при неизвестной конечной размерности множества вариантов.

Поделиться
Отправить
Популярное