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

256 баллов из первых 256 баллов для последовательности Соболя 2,3 (вверху) по сравнению с источником псевдослучайных чисел (внизу). Последовательность Соболь покрывает пространство более равномерно. (красный=1,..,10, синий=11,..,100, зеленый=101,..,256)

Последовательности Соболя LP _τ (также называемые последовательностями или последовательностями ( t , s ) в базе 2) являются примером квазислучайных последовательностей с низким расхождением . Впервые они были введены российским математиком Ильей Собольем (Илья Меерович Соболь) в 1967 году.

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

Хорошие распределения в s -мерном единичном гиперкубе

Позвольте мне ^с = [0,1] ^с — s -мерный единичный гиперкуб , а f — действительная интегрируемая функция над I ^с . Первоначальной мотивацией Соболя было построить последовательность x _n в I ^с так что

$\lim _{n\to \infty }{\frac {1}{n}}\sum _{i=1}^{n}f(x_{i})=\int _{I^{s}}f$

и сходимость должна быть максимально быстрой.

Более-менее понятно, что для того, чтобы сумма сходилась к интегралу, точки x _n должны заполнять I ^с минимизация дырок. Еще одним хорошим свойством было бы то, что проекции x _n на низкомерную грань I ^с оставьте также очень мало отверстий. Отсюда однородное заполнение I ^с не подходит, поскольку в меньших измерениях многие точки будут находиться в одном и том же месте, поэтому бесполезны для интегральной оценки.

Эти хорошие распределения называются ( t , m , s )-сетями и ( t , s )-последовательностями в базе b . Чтобы представить их, определите сначала элементарный s -интервал в базе b - подмножестве I ^с формы

$\prod _{j=1}^{s}\left[{\frac {a_{j}}{b^{d_{j}}}},{\frac {a_{j}+1}{b^{d_{j}}}}\right],$

где a _j и d _j — целые неотрицательные числа, и $a_{j}<b^{d_{j}}$ для всех j из {1,...,s}.

Даны 2 целых числа $0\leq t\leq m$, a ( t , m , s )-сеть в базе b представляет собой последовательность x _n из b ^м точки я ^с такой, что $\operatorname {Card} P\cap \{x_{1},...,x_{b^{m}}\}=b^{t}$ для всех элементарных интервалов P в базе b гиперобъема λ ( P ) = b ^т-м .

Учитывая неотрицательное целое число t , ( t , s )-последовательность в базе b представляет собой бесконечную последовательность точек x _n такую, что для всех целых чисел $k\geq 0,m\geq t$, последовательность $\{x_{kb^{m}},...,x_{(k+1)b^{m}-1}\}$ является ( t , m , s )-сетью в базе b .

В своей статье Соболь описал Π _τ -сети и LP _τ последовательности , которые являются ( t , m , s )-сетями и ( t , s )-последовательностями в базе 2 соответственно. Термины ( t , m , s )-сети и ( t , s )-последовательности в базе b (также называемые последовательностями Нидеррайтера) были придуманы в 1988 году Харальдом Нидеррайтером . Термин «последовательности Соболя» был введен в поздних англоязычных статьях по сравнению с последовательностями Холтона , Фора и другими последовательностями с низким расхождением.

Быстрый алгоритм

Более эффективная реализация кода Грея была предложена Антоновым и Салеевым.

Что касается генерации чисел Соболя, то им явно помогает использование кода Грея. $G(n)=n\oplus \lfloor n/2\rfloor$ вместо n для построения n -й точки.

Предположим, мы уже сгенерировали все отрисовки последовательности Соболя до n − 1 и сохранили в памяти значения x _{n −1, j} для всех требуемых размерностей. Поскольку код Грея G ( n ) отличается от кода предыдущего G ( n − 1) всего на один, скажем, k -й бит (который является крайним правым нулевым битом n − 1), все, что необходимо Необходимо выполнить одну операцию XOR для каждого измерения, чтобы распространить все x _{n −1} на x _n , т.е.

$x_{n,i}=x_{n-1,i}\oplus v_{k,i}.$

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

Соболь ввел дополнительные условия однородности, известные как свойства А и А'.

Определение

Говорят, что последовательность с низким расхождением удовлетворяет свойству А , если для любого двоичного сегмента (не произвольного подмножества) d -мерной последовательности длины 2 ^д в каждых 2-х ровно одна ничья ^д гиперкубы, которые возникают в результате разделения единичного гиперкуба вдоль каждого из его расширений пополам.

Определение

Говорят, что последовательность с низким расхождением удовлетворяет свойству А' , если для любого двоичного сегмента (не произвольного подмножества) d -мерной последовательности длины 4 ^д в каждых 4-х ровно один розыгрыш ^д гиперкубы, которые возникают в результате разделения единичного гиперкуба вдоль каждого из его расширений на четыре равные части.

