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

12

Допустим, я хочу создать набор случайных чисел из интервала (a, b). Сгенерированная последовательность также должна иметь свойство сортировки. Я могу придумать два способа добиться этого.

Позвольте nбыть длина последовательности, которая будет сгенерирована.

1-й алгоритм:

Let `offset = floor((b - a) / n)`
for i = 1 up to n:
   generate a random number r_i from (a, a+offset)
   a = a + offset
   add r_i to the sequence r

2-й алгоритм:

for i = 1 up to n:
    generate a random number s_i from (a, b)
    add s_i to the sequence s
sort(r)

У меня вопрос: дает ли алгоритм 1 последовательности, которые так же хороши, как последовательности, сгенерированные алгоритмом 2?

ultrajohn
источник
Кстати, это удивительно легко создать список отсортированных случайных чисел в R. Для того , чтобы генерировать массив наборов случайных чисел над равномерным интервалом , следующий код работает: . n [ a , b ]kn[a,b]rand_array <- replicate(k, sort(runif(n, a, b))
RobertF

Ответы:

18

Первый алгоритм плохо работает по двум причинам:

  1. Взятие пола может значительно уменьшить его. Действительно, когда , он будет равен нулю, давая вам набор, значения которого одинаковы!(ab)/nba<n

  2. Когда вы не берете слово, полученные значения распределяются слишком равномерно . Так , например, в любой простой случайной выборке из н.о.р. равномерного переменные (скажем , между и ), есть вероятности того, что Наибольшее не будет в верхнем интервале от до . При использовании алгоритма 1 существует вероятность того, что максимум будет в этом интервале. Для некоторых целей эта супер-однородность хороша, но в целом это ужасная ошибка, потому что (а) многие статистические данные будут разрушены, но (б) может быть очень трудно определить, почему.na=0b=1(11/n)n1/e37%11/n1100%

  3. Если вы хотите избежать сортировки, генерируйте независимых экспоненциально распределенных переменных. Нормализовать их совокупную сумму в диапазоне путем деления на сумму. Удалите наибольшее значение (которое всегда будет ). Масштабируйте до диапазона .n+1(0,1)1(a,b)

Гистограммы всех трех алгоритмов показаны. (Каждый показывает совокупные результаты независимых наборов значений каждый.) Отсутствие каких-либо видимых изменений в гистограмме для Алгоритма 1 показывает проблему там. Различия в двух других алгоритмах - это именно то, что следует ожидать - и то, что вам нужно от генератора случайных чисел.1000n=100

Более многие (забавные) способы моделирования независимых равномерных переменных см. В разделе « Моделирование рисунков из равномерного распределения с использованием рисунков из нормального распределения» .

Рисунок: гистограммы

Вот Rкод, который произвел рисунок.

b <- 1
a <- 0
n <- 100
n.iter <- 1e3

offset <- (b-a)/n
as <- seq(a, by=offset, length.out=n)
sim.1 <- matrix(runif(n.iter*n, as, as+offset), nrow=n)
sim.2 <- apply(matrix(runif(n.iter*n, a, b), nrow=n), 2, sort)
sim.3 <- apply(matrix(rexp(n.iter*(n+1)), nrow=n+1), 2, function(x) {
  a + (b-a) * cumsum(x)[-(n+1)] / sum(x)
})

par(mfrow=c(1,3))
hist(sim.1, main="Algorithm 1")
hist(sim.2, main="Algorithm 2")
hist(sim.3, main="Exponential")
Whuber
источник
Что вы думаете об алгоритме (основанном на статистике рангов) в моем ответе? ;-)
ВЫЙТИ - Anony-Mousse
@Anony Это менее эффективная версия моего алгоритма 3. (Похоже, что в нем много ненужного масштабирования.) Вы генерируете экспоненциальные вариации, беря логи униформ, что является стандартным.
whuber
6

Первый алгоритм производства слишком равномерно распределенных чисел

Смотрите также серию с низким расхождением .

Предполагая, что вы хотите 2 случайных числа в . При реальных единообразных данных вероятность составляет 50:50, они оба больше или меньше 0,5 одновременно. При вашем подходе вероятность равна 0. Таким образом, ваши данные не единообразны.[0;1]

(Как указывалось, это может быть желательным свойством, например, для стратификации. Ряды с низким расхождением, такие как Halton и Sobel , имеют свои варианты использования.)

Правильный, но дорогой подход (для реальных ценностей)

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

Предполагая, что данные должны быть сгенерированы в . Наименьшее значение - это . (Для последующих случаев уменьшите и измените масштаб до оставшегося интервала). Чтобы сгенерировать общую бета-случайность, нам нужно сгенерировать два гамма-распределенных случайных значения. Но . Тогда . Для этого мы можем выбрать случайные числа из этого распределения как .[0;1]Beta[1,n]n1XBeta[n,1]ln(1X)Exponential[n]ln(U[0;1])n

ln(1x)=ln(1u)n1x=u1nx=1u1n

Что дает следующий алгоритм:

x = a
for i in range(n, 0, -1):
    x += (b-x) * (1 - pow(rand(), 1. / i))
    result.append(x) 

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

Для целочисленных значений вам может понадобиться другой дистрибутив.

Сортировка невероятно дешева, так что просто используйте ее

Но не беспокойся. Сортировка настолько смехотворно дешева, так что просто сортируйте. За прошедшие годы мы хорошо поняли, как реализовать алгоритмы сортировки, которых не стоит избегать сортировки по двойникам. Теоретически это но постоянный член настолько смехотворно мал в хорошей реализации, что это прекрасный пример того, как бесполезные результаты теоретической сложности могут быть. Запустите тест. Создайте 1 миллион случайностей с сортировкой и без нее. Запустите его несколько раз, и я не удивлюсь, если довольно часто сортировка превосходит несортировку, потому что стоимость сортировки все равно будет намного меньше, чем ваша ошибка измерения.O(nlogn)

ВЫЙТИ - Anony-Mousse
источник
1
Там могут быть причины, чтобы избежать сортировки. Один из них - когда вы хотите сгенерировать огромное количество случайных переменных, так много, что стандартная процедура сортировки не может их обработать.
whuber
Я думаю, что числовые проблемы с суммами с использованием математики с плавающей запятой стали проблемой намного раньше. (И проблемы с циклическими шаблонами в псевдослучайных числах!) Довольно легко масштабировать подход сортировки к терабайтам и эксабайтам в распределенных системах.
ВЫЙТИ - Anony-Mousse
При таком масштабировании термин журнала начинает становиться более ... интересным. Хотя хорошо беспокоиться об ошибках с плавающей запятой, они не будут иметь никакого значения, пока вы не суммируете более чем значений, и проблема легко решается (хотя я допускаю больше программирования, разбивая) суммы в подгруппы. Моя точка зрения заключается в том, что когда вы выполняете вычисление, которое должно последовательно проходить через набор однородных переменных, методы без сортировки полностью избавляют от необходимости изначально генерировать, хранить и сортировать их все. 1012
whuber
Хорошо, не хранить их - это аргумент. Но тогда вам понадобится мой подход, ваш вариант 3, использующий накопленную сумму, не сработает.
ВЫЙТИ - Anony-Mousse
Это отличный момент. Теперь я вижу достоинство дополнительных расчетов! (+1)
whuber
5

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

user67054
источник
2
+1 Я думаю, что это полезный вклад в вопрос, особенно характеризуя Алгоритм 1 с точки зрения стратификации.
whuber