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

Тип математической последовательности

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

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

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

Приложения

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

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

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

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

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

Последовательности с малым расхождением в численном интегрировании

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

${\displaystyle \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 увеличивается, но наборы точек не имеют минимального расхождения. Используя последовательности с низким расхождением, мы стремимся к низкому расхождению и отсутствию необходимости в повторных вычислениях, но на самом деле последовательности с низким расхождением могут быть только постепенно эффективными в отношении несоответствий, если мы не допускаем повторных вычислений.

Определение расхождения

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

${\displaystyle 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 -мерных интервалов или ящиков вида

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

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

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

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

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

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

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

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

Неравенство Коксмы–Главки.

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

${\displaystyle \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}).}$

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

${\displaystyle \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 ^* _N ( x1 ,... , _{xN )} .

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

Позволять . Ибо мы пишем ${\displaystyle D=\{1,2,\ldots ,d\}}$ ${\displaystyle \emptyset \neq u\subseteq D}$

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

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

${\displaystyle {\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},}$

где - функция невязки. ${\displaystyle \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 - версия неравенства Коксмы–Главки.

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

${\displaystyle \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}\}),}$

где

${\displaystyle \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}}$

и

${\displaystyle \|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}.}$

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

Неравенство Эрдеша–Турана–Коксмы

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

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

${\displaystyle 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)}$

где

${\displaystyle 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 , такая, что

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

${\displaystyle 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 }. Йозеф Бек ^[1] ​​установил двойное логарифмическое улучшение этого результата в трех измерениях. Это было улучшено Д. Билыком и М. Т. Лейси до степени одиночного логарифма. Наиболее известная оценка для s  > 2 принадлежит Д. Билыку, М.Т. Лейси и А. Вагаршакяну. ^[2] Для s  > 2 существует такое t  > 0, что

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

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

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

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

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

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

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

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

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

${\displaystyle s_{i}=r_{i}}$для нечетного и для четного. ${\displaystyle i}$ ${\displaystyle s_{i}=0.5+r_{i}}$ ${\displaystyle i}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Значение с наименьшим расхождением представляет собой дробную часть золотого сечения : ^[5] ${\displaystyle c}$

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

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

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

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

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

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

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

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

Позволять

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

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

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

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

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

где D ^* _N — звездное расхождение .

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

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

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

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

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

${\displaystyle 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 определяется формулой ^[7]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Примечания

1. Бек, Йожеф (1989). «Двумерная теорема Ван Аарденна-Эренфеста о неоднородностях распределения». Математическая композиция . 72 (3): 269–339. MR  1032337. S2CID  125940424. Збл  0691.10041.
2. Билык, Дмитрий; Лейси, Майкл Т.; Вагаршакян, Армен (2008). «О неравенстве малого мяча во всех измерениях». Журнал функционального анализа . 254 (9): 2470–2502. arXiv : 0705.4619 . дои : 10.1016/j.jfa.2007.09.010 . S2CID  14234006.
3. Kuipers & Niederreiter 2005, стр. 123
4. Кнут, Дональд Э. «Глава 3 – Случайные числа». Искусство компьютерного программирования . Том. 2.
5. Скарупке, Мальте (16 июня 2018 г.). «Хеширование Фибоначчи: оптимизация, о которой мир забыл». Одним из свойств золотого сечения является то, что вы можете использовать его для примерно равномерного разделения любого диапазона... если вы заранее не знаете, сколько шагов вы собираетесь сделать.
6. Робертс, Мартин (2018). «Необоснованная эффективность квазислучайных последовательностей».
7. Хаммерсли, Дж. М.; Хэндскомб, округ Колумбия (1964). Методы Монте-Карло . дои : 10.1007/978-94-009-5819-7. ISBN 978-94-009-5821-0.
8. Герман Туллекен.Туллекен, Герман (март 2008 г.). «Выборка диска Пуассона». Дев.Маг . № 21. С. 21–25.
9. Брэтли, Пол; Фокс, Беннетт Л. (1988). «Алгоритм 659». Транзакции ACM в математическом программном обеспечении . 14 : 88–100. дои : 10.1145/42288.214372 . S2CID  17325779.

Рекомендации

• Дик, Йозеф; Пиллихшаммер, Фридрих (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