Codificación y correlación en secuencias de baja discrepancia (Halton/Sobol)

Question

Actualmente estoy trabajando en un proyecto en el que generar valores aleatorios utilizando discrepancia baja / conjuntos de puntos casi aleatorios como los conjuntos de puntos Halton y Sobol. Estos son esencialmente $d$ -vectores dimensionales que imitan un $d$ -dimensionales uniformes(0,1), pero tienen una mejor dispersión. En teoría, se supone que ayudan a reducir la varianza de mis estimaciones en otra parte del proyecto.

Por desgracia, me he encontrado con problemas al trabajar con ellos y gran parte de la bibliografía al respecto es densa. Por lo tanto, esperaba obtener alguna información de alguien que tenga experiencia con ellos, o al menos encontrar una manera de evaluar empíricamente lo que está pasando:

Si ha trabajado con ellos:

• ¿Qué es exactamente el scrambling? ¿Y qué efecto tiene en el flujo de puntos que se generan? En concreto, ¿tiene algún efecto cuando aumenta la dimensión de los puntos que se generan?

• ¿Por qué si genero dos flujos de puntos Sobol con la codificación MatousekAffineOwen, obtengo dos flujos de puntos diferentes? ¿Por qué no ocurre lo mismo cuando utilizo la codificación de retícula inversa con puntos Halton? ¿Existen otros métodos de codificación para estos conjuntos de puntos y, en caso afirmativo, existe una implementación de MATLAB?

Si no ha trabajado con ellos:

• Digamos que tengo $n$ secuencias $S_1, S_2, \ldots,S_n$ de números supuestamente aleatorios, ¿qué tipo de estadística debo utilizar para demostrar que no están correlacionados entre sí? ¿Y qué número $n$ ¿tendría que demostrar que mi resultado es estadísticamente significativo? Además, ¿cómo podría hacer lo mismo si tuviera $n$ secuencias $S_1, S_2, \ldots,S_n$ de $d$ -aleatorio dimensional $[0,1]$ ¿Vectores?

---

Preguntas complementarias sobre la respuesta del Cardenal

1. En teoría, ¿podemos emparejar cualquier método de codificación con cualquier secuencia de baja discrepancia? MATLAB sólo me permite aplicar la codificación de radix inversa en secuencias Halton, y me pregunto si se trata simplemente de un problema de implementación o de un problema de compatibilidad.

2. Estoy buscando una forma que me permita generar dos redes (t,m,s) que no estén correlacionadas entre sí. ¿Me lo permitirá MatouseAffineOwen? ¿Qué tal si utilizara un algoritmo de desorden determinista y simplemente decidiera elegir cada valor 'kth' donde k fuera un primo?

Answer 1

La codificación suele ser una operación aplicada a un $(t,m,s)$ red digital que utiliza alguna base $b$ . Las redes "Sobol" utilizan $b = 2$ por ejemplo, mientras que las redes de Faure utilizan un número primo para $b$ .

El objetivo de la mezcla es conseguir (con suerte) una distribución aún más uniforme, sobre todo si sólo se puede utilizar un número reducido de puntos. Un buen ejemplo para ver por qué funciona es observar la secuencia de Halton en $d = 2$ y elige dos primos "grandes", como 29 y 31. El cuadrado se rellena muy lentamente usando la secuencia Halton estándar. Pero, con la aleatorización, se rellena de manera más uniforme y mucho más rápidamente. A continuación se muestra un gráfico de los primeros doscientos puntos utilizando un enfoque determinista.

Las formas más básicas de codificación esencialmente permutan la base $b$ expansiones de dígitos del original $n$ puntos entre ellos. Para más detalles exposición clara .

Lo bueno del scrambling es que si empiezas con un $(t,m,s)$ red y la revuelves, obtienes un $(t,m,s)$ red de nuevo fuera. Por lo tanto, hay un cierre propiedad en cuestión. Dado que desea utilizar los beneficios teóricos de una $(t,m,s)$ net en primer lugar, esto es muy deseable.

En cuanto a los tipos de codificación, la codificación de radix inverso es una determinista revolver. El algoritmo de codificación Matousek es un al azar revuelto, hecho, de nuevo, de forma que se mantenga la propiedad de cierre. Si establece la semilla aleatoria antes de hacer la llamada a la función de codificación, siempre debe obtener la misma red de vuelta.

También puede interesarle la Proyecto MinT .