secuencia de Halton

256 puntos de los primeros 256 puntos de la secuencia de Halton 2,3 (arriba) comparados con una fuente de números pseudoaleatorios (abajo). La secuencia de Halton cubre el espacio de manera más uniforme. (rojo = 1, ..., 10; azul = 11, ..., 100; verde = 101, ..., 256)

En estadística , las secuencias de Halton se utilizan para generar puntos en el espacio para métodos numéricos como las simulaciones de Monte Carlo . Aunque estas secuencias son deterministas , presentan una baja discrepancia , es decir, parecen aleatorias para muchos propósitos. Se introdujeron por primera vez en 1960 y son un ejemplo de secuencia de números cuasialeatorios . Generalizan las secuencias unidimensionales de van der Corput .

La sucesión de Halton se construye según un método determinista que utiliza números coprimos como bases. Como ejemplo sencillo, tomemos una dimensión de la sucesión de Halton bidimensional basada en 2 y la otra dimensión en 3. Para generar la sucesión para 2, comenzamos dividiendo el intervalo (0,1) por la mitad, luego en cuartos, octavos, etc., lo que genera

1/2 ,​​

1/4 , 3/4 ,​​​​

1/8 , 5/8 , 3/8 , 7/8 ,​​​​​​​​

1/16 , 9/16 , ...​​​

De forma equivalente, el enésimo número de esta secuencia es el número n escrito en representación binaria, invertido y escrito después del punto decimal. Esto es cierto para cualquier base. Como ejemplo, para encontrar el sexto elemento de la secuencia anterior, escribiríamos 6 = 1*2 ² + 1*2 ¹ + 0*2 ⁰ = 110 ₂ , que se puede invertir y colocar después del punto decimal para dar 0.011 ₂ = 0*2 ^-1 + 1*2 ^-2 + 1*2 ^-3 = 3 ⁄ 8 . Por lo tanto, la secuencia anterior es la misma que

0,1 ₂ , 0,01 ₂ , 0,11 ₂ , 0,001 ₂ , 0,101 ₂ , 0,011 ₂ , 0,111 ₂ , 0,0001 ₂ , 0,1001 ₂ ,...

Para generar la secuencia para 3 para la otra dimensión, dividimos el intervalo (0,1) en tercios, luego en novenos, veintisietevos, etc., lo que genera

1/3 , 2/3 , 1/9 , 4/9 , 7/9 , 2/9 , 5/9 , 8/9 , 1/27 , ...​​​​​​​​​​​​​​​​​

Cuando los emparejamos, obtenemos una secuencia de puntos en un cuadrado unitario :

( 1 ⁄ 2 , 1 ⁄ 3 ), ( 1 ⁄ 4 , 2 ⁄ 3 ), ( 3 ⁄ 4 , 1 ⁄ 9 ), ( 1 ⁄ 8 , 4 ⁄ 9 ), ( 5 ⁄ 8 , 7 ⁄ 9 ), ( 3 ⁄ 8 , 2 ⁄ 9 ), ( 7 ⁄ 8 , 5 ⁄ 9 ), ( 1 ⁄ 16 , 8 ⁄ 9 ), ( 9 ⁄ 16 , 1 ⁄ 27 ).

Aunque las secuencias de Halton estándar funcionan muy bien en dimensiones bajas, se han observado problemas de correlación entre secuencias generadas a partir de primos mayores. Por ejemplo, si partimos de los primos 17 y 19, los primeros 16 pares de puntos: ( 1/17, 1/19 ) , ( 2/17 , 2/19 ) , ( 3/17 , 3/19 ) ... ( 16/17 , 16/19 ) tendrían una correlación lineal perfecta . Para evitar esto , es común descartar las primeras 20 entradas, o alguna otra cantidad predeterminada dependiendo de los primos elegidos. También se han propuesto otros métodos. Una de las soluciones más destacadas es la secuencia de Halton aleatorizada, que utiliza permutaciones de los coeficientes empleados en la construcción de la secuencia estándar. Otra solución es el algoritmo de Halton salteado , que omite puntos en la secuencia estándar. Utilizando, por ejemplo, solo cada punto 409 (también son posibles otros números primos no utilizados en la secuencia central de Halton), se pueden lograr mejoras significativas. ^{[ 1 ]}

En pseudocódigo :

El algoritmo de secuencia de Halton tiene como entradas : índice${\displaystyle i}$ base${\displaystyle b}$Salida : resultado${\displaystyle r}$${\displaystyle f\leftarrow 1}$${\displaystyle r\leftarrow 0}$mientras${\displaystyle i>0}$hacer${\displaystyle f\leftarrow f/b}$${\displaystyle r\leftarrow r+f*(i\operatorname {mod} b)}$${\displaystyle i\leftarrow \lfloor i/b\rfloor }$devolver${\displaystyle r}$

Una implementación alternativa que produce números subsiguientes de una secuencia de Halton para la base b se presenta en la siguiente función generadora (en Python ). ^{[ 2 ]} Este algoritmo utiliza internamente solo números enteros , lo que lo hace robusto frente a errores de redondeo.

def halton_sequence ( b ): """Función generadora para la secuencia de Halton.""" n , d = 0 , 1 while True : x = d - n if x == 1 : n = 1 d *= b else : y = d // b while x <= y : y //= b n = ( b + 1 ) * y - x yield n / d

• Construcciones de secuencias de baja discrepancia

• Kuipers, L.; Niederreiter, H. (2005), Distribución uniforme de secuencias , Publicaciones de Dover , p.  129, ISBN 0-486-45019-8
• Niederreiter, Harald (1992), Generación de números aleatorios y métodos cuasi-Monte Carlo , SIAM , p.  29, ISBN 0-89871-295-5.
• Halton, J. (1964), "Algoritmo 247: Secuencia de puntos cuasialeatorios con inverso radical", Communications of the ACM , 7 (12): 701-701, doi : 10.1145/355588.365104 , S2CID 47096908 .
• Kocis, Ladislav; Whiten, William (1997), "Investigaciones computacionales de secuencias de baja discrepancia", ACM Transactions on Mathematical Software , 23 (2): 266–296 , doi : 10.1145/264029.264064 , S2CID 183263 .