stringtranslate.com

Secuencia de baja discrepancia

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.

Aplicaciones

Error en la curtosis estimada en función del número de puntos de datos. El método "cuasiraleatorio aditivo" proporciona el error máximo cuando c  = ( 5  − 1)/2. El método "aleatorio" proporciona el error promedio en seis ejecuciones de números aleatorios, donde se toma el promedio para reducir la magnitud de las fluctuaciones extremas.

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.

Secuencias de baja discrepancia en la integración numérica

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.

Definición de discrepancia

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 .

La desigualdad Koksma-Hlawka

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 .

La fórmula de Hlawka-Zaremba

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?

ElL 2versión de la desigualdad de Koksma-Hlawka

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.

La desigualdad Erdős-Turán-Koksma

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ősTuránKoksma proporciona un límite superior.

Sea puntos en y un entero positivo arbitrario. Entonces

dónde

Las principales conjeturas

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.

Límites inferiores

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 .

Construcción de secuencias de baja discrepancia

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 ] .

Números aleatorios

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.

Cobertura del cuadrado unitario. A la izquierda, números cuasialeatorios aditivos con c  = 0,5545497..., 0,308517... A la derecha, números aleatorios. De arriba a abajo. 10, 100, 1000, 10000 puntos.

Recurrencia aditiva

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.

secuencia de van der Corput

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 ?

Secuencia de Halton

Primeros 256 puntos de la secuencia de Halton (2,3)

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

Conjunto Hammersley

Juego Hammersley 2D de tamaño 256

Sean números enteros positivos coprimos mayores que 1. Para y dados , el conjunto Hammersley de tamaño -dimensional 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.

Secuencia de Sobol

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 .

Muestreo de disco de Poisson

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".

Ejemplos gráficos

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 .


Véase también

Notas

  1. ^ Beck, József (1989). "Un teorema bidimensional de van Aardenne-Ehrenfest en irregularidades de distribución". Composición Matemática . 72 (3): 269–339. SEÑOR  1032337. S2CID  125940424. Zbl  0691.10041.
  2. ^ Bilyk, Dmitriy; Lacey, Michael T.; Vagharshakyan, Armen (2008). "Sobre la desigualdad de la bola pequeña en todas las dimensiones". Journal of Functional Analysis . 254 (9): 2470–2502. arXiv : 0705.4619 . doi : 10.1016/j.jfa.2007.09.010 . S2CID  14234006.
  3. ^ Kuipers y Niederreiter 2005, pág. 123
  4. ^ Knuth, Donald E. "Capítulo 3 – Números aleatorios". El arte de la programación informática . Vol. 2.
  5. ^ Skarupke, Malte (16 de junio de 2018). "Fibonacci Hashing: The Optimization that the World Forgot". 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.
  6. ^ Roberts, Martin (2018). "La eficacia irrazonable de las secuencias cuasialeatorias".
  7. ^ Hammersley, JM; Handscomb, DC (1964). Métodos de Monte Carlo . doi :10.1007/978-94-009-5819-7. ISBN. 978-94-009-5821-0.
  8. ^ Herman Tulleken. Tulleken, Herman (marzo de 2008). "Muestreo de disco de Poisson". Dev.Mag . Núm. 21, págs. 21-25.
  9. ^ Bratley, Paul; Fox, Bennett L. (1988). "Algoritmo 659". ACM Transactions on Mathematical Software . 14 : 88–100. doi : 10.1145/42288.214372 . S2CID  17325779.

Referencias

Enlaces externos