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${\displaystyle N}$, su subsecuencia${\displaystyle x_{1},\ldots ,x_{N}}$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 ocurriría en promedio (pero no para muestras particulares) en el caso de una secuencia equidistribuida . Las definiciones específicas de discrepancia difieren en cuanto a la elección de B ( hiperesferas , hipercubos , etc.) y cómo se calcula (normalmente normaliza) y combina la discrepancia para cada B (normalmente tomando el peor valor).

Las secuencias de baja discrepancia también se denominan secuencias cuasialeatorias , debido a su uso común como sustituto de los números aleatorios distribuidos uniformemente . El modificador "cuasi" se utiliza para indicar con mayor claridad que los valores de una secuencia de baja discrepancia no son ni 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 representa una ventaja importante.

Los números cuasialeatorios tienen una ventaja sobre los números puramente aleatorios, ya que cubren el dominio de interés de forma rápida y uniforme.

Dos aplicaciones útiles son la determinación de la función característica de una función de densidad de probabilidad y la obtención de la derivada de una función determinista con un bajo nivel de ruido. Los números cuasialeatorios permiten calcular momentos de orden superior con gran precisión y rapidez.

Las aplicaciones que no implican ordenación serían el cálculo de la media , la desviación estándar , la asimetría y la curtosis de una distribución estadística, así como la determinación de los máximos y mínimos integrales y globales de funciones deterministas complejas. Los números cuasialeatorios también pueden utilizarse como puntos de partida para algoritmos deterministas que solo funcionan localmente, como la iteración de Newton-Raphson .

Los números cuasialeatorios también pueden combinarse con algoritmos de búsqueda. Mediante un algoritmo de búsqueda , los números cuasialeatorios pueden utilizarse para hallar la moda , la mediana , los intervalos de confianza y la distribución acumulativa de una distribución estadística, así como todos los mínimos locales y todas las soluciones de funciones deterministas.

La discrepancia de un conjunto${\displaystyle P=\{x_{1},\dots ,x_{N}}\}$se define, utilizando la notación de Niederreiter , como $${\displaystyle D_{N}(P)=\sup _{B\in J}\left|{\frac {A(B;P)}{N}}-\lambda _{s}(B)\right|}$$

dónde${\displaystyle \lambda _{s}}$es el${\displaystyle s}$medida de Lebesgue -dimensional , ${\displaystyle A(B;P)}$es el número de puntos en${\displaystyle P}$que caen en${\displaystyle B}$, y${\displaystyle J}$es el conjunto de${\displaystyle s}$-intervalos dimensionales o cajas de la forma

$${\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 estelar${\displaystyle D_{N}^{*}(P)}$se define de manera similar, excepto que el supremo se toma sobre el conjunto${\displaystyle J^{*}}$de cajas rectangulares de la forma

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

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

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 del peor caso de la densidad de puntos de un conjunto uniforme. Sin embargo, también otras medidas de error son significativas, lo que lleva a otras definiciones y medidas de variación. Por ejemplo,${\displaystyle L^{2}}$-discrepancia o centrado modificado${\displaystyle L^{2}}$-Las discrepancias también se utilizan intensivamente para comparar la calidad de conjuntos de puntos uniformes. Ambos son mucho más fáciles de calcular para grandes${\displaystyle N}$y${\displaystyle s}$.

Dejar${\displaystyle {\overline {I}}^{s}}$ser el${\displaystyle s}$cubo unitario dimensional ,${\displaystyle {\overline {I}}^{s}=[0,1]\times \cdots \times [0,1]}$. Dejar${\displaystyle f}$tienen variación limitada${\displaystyle V(f)}$en${\displaystyle {\overline {I}}^{s}}$en el sentido de Hardy y Krause. Entonces, para cualquier${\displaystyle x_{1},\ldots ,x_{N}}$en${\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 precisa en el siguiente sentido: Para cualquier conjunto de puntos${\displaystyle \{x_{1},\ldots ,x_{N}\}}$en${\displaystyle I^{s}}$y cualquier${\displaystyle \varepsilon >0}$, hay una función${\displaystyle f}$con variación limitada y${\displaystyle V(f)=1}$de tal manera que

$${\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})}$.

Dejar${\displaystyle D=\{1,2,\ldots ,d\}}$. Para${\displaystyle \emptyset \neq u\subseteq D}$escribimos $${\displaystyle dx_{u}:=\prod _{j\in u}dx_{j}}$$ y denotar por${\displaystyle (x_{u},1)}$el punto obtenido de x reemplazando las coordenadas que no están en u por${\displaystyle 1}$. Entonces

$${\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${\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}}$es la función de discrepancia.

Aplicando la desigualdad de Cauchy-Schwarz para integrales y sumas a la identidad de Hlawka-Zaremba, obtenemos una${\displaystyle L^{2}}$Versión de la desigualdad de Koksma-Hlawka:

