Números aleatorios uniformes falsos: Más uniformes que los verdaderos datos uniformes

Question

Estoy buscando una forma de generar números aleatorios que aparece para que se distribuyan uniformemente - y todas las pruebas mostrarán que son uniformes - excepto que son más uniformes que los verdaderos datos uniformes .

El problema que tengo con los "verdaderos" uniformes aleatorios es que ocasionalmente se agrupan. Este efecto es más fuerte con un tamaño de muestra bajo. Dicho a grandes rasgos: cuando saco dos aleatorios uniformes en U[0;1], las probabilidades de que estén dentro de un rango de 0,1 son de alrededor del 10%, y del 1% de que estén dentro de 0,01.

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

Ejemplo de caso de uso: digamos que estoy haciendo un juego de ordenador, y quiero colocar un tesoro de forma aleatoria en un mapa (sin preocuparme de nada más). No quiero que el tesoro esté todo en un solo lugar, sino que debe estar por todo el mapa. Con aleatoriedad uniforme, si coloco, digamos, 10 objetos, las probabilidades no son tan bajas de que haya 5 o más muy cerca unos de otros. Esto puede dar ventaja a un jugador sobre otro. Piensa en el buscaminas, las posibilidades (aunque bajas, si hay suficientes minas) son que tengas mucha suerte y ganes con un solo clic.

Un enfoque muy ingenuo para mi problema es dividir los datos en una cuadrícula. Siempre que el número sea lo suficientemente grande (y tenga factores), se puede reforzar la uniformidad de esta manera. Así, 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 conseguir esta uniformidad adicional en el uniforme? Probablemente sólo funcione para los aleatorios por lotes (al extraer un único aleatorio, obviamente tengo que considerar todo el rango). En particular, puedo volver a barajar los registros después (para que no sean los cuatro primeros del primer tercio).

¿Qué tal si lo hacemos de forma gradual? ¿Así que el primero está en U[0;1], luego dos de cada mitad, uno de cada tercio, uno de cada cuarto? ¿Se ha investigado esto, y qué tan bueno es? Puede que tenga que tener cuidado de utilizar diferentes generadores para x e y para no conseguir que se correlacionen (el primer xy siempre estaría en la mitad inferior, el segundo en la mitad izquierda y en el tercio inferior, el tercero en el tercio central y en el tercio superior... así que también se necesita al menos alguna permutación aleatoria de contenedores. y a la larga, será demasiado uniforme, supongo.

Como nodo secundario, ¿existe una prueba bien conocida de si alguna distribución es también distribuido uniformemente para ser realmente uniforme? Es decir, probar la "uniformidad real" frente a "alguien ha manipulado los datos y ha distribuido los elementos de forma más uniforme". Si no recuerdo mal, el estadístico de Hopkins puede medir esto, pero ¿también se puede utilizar para hacer pruebas? También algo así como una prueba K-S inversa: si la mayor desviación está por debajo de un determinado umbral esperado, ¿los datos están distribuidos de forma demasiado uniforme?

Answer 1

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.

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.

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.

$(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).

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.

Answer 2

Una forma de hacerlo sería generar números aleatorios uniformes, luego probar la "cercanía" usando el método que quieras y luego eliminar los elementos aleatorios que estén demasiado cerca de otros y elegir otro conjunto de uniformes aleatorios para compensarlos.

¿Pasaría dicha distribución todas las pruebas de uniformidad? Espero que no. Ya no está distribuida uniformemente, ahora es otra distribución.

Un aspecto poco intuitivo de la probabilidad es que el azar es desigual. En los datos aleatorios hay más corridas de las que la gente cree que habrá. Creo que Tversky hizo algunas investigaciones sobre esto (aunque investigó tanto que es difícil de recordar).

Answer 3

Esto se conoce como un proceso de puntos de Poisson de "núcleo duro", llamado así por Brian Ripley en los años 70; es decir, se quiere que sea aleatorio, pero no se quiere que ningún punto esté demasiado cerca. El "núcleo duro" puede imaginarse como una zona de amortiguación alrededor de la cual no pueden entrar otros puntos.

Imagina que registras la posición de unos coches en una ciudad, pero sólo registras el punto del centro nominal del coche. Mientras están en la calle, ningún par de puntos puede acercarse porque los puntos están protegidos por el "núcleo duro" de la carrocería - ignoramos la posible superposición en los aparcamientos de varias plantas :-)

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

Para conocer algunos detalles sobre estos procesos, consulte, por ejemplo este

Answer 4

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

Con respecto a la generación incremental, lo que se busca esencialmente es 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 las series temporales, pero sospecho que hay algoritmos existentes para esto.

Con respecto a una prueba de "demasiado uniforme", cualquier prueba para saber si una muestra sigue una distribución específica (como la KS señalada anteriormente) servirá, sólo hay que comprobar si $p > (1-\alpha)$ en lugar del enfoque estándar. Escribí sobre un ejemplo de este enfoque alternativo aquí: chi-cuadrado siempre es una prueba unilateral .

Answer 5

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

Una forma fácil de generar estos vectores es hacer un muestreo de Gibbs.