secuencia de Sobol

256 puntos de los primeros 256 puntos para la secuencia de Sobol' 2,3 (arriba) comparados con una fuente de números pseudoaleatorios (abajo). La secuencia de Sobol' cubre el espacio de manera más uniforme. (rojo=1,...,10, azul=11,...,100, verde=101,...,256)

Las secuencias de Sobol (también llamadas secuencias LP _τ o secuencias ( t , s ) en base 2) son un tipo de secuencia cuasialeatoria de baja discrepancia . Fueron introducidas por primera vez por el matemático ruso Ilya M. Sobol (Илья Меерович Соболь) en 1967. ^{[ 1 ]}  

Estas secuencias utilizan una base de dos para formar particiones uniformes cada vez más finas del intervalo unitario y luego reordenar las coordenadas en cada dimensión.

Sea I ^s = [0,1] ^s el hipercubo unitario s -dimensional , y f una función integrable real sobre I ^s . La motivación original de Sobol' fue construir una sucesión x _n en I ^s tal que $${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\sum _{i=1}^{n}f(x_{i})=\int _{I^{s}}f}$$ y que la convergencia sea lo más rápida posible.

Resulta bastante claro que, para que la suma converja hacia la integral, los puntos x _n deben llenar I ^s minimizando los huecos. Otra propiedad deseable sería que las proyecciones de x _n sobre una cara de menor dimensión de I ^s también dejen muy pocos huecos. Por lo tanto, el llenado homogéneo de I ^s no es suficiente, ya que en dimensiones inferiores muchos puntos coincidirán en el mismo lugar, lo que resulta inútil para la estimación de la integral.

Estas buenas distribuciones se denominan redes ( t , m , s ) y secuencias ( t , s ) en base b . Para introducirlas, definimos primero un intervalo s elemental en base b, un subconjunto de I ^s de la forma $${\displaystyle \prod _{j=1}^{s}\left[{\frac {a_{j}}{b^{d_{j}}}},{\frac {a_{j}+1}{b^{d_{j}}}}\right],}$$ donde a _j y d _j son enteros no negativos, y${\displaystyle a_{j}<b^{d_{j}}}$para todo j en {1, ...,s}.

Dados 2 números enteros${\displaystyle 0\leq t\leq m}$, una red ( t , m , s ) en base b es una secuencia x _n de b ^m puntos de I ^s tal que${\displaystyle \operatorname {Card} P\cap \{x_{1},...,x_{b^{m}}\}=b^{t}}$para todo intervalo elemental P en base b del hipervolumen λ ( P ) = b ^t−m .

Dado un entero no negativo t , una secuencia ( t , s ) en base b es una secuencia infinita de puntos x _n tal que para todos los enteros${\displaystyle k\geq 0,m\geq t}$, la secuencia${\displaystyle \{x_{kb^{m}},...,x_{(k+1)b^{m}-1}\}}$es una red ( t , m , s ) en base b .

En su artículo, Sobol' describió las mallas Π _τ y las secuencias LP _τ , que son redes ( t , m , s ) y secuencias ( t , s ) en base 2 respectivamente. Los términos redes ( t , m , s ) y secuencias ( t , s ) en base b (también llamadas secuencias de Niederreiter) fueron acuñados en 1988 por Harald Niederreiter . ^{[ 2 ]} El término secuencias de Sobol' se introdujo en trabajos posteriores en inglés en comparación con las secuencias de Halton , Faure y otras secuencias de baja discrepancia.

Antonov y Saleev propusieron una implementación más eficiente del código Gray . ^{[ 3 ]}

En cuanto a la generación de números Sobol', es evidente que se ven facilitados por el uso del código Gray.${\displaystyle G(n)=n\oplus \lfloor n/2\rfloor }$en lugar de n para construir el dibujo del n -ésimo punto.

Supongamos que ya hemos generado todas las secuencias de Sobol hasta n − 1 y hemos almacenado en memoria los valores x _{n − 1, j} para todas las dimensiones requeridas. Dado que el código Gray G ( n ) difiere del anterior G ( n − 1) en un solo bit, digamos el k -ésimo bit (que es el bit cero más a la derecha de n − 1), todo lo que se necesita hacer es una sola operación XOR para cada dimensión con el fin de propagar todos los x _{n − 1} a x _n , es decir      

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

