Случайный алгоритм с регулируемой вероятностью

Question

Я ищу алгоритм (независимо от того, какой язык программирования, может быть, псевдокод?), Где вы получаете случайное число с различной вероятностью.

Например:

генератор случайных чисел, который имитирует кости, где шанс на «6» составляет 50%, а для других 5 номеров это 10%.

Алгоритм должен быть масштабируемым, потому что это моя точная проблема:

У меня есть массив (или базу данных) элементов, из которых я хочу выбрать 1 случайный элемент. Но каждый элемент должен иметь другую вероятность, которую нужно выбрать. Поэтому моя идея заключается в том, что каждый элемент получает номер . И это число, деленное на сумму всех чисел, приводит к случайному выбору случайного выбора .

Кто-нибудь знает хороший язык программирования (или библиотеки) для решения этой проблемы? Лучшим решением будет хороший SQL-запрос, который обеспечивает 1 случайную запись. Но я также был бы доволен каждым намеком или попыткой на другом языке программирования.

Answer 1

Простой алгоритм для ее достижения является:

1. Создать auexillary массив, где sum[i] = p1 + p2 + ... + pi. Это делается только один раз.
2. Когда вы рисуете число, нарисуйте число r с равномерным распределением по [0,sum[n]) и двоичный поиск первого номера выше, чем равномерно распределенное случайное число. Это можно сделать, используя binary search эффективно.

Легко видеть, что на самом деле вероятность r лежать в определенном диапазоне [sum[i-1],sum[i]), действительно sum[i]-sum[i-1] = pi
(В приведенном выше, мы рассматриваем sum[-1]=0, для полноты картины)

---

Для ваш куб пример:

у вас есть:

p1=p2=....=p5 = 0.1 
p6 = 0.5 

Во-первых, вычислить sum массив:

sum[1] = 0.1 
sum[2] = 0.2 
sum[3] = 0.3 
sum[4] = 0.4 
sum[5] = 0.5 
sum[6] = 1 

Затем, каждый раз, когда вам нужно сделать ряд: Нарисовать случайное число r в [0,1) и выбрать номер ближайшего к нему, например:

r1 = 0.45 -> element = 4 
r2 = 0.8 -> element = 6 
r3 = 0.1 -> element = 2 
r4 = 0.09 -> element = 1 

Answer 2

Альтернативный ответ. Ваш пример был в процентах, поэтому настройте массив со 100 слотами. A 6 - 50%, поэтому установите 6 из 50 слотов. От 1 до 5 - по 10% каждый, поэтому поставьте 1 на 10 слотов, 2 на 10 слотов и т. Д., Пока не заполните все 100 слотов в массиве.Теперь выберите один из слотов в случайном порядке, используя равномерное распределение в [0, 99] или [1, 100] в зависимости от языка, который вы используете.

Содержимое выбранного слота массива даст вам необходимый вам дистрибутив.

ETA: На второй мысли, вы на самом деле не нужен массив, просто использовать интегральную вероятность эмулировать массив:

r = rand(100) // In range 0 -> 99 inclusive. 

if (r < 50) return 6; // Up to 50% returns a 6. 
if (r < 60) return 1; // Between 50% and 60% returns a 1. 
if (r < 70) return 2; // Between 60% and 70% returns a 2. 
etc. 

Вы уже знаете, что номера находятся в каких слотах, так что просто использовать интегральную вероятность выбрать виртуальный слот: 50; 50 + 10; 50 + 10 + 10; ...

Будь осторожен крайние случаи и будет ли ваш ГСЧ 0 -> 99 или 1 -> 100.