Я ищу способ генерирования случайных чисел, которые кажутся равномерно распределенными - и каждый тест покажет, что они равномерно распределены - за исключением того, что они распределены более равномерно, чем истинные однородные данные .
Проблема, с которой я сталкиваюсь с «настоящими» униформами, состоит в том, что они иногда будут группироваться. Этот эффект сильнее при небольшом размере выборки. Грубо говоря: когда я рисую два единообразных рандома в U [0; 1], вероятность составляет около 10%, что они находятся в диапазоне от 0,1, и 1%, что они находятся в пределах 0,01.
Поэтому я ищу хороший способ генерировать случайные числа, которые распределены более равномерно, чем равномерные случайные числа .
Пример использования: скажем, я играю в компьютерную игру и хочу произвольно разместить сокровища на карте (не заботясь ни о чем другом). Я не хочу, чтобы сокровища были в одном месте, они должны быть по всей карте. При равномерном случайном расположении, если я размещу, скажем, 10 объектов, шансы не настолько низкие, что 5 или около того действительно близко друг к другу. Это может дать одному игроку преимущество перед другим. Подумайте о тральщике, но есть вероятность (пусть и небольшая, если мин достаточно), что вам действительно повезло, и вы выиграли одним кликом.
Очень наивный подход к моей проблеме - разделить данные на сетку. Пока число достаточно велико (и имеет факторы), таким образом можно обеспечить дополнительную однородность. Таким образом, вместо рисования 12 случайных величин из U [0; 1], я могу извлечь 6 из U [0; .5] и 6 из U [0.5; 1] или 4 из U [0; 1/3] + 4 из U [1/3; 2/3] + 4 из U [2/3; 1].
Есть ли какой-нибудь лучший способ придать этой дополнительной ровности форму? Вероятно, это работает только для пакетных случайностей (когда я рисую одну случайную единицу, я, очевидно, должен учитывать весь диапазон). В частности, я могу снова перемешать записи (так что это не первые четыре из первой трети).
Как насчет того, чтобы делать это постепенно? Итак, первое находится на U [0; 1], затем по две от каждой половины, по одной от каждой третьей, по одной от каждой четвертой? Было ли это исследовано, и насколько это хорошо? Возможно, мне придется быть осторожным, чтобы использовать разные генераторы для x и y, чтобы не получить их корреляцию (первый xy всегда будет в нижней половине, второй в левой половине и нижней трети, третий в центральной трети и верхней трети. .. так что по крайней мере некоторая случайная перестановка мусора также необходима. и в конечном счете, это будет слишком даже, я думаю.
Как побочный узел, существует ли хорошо известный тест, является ли некоторое распределение слишком равномерным, чтобы быть действительно равномерным? Таким образом, тестирование «истинная униформа» против «кто-то испортил данные и распределял предметы более равномерно». Если я правильно помню, Hopkins Statistic может измерить это, но можно ли его использовать и для тестирования? Также несколько обратный тест KS: если наибольшее отклонение ниже определенного ожидаемого порога, данные распределены слишком равномерно?
Ответы:
Да , есть много способов создать последовательность чисел, которые распределены более равномерно, чем случайные формы. На самом деле есть целая область, посвященная этому вопросу; это основа квази-Монте-Карло (QMC). Ниже краткий обзор основ.
Измерение однородности
Есть много способов сделать это, но самый распространенный способ имеет сильный, интуитивный, геометрический вкус. Предположим, что мы имеем дело с генерацией точек в для некоторого натурального числа . Определить где - прямоугольник в такой, что иx 1 , x 2 , … , x n [ 0 , 1 ] d dn x1,x2,…,xn [0,1]d d
Величину часто называют расхождением или крайним расхождением множества точек . Интуитивно понятно, что мы находим «худший» прямоугольник котором доля точек больше всего отличается от того, что мы ожидаем при идеальной однородности.Dn (xi) R
Это громоздко на практике и сложно вычислить. По большей части люди предпочитают работать с расхождением звезд : Единственным отличием является набор над которым взят супремум. Это набор закрепленных прямоугольников (в начале координат), т. Где .
Лемма : для всех , . Доказательство . Левая рука связана очевидна , так как . Правая оценка следует из того, что каждый может быть составлен через объединения, пересечения и дополнения не более чем закрепленных прямоугольников (т. ).D⋆n≤Dn≤2dD⋆n n d
A⊂R R∈R 2d A
Таким образом, мы видим, что и эквивалентны в том смысле, что если один мал с ростом , другой тоже будет. Вот (мультфильм) картина, показывающая прямоугольники-кандидаты для каждого несоответствия.Dn D⋆n n
Примеры «хороших» последовательностей
Последовательности с достоверно низким расхождением звезд часто называют последовательностями с низким расхождением .D⋆n
ван дер Корпут . Это, пожалуй, самый простой пример. Для последовательности Ван-дер-Корпута формируются путем расширения целого числа в двоичном виде и последующего «отражения цифр» вокруг десятичной точки. Более формально это делается с помощью радикальной обратной функции в базе , где и - цифры в расширении базы для . Эта функция является основой для многих других последовательностей. Например, в двоичном виде это и такd=1 i b
Обратите внимание, что, поскольку младший значащий бит колеблется между и , точки для нечетного находятся в , тогда как точки для четного находятся в .i 0 1 xi i [1/2,1) xi i (0,1/2)
Последовательности Хэлтона . Среди наиболее популярных классических последовательностей с низким расхождением это расширения последовательности Ван-дер-Корпута для нескольких измерений. Пусть будет м наименьшим простым числом. Затем й точки в - мерной последовательности Хэлтон является Для низких они работают довольно хорошо, но имеют проблемы в более высоких измерениях .pj j i xi d
Последовательности удовлетворяют . Они также хороши тем, что они расширяемы тем, что построение точек не зависит от априорного выбора длины последовательности .D⋆n=O(n−1(logn)d) n
Последовательности Хэммерсли . Это очень простая модификация последовательности Халтона. Вместо этого мы используем Возможно, удивительно, преимущество в том, что они имеют лучшее расхождение звезд: .
Вот пример последовательностей Халтона и Хаммерсли в двух измерениях.
Перманутные перестановки Халтона . Специальный набор перестановок (фиксированный как функция ) может быть применен к разложению цифр для каждого при создании последовательности Halton. Это помогает исправить (до некоторой степени) проблемы, на которые ссылаются в более высоких измерениях. Каждая из перестановок обладает интересным свойством сохранения и качестве фиксированных точек.i ak i 0 b−1
Правила решетки . Пусть будут целыми числами. Возьмем где обозначает дробную часть . Разумный выбор значений дает хорошие свойства однородности. Плохой выбор может привести к плохим последствиям. Они также не являются расширяемыми. Вот два примера.β1,…,βd−1
Простая рандомизация: вращения Крэнли-Паттерсона . Пусть - последовательность точек. Пусть . Тогда точки равномерно распределены в .xi∈[0,1]d U∼U(0,1) x^i={xi+U} [0,1]d
Вот пример с синими точками, являющимися исходными точками, и красными точками, являющимися повернутыми с линиями, соединяющими их (и показаны обернутыми, где это уместно).
Полностью равномерно распределенные последовательности . Это еще более сильное понятие единообразия, которое иногда вступает в игру. Пусть - последовательность точек в и теперь формируем перекрывающиеся блоки размера чтобы получить последовательность . Итак, если , мы берем затем и т. Д. Если для каждого , , то называется равномерно распределенным . Другими словами, последовательность дает набор точек любого(ui) [0,1] d (xi) s=3 x1=(u1,u2,u3) x2=(u2,u3,u4) s≥1 D⋆n(x1,…,xn)→0 (ui) измерение, которое имеет желательные свойства .D⋆n
Например, последовательность Ван-дер-Корпута не полностью распределена равномерно, поскольку при точки находятся в квадрате а точки в . Следовательно, нет точек в квадрате , который предполагает , что при , для всех .s=2 x2i (0,1/2)×[1/2,1) x2i−1 [1/2,1)×(0,1/2) (0,1/2)×(0,1/2) s=2 D⋆n≥1/4 n
Стандартные ссылки
Нидеррейтер (1992) монография и Fang и Ван (1994) текст место , чтобы пойти для дальнейшего исследования.
источник
Один из способов сделать это состоит в том, чтобы сгенерировать однородные случайные числа, затем проверить «близость», используя любой метод, который вам нравится, и затем удалить случайные элементы, которые слишком близки к другим, и выбрать другой набор случайных униформ, чтобы восполнить их.
Будет ли такое распределение проходить каждый тест на однородность? Я надеюсь, что нет! Он больше не распределен равномерно, теперь это другой дистрибутив.
Один неинтуитивный аспект вероятности - это случайность. В случайных данных больше прогонов, чем думают люди. Я думаю, что Тверский провел некоторое исследование по этому вопросу (хотя он исследовал так много, что его трудно запомнить).
источник
Это известно как «ядро» пуассоновского точечного процесса - так назвал Брайан Рипли в 1970-х; то есть вы хотите, чтобы оно было случайным, но вы не хотите, чтобы какие-либо точки были слишком близко друг к другу. «Жесткое ядро» можно представить как буферную зону, в которую не могут проникнуть другие точки.
Представьте, что вы записываете положение некоторых автомобилей в городе - но вы записываете только точку в номинальном центре автомобиля. Пока они на улицах, две пары точек не могут сблизиться, потому что точки защищены "жесткой" конструкцией кузова - мы будем игнорировать потенциальную суперпозицию в многоэтажных парковках :-)
Существуют процедуры для генерации таких точечных процессов - один из способов - это просто сгенерировать точки равномерно, а затем удалить все, которые находятся слишком близко друг к другу!
Для некоторых подробностей о таких процессах, обратитесь, например, к этому
источник
Что касается генерации пакетов заранее, я бы сгенерировал большое количество наборов псевдослучайных переменных, а затем протестировал их с помощью теста, такого как тест Колмогорова-Смирнова. Вы хотите выбрать набор, который имеет наибольшее значение p (т. Е. является идеальным). Обратите внимание, что это будет медленно, но по мере увеличения оно, вероятно, становится менее необходимым.p≈1 N
Что касается инкрементальной генерации, вы, по сути, ищете серию с умеренно отрицательной автокорреляцией. Я не уверен, как лучше всего это сделать, поскольку у меня очень ограниченный опыт работы с временными рядами, но я подозреваю, что для этого существуют алгоритмы.
Что касается теста на «слишком четный», то любой тест на то, соответствует ли образец определенному распределению (например, KS, отмеченный выше), вы просто хотите проверить, если , а не стандартный подход. Я написал пример такого альтернативного подхода: хи-квадрат всегда односторонний тест .p>(1−α)
источник
Я бы формализовал вашу проблему следующим образом: вы хотите распределение по так, чтобы плотность была для некоторого определяющего отталкивание точек.[0,1]n f(x)∝e(1k∑ij|xi−xj|k)1k k<0
Один простой способ создать такие векторы - сделать выборку Гиббса.
источник