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

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

В математике последовательность с низким расхождением — это последовательность , обладающая тем свойством, что для всех значений ее подпоследовательность имеет низкое расхождение . ${\displaystyle N}$ ${\displaystyle x_{1},\ldots ,x_{N}}$

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

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

Приложения

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

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

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

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

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

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

Различные методы численного интегрирования можно сформулировать как приближение интеграла функции в некотором интервале, например, [0,1], как среднего значения функции, вычисленной на некотором наборе в этом интервале: ${\displaystyle f}$ ${\displaystyle \{x_{1},\dots ,x_{N}}\}$

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

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

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

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

Расхождение множества определяется с использованием обозначения Нидеррайтера как ${\displaystyle P=\{x_{1},\dots ,x_{N}}\}$

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

где — -мерная мера Лебега , — число точек , попадающих в , а — множество -мерных интервалов или ящиков вида ${\displaystyle \lambda _{s}}$ ${\displaystyle s}$ ${\displaystyle A(B;P)}$ ${\displaystyle P}$ ${\displaystyle B}$ ${\displaystyle J}$ ${\displaystyle 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}$

Звездное расхождение определяется аналогично, за исключением того, что супремум берется по набору прямоугольных ящиков вида ${\displaystyle D_{N}^{*}(P)}$ ${\displaystyle J^{*}}$

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

где находится в полуоткрытом интервале [0, 1). ${\displaystyle u_{i}}$

Эти два понятия связаны между собой

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

Примечание : При этих определениях расхождение представляет собой наихудшее или максимальное отклонение плотности точек однородного набора. Однако, также имеют смысл и другие меры ошибок, что приводит к другим определениям и мерам вариации. Например, -расхождение или модифицированное центрированное -расхождение также интенсивно используются для сравнения качества однородных наборов точек. Оба они гораздо проще для вычисления для больших и . ${\displaystyle L^{2}}$ ${\displaystyle L^{2}}$ ${\displaystyle N}$ ${\displaystyle s}$

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

Пусть будет -мерным единичным кубом, . Пусть имеет ограниченную вариацию по в смысле Харди и Краузе. Тогда для любого в , ${\displaystyle {\overline {I}}^{s}}$ ${\displaystyle s}$ ${\displaystyle {\overline {I}}^{s}=[0,1]\times \cdots \times [0,1]}$ ${\displaystyle f}$ ${\displaystyle V(f)}$ ${\displaystyle {\overline {I}}^{s}}$ ${\displaystyle x_{1},\ldots ,x_{N}}$ ${\displaystyle I^{s}=[0,1)^{s}=[0,1)\times \cdots \times [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}).}$

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

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

Поэтому качество правила численного интегрирования зависит только от невязки . ${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})}$

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

Пусть . Ибо мы пишем ${\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}}$

TheЛ 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}}$Discrepancy имеет большое практическое значение, поскольку для заданного набора точек возможны быстрые явные вычисления. Таким образом, легко создавать оптимизаторы набора точек, используя Discrepancy в качестве критерия. ${\displaystyle L^{2}}$

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

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

Пусть — точки в и — произвольное положительное целое число. Тогда ${\displaystyle x_{1},\ldots ,x_{N}}$ ${\displaystyle I^{s}}$ ${\displaystyle 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. Существует константа, зависящая только от размерности , такая, что ${\displaystyle c_{s}}$ ${\displaystyle s}$

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

для любого конечного множества точек . ${\displaystyle {x_{1},\ldots ,x_{N}}}$

Гипотеза 2. Существует константа, зависящая только от : , такая, что: ${\displaystyle c'_{s}}$ ${\displaystyle s}$ ${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c'_{s}{\frac {(\ln N)^{s}}{N}}}$

для бесконечного числа для любой бесконечной последовательности . ${\displaystyle N}$ ${\displaystyle x_{1},x_{2},x_{3},\ldots }$

Эти гипотезы эквивалентны. Они были доказаны для WM Schmidt . В более высоких размерностях соответствующая проблема все еще открыта. Наиболее известные нижние границы принадлежат Майклу Лейси и его коллегам. ${\displaystyle s\leq 2}$

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

Пусть . Тогда ${\displaystyle s=1}$

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

для любого конечного множества точек . ${\displaystyle \{x_{1},\dots ,x_{N}}\}$

Пусть . В. М. Шмидт доказал, что для любого конечного множества точек , ${\displaystyle s=2}$ ${\displaystyle \{x_{1},\dots ,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 .}$

Для произвольных измерений К. Ф. Рот доказал, что ${\displaystyle 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}}}$

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

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

