Secuencia de baja discrepancia

Tipo de secuencia matemática

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 . ${\displaystyle N}$ ${\displaystyle x_{1},\ldots ,x_{N}}$

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: ${\displaystyle f}$ ${\displaystyle \{x_{1},\dots ,x_{N}}\}$

${\displaystyle \int _{0}^{1}f(u)\,du\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).}$

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 . ${\displaystyle x_{i}=i/N}$ ${\displaystyle f}$ ${\displaystyle \{x_{1},\dots ,x_{N}}\}$

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. ${\displaystyle \{x_{1},\dots ,x_{N}}\}$ ${\displaystyle N+1}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$

Definición de discrepancia

La discrepancia de un conjunto se define, utilizando la notación de Niederreiter , como ${\displaystyle P=\{x_{1},\dots ,x_{N}}\}$

${\displaystyle D_{N}(P)=\sup _{B\in J}\left|{\frac {A(B;P)}{N}}-\lambda _{s}(B)\right|}$

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 ${\displaystyle \lambda _{s}}$ ${\displaystyle s}$ ${\displaystyle A(B;P)}$ ${\displaystyle P}$ ${\displaystyle B}$ ${\displaystyle J}$ ${\displaystyle s}$

${\displaystyle \prod _{i=1}^{s}[a_{i},b_{i})=\{\mathbf {x} \in \mathbf {R} ^{s}:a_{i}\leq x_{i}<b_{i}\}\,}$

dónde . ${\displaystyle 0\leq a_{i}<b_{i}\leq 1}$

La discrepancia en estrella se define de manera similar, excepto que el supremo se toma sobre el conjunto de cajas rectangulares de la forma ${\displaystyle D_{N}^{*}(P)}$ ${\displaystyle J^{*}}$

${\displaystyle \prod _{i=1}^{s}[0,u_{i})}$

donde está en el intervalo semiabierto [0, 1). ${\displaystyle u_{i}}$

Los dos están relacionados por

${\displaystyle D_{N}^{*}\leq D_{N}\leq 2^{s}D_{N}^{*}.\,}$

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 . ${\displaystyle L^{2}}$ ${\displaystyle L^{2}}$ ${\displaystyle N}$ ${\displaystyle s}$

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 , ${\displaystyle {\overline {I}}^{s}}$ ${\displaystyle s}$ ${\displaystyle {\overline {I}}^{s}=[0,1]\times \cdots \times [0,1]}$ ${\displaystyle f}$ ${\displaystyle V(f)}$ ${\displaystyle {\overline {I}}^{s}}$ ${\displaystyle x_{1},\ldots ,x_{N}}$ ${\displaystyle I^{s}=[0,1)^{s}=[0,1)\times \cdots \times [0,1)}$

${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|\leq V(f)\,D_{N}^{*}(x_{1},\ldots ,x_{N}).}$

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 ${\displaystyle \{x_{1},\ldots ,x_{N}\}}$ ${\displaystyle I^{s}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle f}$ ${\displaystyle V(f)=1}$

${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|>D_{N}^{*}(x_{1},\ldots ,x_{N})-\varepsilon .}$

Por lo tanto, la calidad de una regla de integración numérica depende únicamente de la discrepancia . ${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})}$

La fórmula de Hlawka-Zaremba

Sea . Porque escribimos ${\displaystyle D=\{1,2,\ldots ,d\}}$ ${\displaystyle \emptyset \neq u\subseteq D}$

${\displaystyle dx_{u}:=\prod _{j\in u}dx_{j}}$

y denotamos por el punto obtenido de x reemplazando las coordenadas que no están en u por . Entonces ${\displaystyle (x_{u},1)}$ ${\displaystyle 1}$

${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du=\sum _{\emptyset \neq u\subseteq D}(-1)^{|u|}\int _{[0,1]^{|u|}}\operatorname {disc} (x_{u},1){\frac {\partial ^{|u|}}{\partial x_{u}}}f(x_{u},1)\,dx_{u},}$

¿Dónde está la función de discrepancia? ${\displaystyle \operatorname {disc} (z)={\frac {1}{N}}\sum _{i=1}^{N}\prod _{j=1}^{d}1_{[0,z_{j})}(x_{i,j})-\prod _{j=1}^{d}z_{i}}$

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: ${\displaystyle L^{2}}$

${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|\leq \|f\|_{d}\operatorname {disc} _{d}(\{t_{i}\}),}$

dónde

${\displaystyle \operatorname {disc} _{d}(\{t_{i}\})=\left(\sum _{\emptyset \neq u\subseteq D}\int _{[0,1]^{|u|}}\operatorname {disc} (x_{u},1)^{2}\,dx_{u}\right)^{1/2}}$

y

