Единая выборка из симплекса

29

Я ищу алгоритм для генерации массива из N случайных чисел, так что сумма из N чисел равна 1, а все числа лежат в пределах от 0 до 1. Например, N = 3, случайная точка (x, y, я) должен лежать в треугольнике:

x + y + z = 1
0 < x < 1
0 < y < 1
0 < z < 1

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

Ruofeng
источник
Каково целевое распределение? Что вы пробовали?
Рафаэль
3
Обратите внимание, что всегда есть выборка отклонения : выберите одинаковых чисел и отклоните, если числа не складываются до 1 . Здесь ожидаемое количество итераций неоправданно велико, поэтому вы должны сделать что-то еще. n1
Рафаэль

Ответы:

28

Давайте сначала предположим, что вы хотите попробовать в течение

x + y + z = 1
0 ≤ x ≤ 1
0 ≤ y ≤ 1
0 ≤ z ≤ 1

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

Теперь у вас есть выборка точки из симплекса . В 3-м примере вы получите 2-й симплекс (треугольник), реализованный в 3-м.

Как подобрать точку случайным образом равномерно обсуждалось в этом сообщении в блоге (см. Комментарии).

Для вашей проблемы это будет означать, что вы берете случайных чисел из интервала ( 0 , 1 ) , затем вы добавляете 0 и 1, чтобы получить список из n + 1 чисел. Вы сортируете список, а затем записываете различия между двумя последовательными элементами. Это дает вам список из n чисел, которые будут суммироваться до 1 . Кроме того, эта выборка является равномерной. Эту идею можно найти в Donald B. Rubin, The Bayesian bootstrap Ann. Statist. 9, 1981, 130-134.n1(0,1)01n+1n1

Например, ( ) у вас есть три случайных числа, затем вы получаете отсортированную последовательность, и это дает различия , и по построению эти четыре числа суммируют до 1.n=40.4 0.2 0.10 0.1 0.2 0.4 10.1 0.1 0.2 0.6

Другой подход заключается в следующем: сначала выборка из гиперкуба (о которой вы забыли x+y+z=1), а затем нормализация точки выборки. Нормализация - это проекция гиперкуба на d - 1 -симплекс. Интуитивно понятно, что точки в центре симплекса имеют больше «точек перед изображением», чем снаружиdd1, Следовательно, если вы делаете выборку равномерно из гиперкуба, это не даст вам равномерную выборку в симплексе. Однако, если вы производите выборку из гиперкуба с соответствующим экспоненциальным распределением, этот эффект отменяется. Рисунок дает вам представление о том, как будут использоваться оба метода. Однако я предпочитаю метод «сортировки» из-за его простой формы. Это также легче реализовать.

Пример 2 методов отбора проб

A.Schulz
источник
n(0,1)
Я обратился к вашему вопросу в расширенном ответе.
А.Шульц
1
Есть ли простое доказательство того, что сортировка дает равномерное распределение? У меня есть только элементарный фон в вероятности, поэтому бумага над моей головой.
Чао Сюй
5
n(0,1)nn1(0,1)
1
@ Ориент: Пожалуйста, задавайте вопросы в отдельном сообщении и не злоупотребляйте комментариями для этого.
А.Шульц
8

Это добавить к существующим ответам.

Devroye является отличным справочником для вопросов такого рода. В главе 7 приведены алгоритмы, необходимые для генерации статистики единообразного порядка, за которой следует OP.

n[0,1]O(nlogn)nx1,,xnExp(1)

(yi)1in=1ixj1nxj
O(n)

[0,1]2x+3y+z=5

PKG
источник
Если я последую ответу здесь: stackoverflow.com/questions/2106503/… Тогда генерация случайного числа из экспоненциального распределения включает в себя оценку логарифма, который может быть немного медленным.
Р зу
3
X[0] = 0
for i = 1 to N-1
    X[i] = uniform(0,1)
X[n] = 1
sort X[0..N]
for i = 1 to N
    Z[i] = X[i] - X[i-1]
return Z[1..N]

Здесь uniform(0,1)возвращает действительное число независимо и равномерно распределенное между 0 и 1.

JeffE
источник
5
Это ответ А. Шульца в коде без объяснения, верно?
Рафаэль
1

См. Эту статью : Смит, Н. и Тромбл, Р., Выборка равномерно из простого симплекса .

сельдь
источник
2
Пожалуйста, отформатируйте ваш ответ в удобочитаемой форме: вы пишете для людей, а не для компилятора bibtex. Кроме того, если статья доступна в Интернете, вам будет гораздо удобнее предоставить ссылку.
Дэвид Ричерби