math - procesos - ¿Generando entradas aleatorias ordenadas sin la clasificación? En)

procesos estocasticos libros

Question

Acabo de ver una pregunta de código de golf sobre cómo generar una lista ordenada de 100 enteros aleatorios . Sin embargo, lo que me vino a la cabeza fue la idea de que en su lugar podría generar una lista de deltas positivos y seguir agregándolos a un total acumulado, por lo tanto

deltas: 1 3 2 7 2
ints: 1 4 6 13 15

De hecho, usaría flotadores, luego se normalizaría para ajustarse a algún límite superior y redondear, pero el efecto es el mismo.

Aunque no sería un código más corto, sin duda sería más rápido sin el paso de clasificación. Pero lo que no tengo un control real es esto: ¿la distribución resultante de los enteros sería la misma que la generación de 100 enteros aleatorios a partir de una función de densidad de probabilidad distribuida uniformemente?

Edición: Un script de ejemplo:

import random,sys
running = 0
max = 1000
deltas = [random.random() for i in range(0,11)]
floats = []
for d in deltas:
running += d
floats.append(running)
upper = floats.pop()
ints = [int(round(f/upper*max)) for f in floats]
print(ints)

Cuya salida (tirada de dados justa) fue:

[24, 71, 133, 261, 308, 347, 499, 543, 722, 852]

ACTUALIZACIÓN: La respuesta de Alok y el comentario de Dan Dyer señalan que el uso de una distribución exponencial para los deltas daría una distribución uniforme de enteros.

Answer 1

Creo que será extremadamente similar pero los extremos serán diferentes debido a la normalización. Por ejemplo, 100 números elegidos al azar entre 1 y 100 podrían ser 1. Sin embargo, 100 números creados usando su sistema podrían tener deltas de 0.01, pero cuando los normalice, los escalará para estar en el rango 1 -> 100, lo que significa que nunca tendrás esa extraña posibilidad de un conjunto de números muy bajos.

Answer 2

Entonces, usted está preguntando si los números generados de esta manera se distribuirán de manera uniforme.

Estás generando una serie:

y _j = ∑ _{i = 0} ^j (x _i / A)

donde A es la suma de todos x _i . x _i es la lista de deltas (positivas).

Esto se puede hacer si xi _i se distribuye exponencialmente (con cualquier media fija). Entonces, si x _i se distribuyen uniformemente, el _yj resultante no se distribuirá uniformemente.

Dicho esto, es bastante fácil generar valores xi exponenciales.

Un ejemplo sería:

sum := 0
for I = 1 to N do:
X[I] = sum = sum - ln(RAND)
sum = sum - ln(RAND)
for I = 1 to N do:
X[I] = X[I]/sum

y tendrá sus números aleatorios ordenados en el rango [0, 1) .

Referencia: Generación de listas ordenadas de números aleatorios . El papel tiene otros algoritmos (más rápidos) también.

Por supuesto, esto genera números de punto flotante. Para una distribución uniforme de enteros , puede reemplazar la sum anterior por sum/RANGE en el último paso (es decir, el RHS se convierte en X[I]*RANGE/sum , y luego redondear los números al entero más cercano).

Answer 3

La referencia (1979) en la respuesta de Alok es interesante. Proporciona un algoritmo para generar las estadísticas de orden uniforme no por adición sino por multiplicación sucesiva:

max = 1.
for i = N downto 1 do
out[i] = max = max * RAND^(1/i)

donde RAND es uniforme en [0,1). De esta manera, no tiene que normalizarse al final y, de hecho, ni siquiera tiene que almacenar los números en una matriz; Podrías usar esto como un iterador.

La distribución exponencial: teoría, métodos y aplicaciones Por N. Balakrishnan, Asit P. Basu da otra derivación de este algoritmo en la página 22 y acredita a Malmquist (1950).

Answer 4