$${\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 permite realizar cálculos explícitos rápidos para un conjunto de puntos dado. De esta manera, es fácil crear optimizadores de conjuntos de puntos utilizando${\displaystyle L^{2}}$discrepancia como criterio.

Resulta computacionalmente difícil hallar el valor exacto de la discrepancia de conjuntos de puntos grandes. La desigualdad de Erdős - Turán - Koksma proporciona una cota superior.

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

$${\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 {\text{for}}\quad h=(h_{1},\ldots ,h_{s})\in \mathbb {Z} ^{s}.}$$

Conjetura 1. Existe una constante${\displaystyle c_{s}}$dependiendo únicamente de la dimensión${\displaystyle s}$, de tal manera que $${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c_{s}{\frac {(\ln N)^{s-1}}{N}}}$$ para cualquier conjunto de puntos finito${\displaystyle {x_{1},\ldots ,x_{N}}}$.

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

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

Estas conjeturas son equivalentes. Han sido probadas para${\displaystyle s\leq 2}$Por WM Schmidt . En dimensiones superiores, el problema correspondiente aún está abierto. Los límites inferiores más conocidos se deben a Michael Lacey y sus colaboradores.

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

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

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

Dejar${\displaystyle s=2}$WM Schmidt demostró que para cualquier conjunto de puntos finito${\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${\displaystyle s>1}$, KF Roth demostró que

$${\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 finito${\displaystyle \{x_{1},\dots ,x_{N}}\}$. 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. La mejor cota conocida para s  >  2 se debe a D. Bilyk y MT Lacey y A. Vagharshakyan. ^{[ 2 ]} Existe una${\displaystyle t>0}$dependiendo de s para que $${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq t{\frac {\log ^{{\frac {s-1}{2}}+t}N}{N}}}$$

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

Se puede calcular un límite inferior general para la discrepancia local promedio utilizando solo el tamaño mínimo de la brecha y los tamaños de brecha por encima de la brecha promedio ^{[ 3 ]} .

Dado que cualquier distribución de números aleatorios puede representarse mediante una distribución uniforme, y los números cuasialeatorios se representan de la misma manera, este artículo solo trata sobre 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}}.}$$ dónde${\displaystyle C}$es una constante determinada, que depende de la secuencia. Después de la Conjetura 2, se cree que estas secuencias tienen el mejor orden de convergencia posible. 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, una baja discrepancia solo se puede lograr si${\displaystyle N}$es suficientemente grande, y para grandes dado este mínimo${\displaystyle N}$puede ser muy grande. Esto significa realizar un análisis de Monte Carlo con, por ejemplo,${\displaystyle s=20}$variables y${\displaystyle N=1000}$Los puntos obtenidos con un generador de secuencias de baja discrepancia pueden ofrecer solo una mejora mínima en la precisión .

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.${\displaystyle r_{i}}$en${\displaystyle [0,0.5)}$y construir números cuasialeatorios${\displaystyle s_{i}}$que son uniformes en${\displaystyle [0,1)}$usando:

${\displaystyle s_{i}=r_{i}}$para${\displaystyle i}$extraño y${\displaystyle s_{i}=0.5+r_{i}}$para${\displaystyle i}$incluso.

Una segunda forma de hacerlo con los números aleatorios iniciales es construir un paseo 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, sumarle 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 desplazamientos que garanticen que todo el dominio esté cubierto de manera uniforme.

secuencia de Halton

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 enteros coprimos arbitrarios mayores que 1. Definimos

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

Entonces hay una constante C que depende solo 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

Dejar${\displaystyle b_{1},\ldots ,b_{s-1}}$sean coprimos enteros positivos mayores que 1. Para un dado${\displaystyle s}$y${\displaystyle N}$, el${\displaystyle s}$-conjunto dimensional Hammersley de tamaño${\displaystyle N}$se define por ^{[ 8 ]}

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

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

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

dónde${\displaystyle C}$es una constante que depende únicamente de${\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 ${\displaystyle N}$Se conoce de antemano. Un conjunto lineal es también el conjunto con la menor discrepancia unidimensional posible en general. Desafortunadamente, para dimensiones superiores, no se conocen tales "conjuntos de registros de discrepancia". Para${\displaystyle s=2}$La mayoría de los generadores de conjuntos de puntos de baja discrepancia ofrecen discrepancias al menos casi óptimas.

Los puntos representados a continuación corresponden a los primeros 100, 1000 y 10000 elementos de una secuencia del tipo Sobol'. Para fines comparativos, también se muestran 10000 elementos de una secuencia de puntos pseudoaleatorios. La secuencia de baja discrepancia fue generada por el algoritmo TOMS 659. ^{[ 10 ]} Una implementación del algoritmo en Fortran está disponible en Netlib .

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

• Algoritmos recopilados de la ACM (véanse los algoritmos 647, 659 y 738).
• Secuencias cuasi aleatorias de la Biblioteca Científica GNU
• Muestreo cuasialeatorio sujeto a restricciones en FinancialMathematics.Com
• Generador en C++ de la secuencia de Sobol
• Referencia de la API QMC de SciPy: scipy.stats.qmc