${\displaystyle \|f\|_{d}=\left(\sum _{u\subseteq D}\int _{[0,1]^{|u|}}\left|{\frac {\partial ^{|u|}}{\partial x_{u}}}f(x_{u},1)\right|^{2}dx_{u}\right)^{1/2}.}$

${\displaystyle L^{2}}$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. ${\displaystyle L^{2}}$

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ős – Turán – Koksma proporciona un límite superior.

Sea puntos en y un entero positivo arbitrario. Entonces ${\displaystyle x_{1},\ldots ,x_{N}}$ ${\displaystyle I^{s}}$ ${\displaystyle H}$

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\leq \left({\frac {3}{2}}\right)^{s}\left({\frac {2}{H+1}}+\sum _{0<\|h\|_{\infty }\leq H}{\frac {1}{r(h)}}\left|{\frac {1}{N}}\sum _{n=1}^{N}e^{2\pi i\langle h,x_{n}\rangle }\right|\right)}$

dónde

${\displaystyle r(h)=\prod _{i=1}^{s}\max\{1,|h_{i}|\}\quad {\mbox{for}}\quad h=(h_{1},\ldots ,h_{s})\in \mathbb {Z} ^{s}.}$

Las principales conjeturas

Conjetura 1. Existe una constante que depende únicamente de la dimensión , tal que ${\displaystyle c_{s}}$ ${\displaystyle s}$

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c_{s}{\frac {(\ln N)^{s-1}}{N}}}$

para cualquier conjunto de puntos finitos . ${\displaystyle {x_{1},\ldots ,x_{N}}}$

Conjetura 2. Existe una constante que depende únicamente de : , tal que: ${\displaystyle c'_{s}}$ ${\displaystyle s}$ ${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c'_{s}{\frac {(\ln N)^{s}}{N}}}$

para un número infinito de para cualquier secuencia infinita . ${\displaystyle N}$ ${\displaystyle x_{1},x_{2},x_{3},\ldots }$

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. ${\displaystyle s\leq 2}$

Límites inferiores

Dejar . Entonces ${\displaystyle s=1}$

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2N}}}$

para cualquier conjunto de puntos finitos . ${\displaystyle \{x_{1},\dots ,x_{N}}\}$

Sea . WM Schmidt demostró que para cualquier conjunto de puntos finito , ${\displaystyle s=2}$ ${\displaystyle \{x_{1},\dots ,x_{N}}\}$

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq C{\frac {\log N}{N}}}$

dónde

${\displaystyle C=\max _{a\geq 3}{\frac {1}{16}}{\frac {a-2}{a\log a}}=0.023335\dots .}$

Para dimensiones arbitrarias , KF Roth demostró que ${\displaystyle s>1}$

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2^{4s}}}{\frac {1}{((s-1)\log 2)^{\frac {s-1}{2}}}}{\frac {\log ^{\frac {s-1}{2}}N}{N}}}$

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 ${\displaystyle \{x_{1},\dots ,x_{N}}\}$ ${\displaystyle \{x_{1},\dots ,x_{N}}\}$ ${\displaystyle t=0}$

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq t{\frac {\log ^{{\frac {s-1}{2}}+t}N}{N}}}$

para cualquier conjunto de puntos finitos . ${\displaystyle \{x_{1},\dots ,x_{N}}\}$

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

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\leq C{\frac {(\ln N)^{s}}{N}}.}$

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 ]} . ${\displaystyle C}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle s=20}$ ${\displaystyle N=1000}$

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: ${\displaystyle r_{i}}$ ${\displaystyle [0,0.5)}$ ${\displaystyle s_{i}}$ ${\displaystyle [0,1)}$

${\displaystyle s_{i}=r_{i}}$para pares e impares . ${\displaystyle i}$ ${\displaystyle s_{i}=0.5+r_{i}}$ ${\displaystyle i}$

Una segunda forma de hacerlo con los números aleatorios iniciales es construir un recorrido aleatorio con un desplazamiento de 0,5 como en:

${\displaystyle s_{i}=s_{i-1}+0.5+r_{i}{\pmod {1}}.\,}$

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 ${\displaystyle \alpha }$

${\displaystyle s_{n}=\{s_{0}+n\alpha \}}$

tiene una discrepancia que tiende a . Nótese que la secuencia se puede definir recursivamente por ${\displaystyle 1/N}$

${\displaystyle s_{n+1}=(s_{n}+\alpha ){\bmod {1}}\;.}$

Un buen valor de proporciona una discrepancia menor que una secuencia de números aleatorios uniformes independientes. ${\displaystyle \alpha }$

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] ${\displaystyle \alpha }$ ${\displaystyle \mu }$ ${\displaystyle \varepsilon >0}$

${\displaystyle D_{N}((s_{n}))=O_{\varepsilon }(N^{-1/(\mu -1)+\varepsilon }).}$

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. ${\displaystyle N^{-1+\varepsilon }}$

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]

