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

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

Например, у меня есть набор чисел, которые я хочу сгенерировать. Скажем, они помечены как 1-3 следующим образом.

1: 4%, 2: 50%, 3: 46%

По сути, проценты - это вероятность того, что они появятся в выходных данных генератора случайных чисел. У меня есть генератор псевдослучайных чисел, который будет генерировать равномерное распределение в интервале [0, 1]. Есть ли способ сделать это?

Нет никаких ограничений на количество элементов, которые я могу иметь, но% прибавит до 100%.

Одним из лучших алгоритмов выборки из дискретного распределения является метод псевдонимов .

Метод псевдонима (эффективно) предварительно вычисляет двумерную структуру данных, чтобы разделить прямоугольник на области, пропорциональные вероятностям.

В этой схеме из ссылочного сайта, прямоугольник единичной высоты был разделен на четыре вида областей - в дифференцирован по цвету - в пропорциях , 1 / 3 , 1 / 12 и 1 / 12 , в порядок выборки повторно из дискретного распределения с этими вероятностями. Вертикальные полосы имеют постоянную (единичную) ширину. Каждый разделен на одну или две части. Идентификационные данные частей и расположение вертикальных делений хранятся в таблицах, доступных через индекс столбца.$1/2$$1/3$$1/12$$1/12$

Таблица может быть выбрана в два простых шага (по одному для каждой координаты), требующих генерации только двух независимых унифицированных значений и вычисления Это улучшает вычисление O ( log ( n ) ), необходимое для инвертирования дискретного CDF, как описано в других ответах здесь.$O(1)$$O(\log(n))$

Вы можете сделать это легко в R, просто укажите нужный размер:

sample(x=c(1,2,3), size=1000, replace=TRUE, prob=c(.04,.50,.46))

В вашем примере, скажем, вы рисуете псевдослучайное значение Uniform [0,1] и называете его U. Затем выведите:

1, если U <0,04

2, если U> = 0,04 и U <0,54

3, если U> = 0,54

Если указанный% является a, b, ..., просто выведите

значение 1, если U

значение 2, если U> = a и U <(a + b)

и т.п.

По сути, мы отображаем% в подмножества [0,1], и мы знаем, что вероятность того, что равномерное случайное значение попадет в любой диапазон, является просто длиной этого диапазона. Упорядочение диапазонов кажется самым простым, если не уникальным, способом сделать это. Это предполагает, что вы спрашиваете только о дискретных распределениях; для непрерывного, может сделать что-то вроде «выборки отклонения» ( запись в Википедии ).

Предположим, есть возможных дискретных результатов. Вы делите интервал [ 0 , 1 ] на подынтервалы на основе функции кумулятивной массовой вероятности F , чтобы получить разделенный ( 0 , 1 ) интервал$m$$[0,1]$$F$$(0,1)$

где и F ( 0 ) ≡ 0 . В вашем примере m = 3 и$I_{j} = (F(j-1), F(j))$$F(0) \equiv 0$$m = 3$

так как и F ( 2 ) = .54 и F ( 3 ) = 1 .$F(1) = .04$$F(2) = .54$$F(3) = 1$

Затем вы можете сгенерировать с распределением F, используя следующий алгоритм:$X$$F$

(1) генерировать $U \sim {\rm Uniform}(0,1)$

(2) Если , то X = j .$U \in I_{j}$$X = j$

• Этот шаг можно выполнить, посмотрев, меньше ли чем каждая из совокупных вероятностей, и увидев, где происходит точка изменения (с на ), что должно зависеть от использования логического оператора в любом используемом языке программирования и найти, где первое происходит в векторе.$U$TRUEFALSEFALSE

Отметим, что будет находиться точно в одном из интервалов I j, поскольку они не пересекаются и разбивают [ 0 , 1 ] .$U$$I_{j}$$[0,1]$

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

Это хорошо в том смысле, что число значений / вероятностей может быть бесконечным, но вам нужно вычислять вероятности только тогда, когда вы приближаетесь к этим числам (для чего-то вроде генерации по пуассоновскому или отрицательному биномиальному распределению).

Если у вас есть конечный набор вероятностей, но вы будете генерировать из них много чисел, то было бы более эффективно отсортировать вероятности так, чтобы вы вычли наибольшее первое, затем второе наибольшее следующее и так далее.

Прежде всего, позвольте мне обратить ваше внимание на библиотеку Python с готовыми к использованию классами для генерации целых или случайных чисел с плавающей запятой, которые следуют за произвольным распределением.

Вообще говоря, существует несколько подходов к этой проблеме. Некоторые из них линейны по времени, но требуют большого объема памяти, другие запускаются за время O (n log (n)). Некоторые оптимизированы для целых чисел, а некоторые определены для круговых гистограмм (например: генерация случайных временных точек в течение дня). В вышеупомянутой библиотеке я использовал эту статью для целых чисел и этот рецепт для чисел с плавающей запятой. У него (все еще) отсутствует поддержка круговой гистограммы, и он, как правило, грязный, но работает хорошо.

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

Следующая функция рисует самый низкий из $N$ равномерно распределенные случайные числа в интервале $[a,1)$, Позволять$r$ быть случайным числом из $[0,1)$,

Вы можете использовать эту функцию, чтобы нарисовать восходящий ряд$(a_i)$ of $N$ uniformly distributed random numbers in [0,1). Here is an example with $N = 10$:

$a_0 = \text{next}(10, 0)$
$a_1 = \text{next}(9, a_0)$
$a_2 = \text{next}(8, a_1)$
$\dots$
$a_9 = \text{next}(1, a_8)$

While drawing that ascending series $(a_i)$ of uniformly distributed numbers, iterate over the set of probabilities $P$ which represents your arbitraty (yet finite) distribution. Let $0 \leq k < |P|$ be the iterator and $p_k \in P$. After drawing $a_i$, increment $k$ zero or more times until $\sum p_0 \dots p_k > a_i$. Then add $p_k$ to your sample and move on with drawing $a_{i+1}$.

Example with the op's set $\{(1, 0.04), (2, 0.5), (3, 0.46)\}$ and sample size $N = 10$:

i  a_i    k  Sum   Draw
0  0.031  0  0.04  1
1  0.200  1  0.54  2
2  0.236  1  0.54  2
3  0.402  1  0.54  2
4  0.488  1  0.54  2
5  0.589  2  1.0   3
6  0.625  2  1.0   3
7  0.638  2  1.0   3
8  0.738  2  1.0   3
9  0.942  2  1.0   3

Sample: $(1, 2, 2, 2, 2, 3, 3, 3, 3, 3)$

If you wonder about the $\text{next}$ function: It is the inverse of the probability that one of $N$ uniformly distributed random numbers lies within the interval $[a, x)$ with $x \leq 1$.