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

В математике последовательность с малым расхождением — это последовательность , обладающая свойством, что для всех значений N ее подпоследовательность x ₁ , ..., x _N имеет малое расхождение .

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

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

Приложения

Ошибка оценки эксцесса как функция количества точек данных. «Аддитивная квазислучайность» дает максимальную ошибку, когда c = ( √ 5 - 1)/2. «Случайный» дает среднюю ошибку по шести сериям случайных чисел, где среднее значение берется для уменьшения величины резких колебаний.

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

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

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

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

с низким расхождением в

Различные методы численного интегрирования можно сформулировать как аппроксимацию интеграла функции f в некотором интервале, например [0,1], как среднего значения функции, вычисленной в наборе { x ₁ , ..., x _N } в этом интервал:

$\int _{0}^{1}f(u)\,du\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).$

Если точки выбраны как x _i = i / N , это правило прямоугольника .Если точки выбраны случайным (или псевдослучайным ) распределением, это метод Монте-Карло .Если точки выбираются как элементы последовательности с малым расхождением, это и есть метод квази-Монте-Карло .Замечательный результат — неравенство Коксмы–Главки (приведенное ниже) показывает, что погрешность такого метода может быть ограничена произведением двух слагаемых, одно из которых зависит только от f , а другое — невязка множества { х ₁ , ..., х _N }.

Удобно построить набор { x ₁ , ..., x _N } таким образом, что если набор из N построен +1 элементов, предыдущие N элементов не нужно пересчитывать.Правило прямоугольника использует набор точек, которые имеют небольшое расхождение, но обычно элементы необходимо пересчитывать, если N увеличивается.Элементы не нужно пересчитывать случайным методом Монте-Карло, если N увеличивается,но наборы точек не имеют минимального расхождения.Используя последовательности с низким расхождением, мы стремимся к малому расхождению и отсутствию необходимости в повторных вычислениях, но на самом деле последовательности с низким расхождением могут быть только постепенно эффективными в отношении несоответствий, если мы не допускаем повторных вычислений.

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

Невязка 1 набора P = { x _как , ..., x _N } определяется с использованием Нидеррайтера обозначений

$D_{N}(P)=\sup _{B\in J}\left|{\frac {A(B;P)}{N}}-\lambda _{s}(B)\right|$

гдеλ _s – s -мерная мера Лебега , A ( B ; P ) — количество точек из P , попадающих в B , — J множество s- мерных интервалов или ящиков вида

$\prod _{i=1}^{s}[a_{i},b_{i})=\{\mathbf {x} \in \mathbf {R} ^{s}:a_{i}\leq x_{i}<b_{i}\}\,$

где $0\leq a_{i}<b_{i}\leq 1$.

Звездное несоответствие D ^* _N ( P ) определяется аналогично, за исключением того, что верхняя грань берется по множеству J ^* прямоугольных коробок формы

$\prod _{i=1}^{s}[0,u_{i})$

где u _i находится в полуинтервале [0, 1).

Эти два связаны

$D_{N}^{*}\leq D_{N}\leq 2^{s}D_{N}^{*}.\,$

Примечание. Согласно этим определениям, несоответствие представляет собой наихудшее или максимальное отклонение плотности точек однородного набора. Однако имеют значение и другие меры ошибок, что приводит к другим определениям и мерам вариаций. Например, расхождение L2 или модифицированное центрированное расхождение L2 также интенсивно используются для сравнения качества однородных наборов точек. И то, и другое гораздо проще вычислить при больших N и s.

Коксмы

Пусть я ^с быть s -мерным единичным кубом,Я ^с = [0, 1] × ... × [0, 1].Пусть f имеет ограниченную вариацию V ( f ) на Ī ^с в смысле Харди и Краузе.Тогда для любого x ₁ , ..., x _N во мне ^с =[0, 1) × ... ×[0, 1),

$\left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|\leq V(f)\,D_{N}^{*}(x_{1},\ldots ,x_{N}).$

Неравенство Коксмы I – Главки является точным в следующем смысле: для любого множества точек { 1 _, ..., x _N } в x ^с и любой $\varepsilon >0$, существует функция f с ограниченной вариацией и V ( f ) = 1 такая, что

$\left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|>D_{N}^{*}(x_{1},\ldots ,x_{N})-\varepsilon .$

Поэтому качество правила численного интегрирования зависит только от невязки D ^* _Н ( х ₁ ,..., х _Н ).

Формула Главки–Зарембы

Позволять $D=\{1,2,\ldots ,d\}$. Для $\emptyset \neq u\subseteq D$ мыписать

$dx_{u}:=\prod _{j\in u}dx_{j}$

