Cito el libro de Peter Jäckel "Monte Carlo Methods in Finance", página 96:
...Para los números de baja discrepancia, la situación es diferente. Los números de Sobol y otros generadores de números basados en el módulo dos de la aritmética de enteros, por construcción proporcionan propiedades adicionales de equidistribución siempre que el número de iteraciones sea $N=2^n-1$
¿Cuál es el incentivo matemático detrás de esta elección de iteraciones?
¿Se aplica lo mismo a las secuencias de Halton?
Gran parte de lo que sigue puede encontrarse en Glasserman (2003), capítulo 5, Métodos de Monte Carlo en ingeniería financiera .
La razón de utilizar números de baja discrepancia es que están algo "equidistribuidos", lo que significa que se puede garantizar que llenan el intervalo unitario de forma regular sin tener grandes huecos. (lo mismo ocurre con el cuadrado unitario, o el cubo unitario, etc.). De hecho, esto es exactamente lo que se entiende por "baja discrepancia", donde la discrepancia $D$ de un conjunto de $n$ puntos $\mathbf{x} = \{x_i\}_{i=1}^n$ en un volumen $\mathcal{A}$ es $$ D(\mathbf{x}; \mathcal{A}) = \sup_{A \subseteq \mathcal{A}} \left|\dfrac{\left|\{\mathbf{x} \cap A\}\right|}{n} - \mu(A)\right| $$ donde $\mu(A)$ es la medida del volumen de $A$ la discrepancia de las estrellas $D^*$ es cuando $\mathcal{A}$ se toma como un rectángulo. Obsérvese que la discrepancia mide la uniformidad de los puntos, cuantificando el tamaño de los vacíos (relativamente).
La razón por la que nos preocupamos es porque la desigualdad de Koksma-Hlawka limita el error de la estimación de Monte Carlo por un término proporcional a $D^*$ . Ahora bien, fue Niederreiter quien demostró que el mínimo en 1 dimensión se obtiene mediante puntos equidistantes. Sin embargo, estos escalan mal con una dimensión más alta, pero las secuencias de baja discrepancia tienen una estrella que escala con $\mathcal{O}((\log{n})^d/n)$ y, por lo tanto, escalan muy bien con la dimensión (hasta unos 40 más o menos). Si consideramos una secuencia unidimensional para generar una secuencia de baja discrepancia, como una secuencia de Sobol o de Halton (hay muchas más), éstas empiezan por muestrear puntos en intervalos diádicos. La más sencilla es la secuencia de Halton, que consiste en escribir los enteros en binario con un solo decimal y luego invertir la secuencia de dígitos (por ejemplo, 1,2,3 se convierten en 1,0, 10,0, 11,0, que producen 0,1, 0,01, 0,11, etc.). Podemos ver que estas secuencias sólo son equidistantes (y por lo tanto tienen la mínima discrepancia en estrella) cuando tenemos $N=2^n - 1$ (podemos dejar de lado el $-1$ si decidimos incluir el cero). Esto se ve mejor pictóricamente en 2 dimensiones (he incluido el cero en la secuencia):
Obsérvese que en los puntos aleatorios hay grandes vacíos, mientras que la secuencia sobol de baja discrepancia rellena la malla de manera uniforme. Sin embargo, esta uniformidad es óptima cuando hay $2^n$ (o $2^n-1$ si no se utiliza el cero) puntos.
He publicado un extracto gratuito de mi libro Modern Computational Finance en el que se explica la secuencia de Sobol y, en particular, su propiedad de hipercubo latino, lo que significa que cada eje se muestrea de manera uniforme pero en un orden diferente para los distintos ejes, siempre que el número de muestras sea una potencia de 2 menos 1. Espero que le sirva de ayuda:
https://medium.com/@antoine_savine/sobol-secuencia-explicada-188f422b246b
Antoine Savine
FinanHelp es una comunidad para personas con conocimientos de economía y finanzas, o quiere aprender. Puedes hacer tus propias preguntas o resolver las de los demás.
4 votos
La frase que sigue inmediatamente no lo explica suficientemente? "Esto es fácil de ver en el intervalo unitario en una dimensión, donde tal elección de sorteos siempre da lugar a una distribución de puntos perfectamente regular, y también se puede confirmar en los diagramas de discrepancia empírica de la sección 8.6 hasta la dimensión 5."