Существуют математические условия, гарантирующие свойства А и А'.

Теорема

-мерная последовательность d Соболя обладает свойством A тогда и только тогда, когда

$\det(\mathbf {V} _{d})\equiv 1(\mod 2),$

где В ^д - двоичная матрица d × d, определяемая формулой

$\mathbf {V} _{d}:={\begin{pmatrix}{v_{1,1,1}}&{v_{2,1,1}}&{\dots }&{v_{d,1,1}}\\{v_{1,2,1}}&{v_{2,2,1}}&{\dots }&{v_{d,2,1}}\\{\vdots }&{\vdots }&{\ddots }&{\vdots }\\{v_{1,d,1}}&{v_{2,d,1}}&{\dots }&{v_{d,d,1}}\end{pmatrix}},$

где v _{k , j , m} обозначает m -ю цифру после двоичной точки номера направления v _{k , j} = (0. v _{k , j ,1} v _{k , j ,2} ...) ₂ .

Теорема

-мерная последовательность d Соболя обладает свойством А' тогда и только тогда, когда

$\det(\mathbf {U} _{d})\equiv 1\mod 2,$

где U ^д - двоичная матрица размером 2 d × 2 d, определяемая формулой

$\mathbf {U} _{d}:={\begin{pmatrix}{v_{1,1,1}}&{v_{1,1,2}}&{v_{2,1,1}}&{v_{2,1,2}}&{\dots }&{v_{d,1,1}}&{v_{d,1,2}}\\{v_{1,2,1}}&{v_{1,2,2}}&{v_{2,2,1}}&{v_{2,2,2}}&{\dots }&{v_{d,2,1}}&{v_{d,2,2}}\\{\vdots }&{\vdots }&{\vdots }&{\vdots }&{\ddots }&{\vdots }&{\vdots }\\{v_{1,2d,1}}&{v_{1,2d,2}}&{v_{2,2d,1}}&{v_{2,2d,2}}&{\dots }&{v_{d,2d,1}}&{v_{d,2d,2}}\end{pmatrix}},$

где v _{k , j , m} обозначает m -ю цифру после двоичной точки номера направления v _{k , j} = (0. v _{k , j ,1} v _{k , j ,2} ...) ₂ .

Критерии свойств A и A' независимы. Таким образом, можно построить последовательность Соболя, удовлетворяющую обоим свойствам А и А' или только одному из них.

Инициализация чисел Соболя

Для построения последовательности Соболя vi _{j , набор номеров направлений} необходимо выбрать . Имеется некоторая свобода в выборе начальных номеров направлений. Следовательно, для выбранных размерностей можно получить разные реализации последовательности Соболя. Неправильный выбор начальных чисел может значительно снизить эффективность использования последовательностей Соболя для вычислений.

Вероятно, самый простой выбор номеров инициализации — это просто установить l -й крайний левый бит, а все остальные биты равны нулю, т. е. m _{k , j} = 1 для всех k и j . Эту инициализацию обычно называют инициализацией устройства . Однако такая последовательность не проходит тест на свойства A и A' даже для малых размерностей, и, следовательно, эта инициализация плоха.

Реализация и доступность

Хорошие числа инициализации для разного количества измерений предоставлены несколькими авторами. Например, Соболь предоставляет номера инициализации для размерностей до 51. Тот же набор номеров инициализации используется Брэтли и Фоксом.

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

Другие реализации доступны в виде подпрограмм C, Fortran 77 или Fortran 90 в коллекции программного обеспечения Numerical Recipes . Бесплатная реализация с открытым исходным кодом , имеющая до 1111 измерений, основанная на числах инициализации Джо и Куо, доступна на языке C. и до 21201 измерения в Python и Джулия . Другая бесплатная реализация с открытым исходным кодом, имеющая до 1111 измерений, доступна для C++ , Fortran 90 , Matlab и Python .

Коммерческие генераторы последовательностей Соболя доступны, например, в библиотеке NAG . ООО "БРОДА". обеспечивает генераторы Соболя и скремблированных последовательностей Соболя с дополнительными свойствами однородности A и A' до максимальной размерности 131072. Эти генераторы были разработаны совместно с профессором И. Соболь. МАТЛАБ содержит генераторы последовательностей Соболя размером до 1111 как часть панели инструментов статистики.

См. также

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

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

• Сборник алгоритмов АКМ (см. алгоритмы 647, 659 и 738).
• Сборник программных кодов генератора последовательностей Соболя
• Бесплатный C++-генератор последовательности Соболя