Números aleatorios falsos uniformes: distribuidos de manera más uniforme que los datos uniformes verdaderos

Estoy buscando una forma de generar números aleatorios que parezcan distribuidos uniformemente, y cada prueba mostrará que son uniformes, excepto que están distribuidos de manera más uniforme que los datos uniformes verdaderos .

El problema que tengo con los randoms uniformes "verdaderos" es que ocasionalmente se agruparán. Este efecto es más fuerte con un tamaño de muestra bajo. Aproximadamente dicho: cuando dibujo dos randoms uniformes en U [0; 1], las posibilidades son de alrededor del 10% de que están dentro de un rango de 0.1, y del 1% de que están dentro de 0.01.

Así que estoy buscando una buena manera de generar números aleatorios que estén distribuidos de manera más uniforme que los randoms uniformes .

Ejemplo de caso de uso: digamos que estoy haciendo un juego de computadora y quiero colocar tesoros al azar en un mapa (sin importarme ninguna otra cosa). No quiero que el tesoro esté en un solo lugar, debería estar en todo el mapa. Con randoms uniformes, si coloco, digamos, 10 objetos, las posibilidades no son tan bajas de que haya 5 o menos realmente cerca el uno del otro. Esto puede dar a un jugador una ventaja sobre otro. Piense en el buscaminas, las posibilidades (aunque sean bajas, si hay suficientes minas) son que tenga mucha suerte y gane con un solo clic.

Un enfoque muy ingenuo para mi problema es dividir los datos en una cuadrícula. Mientras el número sea lo suficientemente grande (y tenga factores), se puede imponer una uniformidad adicional de esta manera. Entonces, en lugar de extraer 12 variables aleatorias de U [0; 1], puedo extraer 6 de U [0; .5] y 6 de U [0.5; 1], o 4 de U [0; 1/3] + 4 de U [1/3; 2/3] + 4 de U [2/3; 1]

¿Hay alguna forma mejor de lograr esta uniformidad adicional en el uniforme? Probablemente solo funcione para randoms por lotes (al dibujar un solo azar, obviamente tengo que considerar todo el rango). En particular, puedo mezclar los registros nuevamente después (por lo que no son los primeros cuatro del primer tercio).

¿Qué tal hacerlo de forma incremental? Entonces, ¿el primero está en U [0; 1], luego dos de cada mitades, uno de cada tercero, uno de cada cuarto? ¿Se ha investigado esto y qué tan bueno es? Es posible que tenga que tener cuidado de usar diferentes generadores para x e y para no correlacionarlos (el primer xy siempre estará en la mitad inferior, el segundo en la mitad izquierda y el tercio inferior, el tercero en el tercio central y el tercero superior). ... por lo que también se necesita al menos una permutación aleatoria del contenedor y, a la larga, será demasiado parejo, supongo.

Como nodo lateral, ¿existe una prueba bien conocida de si alguna distribución está demasiado uniformemente distribuida para ser realmente uniforme? Por lo tanto, probar "verdadero uniforme" versus "alguien se metió con los datos y distribuyó los elementos de manera más uniforme". Si recuerdo correctamente, Hopkins Statistic puede medir esto, pero ¿puede usarse también para pruebas? También es una prueba KS inversa: si la desviación más grande está por debajo de un cierto umbral esperado, ¿los datos se distribuyen de manera uniforme?

Sí , hay muchas formas de producir una secuencia de números que se distribuyen de manera más uniforme que los uniformes aleatorios. De hecho, hay todo un campo dedicado a esta pregunta; Es la columna vertebral de cuasi-Monte Carlo (QMC). A continuación se muestra un breve recorrido por los conceptos básicos absolutos.

Medición de uniformidad

Hay muchas formas de hacer esto, pero la forma más común tiene un sabor fuerte, intuitivo y geométrico. Supongamos que estamos interesados ​​en generar puntos en para algún número entero positivo . Definir donde es un rectángulo en tal que yx 1 , x 2 , … , x n [ 0 , 1 ] d$n$$x_1,x_2,\ldots,x_n$$[0,1]^d$$d$

$$\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| \>,$$ $R$$[a_1, b_1] \times \cdots \times [a_d, b_d]$$[0,1]^d$$0 \leq a_i \leq b_i \leq 1$$\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 y el segundo término es el volumen de , .$R$$R$$\mathrm{vol}(R) = \prod_i (b_i - a_i)$

La cantidad menudo se denomina discrepancia o discrepancia extrema del conjunto de puntos . Intuitivamente, encontramos el "peor" rectángulo donde la proporción de puntos se desvía más de lo que esperaríamos con una uniformidad perfecta.$D_n$$(x_i)$$R$

Esto es difícil de manejar en la práctica y difícil de calcular. En su mayor parte, las personas prefieren trabajar con la discrepancia de estrella , La única diferencia es el conjunto sobre el cual se toma el supremum. Es el conjunto de rectángulos anclados (en el origen), es decir, donde .

