Введение

Тип математической последовательности
В математике последовательность с низким расхождением – это последовательность, обладающая свойством, что для всех значений N её подпоследовательность x1, …, xN имеет низкое расхождение. Говоря упрощенно, расхождение последовательности мало, если доля точек в последовательности, попадающих в произвольное множество B, близка к пропорциональной мере B, как это происходило бы в среднем (но не для отдельных выборок) в случае равномерно распределённой последовательности. Конкретные определения расхождения различаются в зависимости от выбора множества B (гиперсферы, гиперкубы и т.д.) и способа вычисления расхождения для каждого B (обычно нормализуется) и их объединения (обычно берётся наихудшее значение). Последовательности с низким расхождением также называют квазислучайными последовательностями из-за их частого использования в качестве замены равномерно распределённых случайных чисел. Приставка "квази" используется для более чёткого указания на то, что значения последовательности с низким расхождением не являются ни случайными, ни псевдослучайными, но такие последовательности обладают некоторыми свойствами случайных величин, и в определённых приложениях, таких как метод квази-Монте-Карло, их меньшее расхождение является важным преимуществом.

Приложения

Квазислучайные числа имеют преимущество перед истинно случайными числами в том, что они быстро и равномерно покрывают интересующую область. Два полезных применения – это определение характеристической функции функции плотности вероятности и нахождение производной детерминированной функции с небольшим добавлением шума. Квазислучайные числа позволяют очень быстро и с высокой точностью вычислять моменты высоких порядков. Области применения, не требующие сортировки, включают вычисление среднего значения, стандартного отклонения, асимметрии и эксцесса статистического распределения, а также поиск интеграла и глобальных максимумов и минимумов сложных детерминированных функций. Квазислучайные числа также могут использоваться для задания начальных точек для детерминированных алгоритмов, работающих только локально, таких как итерация Ньютона-Рафсона. Квазислучайные числа также можно комбинировать с алгоритмами поиска. Используя алгоритм поиска, квазислучайные числа позволяют находить моду, медиану, доверительные интервалы и кумулятивную функцию распределения статистического распределения, а также все локальные минимумы и все решения детерминированных функций.

Основные предположения

Предположение 1. Существует постоянная cs, зависящая только от размерности s, такая, что

для любого конечного множества точек {x1, ..., xN}. Предположение 2. Существует постоянная c's, зависящая только от s, такая, что

для бесконечного числа N для любой бесконечной последовательности x1, x2, x3, ...

Эти предположения эквивалентны. Они были доказаны для s ≤ 2 В. М. Шмидтом. В более высоких размерностях соответствующая задача остаётся открытой. Наилучшие известные нижние оценки получены Майклом Лейси и его коллегами.

Случайные числа

Последовательности квазислучайных чисел могут быть сгенерированы из случайных чисел путем наложения отрицательной корреляции на эти случайные числа. Один из способов сделать это — начать с набора случайных чисел и построить квазислучайные числа, равномерно распределенные, используя: для нечетных и для четных. Другой способ, используя исходные случайные числа, — построить случайное блуждание со смещением 0,5, как в: То есть, к предыдущему квазислучайному числу прибавьте 0,5 и случайное число, а затем возьмите результат по модулю 1. Для более чем одного измерения можно использовать латинские квадраты соответствующей размерности для обеспечения смещений, гарантирующих равномерное покрытие всей области.

Последовательность Халтона

Последовательность Халтона является естественным обобщением последовательности Ван дер Корпута на большее число измерений. Пусть s – произвольная размерность, а b₁, …, bₛ – произвольные взаимно простые целые числа, большие 1. Определим

Тогда существует константа C, зависящая только от b₁, …, bₛ, такая что последовательность {x(n)}ₙ≥₁ является s-мерной последовательностью с

Набор Хаммерсли

Пусть b1, …, bs−1 — взаимно простые положительные целые числа, большие 1. Для заданных s и N, s-мерное множество Хаммерсли размера N определяется для n = 1, …, N. Тогда

где C — константа, зависящая только от b1, …, bs−1. Примечание: Формулы показывают, что множество Хаммерсли фактически является последовательностью Халтона, но мы получаем дополнительное измерение, добавив линейную развертку. Это возможно только в том случае, если N известно заранее. Линейный набор также является набором с наименьшим возможным одномерным расхождением в общем случае. К сожалению, для более высоких размерностей не известно наборов, обладающих подобным рекордно низким расхождением. Для s = 2 большинство генераторов точек с низким расхождением обеспечивают, по крайней мере, почти оптимальные значения расхождения.

Последовательность Соболя

Вариант Антонова — Салеева последовательности Соболя генерирует числа между нулем и единицей непосредственно в виде двоичных дробей длины *l*, из набора специальных двоичных дробей, называемых числами направлений. Биты серого кода для *i*, *i* = 0, 1, ..., используются для выбора чисел направлений. Чтобы получить значение последовательности Соболя, необходимо выполнить операцию исключающего ИЛИ между двоичным представлением серого кода для *i* и соответствующим числом направления. Количество требуемых размерностей влияет на выбор *l*.

Графические примеры

На графике ниже показаны первые 100, 1000 и 10000 элементов последовательности типа Соболя. Для сравнения также показаны 10000 элементов последовательности псевдослучайных точек. Последовательность с низкой расходимостью была сгенерирована алгоритмом 659 из TOMS. Реализация алгоритма на Фортране доступна в Netlib.