2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 ГСЧ с заданной плотностью распределения
Сообщение08.01.2023, 15:15 


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

 Профиль  
                  
 
 Re: ГСЧ с заданной плотностью распределения
Сообщение08.01.2023, 22:26 


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

 Профиль  
                  
 
 Re: ГСЧ с заданной плотностью распределения
Сообщение08.01.2023, 23:22 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: ГСЧ с заданной плотностью распределения
Сообщение09.01.2023, 10:34 


31/08/22
179
artur_k, alisa-lebovski спасибо за подсказки.

artur_k в сообщении #1576544 писал(а):
Метод обратного преобразования

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

 Профиль  
                  
 
 Re: ГСЧ с заданной плотностью распределения
Сообщение09.01.2023, 11:05 
Заслуженный участник


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

 Профиль  
                  
 
 Re: ГСЧ с заданной плотностью распределения
Сообщение09.01.2023, 14:22 


31/08/22
179
Цитата:
Метод обратного преобразования

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

Dmitriy40 в сообщении #1576570 писал(а):
Генерим случайное число в этом отрезке и выбираем соответствующее кусочку значение.

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

alisa-lebovski в сообщении #1576547 писал(а):
Вот ссылка на лекции моего друга

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

 Профиль  
                  
 
 Re: ГСЧ с заданной плотностью распределения
Сообщение09.01.2023, 15:22 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
Schrodinger's cat в сообщении #1576600 писал(а):
Прошу прощения, на стр.4 как второй алгоритм называется?
Метод порядковых статистик.

 Профиль  
                  
 
 Re: ГСЧ с заданной плотностью распределения
Сообщение09.01.2023, 16:39 


31/08/22
179
alisa-lebovski Спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group