Sobol序列

Sobol序列（亦称LPτ序列或基2的(t, s)序列）是一类准随机。它们由俄国数学家（Илья Меерович Соболь）于1967年首次提出。Sobol’, I.M. (1967), "Distribution of points in a cube and approximate evaluation of integrals". Zh. Vych. Mat. Mat. Fiz. 7: 784–802 (in Russian); U.S.S.R Comput. Maths. Math. Phys. 7: 86–112 (in English).

这些序列使用以二为基底将单位区间依次划分为更细的均匀子区间，并在每一维度中对坐标重排。

 在s维单位超立方体中的良好分布 
设为s维单位超立方体，且是定义在上的可积实函数。Sobol'最初的动机是构造序列（位于中），使得且收敛尽可能快。

使和收敛到积分，较为明显的是点应尽量填满以最小化空洞。另一个好的性质是在低维面的投影也应尽量少留空洞。因此简单的均匀填充Is并不合适，因为在低维投影中许多点会重合，因而对积分估计无用。

这些良好分布称为基的(t,m,s)-网与(t,s)-序列。先定义基的基本s-区间为形式其中与为非负整数，且对所有{1,…,s}有。

给定整数，基的(t,m,s)-网是位于的个点的序列，使得对任意基的基本区间 ''P''，当其超体积为时，有 。

给定非负整数，基的(t,s)-序列是一个无限序列，满足对任意整数序列是基的一个(t,m,s)-网。

Sobol'在他的文章中描述了Πτ-网格与LPτ-序列，它们分别是基2的(t,m,s)-网与(t,s)-序列。基的(t,m,s)-网与(t,s)-序列（也称为Niederreiter序列）这一术语由在1988年提出。Niederreiter, H. (1988). "Low-Discrepancy and Low-Dispersion Sequences", Journal of Number Theory 30: 51–70.“Sobol序列”这一术语在晚期的英语文献中被用来与、Faure及其它低差异序列相区分。

 快速算法 
Antonov与Saleev提出了一种更高效的格雷码实现。Antonov, I.A. and Saleev, V.M. (1979) "An economic method of computing LPτ-sequences". Zh. Vych. Mat. Mat. Fiz. 19: 243–245 (in Russian); U.S.S.R. Comput. Maths. Math. Phys. 19: 252–256 (in English).

在生成Sobol数时，使用格雷码代替来构造第n个点是很有帮助的。

设已生成直到的所有Sobol序列值，并在内存中保存了所有维度所需的值。由于格雷码与前一项只在单一位上不同（该位为n−1的最右侧零位），因此对每一维度只需做一次异或（XOR）运算即可将所有推导为，即

 额外的均匀性性质 
Sobol'引入了称为性质A与A'的附加均匀性条件。Sobol’, I. M. (1976) "Uniformly distributed sequences with an additional uniform property". Zh. Vych. Mat. Mat. Fiz. 16: 1332–1337 (in Russian); U.S.S.R. Comput. Maths. Math. Phys. 16: 236–242 (in English).

 定义
 若对任意二进段（而非任意子集）长度为的d维序列段，单位超立方体沿每条边各自二等分所得到的个超立方体中恰有且只有一个抽样点，则称该低差异序列满足性质A。

 定义
 若对任意二进段（而非任意子集）长度为的d维序列段，单位超立方体沿每条边各自四等分所得到的个超立方体中恰有且只有一个抽样点，则称该低差异序列满足性质A'。

存在保证性质A与A'的数学条件。

对性质A与A'的检验是相互独立的。因此可以构造同时满足A和A'的Sobol序列，或仅满足其中之一的序列。

 Sobol数的初始化 
要构造Sobol序列，需要选择一组方向数。初始化方向数的选择存在一定自由度。这些数通常被称为“初始化数”。因此针对不同维数可能得到不同的Sobol序列实现。若初始化数选择不佳，会显著降低Sobol序列在计算中的效率。

一种最容易的初始化选择是令第l位最左侧位为1，其余位为0，即对所有和取。此初始化通常称为“单位初始化”。然而，该初始化即使在低维度下也不能通过性质A与A'的检验，因此属于较差的初始化。

 实现与可获得性 
针对不同维数的良好初始化数已由若干作者提供。例如，Sobol'提供了最高到51维的初始化数。Sobol’, I.M. and Levitan, Y.L. (1976). "The production of points uniformly distributed in a multidimensional cube" Tech. Rep. 40, Institute of Applied Mathematics, USSR Academy of Sciences (in Russian).同一组初始化数也被Bratley和Fox使用。Bratley, P. and Fox, B. L. (1988), "Algorithm 659: Implementing Sobol’ quasirandom sequence generator". ACM Trans. Math. Software 14: 88–100.

高维度的初始化数可在Joe和Kuo处获得。在其著作《》中提供了到32维的初始化数。Jäckel, P. (2002) "Monte Carlo methods in finance". New York: John Wiley and Sons. (.)

其它实现作为C、Fortran 77或Fortran 90例程出现在《》软件集。Press, W.H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. (1992) "Numerical Recipes in Fortran 77: The Art of Scientific Computing, 2nd ed." Cambridge University Press, Cambridge, U.K.基于Joe和Kuo的初始化数，有一个可支持最多1111维的自由/开源C实现（见NLopt库）C implementation of the Sobol’ sequence  in the NLopt library  (2007).，以及一个可支持最多21201维的Python实现和Julia实现Sobol.jl package: Julia implementation of the Sobol’ sequence.。另一套可支持最多1111维的自由/开源实现可用于C++、Fortran 90、MATLAB与Python。The Sobol’ Quasirandom Sequence , code for C++/Fortran 90/Matlab/Python by J. Burkardt

商业的Sobol序列生成器可在例如NAG Library中获得。BRODA Ltd.提供具有附加均匀性性质A与A'的Sobol与扰动Sobol序列生成器，最大维度可达131072；这些生成器由BRODA与Ilya M. Sobol协同开发。MATLABsobolset reference page . Retrieved 2017-07-24.的统计工具箱亦包含最多到1111维的Sobol序列生成器。

 相关 


 拟蒙特卡罗方法

 注释 

 参考 

Category:序列