Generar aleatoriamente un conjunto ordenado con una distribución uniforme

Question

Tengo un conjunto ordenado $S = \langle S_1, S_2, .., S_M \rangle$ a partir de la cual quiero sacar una muestra de $N$ elementos de tal manera que la muestra no es estrictamente totalmente ordenado (como con $\leq$ y de los enteros), y todas las posibilidades de ocurrir con igual probabilidad. La muestra debe ser tomada con la repetición.

Por ejemplo, vamos a decir $S = \langle 1, 2, 3, 4 \rangle$ e $N=3$, las muestras: $[1, 1, 1]$, $[1,2,3]$, $[2,3,3]$ sería válido, pero los $[3,2,1]$ o $[2,1,1]$ no sería válida.

Una forma sencilla para generar este conjunto sería simplemente al azar de la muestra de $S$, y, a continuación, ordenar la secuencia resultante. Sin embargo, por favor tenga en cuenta que el siguiente enfoque es parcial ($[1,1,1]$ es menos probable que ocurra de $[1,2,3]$, por ejemplo).

Esta pregunta está relacionada con una de las respuestas dadas en este StackOverflow pregunta:https://stackoverflow.com/questions/26467434/generating-random-number-in-sorted-order. Tenga en cuenta que el algoritmo propuesto no es para generar una muestra sin repetición, mientras que yo quiero que mi ejemplo a ser generado con la repetición.

Answer 1

Es suficiente para recoger $N$ elementos aleatorios de $\{ 1, 2, \ldots, M+N-1 \}$ sin reemplazo y, a continuación, hacer un postprocesamiento. Decir que usted escoja $T_1 < T_2 < \ldots < T_N$; a continuación, vamos a $S_K = T_K - K + 1$. Por ejemplo, con $M = 4, N = 3$, esto es como recoger $3$ elementos aleatorios de $\{1 ,2 , \ldots, 6\}$. Así, por ejemplo, usted puede recoger $T = \langle 1, 4, 5 \rangle$ y, a continuación, $S = \langle 1 - 1 + 1, 4 - 2 + 1, 5 - 3 + 1 \rangle = \langle 1, 3, 3 \rangle$.

Por lo que necesita un algoritmo para la selección aleatoria de los subconjuntos de un tamaño dado.

Escoger un subconjunto aleatorio de tamaño $k$ del conjunto de $\{1, 2, \ldots, n\}$, hay un buen algoritmo recursivo. Este conjunto incluye $n$ con una probabilidad de $k/n$. Si se incluye a $n$, luego tome el conjunto a es un subconjunto de a$\{1, 2, \ldots, n-1\}$ de tamaño de $k-1$, $n$ contigua; si no se incluyen los $n$, el resto es un subconjunto de a$\{1, 2, \ldots, n-1 \}$ de tamaño de $k$. (Me enteré de este algoritmo a partir de finales de la década de Hierba Wilf notas del "East Side, West Side", disponible en línea en https://www.math.upenn.edu/~wilf/eastwest.pdf - consulte la página 16 para el código. Es en madera de Arce, pero debe ser razonablemente comprensible.)

Answer 2

Acabo de dibujar $3$ números al azar y sólo aceptan en orden ascendente, de esa manera usted tiene la igualdad de probabilidades (es decir, el rechazo del método como se discute)

De lo contrario,

Muestra los triples mediante monte carlo. I. e. contar cuántas combinaciones diferentes que son permisibles, y aceptar cada uno con la misma probabilidad de acuerdo a diferentes valores de a $U[0,1]$, es decir, proporcionar a $111$ el rango de $[0,1/n]$, $211$ es $[1/n, 2/n]$. Siempre y cuando tenga un poco sensible con el pedido en el conjunto de posibles secuencias que están en el negocio. Se puede utilizar para bucles para lograr esto.