и обозначим через $(x_{u},1)$ точка, полученная из x заменойкоординаты не тебе в $1$. Затем

${\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du=\sum _{\emptyset \neq u\subseteq D}(-1)^{|u|}\int _{[0,1]^{|u|}}\operatorname {disc} (x_{u},1){\frac {\partial ^{|u|}}{\partial x_{u}}}f(x_{u},1)\,dx_{u},$

где $\operatorname {disc} (z)={\frac {1}{N}}\sum _{i=1}^{N}\prod _{j=1}^{d}1_{[0,z_{j})}(x_{i,j})-\prod _{j=1}^{d}z_{i}$ – функция несоответствия.

Л ​ ² неравенства Коксмы

Применяя неравенство Коши–Шварца для интегралов и сумм к тождеству Главки–Зарембы, получаем $L^{2}$ вариант неравенства Коксмы – Главки:

$\left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|\leq \|f\|_{d}\operatorname {disc} _{d}(\{t_{i}\}),$

где

$\operatorname {disc} _{d}(\{t_{i}\})=\left(\sum _{\emptyset \neq u\subseteq D}\int _{[0,1]^{|u|}}\operatorname {disc} (x_{u},1)^{2}\,dx_{u}\right)^{1/2}$

и

$\|f\|_{d}=\left(\sum _{u\subseteq D}\int _{[0,1]^{|u|}}\left|{\frac {\partial ^{|u|}}{\partial x_{u}}}f(x_{u},1)\right|^{2}dx_{u}\right)^{1/2}.$

$L^{2}$ Расхождение имеет большое практическое значение, поскольку для данного набора точек возможны быстрые явные вычисления. Таким образом, можно легко создавать оптимизаторы набора точек, используя $L^{2}$ несоответствие как критерий.

Эрдеша – Турана

Трудно с вычислительной точки зрения найти точное значение невязки больших наборов точек. Неравенство Эрдеша – – Турана . Коксмы дает верхнюю границу

Пусть x ₁ ,..., x _N — точки в I ^с и H — произвольное положительное целое число. Затем

$D_{N}^{*}(x_{1},\ldots ,x_{N})\leq \left({\frac {3}{2}}\right)^{s}\left({\frac {2}{H+1}}+\sum _{0<\|h\|_{\infty }\leq H}{\frac {1}{r(h)}}\left|{\frac {1}{N}}\sum _{n=1}^{N}e^{2\pi i\langle h,x_{n}\rangle }\right|\right)$

где

$r(h)=\prod _{i=1}^{s}\max\{1,|h_{i}|\}\quad {\mbox{for}}\quad h=(h_{1},\ldots ,h_{s})\in \mathbb {Z} ^{s}.$

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

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

$D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c_{s}{\frac {(\ln N)^{s-1}}{N}}$

для любого конечного множества точек { x ₁ ,..., x _N }.

Гипотеза 2. Существует константа c ^' _s зависит только от s , такого, что

$D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c'_{s}{\frac {(\ln N)^{s}}{N}}$

для бесконечного числа N для любой бесконечной последовательности x ₁ , x ₂ , x ₃ ,....

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

Нижние границы

Пусть s = 1. Тогда

$D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2N}}$

для любого конечного множества точек { x ₁ , ..., x _N }.

Пусть s = 2. В.М. Шмидт доказал, что для любого конечного множества точек { x ₁ , ..., x _N }

$D_{N}^{*}(x_{1},\ldots ,x_{N})\geq C{\frac {\log N}{N}}$

где

$C=\max _{a\geq 3}{\frac {1}{16}}{\frac {a-2}{a\log a}}=0.023335\dots .$

Для произвольных размерностей s > 1 К. Ф. Рот доказал, что

$D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2^{4s}}}{\frac {1}{((s-1)\log 2)^{\frac {s-1}{2}}}}{\frac {\log ^{\frac {s-1}{2}}N}{N}}$

для любого конечного множества точек { x ₁ , ..., x _N }. Йозеф Бек установили двойное логарифмическое улучшение этого результата в трех измерениях. Это было улучшено Д. Билыком и М. Т. Лейси до степени одиночного логарифма. Самая известная оценка для s > 2 обусловленаД. Билык и М.Т. Лейси и А. Вагаршакян. Для s > 2 существует t > 0, так что

$D_{N}^{*}(x_{1},\ldots ,x_{N})\geq t{\frac {\log ^{{\frac {s-1}{2}}+t}N}{N}}$

для любого конечного множества точек { x ₁ , ..., x _N }.

Построение последовательностей

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

Известны конструкции последовательностей такие, что

$D_{N}^{*}(x_{1},\ldots ,x_{N})\leq C{\frac {(\ln N)^{s}}{N}}.$