для любого конечного множества точек . ${\displaystyle \{x_{1},\dots ,x_{N}}\}$

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

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

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

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

где — некоторая константа, зависящая от последовательности. После гипотезы 2 считается, что эти последовательности имеют наилучший возможный порядок сходимости. Примерами ниже являются последовательность Ван дер Корпута , последовательности Холтона и последовательности Соболя . Одним из общих ограничений является то, что методы построения обычно могут гарантировать только порядок сходимости. На практике низкое расхождение может быть достигнуто только в том случае, если достаточно велико, и для больших заданных s этот минимум может быть очень большим. Это означает, что выполнение анализа Монте-Карло с, например, переменными и точками из генератора последовательностей с низким расхождением может дать лишь очень незначительное улучшение точности ^{[ требуется ссылка ]} . ${\displaystyle C}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle s=20}$ ${\displaystyle 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]

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

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

Позволять

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

быть -арным представлением положительного целого числа , т.е. . Установите ${\displaystyle b}$ ${\displaystyle n\geq 1}$ ${\displaystyle 0\leq d_{k}(n)<b}$

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

Тогда существует константа, зависящая только от , такая, что удовлетворяет условию ${\displaystyle C}$ ${\displaystyle b}$ ${\displaystyle (g_{b}(n))_{n\geq 1}}$

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

где находится звездное расхождение . ${\displaystyle 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

Пусть будут взаимно простыми положительными целыми числами, большими 1. Для заданных и -мерное множество Хаммерсли размера определяется как ^[7] ${\displaystyle b_{1},\ldots ,b_{s-1}}$ ${\displaystyle s}$ ${\displaystyle N}$ ${\displaystyle s}$ ${\displaystyle N}$

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

для . Тогда ${\displaystyle n=1,\ldots ,N}$

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

где — константа, зависящая только от . ${\displaystyle C}$ ${\displaystyle b_{1},\ldots ,b_{s-1}}$

Примечание : Формулы показывают, что множество Хаммерсли на самом деле является последовательностью Холтона, но мы получаем еще одно измерение бесплатно, добавляя линейную развертку. Это возможно только в том случае, если известно заранее. Линейное множество также является множеством с минимально возможным одномерным расхождением в целом. К сожалению, для более высоких измерений такие «наборы записей о расхождении» неизвестны. Для большинство генераторов множеств точек с низким расхождением обеспечивают по крайней мере близкие к оптимальным расхождения. ${\displaystyle N}$ ${\displaystyle 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] Реализация алгоритма на языке Fortran доступна в Netlib .

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

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

Примечания

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

Ссылки

• Дик, Йозеф; Пиллихшаммер, Фридрих (2010). Цифровые сети и последовательности: теория расхождений и квази-Монте-Карло интеграция . Cambridge University Press. ISBN 978-0-521-19159-3.
• Койперс, Л.; Нидеррайтер, Х. (2005), Равномерное распределение последовательностей , Dover Publications , ISBN 0-486-45019-8
• Харальд Нидеррайтер (1992). Генерация случайных чисел и методы квази-Монте-Карло . Общество промышленной и прикладной математики. ISBN 0-89871-295-5.
• Drmota, Michael; Tichy, Robert F. (1997). Последовательности, расхождения и приложения . Конспект лекций по математике. Том 1651. Springer. ISBN 3-540-62606-9.
• Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (1992). Numerical Recipes in C (2nd ed.). Cambridge University Press. см. Раздел 7.7 для менее технического обсуждения последовательностей с низким расхождением. ISBN 0-521-43108-5.

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

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