Как генерировать числа с линейно заданной вероятностью?

Question

[Anikav]

Здравствуйте.

Есть задача генерировать числа в заданном диапазоне. Причем вероятность появления чисел задается, она не одинакова.

Приведу пример вызова нужной функции:
random([[0, 0], [10, 50], [15, 10], [20, 40]])



Тут диапазон чисел для генерации от 0 до 20. Вероятность появления 0 - 0%.
10 - 50%, 15 - 10%, 20 - 40%.

Соответственно, например, число 5 появится уже с 25% вероятностью, число 1 с 5% вероятностью и так далее. Количество пар значений на входе в функцию может быть любым, диапазон тоже любым. Генерируемые числа не обязательно должны быть целыми.

Как реализовать такую функцию? Может есть уже готовые реализации?

P.S. В комментариях справедливо подсказали, что сумма вероятностей на моем графике получится больше 100%, что невозможно. Поэтому можно считать что указаны не проценты вероятности, а единицы вероятности.

Comments

[Сергей Соколов]

Если и дробные числа допустимы, то ваш график невозможен.
Суммарная вероятность только на отрезке 0..10 уже превышает 100%: 10 * 50 / 2 = 250%

[CHolfield]

Сергей Соколов, у него вероятность непостоянна на отрезках, тут по-хорошему интегрировать надо)

[Сергей Соколов]

С только-целыми можно дискретно расписать вероятности:

0: 0%
1: 5%
2: 10%
3: 15%
4: 20%
5: 25%
...
10: 50%

Но и тут сумма превысит 100%.

[Anikav]

Сергей Соколов, абсолютно верно. Будем считать это единицами вероятности, а не процентами

[CHolfield]

Anikav, ШТА?

[dmshar]

Anikav, Простите, а что такое "единица вероятности"?

[Anikav]

dmshar, считайте это долей от суммы чисел, идущих второй позицией в массивах аргумента функции примера

Answer 1

[Alexander Movchan]

Поделите фашу функцию на площадь под ней и получите плотность вероятности, возьмите интеграл плотности (не сложно для линейной функции) и получите функцию распределения.
Постройте функцию обратную функции распределения, сгенерируйте число равномерно распределённое от 0 до 1 и вычислите значение полученной функции.

Comments

[Anikav]

Вроде звучит неплохо, но проблема начинается с того, что у меня нет функции, а только точки. Насколько я знаю, можно по точкам сделать функцию, но тогда функция будет N порядка. А точек может быть много и порядок функции улетит до небес.

[Alexander Movchan]

Anikav, интерполируйте значения. У вас же на графике точки соеденены линиями, соответсвенно используйте линейную интерполяцию.

Answer 2

[Сергей Соколов]

Для начала простой случай, где вероятность линейна на всём диапазоне, один сегмент.
Генератор случайных чисел даёт дробное от 0 до 1 с постоянной вероятностью.

Теперь вспомните график параболы y = x^2 Там на шаге x от 0 до 1, y растет от 0 до 1, на шаге от 3 до 4 y растёт уже от 9 до 16, на 7. Взяв равномерно-случайную величину от 0 до 16, квадратный корень из неё неравномерно попадёт на диапазон от 0 до 4. Вероятнее на диапазон 3-4, чем на 0-1. И вероятность попадания в точку x будет прямо пропорциональна x.

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

Answer 3

[rPman]

Если параметры задают вероятность дискретно (на картинке кстати у вас не дискретно а сложные нелинейные зависимости, т.е. 1 встречается почти в 50 раз реже 10, смею предположить что вам ТАК не надо) на интервалах, типа от [0-10) - 50 то решайте проблему в лоб, сначала выбирайте интервал в соответствии с вероятностями (если задаете количественно, то это сумма заданых значений - максимальное значение, а интервал значения rand - соответствующее значение для суммы до этого интервала и с ним, после выбора интервала просто делаете повторный rand так как в пределах интервала вам нужно равномерное.

Comments

[Anikav]

Мне как раз нужно, чтобы 1 встречался в 50 раз реже, чем 10. 15 - в 5 раз реже, чем 10 итд.

Answer 4

[polybook]

Генерируете пару случайных чисел с равномерным распределением. Предположим, первое х=10. Если второе лежит под вашим графиком, т.е. у