Генерирование случайного числа по заданному закону

Построить программный генератор случайных чисел с заданным законом распределения. Рекомендуется использовать метод обратных функций.
Это задача. Как построить такое генератор?
Понятно есть разные функции rand() и т.п. в разных языках, но как привязать это к закону распределения?

Плотность распределения вероятностей:

Интервал распределения:

0

Нарисуйте график и кидайте случайным образом точки в площадку под графиком. Ордината точки будет иметь нужный закон распределения.

Подробнее:

Собственно,
Если случайно кинуть точку r из 0..s(zmax), то и
Всё! Только требуется, чтоб f(z)>0 при всех z.

Можно убедиться, что такая точка z=s^{-1}(r) действительно имеет плотность s'(z)=f(z).

1

Гм. Для начала практический смысл : случайных чисел будет больше тех, где будет больше значение функции распределения вероятностей?
Например в моей функции плотности распределения так : около 0 будет много св, ближе к pi/4 колво св должно быть меньше.

Так?

0

Сообщение от Mysterious Light Нарисуйте график и кидайте случайным образом точки в площадку под графиком. Ордината точки будет иметь нужный закон распределения.

Всего неск дней назад делал эту задачу. Причем да, даю пользователю именно график. Вот только дальше я Вас не очень понял - что значит "кидайте"? Выбросили случайное "белое" значение от 0 до 1 (пусть z = 1 для простоты) и что? Где результат?

Я делал так: представил график в виде гистограммы (200 столбцов), высота каждого берется из графика. Получил ряд значений (x, y), напр

(0, 0.9) (1, 0.8) (2, 0.75)...

Заменил x на накопленный y
(0, 0.9) (0.9, 0.8)(1.7, 0.75) ...

Теперь выбрасываю случайное число, умножаю его на сумму всех y (по сути нормирую) и нахожу поиском куда (в какой элемент массива) оно попало по х и беру y. Напр после умножения число 1.2, значит результат 0.8 или, более точно интерполировать между 0.8 и 0.85 (ну мне большая точность была не нужна)

Я понял все что Вы написали, кроме реализации. Если можно как-то проще/элегантнее - поясните как

0

Igor3D, Вы хорошо объяснили вариант этого алгоритма, хотя и работаете в конечном приближении.

На всякий случай ещё раз проговорю теорию с картинкой.


Окружим точки 0.2 и 0.6 окрестностями равной длины (на рисунке это 0.02) и зададимся вопросом, в какую СВ попадёт чаще. Очевидно, что в 0.2, потому что f(0.2)>f(0.6). При этом f(z) пропорционально площадке под кривой f в малой окрестности z фиксированной ширины (на рис. пунктир показывает, что слева над ним находится избыточная площадь по сравн. с площадью справа).

Напрашивается утверждение: если мы будем в эту площадь закрашенной фигуры кидать точку равномерно по площади, то её абсцисса (вот здесь я ошибся! абсцисса — это z, он нас интересует, а не ордината) будет удовлетворять закону f(z). Под равномерностю понимается то, что в любые фигуры равной площади имеется равный шанс попасть.

Этого можно достичь, например, разбив всю площадь на квадратики равного размера и случайно выбрав один из них. По сути, Igor3D делает то же самое, когда берёт число от 0 до суммы всех y, у него «накопленный y» играет роль номера квадратика, нумерация по горизонтали слева направо, по вертикали не важно как.
В пределе малых квадратиков (что является более точным методом) речь идёт о настоящий площадях, а не о приближениях, поэтому появляется интеграл функции с верхним переменным пределом — аналог «накопленного y», но непрерывный.

Вернёмся к утверждению. Его доказательство на уровне «квадратиков» тривиально: чем больше f(z), тем больше квадратиков в столбце, тем больше вероятность выбрать один из них. В предельном случае это утверждение является следствием теоремы

Далее у меня была чистая математика. Я говорил, что если s(z) имеет равномерное распределение r, то .

Существенно отличие последнего подхода от предложенного Igor3D заключается в то, что предельный переход в него уже вложен. Если Igor3D вынужден для повышения точности либо неким образом аппроксимировать результат, либо уменшать дискретизацию, то в моём методе (хотя он не мой! просто сейчас его здесь отстаиваю я) формула может быть выведена точно, аналитически.
Мы знаем аналитический вид f(z), мы можем проинтегрировать и получить
Заметим, что . затем можем явно найти обратную функцию:
Ниже приведена гистограмма значений 1 000 000 случайный чисел по этой формуле.

1

Сообщение от Mysterious Light то в моём методе (хотя он не мой! просто сейчас его здесь отстаиваю я) формула может быть выведена точно, аналитически.

Ну как минимум надо иметь аналитическую ф-цию на входе. У меня пользователь задает размеры пузырьков, естественное желание "очень много маленьких и совсем чуть-чуть больших". Но сколько это "много" - никто не знает, включая самого пользователя. Ему надо попробовать/прикинуть. Заряжаю ему график, можно удалять/вставлять точки, менять сглаживание.

Конечно аналитика - дело хорошее, но ее уязвимое место - отсутствие гибкости (а может и общности)

Изображения

 

0

Igor3D, Вы правы. Точнее сказать, есть свои плюсы и минусы в каждом из этих методом и они должны использоваться в разных местах.

Если кратко (но Вы же это и без меня знаете?)
1. Аппроксимация позволяет не знать заранее функцию распр. или работать с монстрами.
2. Она допускает менять функцию на ходу.
3. Аналитическое решение более точное. По крайней мере, точность ограничивается машинной или ещё чем-то, но не шагом.
4. Оно быстрее. Сравните функцию ТС: мой код предлагает 3 действия для получения результата, Ваша — по числу ячеек.
Итак, когда Вашу функцию использовать — Вы описали, а аналитеческое решение — когда функция распр. заведомо известна и нужно за наименшее время нагенерировать много чисел.

0

Сообщение от Mysterious Light Точнее сказать, есть свои плюсы и минусы в каждом из этих методом и они должны использоваться в разных местах.

Конечно, тут спорить не о чем

Сообщение от Mysterious Light 4. Оно быстрее. Сравните функцию ТС: мой код предлагает 3 действия для получения результата, Ваша — по числу ячеек.

Ой нет, здесь все наоборот Двоичный спуск - это 5-6 простых сравнений, я брал 200 ячеек. Ну ладно пусть 20 (для миллиона) - все равно это несоразмеримо с внутренностями sqrt и asin. Железячники (напр OpenGL) часто именно так и ускоряются - заменяют ф-цию таблицей.

Другое дело куда приятнее записать строчку формулы чем городить массив и.т.д - совсем не 1 десяток строк. Ну что поделать если аналитики нет

1

Сообщение от Igor3D Двоичный спуск - это 5-6 простых сравнений, я брал 200 ячеек. Ну ладно пусть 20 (для миллиона) - все равно это несоразмеримо с внутренностями sqrt и asin. Железячники (напр OpenGL) часто именно так и ускоряются - заменяют ф-цию таблицей

Я об этом как-то забыл

0