где C — некоторая константа, зависящая от последовательности. После гипотезы 2 считается, что эти последовательности имеют наилучший возможный порядок сходимости. Ниже приведены примеры последовательности Ван дер Корпута , последовательности Холтона и последовательности Соболя . Одним из общих ограничений является то, что методы построения обычно могут гарантировать только порядок сходимости. Практически, малое расхождение может быть достигнуто только в том случае, если N достаточно велико, а при больших заданных s этот минимум N может быть очень большим. Это означает, что выполнение анализа Монте-Карло, например, с s=20 переменными и N=1000 точками с помощью генератора последовательностей с низким расхождением, может дать лишь очень незначительное улучшение точности. .

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

Последовательности квазислучайных чисел можно генерировать из случайных чисел, налагая на эти случайные числа отрицательную корреляцию. Один из способов сделать это — начать с набора случайных чисел. $r_{i}$ на $[0,0.5)$ и построить квазислучайные числа $s_{i}$ которые однородны по $[0,1)$ с использованием:

$s_{i}=r_{i}$ для $i$ странный и $s_{i}=0.5+r_{i}$ для $i$ даже.

Второй способ сделать это с начальными случайными числами — построить случайное блуждание со смещением 0,5, как показано ниже:

$s_{i}=s_{i-1}+0.5+r_{i}{\pmod {1}}.\,$

То есть возьмите предыдущее квазислучайное число, добавьте 0,5 и случайное число и возьмите результат по модулю 1.

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

Покрытие единицы площади. Слева для аддитивных квазислучайных чисел с c = 0,5545497..., 0,308517... Справа для случайных чисел. Сверху вниз. 10, 100, 1000, 10000 очков.

Аддитивная повторяемость

Для любого иррационального $\alpha$, последовательность

$s_{n}=\{s_{0}+n\alpha \}$

имеет несоответствие, имеющее тенденцию к $1/N$. Обратите внимание, что последовательность может быть определена рекурсивно с помощью

$s_{n+1}=(s_{n}+\alpha ){\bmod {1}}\;.$

Хорошее соотношение цены и качества $\alpha$ дает меньшее расхождение, чем последовательность независимых однородных случайных чисел.

Расхождение может быть ограничено аппроксимации показателем $\alpha$. Если показатель аппроксимации равен $\mu$, то для любого $\varepsilon >0$, имеет место следующая оценка:

$D_{N}((s_{n}))=O_{\varepsilon }(N^{-1/(\mu -1)+\varepsilon }).$

По теореме Туэ-Зигеля-Рота показатель аппроксимации любого иррационального алгебраического числа равен 2, что дает оценку $N^{-1+\varepsilon }$ выше.

Приведенное выше рекуррентное соотношение похоже на рекуррентное соотношение, используемое линейным конгруэнтным генератором — генератором псевдослучайных чисел низкого качества:

$r_{i}=(ar_{i-1}+c){\bmod {m}}$

Для аддитивной повторяемости с низким расхождением, описанной выше, a и m выбраны равными 1. Однако обратите внимание, что это не будет генерировать независимые случайные числа, поэтому их не следует использовать для целей, требующих независимости.

Стоимость $c$ с наименьшим расхождением является дробная часть золотого сечения :

$c={\frac {{\sqrt {5}}-1}{2}}=\varphi -1\approx 0.618034.$

Другая величина, которая почти так же хороша, — это дробная часть отношения серебра , которая представляет собой дробную часть квадратного корня из 2:

$c={\sqrt {2}}-1\approx 0.414214.\,$

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

$c={\sqrt {2}},{\sqrt {3}},{\sqrt {5}},{\sqrt {7}},{\sqrt {11}},\ldots \,$

Однако было показано, что набор значений, основанный на обобщенном золотом сечении, дает более равномерно распределенные точки.

В списке генераторов псевдослучайных чисел перечислены методы генерации независимых псевдослучайных чисел.Примечание. В небольшом количестве измерений рекурсивная рекурсия приводит к однородным наборам хорошего качества, но для больших s (например, s>8) другие генераторы наборов точек могут обеспечить гораздо меньшие расхождения.

последовательность Ван дер Корпута

Основная статья: последовательность Ван дер Корпута

Позволять

$n=\sum _{k=0}^{L-1}d_{k}(n)b^{k}$

быть b -арным представлением натурального числа n ≥ 1, т.е. 0 ≤ d _k ( n ) < b . Набор

$g_{b}(n)=\sum _{k=0}^{L-1}d_{k}(n)b^{-k-1}.$

Тогда существует константа C, зависящая только от b, такая, что ( g _b ( n )) _{n ≥ 1} удовлетворяет условию