${\displaystyle r_{i}=(ar_{i-1}+c){\bmod {m}}}$

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] ${\displaystyle c}$

${\displaystyle c={\frac {{\sqrt {5}}-1}{2}}=\varphi -1\approx 0.618034.}$

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:

${\displaystyle c={\sqrt {2}}-1\approx 0.414214.\,}$

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:

${\displaystyle c={\sqrt {2}},{\sqrt {3}},{\sqrt {5}},{\sqrt {7}},{\sqrt {11}},\ldots \,}$

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. ${\displaystyle s}$ ${\displaystyle s>8}$

secuencia de van der Corput

Dejar

${\displaystyle n=\sum _{k=0}^{L-1}d_{k}(n)b^{k}}$

sea ​​la representación -aria del entero positivo , es decir . Conjunto ${\displaystyle b}$ ${\displaystyle n\geq 1}$ ${\displaystyle 0\leq d_{k}(n)<b}$

${\displaystyle g_{b}(n)=\sum _{k=0}^{L-1}d_{k}(n)b^{-k-1}.}$

Entonces hay una constante que depende sólo de tal que satisface ${\displaystyle C}$ ${\displaystyle b}$ ${\displaystyle (g_{b}(n))_{n\geq 1}}$

${\displaystyle D_{N}^{*}(g_{b}(1),\dots ,g_{b}(N))\leq C{\frac {\log N}{N}},}$

¿Dónde está la discrepancia estelar ? ${\displaystyle D_{N}^{*}}$

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 ₁ , ..., b _s números enteros coprimos arbitrarios mayores que 1. Definir

${\displaystyle x(n)=(g_{b_{1}}(n),\dots ,g_{b_{s}}(n)).}$

Entonces existe una constante C que depende únicamente de b ₁ , ..., b _s , tal que la secuencia { x ( n )} _{n ≥1} es una secuencia s -dimensional con

${\displaystyle D_{N}^{*}(x(1),\dots ,x(N))\leq C'{\frac {(\log N)^{s}}{N}}.}$

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] ${\displaystyle b_{1},\ldots ,b_{s-1}}$ ${\displaystyle s}$ ${\displaystyle N}$ ${\displaystyle s}$ ${\displaystyle N}$

${\displaystyle x(n)=\left(g_{b_{1}}(n),\dots ,g_{b_{s-1}}(n),{\frac {n}{N}}\right)}$

Para . Entonces ${\displaystyle n=1,\ldots ,N}$

${\displaystyle D_{N}^{*}(x(1),\dots ,x(N))\leq C{\frac {(\log N)^{s-1}}{N}}}$

donde es una constante que depende únicamente de . ${\displaystyle C}$ ${\displaystyle b_{1},\ldots ,b_{s-1}}$

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. ${\displaystyle N}$ ${\displaystyle s=2}$

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 . ${\displaystyle w,}$ ${\displaystyle w}$ ${\displaystyle V_{i},i=1,2,\dots ,w}$ ${\displaystyle i}$ ${\displaystyle G(i)}$ ${\displaystyle s_{i}}$ ${\displaystyle i}$ ${\displaystyle V_{i}}$

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

• Teoría de la discrepancia
• Cadena de Markov Monte Carlo
• Método cuasi-Monte Carlo
• Cuadrícula dispersa
• Muestreo sistemático

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

• Dick, Josef; Pillichshammer, Friedrich (2010). Redes y secuencias digitales: teoría de la discrepancia e integración cuasi-Monte Carlo . Cambridge University Press. ISBN 978-0-521-19159-3.
• Kuipers, L.; Niederreiter, H. (2005), Distribución uniforme de secuencias , Publicaciones de Dover , ISBN 0-486-45019-8
• Harald Niederreiter (1992). Generación de números aleatorios y métodos cuasi-Monte Carlo . Sociedad de Matemáticas Industriales y Aplicadas. ISBN 0-89871-295-5.
• Drmota, Michael; Tichy, Robert F. (1997). Secuencias, discrepancias y aplicaciones . Apuntes de clase de matemáticas. Vol. 1651. Springer. ISBN 3-540-62606-9.
• Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (1992). Recetas numéricas en C (2.ª ed.). Cambridge University Press. Véase la sección 7.7 para una discusión menos técnica de las secuencias de baja discrepancia. ISBN 0-521-43108-5.

Enlaces externos

• Algoritmos recopilados del ACM (ver algoritmos 647, 659 y 738).
• Secuencias cuasialeatorias de la biblioteca científica GNU
• Muestreo cuasialeatorio sujeto a restricciones en FinancialMathematics.Com
• Generador de secuencias de Sobol en C++
• Referencia de API de SciPy QMC: scipy.stats.qmc