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

Question

[Евгений Петряев]

Допустим есть вектор с целыми числами от 0 до 6 включая. У меня есть гуй где напротив каждого числа от 0 до 6 включая стоит число от 0.00 до 1 (вероятности) причем в сумме эти 7 чисел дают 1цу. Как сделать генератор чтобы выдавал числа от 0 до 6 включая с этими заданными вероятностями и как бы еще сделать чтобы гуй при изменении чисел вероятностей в ячейках как-то нормировал сумму всех вероятностей в 1цу?

Comments

[Евгений Петряев]

а может сделать всего 100 элементов где например 20 нулей, 25 единиц и т.д. откуда у нуля будет вероятность 0.2, у единицы 0.25 и уже из этих 100 элементов выбирать равновероятностно?
мне на плюсах надо или на крайняк на СИ

Answer 1

[Griboks]

В каждом языке программирования присутствует специальная функция для генерирования случайных чисел от 0 до 1. Соответственно, вы представляете ваши числа в виде интервалов, а случайное число в виде относительной координаты. В какой интервал укажет координата, то число и является искомым.

Пример
Дана таблица:

1 - 0.9
2 - 0.8
3 - 0.7

Тогда интервалы будут следующие: 0-0.9, 0.9-1.7, 1.7-2.4.
Допустим, сгенерировано случайно число 0.65 - примем его за относительные координаты.
Переводим координаты в абсолютные 0.65*2.4=1.56. Следовательно, случайно число попадает в интервал 0.9-1.7, значит искомое число - 2.

Answer 2

[Максим Припадчев]

приведу пример кода на python с использованием библиотеки numpy

import numpy as np
sample_space = [0,1,2,3,4,5,6]
probabilities = [0.3,0.2,0.05,0.05,0.1,0.15,0.15]
n = 20
result = np.random.choice(sample_space,size=n,p=probabilities)
print(result)

sample_space - лист откуда будет производится выборка
probabilities - лист соответствующих вероятностей (0 с вероятностью 0.3, 1 с вероятностью 0.2, и.т.д) вероятности я взял свои, вы поставите свои главное чтобы вероятности в сумме были 1.
n - количество сгенерированных чисел для примера я взял 20, вы зададите сколько ва нужно.
функция choice также имеет параметр replace по умолчанию установленный в True он регулирует может ли ранее выбранный элемент, быть выбранном снова, в нашем случае могут ли быть повторения при выборке из sample_space (по умолчанию может).
Насчет нормирования вероятностей, такое возможно только если n=2, или если есть дополнительная информация позволяющая создать систему уравнений. В вашем случае это невозможно например
возьмем нашу дистрибуцию мы имеем 0 с вероятностью 0.3, мы меняем ее 0.2, у нас будет существовать бесконечное количество сценариев как мы можем раскидать 0.1 на остальные 6 элементов. Уникального решения не существует.

Answer 3

[alexalexes]

Как сделать логику гуя:
Выставляете все интервалы поровну 1 / n или рандомно-нормированно.
При движении ползунка n он "отбирает" значение приращения у ползунка n+1.
Ползунок n+1 ограничивает движение ползунка n.
Последний ползунок влияет на значение первого.

Answer 4

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

Можно разрешить вводить любые неотрицательные веса в GUI.
Например, [ 1, 1, 1, 100000000, 100, 10, 1 ]

Сложить все веса: это длина отрезка, на котором равновероятно выбрать любую точку.
И посмотреть, на «чей» отрезок она попала.

Например, для всего 3 вариантов ввели значение 1, 2, 5. В сумме 8.
Получаем равновероятно случайное число от 0 до 8 [включая 0, исключая 8):

-++=====
01234567

Например, выпало 4.321, попадает на отрезок принадлежащий варианту «3»
(который с «вероятностью» весом 5 )

Comments

[res2001]

