ГСЧ с заданной плотностью распределения

[Schrodinger's cat]

Всем доброго здоровья и хорошего настроения. С прошедшим новым годом!
Необходимо сделать эффективный алгоритм генератора случайных чисел (ГСЧ) с заданной плотностью распределения которая задается функцией (так же необходим еще один вариант когда задается вектором значений, что в целом очень похоже на функцию).
Есть классический алгоритм (похож на методы Монте Карло) когда генерируют 2 случайных значения с равномерным распределением. Первое отправляют в функцию плотности, результат сравнивают со вторым значением. Если второе значение меньше то возвращаем первое в качестве результата, если больше повторяем все сначала пока не окажемся ниже функции.
Очевидно что довольно значительная часть телодвижений осуществляется в пустую, если мы попадаем выше функции распределения.
Существуют ли более эффективные способы получения случайного значения с заданной плотностью распределения?
Под эффективными понимаю отсутствие или значительное снижение операций не приводящих к результату а так же уменьшение числа операций в целом.

[artur_k]

Это не поможет: Метод обратного преобразования ?
По заданной плотности распределения надо один раз построить вектор значений обратной функции распределения, и потом, используя его, за один шаг из равномерно распределенной случайной величины получать случайную величину с нужным распределением.

[alisa-lebovski]

Вот ссылка на лекции моего друга - https://disk.yandex.ru/i/aJKxGceD-W-6_Q
См. с. 4-6.

[Schrodinger's cat]

artur_k, alisa-lebovski спасибо за подсказки.

artur_k в сообщении #1576544 писал(а):

Метод обратного преобразования

Выглядит интересно.
Для случая когда можно посчитать руками обратную функцию ситуация ясна.
А как быть если аналитическая функция неизвестна (но вычислить y по x возможно численно) или например задана вектором значений?
Вообще говоря генератор хочу использовать в том числе для одного алгоритма в котором функция плотности будет задана вектором и она будет меняться на каждом шаге. Поэтому тут нахождение обратной функции руками отпадает, нужен алгоритм и желательно не сильно тяжеловесный.

[Dmitriy40]

Если функция плотности задана вектором, то фактически кусочно-линейно, ведь так? Меняем или его сам или дополнительный вектор той же размерности чтобы значения "плотности" шли с накоплением, нормируем на 1, получаем разбиение отрезка [0,1) на кусочки переменной длины (в том числе и нулевой). Генерим случайное число в этом отрезке и выбираем соответствующее кусочку значение.
Лишних действий: суммирование вектора плотности, нормирование (можно и не делать, тогда случайное число генерить не до 1, а до полученной суммы), поиск и выборка из вектора. Последнюю можно сделать двоичным поиском (вряд ли размерность задачи такова что придётся думать что-то более быстрое), а если сумма целочисленна и невелика, то и сформировать таблицу/вектор пересчёта из интервала до суммы в реальное значение (что не сложнее суммирования).

[Schrodinger's cat]

Цитата:

Метод обратного преобразования

Попробовал суммировать как Вы сказали, потом просто меняю местами x и y получаю обратную кусочно линейную функцию. Которую пробую интерполировать Лагранжем, на каких то примерах получается нормально, на каких то осциллирует, феномен Рунге все портит. Можно было бы попробовать что то выжать из узлов Чебышева, с этой темой я не знаком, но не думаю что это кардинально решит проблему ИМХО.
Можно ли что то придумать более устойчивое чем Лагранж?

Dmitriy40 в сообщении #1576570 писал(а):

Генерим случайное число в этом отрезке и выбираем соответствующее кусочку значение.

Вы имеете в виду генерируем y и по нему обратно находим x. Так как шкала получается нелинейной нужен поиск. Понимаю. Работать будет. Но хочется более красивое решение.
Я вот думал разбить поверхность графика плотности распределения на регулярную прямоугольную сетку. Ячейки которой полностью лежат под функцией принимаем во внимание, которые лежат выше отбрасываем. Потом если положить на бок все столбики сетки и склеить в единый вектор, то за счет того что величины ячеек все одинаковые можно по одному случайному числу сразу получить индекс ячейки этого вектора, а это значит и практически сразу получить значение. Проблему составляют те ячейки которые не полностью попадают под функцию. При попадании в них все равно нужно посмотреть попали ли мы под функцию или над и если над, то мы попали мимо и нужно начать алгоритм заново.
Но все равно это значительный прогресс по сравнению с классическим методом так как ячейки находящиеся полностью над функцией мы игнорируем, а это значительная площадь графика где телодвижения оказываются напрасными.
Только что вычитал, что есть похожий алгоритм (4.4 Аппроксимация плотностей) но в нем сетка нерегулярная а значит требуется поиск.

alisa-lebovski в сообщении #1576547 писал(а):

Вот ссылка на лекции моего друга

Прошу прощения, на стр.4 как второй алгоритм называется? Что то там "Метод порядк статк"?!

[alisa-lebovski]

Schrodinger's cat в сообщении #1576600 писал(а):

Прошу прощения, на стр.4 как второй алгоритм называется?

Метод порядковых статистик.

[Schrodinger's cat]

alisa-lebovski Спасибо.