$D_{N}^{*}(g_{b}(1),\dots ,g_{b}(N))\leq C{\frac {\log N}{N}},$

где Д ^* _N - это звездное несоответствие .

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

Первые 256 точек последовательности (2,3) Холтона

Основная статья: последовательность Холтона

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

$x(n)=(g_{b_{1}}(n),\dots ,g_{b_{s}}(n)).$

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

$D_{N}^{*}(x(1),\dots ,x(N))\leq C'{\frac {(\log N)^{s}}{N}}.$

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

2D набор Hammersley размера 256

Пусть b ₁ ,..., b _{s −1} — взаимно простые большие 1. Для заданных s и N s -мерное положительные целые числа , множество Хаммерсли размера N определяется формулой

$x(n)=\left(g_{b_{1}}(n),\dots ,g_{b_{s-1}}(n),{\frac {n}{N}}\right)$

для n = 1, ..., N . Затем

$D_{N}^{*}(x(1),\dots ,x(N))\leq C{\frac {(\log N)^{s-1}}{N}}$

где C — константа, зависящая только от b ₁ , ..., b _{s −1} .Примечание. Формулы показывают, что множество Хаммерсли на самом деле является последовательностью Холтона, но мы получаем еще одно измерение бесплатно, добавляя линейную прогонку. Это возможно только в том случае, если N известно заранее. Линейный набор также является набором с наименьшей возможной одномерной невязкой в ​​целом. К сожалению, для более высоких размерностей такие «наборы записей несоответствий» неизвестны. Для s = 2 большинство генераторов наборов точек с низким расхождением обеспечивают по крайней мере почти оптимальные расхождения.

Sobol’ sequence

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

Вариант Антонова-Салеева последовательности Соболя генерирует числа от нуля до единицы непосредственно как двоичные дроби длины. $w$, из набора $w$ специальные бинарные дроби, $V_{i},i=1,2,\dots ,w$ называются номерами направления. Биты Грея кода $i$, $G(i)$, используются для выбора номеров направлений. Чтобы получить значение последовательности Соболя $s_{i}$ возьмите исключительное или двоичное значение кода Грея $i$ с соответствующим номером направления. Количество требуемых размеров влияет на выбор $V_{i}$.

Выборка диска Пуассона

Основная статья: Суперсэмплинг § Диск Пуассона

Выборка диска Пуассона популярна в видеоиграх для быстрого размещения объектов так, чтобы они выглядели случайными.но гарантирует, что каждые две точки разделены как минимум указанным минимальным расстоянием. Это не гарантирует низкое расхождение (как, например, у Соболь), но, по крайней мере, значительно меньшее расхождение, чем чисто случайная выборка. Целью этих шаблонов выборки является частотный анализ, а не несоответствие, тип так называемых шаблонов «синего шума».

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

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

Первые 100 точек малорасходящейся последовательности типа Соболь .

Первые 1000 очков в той же последовательности. Эти 1000 составляют первые 100 и еще 900 очков.

Первые 10000 очков в той же последовательности. Эти 10 000 составляют первую 1000 и еще 9 000 очков.

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

См. также

• Теория несоответствия
• Цепь Маркова Монте-Карло
• Метод квази-Монте-Карло
• Разреженная сетка
• Систематический отбор проб

Ссылки

• Дик, Йозеф; Пиллихшаммер, Фридрих (2010). Цифровые сети и последовательности: теория несоответствия и интеграция квазимонте-карло . ISBN  978-0-521-19159-3 .
• Койперс, Л.; Нидеррайтер, Х. (2005), Равномерное распределение последовательностей , Dover Publications , ISBN  0-486-45019-8
• Харальд Нидеррайтер (1992). Генерация случайных чисел и методы квази-Монте-Карло . Общество промышленной и прикладной математики. ISBN  0-89871-295-5 .
• Дрмота, Майкл; Тичи, Роберт Ф. (1997). Последовательности, расхождения и приложения . Конспект лекций по математике. Том. 1651. Спрингер. ISBN  3-540-62606-9 .
• Пресс, Уильям Х.; Фланнери, Брайан П.; Теукольский, Саул А.; Веттерлинг, Уильям Т. (1992). Численные рецепты на языке C (2-е изд.). Издательство Кембриджского университета. см. раздел 7.7 для менее технического обсуждения последовательностей с низким расхождением. ISBN  0-521-43108-5 .

Внешние ссылки

• Сборник алгоритмов АКМ (см. алгоритмы 647, 659 и 738.)
• Квазислучайные последовательности из научной библиотеки GNU
• Квазислучайная выборка с учетом ограничений на FinancialMathematics.Com
• C++-генератор последовательности Соболя
• Ссылка на API SciPy QMC: scipy.stats.qmc