Равномерная выборка из простого

Question

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

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

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

Answer 1

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

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

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

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

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

Для вашей проблемы это будет означать, что вы берете случайные числа $ N-1 $ с интервалом $ (0,1) $, затем вы добавляете 0 $ и $ 1 $, чтобы получить список из чисел $ N+1 $. Вы сортируете список, а затем записываете различия между двумя последовательными элементами. Это дает вам список номера $ N $, который составит сумму до $ 1 $. Более того, эта выборка равномерна. Эту идею можно найти в Дональде Б. Рубине, Байесовская начальная загрузка Анна. Статистика. 9, 1981, 130-134.

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

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

Answer 2

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

Девроя является отличной ссылкой на вопросы такого рода. Глава 7 дает алгоритмы, необходимые для генерации статистики единого порядка, которую после ОП.

Для получения единой статистики заказа, сортировка образцов $ n $ $ [0,1] $ подойдет. Этот подход занимает время $ o (n log n) $. Более быстрый способ (доступный в книге) включает выборку $ n $ случайные номера $ x_1, ldots, x_n $ из $ mathrm {exp} (1) $ pdf. (Эти расстояния формы PDF). Затем верните значения $$ (y_i) _ {1 leq i leq n} = frac { sum limits_ {1 ldots i} x_j} { sum limits_ {1 ldots n} x_j} $ $, которые автоматически отсортируются, в $ O (n) $ время в целом. (Я перекрываю ответ А. Схульца здесь- просто делаю вычисление более явным).

Тот же подход может быть адаптирован с помощью обратной выборки CDF для выборки любого неравномерного PDF более $ [0,1] $. Существует также трюк, который позволяет вам равномерно попробовать простое простое, отличное от канонического Simplex (скажем, $ 2x+3y+z = 5 $).

Answer 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.

Answer 4

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