Последовательность с низким расхождением

Последовательность с низким расхождением — это последовательность, обладающая тем свойством, что при всех значениях $n$ её подпоследовательность $s_{1},...,s_{n}$ имеет низкое расхождение.

Грубо говоря, расхождение последовательности невелико, если доля её элементов, попадающих в произвольное множество $B$, близка к тому, чтобы быть пропорциональной мере множества $B$, как это происходило бы в среднем (но не для конкретных выборок) в случае равномерно распределённой последовательности. Конкретные определения расхождения различаются в зависимости от выбора множества $B$ (гиперсферы, гиперкуба и т.д.), а также от того, как это расхождение вычислено (обычно нормализовано) и скомбинировано (обычно путём взятия наихудшего значения) для каждого множества $B$.

Последовательности с низким расхождением также называются квазислучайными последовательностями из-за их общего использования в качестве замены равномерно распределенных случайных чисел. Префикс "квази" используется для более чёткого обозначения того, что значения последовательности с низким расхождением не являются ни случайными, ни псевдослучайными. Но, в то же время, такие последовательности обладают некоторыми свойствами случайных величин, и в определённых приложениях, таких как метод квази-Монте-Карло, их низкое расхождение является важным преимуществом.

Некоторые приложения

Квазислучайные числа имеют преимущество перед чисто случайными числами в том, что они быстро и равномерно охватывают интересующую область.

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

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

Литература

• Кейперс Л., Нидеррайтер Г. Равномерное распределение последовательностей. — М.: Наука, 1985. — 408 с.