Sobol' introdujo condiciones de uniformidad adicionales conocidas como propiedad A y A'. ^{[ 4 ]}

Definición

Se dice que una secuencia de baja discrepancia satisface la Propiedad A si para cualquier segmento binario (no un subconjunto arbitrario) de la secuencia d -dimensional de longitud 2 ^d hay exactamente un dibujo en cada 2 ^d hipercubos que resultan de subdividir el hipercubo unitario a lo largo de cada una de sus extensiones de longitud por la mitad.

Definición

Se dice que una secuencia de baja discrepancia satisface la Propiedad A' si para cualquier segmento binario (no un subconjunto arbitrario) de la secuencia d -dimensional de longitud 4 ^d hay exactamente un dibujo en cada 4 ^d hipercubos que resultan de subdividir el hipercubo unitario a lo largo de cada una de sus extensiones de longitud en cuatro partes iguales.

Existen condiciones matemáticas que garantizan las propiedades A y A'.

Las pruebas para las propiedades A y A' son independientes. Por lo tanto, es posible construir la secuencia de Sobol' que satisfaga ambas propiedades, A y A', o solo una de ellas.

Para construir una secuencia de Sobol', es necesario seleccionar un conjunto de números de dirección v _{i , j . Existe cierta libertad en la selección de los números de dirección iniciales.} ^{[ nota 1 ]} Por lo tanto, es posible obtener diferentes realizaciones de la secuencia de Sobol' para dimensiones seleccionadas. Una mala selección de los números iniciales puede reducir considerablemente la eficiencia de las secuencias de Sobol' cuando se utilizan para cálculos.

Podría decirse que la opción más sencilla para los números de inicialización es simplemente establecer el l -ésimo bit más a la izquierda y dejar todos los demás bits en cero, es decir, m _{k , j} = 1 para todo k y j . Esta inicialización se suele denominar inicialización unitaria . Sin embargo, esta secuencia no supera la prueba de las propiedades A y A' incluso para dimensiones bajas, por lo que esta inicialización es incorrecta.

Varios autores proporcionan buenos números de inicialización para diferentes números de dimensiones. Por ejemplo, Sobol' proporciona números de inicialización para dimensiones de hasta 51. ^{[ 5 ]} Bratley y Fox utilizan el mismo conjunto de números de inicialización. ^{[ 6 ]}

Los números de inicialización para dimensiones altas están disponibles en Joe y Kuo. ^{[ 7 ]} Peter Jäckel proporciona números de inicialización hasta la dimensión 32 en su libro " Métodos de Monte Carlo en finanzas ". ^{[ 8 ]}

Otras implementaciones están disponibles como rutinas en C, Fortran 77 o Fortran 90 en la colección de software Numerical Recipes . ^{[ 9 ]} Una implementación libre/de código abierto en hasta 1111 dimensiones, basada en los números de inicialización de Joe y Kuo, está disponible en C, ^{[ 10 ]} y hasta 21201 dimensiones en Python ^{[ 11 ] [ 12 ]} y Julia . ^{[ 13 ]} Otra implementación libre/de código abierto en hasta 1111 dimensiones está disponible para C++ , Fortran 90 , Matlab y Python . ^{[ 14 ]}

Los generadores de secuencias Sobol' comerciales están disponibles, por ejemplo, en la Biblioteca NAG . ^{[ 15 ]} BRODA Ltd. ^{[ 16 ] [ 17 ]} proporciona generadores de secuencias Sobol' y Sobol' aleatorizadas con propiedades de uniformidad adicionales A y A' hasta una dimensión máxima de 131072. Estos generadores fueron desarrollados en colaboración con el Prof. I. Sobol'. MATLAB ^{[ 18 ]} contiene generadores de secuencias Sobol' hasta la dimensión 1111 como parte de su Caja de herramientas de estadística.

• Secuencia de baja discrepancia – Tipo de secuencia matemática s 
• Método cuasi-Monte Carlo – Proceso de integración numérica 

• Algoritmos recopilados de la ACM (véanse los algoritmos 647, 659 y 738).
• Colección de códigos de programación para generadores de secuencias Sobol'
• Generador gratuito en C++ de la secuencia de Sobol.