Elegir una distribución discreta no uniforme para generar enteros aleatorios

Question

Tengo una lista de $l$ que contiene números enteros en el rango de $[1,max]$

En la lista de $l$ I hacer una operación $isPresent(x)$ que regresar true si x está presente en $l$.

Me genere $x$ utilizando la función de $nextX()$ que genera la próxima $x$ sobre la marcha usando algunos de distribución aleatoria

Lista de $l$ y la función $isPresent(x)$ poner juntos es un sistema donde la lista de $l$ es un personalizados estructura de datos similar a la de un árbol de búsqueda binario y $isPresent(x)$ es un nuevo algoritmo similar a un algoritmo de búsqueda binaria, que opera de manera eficiente en la estructura de datos.

Quiero probar el rendimiento de este sistema contra los conocidos de búsqueda, los árboles y los algoritmos de búsqueda.

El método actual que estoy usando de referencia de estos sistemas es, generar una random workload. Yo rellenar la lista $l$ con el uniforme de números aleatorios en el rango de $[1,max]$. A continuación, generar un número aleatorio uniforme $x$ $nextX()$ y se pasa a la función de $isPresent(x)$. I do $k$ este tipo de operaciones. Aquí la función $nextX()$ sólo llama a $rand()$ para obtener el siguiente número aleatorio.

Lo que yo quería probar es un skewed workload. He intentado utilizar la distribución de Poisson en $nextX()$ generar $x$ (Utilizando la distribución de Poisson para generar enteros aleatorios) con $mu$ max/1.1 , pero la desviación estándar es pequeña y los números generados son agrupados cerca de la $max$. Quiero escoger una distribución discreta otros de la distribución uniforme, pero los valores generados deben roughly cubrir todo el rango de $[1,max]$

Otra carga de trabajo que quiero generar debería tener la siguiente propiedad.

La función de $nextX()$ debe devolver un entero en el rango de $[1,max]$. Si llamo a $nextX$ función de $k$ a veces, algunas de las $k$ enteros debe ser al azar, pero no puede haber un período en el que algunos de ellos podrían ser una ordenada secuencia (ascendente o desending)

Por ejemplo, si $max=32$, a continuación, llamar a $nextX()$ 18 de las veces se puede volver 17,11,23,5,7,17,23,30,2,31,17,1,19,14,8,6,5,2

Aquí la primera 3 enteros son al azar, seguido por una secuencia ordenada de longitud aleatoria 5, seguido por una secuencia aleatoria de números enteros de longitud 4 , seguido por un inversa secuencia ordenada de longitud aleatoria 6

Me puede lograr esto mediante la generación de 18 ordenados de números y ellos al azar, seleccionando el número de particiones y en cada partición puedo elegir aleatoriamente a los shuffle. Pero el problema con esto es que necesita mucho espacio de almacenamiento y el valor de $k$, lo que representa el número de veces que la función de $nextX()$ se invoca es muy grande por lo que quiero para generar esta distribución desigual sobre la marcha.

Antecedentes:

La razón por la que mirar para generar una secuencia es que un desequilibrio en el árbol de búsqueda binario funciona bien para la distribución al azar, ya que la altura del árbol es de cerca de $O(log(n))$. Para la ordenada secuencia de la altura se puede ir tan alto como $O(n)$. En la práctica ambos son nunca el caso. Las cargas de trabajo tienden a ser al azar con ocasionales ordenan las secuencias intercaladas.

Answer 1

Acaba de lanzar una idea, pero supongo que se podría tratar de usar algo similar a un modelo Oculto de Markov, o algún tipo de modelo de mezcla.

En el caso de que el primer flujo de trabajo, usted podría, por ejemplo, obtener un conjunto de distribuciones como poisson, binomial, uniforme, geométrica y así sucesivamente. A continuación, en cada paso que primero se seleccionan de forma aleatoria a partir de la cual la distribución se dibuja en este paso, y extraer una muestra de una distribución elegida. Por supuesto, usted puede tener muchas copias de la misma distribución en el conjunto que está dibujando, pero con diferentes parámetros (como muchas distribuciones binomiales con diferentes medios). Esto debería darle más interesante multimodal distribuciones que son aún más fáciles de muestra.

En el caso de la segunda de flujo de trabajo, tal vez intente algo HMM-por igual. Recordar el estado en que te encuentras (aumento de la secuencia, disminución de la secuencia, el ruido aleatorio). En cada paso de saltar de un estado a otros estados con una cierta probabilidad (usted puede calcular la distribución estacionaria de la cadena de markov para controlar el tiempo en avarege usted permanecerá en cada estado). Si usted está en el ruido aleatorio del estado, acaba de elegir a la próxima muestra de algunos de distribución de su elección. Si estás en "aumentar" o "disminuir" los estados, sorteo aleatorio número positivo (probablemente de motivos geométricos o distribución de poisson), y añadir o restar de la anterior (por eso he dicho que es HMM-igual, no HMM, las observaciones no son exactamente condicionalmente independientes).

Espero que ayude, saludos.

Answer 2

Dado que, según la dispersión es la principal razón de la distribución de Poisson no se ajusta a su uso, yo sugeriría que la distribución binomial negativa. Una vez que determine los parámetros que el rendimiento bruto de la forma que usted está buscando, debe ser sencillo para truncar la distribución del apoyo a $[1, max]$ mediante el establecimiento $P(X = x) = 0$ para todos los enteros fuera de $[1, max]$, y $$\frac{f(x)}{\sum_{k=1}^{max}f(k)}$$ where $f$ es el PMF de la binomial negativa.

Usted podría utilizar esta distribución, creo, para resolver su segundo trabajo: Escribir truncatedNegBinom(min, max, params) que devuelve un entero aleatorio a partir de una binomial negativa truncada de distribución como el de arriba. A continuación, escribir una segunda función, randomSequence(length), por ejemplo en Python:

def randomSequence(length, mode = "random"):
    seq = []
    for i in range(length):
        if mode == "random":
            seq.append(truncatedNegBinom(1, max, params))
        if mode == "increasing":
            seq.append(truncatedNegBinom(seq[-1] + 1, max, params))
        if mode == "decreasing":
            seq.append(truncatedNegBinom(1, seq[-1] - 1, params))
    return seq

También tendría que construir en algunas excepciones, ya que los de arriba se rompen cuando, por ejemplo, mode == 'increasing' y seq[-1] + 1 > max. Para más información sobre cómo ejemplo de una arbitraria distribución discreta, marque esta pregunta.