Oui Hay muchos maneras de producir una secuencia de números más uniformes que los uniformes al azar. De hecho, hay toda una campo dedicado a esta cuestión; es la columna vertebral de cuasi-Monte Carlo (QMC). A continuación, un breve recorrido por lo más básico.
Medición de la uniformidad
Hay muchas maneras de hacerlo, pero la más común tiene un fuerte sabor intuitivo y geométrico. Supongamos que se trata de generar $n$ puntos $x_1,x_2,\ldots,x_n$ en $[0,1]^d$ para algún número entero positivo $d$ . Definir $$\newcommand{\I}{\mathbf 1} D_n := \sup_{R \in \mathcal R}\,\left|\frac{1}{n}\sum_{i=1}^n \I_{(x_i \in R)} - \mathrm{vol}(R)\right| \>, $$ donde $R$ es un rectángulo $[a_1, b_1] \times \cdots \times [a_d, b_d]$ en $[0,1]^d$ tal que $0 \leq a_i \leq b_i \leq 1$ y $\mathcal R$ es el conjunto de todos esos rectángulos. El primer término dentro del módulo es la proporción "observada" de puntos dentro de $R$ y el segundo término es el volumen de $R$ , $\mathrm{vol}(R) = \prod_i (b_i - a_i)$ .
La cantidad $D_n$ es a menudo llamado el discrepancia o discrepancia extrema del conjunto de puntos $(x_i)$ . Intuitivamente, encontramos el "peor" rectángulo $R$ donde la proporción de puntos se desvía más de lo que cabría esperar en caso de uniformidad perfecta.
En la práctica, esto es poco manejable y difícil de calcular. La mayoría de la gente prefiere trabajar con el discrepancia estelar , $$ D_n^\star = \sup_{R \in \mathcal A} \,\left|\frac{1}{n}\sum_{i=1}^n \I_{(x_i \in R)} - \mathrm{vol}(R)\right| \>. $$ La única diferencia es el conjunto $\mathcal A$ sobre el que se toma el supremum. Es el conjunto de anclado rectángulos (en el origen), es decir, donde $a_1 = a_2 = \cdots = a_d = 0$ .
Lema : $D_n^\star \leq D_n \leq 2^d D_n^\star$ para todos $n$ , $d$ .
Prueba . El límite de la izquierda es obvio ya que $\mathcal A \subset \mathcal R$ . El límite de la derecha se deduce porque cada $R \in \mathcal R$ puede componerse mediante uniones, intersecciones y complementos de no más de $2^d$ rectángulos anclados (es decir, en $\mathcal A$ ).
Así, vemos que $D_n$ y $D_n^\star$ son equivalentes en el sentido de que si uno es pequeño como $n$ crece, el otro también lo hará. Aquí hay una imagen (de dibujos animados) que muestra los rectángulos candidatos para cada discrepancia.
![extremal and star discrepancy]()
Ejemplos de secuencias "buenas"
Secuencias con una discrepancia estelar verificablemente baja $D_n^\star$ se llaman a menudo, como es lógico, secuencias de baja discrepancia .
van der Corput . Este es quizás el ejemplo más sencillo. En $d=1$ las secuencias de van der Corput se forman expandiendo el número entero $i$ en binario y luego "reflejando los dígitos" alrededor del punto decimal. Más formalmente, esto se hace con el inverso radical función en la base $b$ , $$\newcommand{\rinv}{\phi} \rinv_b(i) = \sum_{k=0}^\infty a_k b^{-k-1} \>, $$ donde $i = \sum_{k=0}^\infty a_k b^k$ y $a_k$ son los dígitos de la base $b$ ampliación de $i$ . Esta función es la base de muchas otras secuencias. Por ejemplo, $41$ en binario es $101001$ y así $a_0 = 1$ , $a_1 = 0$ , $a_2 = 0$ , $a_3 = 1$ , $a_4 = 0$ y $a_5 = 1$ . Por lo tanto, el punto 41 de la secuencia de van der Corput es $x_{41} = \rinv_2(41) = 0.100101\,\text{(base 2)} = 37/64$ .
Tenga en cuenta que debido a que el bit menos significativo de $i$ oscila entre $0$ y $1$ los puntos $x_i$ para impar $i$ están en $[1/2,1)$ mientras que los puntos $x_i$ para incluso $i$ están en $(0,1/2)$ .
Secuencias de Halton . Entre las más populares de las secuencias clásicas de baja discrepancia, éstas son extensiones de la secuencia de van der Corput a múltiples dimensiones. Sea $p_j$ sea el $j$ el primo más pequeño. Entonces, el $i$ punto $x_i$ de la $d$ -La secuencia de Halton es $$ x_i = (\rinv_{p_1}(i), \rinv_{p_2}(i),\ldots,\rinv_{p_d}(i)) \>. $$ Para los bajos $d$ funcionan bastante bien, pero tienen problemas en dimensiones superiores .
Las secuencias de Halton satisfacen $D_n^\star = O(n^{-1} (\log n)^d)$ . También son agradables porque son extensible en que la construcción de los puntos no depende de un a priori elección de la longitud de la secuencia $n$ .
Secuencias de Hammersley . Se trata de una modificación muy sencilla de la secuencia Halton. En su lugar utilizamos $$ x_i = (i/n, \rinv_{p_1}(i), \rinv_{p_2}(i),\ldots,\rinv_{p_{d-1}}(i)) \>. $$ Tal vez sorprendentemente, la ventaja es que tienen una mejor discrepancia estelar $D_n^\star = O(n^{-1}(\log n)^{d-1})$ .
He aquí un ejemplo de las secuencias de Halton y Hammersley en dos dimensiones.
![Halton and Hammersley]()
Secuencias Halton de Faure . Un conjunto especial de permutaciones (fijado en función de $i$ ) puede aplicarse a la expansión de dígitos $a_k$ para cada $i$ al producir la secuencia de Halton. Esto ayuda a remediar (hasta cierto punto) los problemas aludidos en dimensiones superiores. Cada una de las permutaciones tiene la interesante propiedad de mantener $0$ y $b-1$ como puntos fijos.
Reglas del entramado . Sea $\beta_1, \ldots, \beta_{d-1}$ sean números enteros. Tomemos $$ x_i = (i/n, \{i \beta_1 / n\}, \ldots, \{i \beta_{d-1}/n\}) \>, $$ donde $\{y\}$ denota la parte fraccionaria de $y$ . Elección juiciosa del $\beta$ produce buenas propiedades de uniformidad. Una mala elección puede dar lugar a malas secuencias. Además, no son extensibles. He aquí dos ejemplos.
![Good and bad lattices]()
$(t,m,s)$ redes . $(t,m,s)$ redes en la base $b$ son conjuntos de puntos tales que todo rectángulo de volumen $b^{t-m}$ en $[0,1]^s$ contiene $b^t$ puntos. Esta es una forma fuerte de uniformidad. Pequeño $t$ es tu amigo, en este caso. Las secuencias Halton, Sobol' y Faure son ejemplos de $(t,m,s)$ redes. Éstas se prestan muy bien a la aleatorización a través de la codificación. La aleatorización (bien hecha) de una $(t,m,s)$ neto produce otro $(t,m,s)$ red. El MinT guarda una colección de estas secuencias.
Aleatorización simple: Rotaciones Cranley-Patterson . Sea $x_i \in [0,1]^d$ sea una secuencia de puntos. Sea $U \sim \mathcal U(0,1)$ . Entonces los puntos $\hat x_i = \{x_i + U\}$ se distribuyen uniformemente en $[0,1]^d$ .
A continuación se muestra un ejemplo en el que los puntos azules son los puntos originales y los rojos son los rotados con líneas que los conectan (y que se muestran envueltos, en su caso).
![Cranley Patterson]()
Secuencias completamente distribuidas de manera uniforme . Esta es una noción de uniformidad aún más fuerte que a veces entra en juego. Dejemos que $(u_i)$ sea la secuencia de puntos en $[0,1]$ y ahora forman bloques superpuestos de tamaño $d$ para obtener la secuencia $(x_i)$ . Por lo tanto, si $s = 3$ tomamos $x_1 = (u_1,u_2,u_3)$ entonces $x_2 = (u_2,u_3,u_4)$ etc. Si, por cada $s \geq 1$ , $D_n^\star(x_1,\ldots,x_n) \to 0$ entonces $(u_i)$ se dice que completamente distribuido de manera uniforme . En otras palabras, la secuencia produce un conjunto de puntos de cualquier dimensión que tiene la deseable $D_n^\star$ propiedades.
Como ejemplo, la secuencia de van der Corput no está completamente distribuida de manera uniforme ya que para $s = 2$ los puntos $x_{2i}$ están en la plaza $(0,1/2) \times [1/2,1)$ y los puntos $x_{2i-1}$ están en $[1/2,1) \times (0,1/2)$ . Por lo tanto, no hay puntos en el cuadrado $(0,1/2) \times (0,1/2)$ lo que implica que para $s=2$ , $D_n^\star \geq 1/4$ para todos $n$ .
Referencias estándar
El Niederreiter (1992) monografía y la Fang y Wang (1994) texto son lugares a los que acudir para seguir explorando.
