Las secuencias de Sobol (también llamadas secuencias LP τ o secuencias ( t , s ) en la base 2) son un ejemplo de secuencias cuasialeatorias de baja discrepancia . Fueron introducidos por primera vez por el matemático ruso Ilya M. Sobol (Илья Меерович Соболь) en 1967. [1]
Estas secuencias utilizan una base de dos para formar sucesivamente particiones uniformes más finas del intervalo unitario y luego reordenar las coordenadas en cada dimensión.
Buenas distribuciones en el hipercubo de la unidad s- dimensional
Sea I s = [0,1] s el hipercubo de la unidad s -dimensional, yf una función integrable real sobre I s . La motivación original de Sobol era construir una secuencia x n en I s para que
y la convergencia sea lo más rápida posible.
Es más o menos claro que para que la suma converja hacia la integral, los puntos x n deben llenar I s minimizando los huecos. Otra buena propiedad sería que las proyecciones de x n en una cara de menor dimensión de I s también dejan muy pocos agujeros. Por lo tanto, el llenado homogéneo de I s no califica porque en dimensiones inferiores muchos puntos estarán en el mismo lugar, por lo que serán inútiles para la estimación integral.
Estas buenas distribuciones se denominan ( t , m , s ) -nets y ( t , s ) -secuencias en base b . Para introducirlos, defina primero un intervalo s elemental en base b un subconjunto de I s de la forma
donde a j y d j son números enteros no negativos, ypara todo j en {1, ..., s}.
Dados 2 enteros , a ( t , m , s ) -net en base b es una secuencia x n de b m puntos de I s tales quepara todo el intervalo elemental P en la base b del hipervolumen λ ( P ) = b t − m .
Dado un número entero no negativo t , una ( t , s ) -secuencia en base b es una secuencia infinita de puntos x n tal que para todos los enteros, la secuencia es a ( t , m , s ) -net en base b .
En su artículo, Sobol describió las secuencias Π τ -mallas y LP τ , que son ( t , m , s ) -redes y ( t , s ) -secuencias en base 2 respectivamente. Los términos ( t , m , s ) -redes y ( t , s ) -secuencias en la base b (también llamadas secuencias de Niederreiter) fueron acuñadas en 1988 por Harald Niederreiter . [2] El término secuencias de Sobol se introdujo en artículos de habla inglesa tardía en comparación con Halton , Faure y otras secuencias de baja discrepancia.
Un algoritmo rápido
Antonov y Saleev propusieron una implementación del código Gray más eficiente . [3]
En cuanto a la generación de números de Sobol, están claramente ayudados por el uso del código Gray. en lugar de n para construir el n -ésimo punto.
Supongamos que ya hemos generado todos los trazos de secuencia de Sobol hasta n - 1 y hemos guardado en la 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, digamos el k -ésimo, bit (que es el bit más a la derecha de n - 1), todo lo que necesita ser hecho es un solo XOR operación para cada dimensión con el fin de propagar la totalidad de la x n -1 a x n , es decir,
Propiedades de uniformidad adicionales
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 hipercubo 2 d que resulta de subdividir el hipercubo unitario a lo largo cada una de sus extensiones de longitud a 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 hipercubo de 4 d que resulta de subdividir el hipercubo unitario a lo largo de cada una de sus extensiones de longitud en cuatro partes iguales.
Hay condiciones matemáticas que garantizan las propiedades A y A '.
- Teorema
- La secuencia de Sobol d- dimensional posee la propiedad A si
- donde V d es la matriz binaria d × d definida por
- donde v k , j , m denota el m -ésimo dígito después del punto binario del número de dirección v k , j = (0. v k , j , 1 v k , j , 2 ...) 2 .
- Teorema
- La secuencia de Sobol d- dimensional posee la propiedad A 'si
- donde U d es la matriz binaria de 2 d × 2 d definida por
- donde v k , j , m denota el m -ésimo dígito después del punto binario del número de dirección v k , j = (0. v k , j , 1 v k , j , 2 ...) 2 .
Las pruebas de las propiedades A y A 'son independientes. Por tanto, es posible construir la secuencia de Sobol que satisfaga ambas propiedades A y A 'o solo una de ellas.
La inicialización de los números de Sobol
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 recibir diferentes realizaciones de la secuencia de Sobol para dimensiones seleccionadas. Una mala selección de números iniciales puede reducir considerablemente la eficiencia de las secuencias de Sobol cuando se utilizan para el cálculo.
Podría decirse que la opción más fácil para los números de inicialización es simplemente tener el l -ésimo bit más a la izquierda establecido, y todos los demás bits a cero, es decir, m k , j = 1 para todos k y j . Esta inicialización se suele denominar inicialización de la unidad . Sin embargo, tal secuencia no pasa la prueba para la propiedad A y A 'incluso para dimensiones bajas y, por lo tanto, esta inicialización es mala.
Implementación y disponibilidad
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 grandes dimensiones 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 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] y Julia . [12] Hay disponible una implementación diferente de código abierto / libre en hasta 1111 dimensiones para C ++ , Fortran 90 , Matlab y Python . [13]
Por último, comerciales generadores de secuencias Sobol están disponibles dentro de, por ejemplo, la biblioteca de Nag ,. [14] Una versión está disponible en la Agencia de Desarrollo Offshore Británico-Ruso (BRODA). [15] [16] MATLAB también contiene una implementación [17] como parte de su Caja de herramientas de estadísticas.
Ver también
Notas
- ^ Estos números generalmente se denominan números de inicialización .
Referencias
- ^ Sobol, IM (1967), "Distribución de puntos en un cubo y evaluación aproximada de integrales". Z h. Vych. Estera. Estera. Fiz. 7 : 784–802 (en ruso); Computación de la URSS. Matemáticas. Matemáticas. Phys. 7 : 86–112 (en inglés).
- ^ Niederreiter, H. (1988). "Secuencias de baja discrepancia y baja dispersión", Journal of Number Theory 30 : 51–70.
- ^ Antonov, IA y Saleev, VM (1979) "Un método económico de calcular LP τ -secuencias". Z h. Vych. Estera. Estera. Fiz. 19 : 243–245 (en ruso); Computación de la URSS. Matemáticas. Matemáticas. Phys. 19 : 252-256 (en inglés).
- ^ Sobol, IM (1976) "Secuencias distribuidas uniformemente con una propiedad uniforme adicional". Z h. Vych. Estera. Estera. Fiz. 16 : 1332-1337 (en ruso); Computación de la URSS. Matemáticas. Matemáticas. Phys. 16 : 236–242 (en inglés).
- ^ Sobol, IM y Levitan, YL (1976). "La producción de puntos distribuidos uniformemente en un cubo multidimensional" Tech. Rep. 40, Instituto de Matemáticas Aplicadas, Academia de Ciencias de la URSS (en ruso).
- ^ Bratley, P. y Fox, BL (1988), "Algoritmo 659: Implementación del generador de secuencia cuasialeatoria de Sobol". ACM Trans. Matemáticas. Software 14 : 88–100.
- ^ "Generador de secuencia de Sobol" . Universidad de Nueva Gales del Sur . 2010-09-16 . Consultado el 20 de diciembre de 2013 .
- ^ Jäckel, P. (2002) "Métodos de Monte Carlo en finanzas". Nueva York: John Wiley and Sons . ( ISBN 0-471-49741-X .)
- ^ Prensa, WH, Teukolsky, SA, Vetterling, WT y Flannery, BP (1992) "Recetas numéricas en Fortran 77: El arte de la informática científica, 2ª ed." Cambridge University Press, Cambridge, Reino Unido
- ^ C implementación de la secuencia de Sobol en la biblioteca NLopt (2007).
- ^ Imperiale, G. "pyscenarios: Python Scenario Generator" .
- ^ Paquete Sobol.jl : implementación de Julia de la secuencia de Sobol.
- ^ La secuencia cuasirandom de Sobol , código para C ++ / Fortran 90 / Matlab / Python por J. Burkardt
- ^ "Grupo de algoritmos numéricos" . Nag.co.uk. 2013-11-28 . Consultado el 20 de diciembre de 2013 .
- ^ I. Sobol ', D. Asotsky, A. Kreinin, S. Kucherenko (2011). "Construcción y comparación de generadores Sobol 'de alta dimensión" (PDF) . Wilmott Journal . Noviembre : 64–79.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ "Broda" . Broda. 2004-04-16 . Consultado el 20 de diciembre de 2013 .
- ^ página de referencia de sobolset . Consultado el 24 de julio de 2017.
enlaces externos
- Algoritmos recopilados del ACM (consulte los algoritmos 647, 659 y 738).
- Colección de códigos de programación del generador de secuencias Sobol
- Generador freeware C ++ de secuencia Sobol