$$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| \>.$$ $\mathcal A$$a_1 = a_2 = \cdots = a_d = 0$

Lema : para todos , . Prueba . La mano izquierda unida es obvia ya que . El límite a la derecha sigue porque cada se puede componer mediante uniones, intersecciones y complementos de no más de rectángulos anclados (es decir, en ).$D_n^\star \leq D_n \leq 2^d D_n^\star$$n$$d$
$\mathcal A \subset \mathcal R$$R \in \mathcal R$$2^d$$\mathcal A$

Por lo tanto, vemos que y son equivalentes en el sentido de que si uno es pequeño a medida que crece, el otro también lo será. Aquí hay una imagen (caricatura) que muestra rectángulos candidatos para cada discrepancia.$D_n$$D_n^\star$$n$

Ejemplos de secuencias "buenas"

Las secuencias con discrepancia de estrella verificablemente baja menudo se denominan, como era de esperar, secuencias de baja discrepancia .$D_n^\star$

Van der Corput . Este es quizás el ejemplo más simple. Para , las secuencias de van der Corput se forman expandiendo el número entero en binario y luego "reflejando los dígitos" alrededor del punto decimal. Más formalmente, esto se hace con la función inversa radical en la base , donde y son los dígitos en la expansión base de . Esta función forma la base de muchas otras secuencias también. Por ejemplo, en binario es y así$d=1$$i$$b$

$$\newcommand{\rinv}{\phi} \rinv_b(i) = \sum_{k=0}^\infty a_k b^{-k-1} \>,$$ $i = \sum_{k=0}^\infty a_k b^k$$a_k$$b$$i$$41$$101001$$a_0 = 1$ , , , , y . Por lo tanto, el punto 41 en la secuencia de van der Corput es .$a_1 = 0$$a_2 = 0$$a_3 = 1$$a_4 = 0$$a_5 = 1$$x_{41} = \rinv_2(41) = 0.100101\,\text{(base 2)} = 37/64$

Tenga en cuenta que debido a que el bit menos significativo de oscila entre y , los puntos para impar están en , mientras que los puntos para incluso están en .$i$$0$$1$$x_i$$i$$[1/2,1)$$x_i$$i$$(0,1/2)$

Secuencias de Halton . Entre las secuencias de baja discrepancia clásicas más populares, estas son extensiones de la secuencia de van der Corput a múltiples dimensiones. Deje que sea ​​la ésima prima más pequeña. Entonces, el ésimo punto de la secuencia dimensional de Halton es Para baja estos funcionan bastante bien, pero tienen problemas en dimensiones más altas .$p_j$$j$$i$$x_i$$d$

$$x_i = (\rinv_{p_1}(i), \rinv_{p_2}(i),\ldots,\rinv_{p_d}(i)) \>.$$ $d$

Las secuencias de Halton satisfacen . También son agradables porque son extensibles porque la construcción de los puntos no depende de una elección a priori de la longitud de la secuencia .$D_n^\star = O(n^{-1} (\log n)^d)$$n$

Secuencias de Hammersley . Esta es una modificación muy simple de la secuencia de Halton. En su lugar, usamos Quizás sorprendentemente, la ventaja es que tienen una mejor discrepancia de estrellas .

$$x_i = (i/n, \rinv_{p_1}(i), \rinv_{p_2}(i),\ldots,\rinv_{p_{d-1}}(i)) \>.$$ $D_n^\star = O(n^{-1}(\log n)^{d-1})$

Aquí hay un ejemplo de las secuencias de Halton y Hammersley en dos dimensiones.

Secuencias de Halton permutadas por Faure . Se puede aplicar un conjunto especial de permutaciones (fijadas en función de ) a la expansión de dígitos para cada cuando se produce la secuencia de Halton. Esto ayuda a remediar (hasta cierto punto) los problemas a los que se alude en dimensiones superiores. Cada una de las permutaciones tiene la propiedad interesante de mantener y como puntos fijos.$i$$a_k$$i$$0$$b-1$

Reglas de celosía . Deje que sean enteros. Tome donde denota la parte fraccional de . La elección juiciosa de los valores produce buenas propiedades de uniformidad. Las malas elecciones pueden conducir a malas secuencias. Tampoco son extensibles. Aquí hay dos ejemplos.$\beta_1, \ldots, \beta_{d-1}$

$$x_i = (i/n, \{i \beta_1 / n\}, \ldots, \{i \beta_{d-1}/n\}) \>,$$ $\{y\}$$y$$\beta$

$(t,m,s)$ redes . redes en la base son conjuntos de puntos de manera que cada rectángulo de volumen en contiene puntos. Esta es una forma fuerte de uniformidad. Pequeño es tu amigo, en este caso. Las secuencias de Halton, Sobol 'y Faure son ejemplos de redes . Estos se prestan muy bien a la aleatorización a través de la codificación. La aleatorización aleatoria (correcta) de una red produce otra red . El proyecto MinT mantiene una colección de tales secuencias.$(t,m,s)$$b$$b^{t-m}$$[0,1]^s$$b^t$$t$$(t,m,s)$$(t,m,s)$$(t,m,s)$

