Secuencia de Sobol

256 puntos de los primeros 256 puntos de la secuencia de Sobol' 2,3 (arriba) en comparación 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 sucesivamente más finas del intervalo unitario y luego reordenan las coordenadas en cada dimensión.

Buenas distribuciones en els-Hipercubo unitario dimensional

Sea I ^s = [0,1] ^s el hipercubo unitario de dimensión s y f una función integrable real sobre I ^s . La motivación original de Sobol' era construir una secuencia x _n en I ^s de modo que

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

y la convergencia sea lo más rápida posible.

Está 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 sobre una cara de I ^s de menor dimensión dejen también muy pocos huecos. Por lo tanto, el llenado homogéneo de I ^s no cumple los requisitos porque en dimensiones inferiores muchos puntos estarán en el mismo lugar, por lo tanto, serán inútiles para la estimación integral.

Estas buenas distribuciones se denominan ( t , m , s )-redes y ( t , s )-secuencias en base b . Para introducirlas, definamos primero un intervalo s elemental en base b, un subconjunto de I ^s de la forma

\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 números enteros no negativos, y para todo j en {1, ...,s}. $a_{j}<b^{d_{j}}$

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

Dado un 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 una ( t , m , s )-red en base b . $k\geq 0,m\geq t$ $\{x_{kb^{m}},...,x_{(k+1)b^{m}-1}\}$

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' fue introducido en artículos tardíos en inglés en comparación con Halton , Faure y otras secuencias de baja discrepancia.

Un algoritmo rápido

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

En cuanto a la generación de números de Sobol, estos se ven claramente facilitados por el uso del código Gray en lugar de n para construir el punto n -ésimo. $G(n)=n\oplus \lpiso n/2\rpiso$

Supongamos que ya hemos generado todas las secuencias de Sobol hasta n − 1 y hemos guardado 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 solo un único bit, digamos el k -ésimo (que es un bit cero más a la derecha de n − 1), todo lo que se necesita hacer es una única operación XOR para cada dimensión para propagar todos los x _{n −1} a x _n , es decir

x_{n,i}=x_{n-1,i}\omás v_{k,i}.

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 una extracción en cada 2 ^d hipercubos que resultan de subdividir el hipercubo unitario a lo largo de cada una de sus extensiones de longitud en 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 una extracción 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'.

Teorema

La secuencia de Sobol' d -dimensional posee la propiedad A si y solo si

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

donde V ^d es la matriz binaria d × d definida por

\mathbf {V} _{d}:={\begin{pmatrix}{v_{1,1,1}}&{v_{2,1,1}}&{\puntos }&{v_{d,1,1}}\\{v_{1,2,1}}&{v_{2,2,1}}&{\puntos }&{v_{d,2,1}}\\{\vpuntos }&{\vpuntos }&{\dpuntos }&{\vpuntos }\\{v_{1,d,1}}&{v_{2,d,1}}&{\puntos }&{v_{d,d,1}}\end{pmatrix}},

con v _{k , j , m} denotando 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} ...) ₂ .

Teorema

La secuencia Sobol' d -dimensional posee la propiedad A' si y solo si

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

donde U ^d es la matriz binaria 2 d × 2 d definida por

\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}}&{\puntos }&{v_{d,2d,1}}&{v_{d,2d,2}}\end{pmatrix}},

con v _{k , j , m} denotando 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} ...) ₂ .

Las pruebas para las propiedades A y A' son independientes. Por lo tanto, es posible construir la secuencia de Sobol' que satisface 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, se debe 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 las 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 sencilla 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 en cero, es decir, m _{k , j} = 1 para todos los k y j . Esta inicialización suele denominarse inicialización unitaria . Sin embargo, una secuencia de este tipo no supera la prueba de las propiedades A y A' incluso para dimensiones bajas y, por lo tanto, esta inicialización es incorrecta.

Implementación y disponibilidad

Varios autores proporcionan buenos números de inicialización para diferentes cantidades 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 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] Una implementación libre/de código abierto diferente 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' desordenados con propiedades de uniformidad adicionales A y A' hasta una dimensión máxima de 131072. Estos generadores fueron desarrollados en conjunto 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ísticas.

Véase también

Secuencia de baja discrepancia – Tipo de secuencias matemáticas
Método cuasi-Monte Carlo – Proceso de integración numérica

Notas

^ Estos números normalmente se denominan números de inicialización .

Referencias

^ Sobol', IM (1967), "Distribución de puntos en un cubo y evaluación aproximada de integrales". Zh. Vych. Mat. Mat. Fiz. 7 : 784–802 (en ruso); URSS Comput. Maths. Math. 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 para calcular secuencias _τ de LP ". Zh. Vych. Mat. Mat. Fiz. 19 : 243–245 (en ruso); URSS Comput. Maths. Math. Phys. 19 : 252–256 (en inglés).
^ Sobol', IM (1976) "Secuencias uniformemente distribuidas con una propiedad uniforme adicional". Zh. Vych. Mat. Mat. Fiz. 16 : 1332–1337 (en ruso); URSS Comput. Maths. Math. 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 secuencias cuasialeatorias de Sobol". ACM Trans. Math. Software 14 : 88–100.
^ "Generador de secuencias de Sobol". Universidad de Nueva Gales del Sur . 16 de septiembre de 2010. 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 .)
^ Press, WH, Teukolsky, SA, Vetterling, WT y Flannery, BP (1992) "Recetas numéricas en Fortran 77: El arte de la computación científica, 2.ª ed." Cambridge University Press, Cambridge, Reino Unido
^ Implementación en C de la secuencia de Sobol en la biblioteca NLopt (2007).
^ "Referencia de la API de SciPy: scipy.stats.qmc.Sobol".
^ Imperiale, G. "pyscenarios: generador de escenarios de Python".
^ Paquete Sobol.jl: implementación de Julia de la secuencia Sobol.
^ La secuencia cuasialeatoria de Sobol, código para C++/Fortran 90/Matlab/Python de J. Burkardt
^ "Grupo de algoritmos numéricos". Nag.co.uk. 28 de noviembre de 2013. 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 . Nov (56): 64–79. doi :10.1002/wilm.10056.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
^ "Broda". Broda. 2024-01-23 . Consultado el 23 de enero de 2024 .
^ Página de referencia de Sobolset. Consultado el 24 de julio de 2017.

Enlaces externos

Algoritmos recopilados del ACM (ver algoritmos 647, 659 y 738).
Colección de códigos de programación del generador de secuencias de Sobol
Generador gratuito de secuencias de Sobol en C++