¿Generar ordenadas aleatoriamente ordenadas sin el género? O (n)

Question

Acabo de ver una pregunta de código de golf sobre generating a sorted list of 100 random integers. Lo que vino a la cabeza, sin embargo, fue la idea de que se podría generar en lugar de una lista de los deltas positivos, y simplemente seguir sumando a un total acumulado, por lo tanto:

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

De hecho, se utiliza flotadores, a continuación, normalizar para adaptarse a un límite superior, y redondo, 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 ordenación. Pero lo que no tengo en cuenta es esto: ¿La distribución resultante de los enteros sería la misma que generar 100 enteros aleatorios a partir de una función de densidad de probabilidad distribuida uniformemente?

Editar: 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) 

quién (tirada de los dados justo) de salida fue de:

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

UPDATE:Alok's answer y Dan Dyer's comment punto de que el uso de un exponential distribution para los deltas daría una distribución uniforme de enteros.

Answer 1

Así que usted está preguntando si los números generados de esta manera van a ser distribuidos uniformemente.

Estás generando una serie:

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

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

Esto se puede hacer iff x _i se distribuyen exponencialmente (con una media fija). Por lo tanto, si x _i se distribuyen uniformemente, el resultado y _j no se distribuirá uniformemente.

Habiendo dicho eso, es bastante fácil generar valores exponenciales x _i.

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: Generating Sorted Lists of Random Numbers. El documento tiene otros algoritmos (más rápidos) también.

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

Answer 2

A uniform distribution tiene un límite superior e inferior. Si usa su método propuesto, y sus deltas resultan ser elegidos lo suficientemente grandes como para llegar al límite superior antes de haber generado todos sus números, ¿qué haría su algoritmo después?

Habiendo dicho eso, es posible que desee investigar el Poisson distribution, que es la distribución de los tiempos de intervalo entre los eventos aleatorios que se producen con una frecuencia promedio dada.

Answer 3

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 obtendrás la extraña posibilidad de tener un conjunto de números muy bajos.

Answer 4

Si toma el rango numérico de 1 a 1000, y tiene que usar 100 de estos números, el delta deberá tener un mínimo de 10, de lo contrario no podrá alcanzar la marca 1000. ¿Qué hay de algunos que trabajan para demostrarlo en acción ...

La posibilidad de cualquier número dado en una selección aleatoria distribuida uniformemente es de 100/1000 p. Ej. 1/10: no hay shock allí, toma eso como base.

Asumiendo empiece a usar un delta y que Delta está a sólo 10.

Las probabilidades de conseguir el número 1 es 1/10 - parece estar bien. Las probabilidades de obtener el número 2 son 1/10 + (1/10 * 1/10) (porque podría golpear 2 deltas de 1 en una fila, o simplemente golpear un 2 como primer delta). Las probabilidades de obtener 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 estaba golpeando 3 deltas de 1 en una fila, el tercer caso sería un delta de 1 seguido por un 2, y el cuarto caso era un delta de 2 seguido por un 1.

Por el bien de mi dedos de escribir, que no va a generar las combinaciones que afectó a 5.

Inmediatamente los primeros números tienen un mayor porcentaje de probabilidad de que el azar recta.

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

Para dar una analogía que podría simplemente hundirlo, si considera que su delta es solo 6 y lo ejecuta dos veces es el equivalente a tirar 2 dados: cada uno de los deltas es independiente, pero sabe que 7 tiene una mayor probabilidad de ser seleccionado que 2.

Answer 5

Puede hacerlo en dos pasos;

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

en el segundo pase, normalizar los números aleatorios que estar dentro de límites

Aún O (n), con buena localidad de referencia.

Answer 6

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?

A: 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 finita y varianza) tenderá a la distribución normal. Por lo tanto, los últimos desvíos en su secuencia serán no distribuidos uniformemente.

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

Answer 7

Alok's answer y Dan Dyer's comment señalan que usar un exponential distribution 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) 

Nota el uso de random.expovariate(1.0), un Python exponential distribution random number generator (muy útil!). Aquí se llama con una media de 1.0, pero como la secuencia de comandos se normaliza contra el último número de la secuencia, la media en sí misma no importa.

salida (tirada de dados justo):

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

Answer 8

El reference (1979) en Alok's answer es interesante. Se da un algoritmo para la generación de las estadísticas de orden uniforme no por adición pero 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 forma, 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.

The Exponential distribution: theory, methods and applications By N. Balakrishnan, Asit P. Basu da otra derivación de este algoritmo en la página 22 y acredita a Malmquist (1950).