Aleatorización simple: rotaciones de Cranley-Patterson . Sea una secuencia de puntos. Deje . Entonces los puntos se distribuyen uniformemente en .$x_i \in [0,1]^d$$U \sim \mathcal U(0,1)$$\hat x_i = \{x_i + U\}$$[0,1]^d$

Aquí hay un ejemplo con los puntos azules que son los puntos originales y los puntos rojos que son los rotados con líneas que los conectan (y se muestran envueltos, cuando corresponde).

Secuencias completamente distribuidas uniformemente . Esta es una noción aún más fuerte de uniformidad que a veces entra en juego. Sea la secuencia de puntos en y ahora forme bloques superpuestos de tamaño para obtener la secuencia . Entonces, si , tomamos luego , etc. Si, por cada , , entonces se dice que está completamente uniformemente distribuida . En otras palabras, la secuencia produce un conjunto de puntos de cualquier$(u_i)$$[0,1]$$d$$(x_i)$$s = 3$$x_1 = (u_1,u_2,u_3)$$x_2 = (u_2,u_3,u_4)$ $s \geq 1$$D_n^\star(x_1,\ldots,x_n) \to 0$$(u_i)$dimensión que tiene propiedades deseables .$D_n^\star$

Como ejemplo, la secuencia de van der Corput no está completamente distribuida uniformemente ya que para , los puntos están en el cuadrado y los puntos están en . Por lo tanto, no hay puntos en el cuadrado que implica que para , para todo .$s = 2$$x_{2i}$$(0,1/2) \times [1/2,1)$$x_{2i-1}$$[1/2,1) \times (0,1/2)$$(0,1/2) \times (0,1/2)$$s=2$$D_n^\star \geq 1/4$$n$

Referencias estándar

La monografía de Niederreiter (1992) y el texto de Fang y Wang (1994) son lugares a donde ir para una mayor exploración.

Una forma de hacerlo sería generar números aleatorios uniformes, luego probar la "cercanía" utilizando cualquier método que desee y luego eliminar elementos aleatorios que estén demasiado cerca de los demás y elegir otro conjunto de uniformes aleatorios para compensarlos.

¿Tal distribución pasaría todas las pruebas de uniformidad? ¡Espero que no! Ya no se distribuye uniformemente, ahora es otra distribución.

Un aspecto poco intuitivo de la probabilidad es que el azar es desordenado. Hay más ejecuciones en datos aleatorios de lo que la gente cree que habrá. Creo que Tversky investigó un poco sobre esto (investigó tanto que es difícil de recordar).

Esto se conoce como un proceso de punto de Poisson "núcleo duro", llamado así por Brian Ripley en la década de 1970; es decir, desea que sea aleatorio, pero no desea que ningún punto esté demasiado cerca. El "núcleo duro" se puede imaginar como una zona de amortiguación alrededor de la cual otros puntos no pueden entrometerse.

Imagine que está registrando la posición de algunos automóviles en una ciudad, pero solo está registrando el punto en el centro nominal del automóvil. Mientras están en la calle, no hay dos pares de puntos que se puedan unir porque los puntos están protegidos por el "núcleo duro" de la carrocería: ignoraremos la posible superposición en aparcamientos de varios pisos :-)

Existen procedimientos para generar tales procesos de puntos: una forma es generar puntos de manera uniforme y luego eliminar los que estén demasiado juntos.

Para obtener algunos detalles sobre tales procesos, consulte, por ejemplo, esto

Con respecto a la generación por lotes de antemano, generaría una gran cantidad de conjuntos de variantes pseudoaleatorias y luego las probaría con una prueba como la prueba de Kolmogorov-Smirnov. Deberá seleccionar el conjunto que tenga el valor p más alto (es decir, es ideal). Tenga en cuenta que esto será lento, pero a medida que hace más grande, probablemente sea menos necesario. $p \approx 1$$N$

Con respecto a la generación incremental, esencialmente está buscando una serie con una autocorrelación moderadamente negativa. No estoy seguro de cuál sería la mejor manera de hacerlo, ya que tengo una experiencia muy limitada con series temporales, pero sospecho que existen algoritmos existentes para esto.

Con respecto a una prueba de "demasiado parejo", cualquier prueba de si una muestra sigue una distribución específica (como el KS mencionado anteriormente) servirá, solo desea verificar si , en lugar de enfoque estándar Escribí sobre un ejemplo de este enfoque alternativo aquí: chi-cuadrado siempre es una prueba unilateral . $p > (1-\alpha)$

Formalizaría su problema de esta manera: desea una distribución sobre tal que la densidad sea para algunos cuantificando la repulsión de puntos.$[0,1]^n$$f(x) \propto e^{\left(\frac1k\sum_{ij}\lvert x_i-x_j \rvert^{k}\right)^{\frac1k}}$$k<0$

Una manera fácil de generar tales vectores es hacer un muestreo de Gibbs.