P: ¿La distribución resultante de enteros sería la misma que la generación de 100 enteros aleatorios a partir de una función de densidad de probabilidad distribuida uniformemente?

R: Cada delta se distribuirá uniformemente. El teorema del límite central nos dice que la distribución de una suma de un gran número de tales desviaciones (ya que tienen una media y varianza finitas) tenderá a la distribución normal. Por lo tanto, las últimas desviaciones en su secuencia no se distribuirán uniformemente.

Así que la respuesta corta es "no". Me temo que no puedo dar una solución simple sin hacer álgebra. ¡No tengo tiempo para hacerlo hoy!

Answer 5

Puedes hacerlo en dos pases;

en la primera pasada, genere deltas entre 0 y (MAX_RAND / n)

en la segunda pasada, normaliza los números aleatorios para que estén dentro de los límites

Todavía O (n), con buena localidad de referencia.

Answer 6

Si toma el rango de números de 1 a 1000, y tiene que usar 100 de estos números, el delta tendrá que ser un mínimo de 10, de lo contrario no podrá alcanzar la marca 1000. ¿Qué tal un trabajo para demostrarlo en acción ...

La posibilidad de un número dado en una selección aleatoria distribuida uniformemente es de 100/1000, por ejemplo, 1/10 - no hay impacto allí, tómelo como base.

Suponiendo que comienzas a usar un delta y ese delta es solo 10.

Las probabilidades de obtener el número 1 son 1/10 - parece bien. Las probabilidades de obtener el número 2 son 1/10 + (1/10 * 1/10) (porque puedes golpear 2 deltas de 1 en una fila, o simplemente golpear un 2 como el primer delta). Las probabilidades de obtener el el número 3 es 1/10 + (1/10 * 1/10 * 1/10) + (1/10 * 1/10) + (1/10 * 1/10)

El primer caso fue un delta de 3, el segundo golpeó 3 deltas de 1 en una fila, el tercer caso sería un delta de 1 seguido de un 2, y el cuarto caso fue un delta de 2 seguido de un 1.

Por el bien de mis dedos, no generaremos las combinaciones que alcancen 5.

Inmediatamente los primeros números tienen una mayor probabilidad de porcentaje que el azar directo.

Esto podría modificarse cambiando el valor delta para que las fracciones sean todas diferentes, pero no creo que puedas encontrar un delta que produzca probabilidades idénticas.

Para dar una analogía que podría simplemente hundirlo, si consideras que tu delta es solo 6 y ejecutas que dos veces es el equivalente a lanzar 2 dados: cada uno de los deltas es independiente, pero sabes que 7 tiene una mayor probabilidad de ser seleccionado de 2.

Answer 7

Una distribución uniforme tiene un límite superior y un límite inferior. Si usa el método propuesto y sus deltas son elegidos lo suficientemente grandes como para que se encuentre en el límite superior antes de que haya generado todos sus números, ¿qué haría su algoritmo a continuación?

Dicho esto, es posible que desee investigar la distribución de Poisson , que es la distribución de los tiempos de intervalo entre eventos aleatorios que ocurren con una frecuencia promedio determinada.

Answer 8

La respuesta de Alok y el comentario de Dan Dyer señalan que el uso de una distribución exponencial para los deltas daría una distribución uniforme de enteros.

Así que la nueva versión del ejemplo de código en la pregunta sería:

import random,sys
running = 0
max = 1000
deltas = [random.expovariate(1.0) for i in range(0,11)]
floats = []
for d in deltas:
running += d
floats.append(running)
upper = floats.pop()
ints = [int(round(f/upper*max)) for f in floats]
print(ints)

Observe el uso de random.expovariate(1.0) , un generador de números aleatorios de distribución exponencial de Python (¡muy útil!). Aquí se llama con una media de 1.0, pero como la secuencia de comandos se normaliza contra el último número en la secuencia, la media en sí no importa.

Salida (tirada de dados justa):

[11, 43, 148, 212, 249, 458, 539, 725, 779, 871]