Это то же самое, что предлагал Griboks но другими словами.
Ваши веса - это интервалы у Griboks, числа не обязательно должны быть целыми.
Веса или интервалы можно представить как вероятности pi, в диапазоне [0; 1]. Сумма вероятностей должна быть равна 1, как требует ТС. Вес или интервал находится из вероятности как pi*length, где length - ваша длина отрезка (или сумма интервалов по Griboks). lentgh - можно взять как длину вектора из вопроса (6) или любое другое число >=6. Чем больше length, тем точнее попадание случайного числа в заданный диапазон при округлении, соответственно, точнее распределение.

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

res2001, это распространённое решение, его упрощенное объяснение.

Answer 5

[Mercury13]

Алгоритм простой, подготовка O(n), расчёт O(log n). Вычислить функцию распределения (она кусочно-постоянная). Сгенерировать равномерно распределённое число, определить, в какой кусок оно попадает.
Для целых «шансов» — если сумма этих «шансов» 123, то генерируем число от 0 до 122, а дальше понятно.

Алгоритм многопамятный, подготовка O(sum a_i), расчёт O(1). Годится только для небольших целых шансов.
Его предложил Сергей Соколов.

Алгоритм палочный, подготовка O(n log n), расчёт O(1).
https://elementy.ru/problems/2263/Razdelyay_i_uravnivay
Алгоритм легко переделывается на ситуацию, когда все палки имеют целую длину, резать-клеить их можно только по целым длинам, при этом последняя палка может оказаться короче. В общем, простым делением определяем, в какую палку попали, а потом доступом к массиву и сравнением — в какой компонент данной палки.

Например, у нас есть четыре шанса — 100, 20, 2 и 1. Палочный алгоритм даст, например, такие палки (у всех длина 31, и у последней — 30).
Палка [0..31): 1 (x<1); 100 (x>=1)
Палка [31..62): 2 (x<33); 100 (x>=33)
Палка [62..93): 20 (x<82); 100 (x>=82)
Палка [93..123): всегда 100
Разыграв 32, получаем: [32/31] = 1, первая палка. 32<33 — та шмотка, у которой два шанса.

Comments

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

целочисленность необязательна. Совсем.

Например, шансы 1.1, 2.2, 3.3
Сумма 6.6
Math.random() * 6.6 даст некое нецелое меньше 6.6

Дальше последовательное сравнение c накапливающейся суммой шансов.

Откуда здесь O(n log n)? Просто O(n)

[Mercury13]

Сергей Соколов, Сравнение с накапливающейся суммой — это «алгоритм простой». O(log n) — потому что двоичный поиск.

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

Mercury13, что-то не представляю, как двоичный поиск может помочь в задаче поиска, в какой из отрезков попадаем.

[Mercury13]

Сергей Соколов, Вычисляем обратную функцию распределения: до 1/6 → вернуть 1, до 1/2 → вернуть 2, до ∞ → вернуть 3. Генерируем, например, 0,2345, берём функцию Си++ upper_bound, и возвращаем 2.

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

Mercury13, не вижу тут двоичного поиска.

[Mercury13]

Сергей Соколов, Хорошо, возьмём больше точек: 0,1, 0,2 и т.д.
0,2345 сравниваем с 0,5 → меньше. Сравниваем с 0,2, например → больше. Теперь с 0,3 → меньше. Всё, нашли подходящий диапазон за три сравнения.

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

Mercury13, плохой пример: много предположений. Откуда известно, с кем сравнивать? По индексу в массиве breakpoints? Чтобы построить этот массив сначала придётся пройти по всем с накопительной суммой. Напомню условия.
Дано: длины отрезков.
Взять линейно-случайное число (в каком диапазоне?)
и найти, какому на какой отрезок оно попадает.

[Mercury13]

Сергей Соколов, Обычно генераций нужно на порядки больше, чем подготовок — потому и такие алгоритмы.

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

Mercury13, а, ну так да – только в таком контексте имеет смысл бинарный поиск: один раз сгенерили интервалы, сто-тыщ-пятьсот раз сгенерили случайное с этим распределением.