En matemáticas , una secuencia de baja discrepancia es una secuencia con la propiedad de que para todos los valores de , su subsecuencia tiene una baja discrepancia .
En términos generales, la discrepancia de una secuencia es baja si la proporción de puntos de la secuencia que caen en un conjunto arbitrario B es casi proporcional a la medida de B , como sucedería en promedio (pero no para muestras particulares) en el caso de una secuencia equidistribuida . Las definiciones específicas de discrepancia difieren con respecto a la elección de B ( hiperesferas , hipercubos , etc.) y cómo se calcula la discrepancia para cada B (generalmente normalizada) y combinada (generalmente tomando el peor valor).
Las secuencias de baja discrepancia también se denominan secuencias cuasialeatorias , debido a su uso común como reemplazo de números aleatorios distribuidos uniformemente . El modificador "cuasi" se utiliza para indicar más claramente que los valores de una secuencia de baja discrepancia no son aleatorios ni pseudoaleatorios , pero dichas secuencias comparten algunas propiedades de las variables aleatorias y en ciertas aplicaciones, como el método cuasi-Monte Carlo, su menor discrepancia es una ventaja importante.
Los números cuasialeatorios tienen una ventaja sobre los números aleatorios puros: cubren el dominio de interés de manera rápida y uniforme.
Dos aplicaciones útiles son la búsqueda de la función característica de una función de densidad de probabilidad y la búsqueda de la función derivada de una función determinista con una pequeña cantidad de ruido. Los números cuasialeatorios permiten calcular momentos de orden superior con gran precisión y muy rápidamente.
Las aplicaciones que no implican ordenamiento serían la búsqueda de la media , la desviación estándar , la asimetría y la curtosis de una distribución estadística, y la búsqueda de los máximos y mínimos integrales y globales de funciones deterministas difíciles. Los números cuasialeatorios también se pueden utilizar para proporcionar puntos de partida para algoritmos deterministas que solo funcionan localmente, como la iteración de Newton-Raphson .
Los números cuasialeatorios también se pueden combinar con algoritmos de búsqueda. Con un algoritmo de búsqueda, los números cuasialeatorios se pueden utilizar para encontrar la moda , la mediana , los intervalos de confianza y la distribución acumulativa de una distribución estadística, y todos los mínimos locales y todas las soluciones de funciones deterministas.
Se pueden formular varios métodos de integración numérica para aproximar la integral de una función en algún intervalo, por ejemplo [0,1], como el promedio de la función evaluada en un conjunto en ese intervalo:
Si los puntos se eligen como , se trata de la regla del rectángulo . Si los puntos se eligen para que estén distribuidos aleatoriamente (o pseudoaleatoriamente ), se trata del método de Monte Carlo . Si los puntos se eligen como elementos de una secuencia de baja discrepancia, se trata del método cuasi-Monte Carlo . Un resultado notable, la desigualdad de Koksma–Hlawka (enunciada a continuación), muestra que el error de dicho método puede estar limitado por el producto de dos términos, uno de los cuales depende solo de , y el otro es la discrepancia del conjunto .
Es conveniente construir el conjunto de tal manera que si se construye un conjunto con elementos, no sea necesario volver a calcular los elementos anteriores. La regla del rectángulo utiliza conjuntos de puntos que tienen una discrepancia baja, pero en general los elementos deben volver a calcularse si aumenta. Los elementos no necesitan volver a calcularse en el método aleatorio de Monte Carlo si aumenta, pero los conjuntos de puntos no tienen una discrepancia mínima. Al utilizar secuencias de baja discrepancia, buscamos una discrepancia baja y no necesitamos volver a calcularlos, pero en realidad las secuencias de baja discrepancia solo pueden ser incrementalmente buenas en cuanto a discrepancia si no permitimos volver a calcularlas.
La discrepancia de un conjunto se define, utilizando la notación de Niederreiter , como
donde es la medida de Lebesgue -dimensional , es el número de puntos en que caen en , y es el conjunto de intervalos o cajas -dimensionales de la forma
dónde .
La discrepancia en estrella se define de manera similar, excepto que el supremo se toma sobre el conjunto de cajas rectangulares de la forma
donde está en el intervalo semiabierto [0, 1).
Los dos están relacionados por
Nota : Con estas definiciones, la discrepancia representa la desviación máxima o peor de la densidad de puntos de un conjunto uniforme. Sin embargo, también son significativas otras medidas de error, lo que lleva a otras definiciones y medidas de variación. Por ejemplo, la discrepancia o la discrepancia centrada modificada también se utilizan intensivamente para comparar la calidad de los conjuntos de puntos uniformes. Ambas son mucho más fáciles de calcular para valores grandes y .
Sea el cubo unitario de dimensión , . Sea que tenga variación acotada en en el sentido de Hardy y Krause. Entonces, para cualquier en ,
La desigualdad de Koksma - Hlawka es aguda en el siguiente sentido: para cualquier punto establecido en y cualquier , existe una función con variación acotada y tal que
Por lo tanto, la calidad de una regla de integración numérica depende únicamente de la discrepancia .
Sea . Porque escribimos
y denotamos por el punto obtenido de x reemplazando las coordenadas que no están en u por . Entonces
¿Dónde está la función de discrepancia?
Aplicando la desigualdad de Cauchy-Schwarz para integrales y sumas a la identidad de Hlawka-Zaremba, obtenemos una versión de la desigualdad de Koksma-Hlawka:
dónde
y
La discrepancia tiene una gran importancia práctica porque es posible realizar cálculos explícitos rápidos para un conjunto de puntos determinado. De esta manera, es fácil crear optimizadores de conjuntos de puntos utilizando la discrepancia como criterio.
Resulta difícil desde el punto de vista computacional encontrar el valor exacto de la discrepancia de conjuntos de puntos grandes. La desigualdad de Erdős – Turán – Koksma proporciona un límite superior.
Sea puntos en y un entero positivo arbitrario. Entonces
dónde
Conjetura 1. Existe una constante que depende únicamente de la dimensión , tal que
para cualquier conjunto de puntos finitos .
Conjetura 2. Existe una constante que depende únicamente de : , tal que:
para un número infinito de para cualquier secuencia infinita .
Estas conjeturas son equivalentes. Han sido demostradas por WM Schmidt . En dimensiones superiores, el problema correspondiente sigue abierto. Las cotas inferiores más conocidas se deben a Michael Lacey y colaboradores.
Dejar . Entonces
para cualquier conjunto de puntos finitos .
Sea . WM Schmidt demostró que para cualquier conjunto de puntos finito ,
dónde
Para dimensiones arbitrarias , KF Roth demostró que
para cualquier conjunto de puntos finitos . Jozef Beck [1] estableció una mejora de doble logaritmo de este resultado en tres dimensiones. Esto fue mejorado por D. Bilyk y MT Lacey a una potencia de un solo logaritmo. El límite más conocido para s > 2 se debe a D. Bilyk y MT Lacey y A. Vagharshakyan. [2] Porque hay un tal que
para cualquier conjunto de puntos finitos .
Dado que cualquier distribución de números aleatorios se puede asignar a una distribución uniforme, y los números cuasialeatorios se asignan de la misma manera, este artículo solo se ocupa de la generación de números cuasialeatorios en una distribución uniforme multidimensional.
Existen construcciones de secuencias conocidas tales que
donde es una cierta constante, dependiendo de la secuencia. Después de la Conjetura 2, se cree que estas secuencias tienen el mejor orden posible de convergencia. Los ejemplos a continuación son la secuencia de van der Corput , las secuencias de Halton y las secuencias de Sobol' . Una limitación general es que los métodos de construcción generalmente solo pueden garantizar el orden de convergencia. En la práctica, solo se puede lograr una discrepancia baja si es lo suficientemente grande, y para s grandes dados este mínimo puede ser muy grande. Esto significa que ejecutar un análisis de Monte-Carlo con, por ejemplo, variables y puntos de un generador de secuencia de baja discrepancia puede ofrecer solo una mejora de precisión muy menor [ cita requerida ] .
Se pueden generar secuencias de números cuasialeatorios a partir de números aleatorios imponiendo una correlación negativa a esos números aleatorios. Una forma de hacerlo es comenzar con un conjunto de números aleatorios en y construir números cuasialeatorios que sean uniformes en usando:
para pares e impares .
Una segunda forma de hacerlo con los números aleatorios iniciales es construir un recorrido aleatorio con un desplazamiento de 0,5 como en:
Es decir, tomar el número cuasialeatorio anterior, sumar 0,5 y el número aleatorio, y tomar el resultado módulo 1.
Para más de una dimensión, se pueden utilizar cuadrados latinos de la dimensión adecuada para proporcionar compensaciones que garanticen que todo el dominio esté cubierto de manera uniforme.
Para cualquier irracional , la secuencia
tiene una discrepancia que tiende a . Nótese que la secuencia se puede definir recursivamente por
Un buen valor de proporciona una discrepancia menor que una secuencia de números aleatorios uniformes independientes.
La discrepancia puede limitarse mediante el exponente de aproximación de . Si el exponente de aproximación es , entonces para cualquier , se cumple el siguiente límite: [3]
Por el teorema de Thue-Siegel-Roth , el exponente de aproximación de cualquier número algebraico irracional es 2, lo que da un límite de arriba.
La relación de recurrencia anterior es similar a la relación de recurrencia utilizada por un generador congruencial lineal , un generador de números pseudoaleatorios de mala calidad: [4]
Para la recurrencia aditiva de baja discrepancia anterior, a y m se eligen como 1. Sin embargo, tenga en cuenta que esto no generará números aleatorios independientes, por lo que no debe usarse para fines que requieran independencia.
El valor con menor discrepancia es la parte fraccionaria de la proporción áurea : [5]
Otro valor que es casi tan bueno es la parte fraccionaria del coeficiente de plata , que es la parte fraccionaria de la raíz cuadrada de 2:
En más de una dimensión, se necesitan números cuasialeatorios separados para cada dimensión. Un conjunto conveniente de valores que se utilizan son las raíces cuadradas de los números primos a partir del dos, todos tomados en módulo 1:
Sin embargo, se ha demostrado que un conjunto de valores basados en la proporción áurea generalizada produce puntos distribuidos de manera más uniforme. [6]
La lista de generadores de números pseudoaleatorios enumera métodos para generar números pseudoaleatorios independientes. Nota : En pocas dimensiones, la recurrencia recursiva genera conjuntos uniformes de buena calidad, pero para dimensiones más grandes (como ), otros generadores de conjuntos de puntos pueden ofrecer discrepancias mucho menores.
Dejar
sea la representación -aria del entero positivo , es decir . Conjunto
Entonces hay una constante que depende sólo de tal que satisface
¿Dónde está la discrepancia estelar ?
La secuencia de Halton es una generalización natural de la secuencia de van der Corput a dimensiones superiores. Sea s una dimensión arbitraria y b 1 , ..., b s números enteros coprimos arbitrarios mayores que 1. Definir
Entonces existe una constante C que depende únicamente de b 1 , ..., b s , tal que la secuencia { x ( n )} n ≥1 es una secuencia s -dimensional con
Sean números enteros positivos coprimos mayores que 1. Para y dados , el conjunto Hammersley -dimensional de tamaño se define por [7]
Para . Entonces
donde es una constante que depende únicamente de .
Nota : Las fórmulas muestran que el conjunto de Hammersley es en realidad la secuencia de Halton, pero obtenemos una dimensión más gratis al agregar un barrido lineal. Esto solo es posible si se conoce de antemano. Un conjunto lineal también es el conjunto con la discrepancia unidimensional más baja posible en general. Desafortunadamente, para dimensiones más altas, no se conocen tales "conjuntos de registros de discrepancia". Para , la mayoría de los generadores de conjuntos de puntos de baja discrepancia brindan discrepancias al menos casi óptimas.
La variante Antonov-Saleev de la secuencia de Sobol genera números entre cero y uno directamente como fracciones binarias de longitud a partir de un conjunto de fracciones binarias especiales, llamadas números de dirección. Los bits del código Gray de , , se utilizan para seleccionar números de dirección. Para obtener el valor de la secuencia de Sobol, tome el o exclusivo del valor binario del código Gray de con el número de dirección apropiado. El número de dimensiones requeridas afecta la elección de .
El muestreo con discos de Poisson es popular en los videojuegos para colocar objetos rápidamente de una manera que parezca aleatoria pero que garantice que cada dos puntos estén separados por al menos la distancia mínima especificada. [8] Esto no garantiza una discrepancia baja (como por ejemplo en Sobol'), pero al menos una discrepancia significativamente menor que el muestreo aleatorio puro. El objetivo de estos patrones de muestreo se basa en el análisis de frecuencias en lugar de en la discrepancia, un tipo de los llamados patrones de "ruido azul".
Los puntos que se muestran a continuación son los primeros 100, 1000 y 10000 elementos de una secuencia del tipo Sobol. A modo de comparación, también se muestran 10000 elementos de una secuencia de puntos pseudoaleatorios. La secuencia de baja discrepancia se generó mediante el algoritmo TOMS 659. [9] Una implementación del algoritmo en Fortran está disponible en Netlib .
Una propiedad de la proporción áurea es que se puede utilizar para subdividir cualquier rango de manera aproximadamente uniforme... si no se sabe de antemano cuántos pasos se van a dar.