Uniformemente Al Azar Tuplas

Question

Considere la posibilidad de un conjunto múltiple de números naturales. Como un ejemplo

$$ M = \{1, 2, 2, 3, 3, 3\} $$

Si tratamos de copias de la misma cantidad que indistinguibles, hay 8 diferentes 2-tuplas podemos formar a partir de este, al no utilizar ningún número más a menudo de lo que parece en $M$:

$$ \{ (1,2), (2,1), (1,3), (3,1), (2,3), (3,2), (2,2), (3,3) \} $$

Hay un algoritmo que genera una de estas tuplas con el uniforme de probabilidad, sin tener que generar todas las tuplas de frente y seleccionar uno al azar? Tenga en cuenta que la uniformidad es en referencia a la lista de tuplas, por lo $(3,3)$ debe aparecer con la misma probabilidad en $(2,2)$ o $(1,2)$, respectivamente.

El algoritmo debe trabajar para arbitrario no vacía $M$$n \leq |M|$, donde el objetivo es generar $n$-tuplas.

Idealmente, estoy en busca de un algoritmo que no se basa en el rechazo, pero si eso no es posible, también me gustaría estar interesado en cómo puedo minimizar el número de rechazos para generar las tuplas de manera eficiente.

Si en casos especiales (es decir, pequeños, fijos $n$) rendimiento de los buenos algoritmos, yo todavía estaría interesado en eso, incluso si no generalizar a mayor $n$.

Answer 1

Esta es una variante de leonbloy la respuesta con la misma idea básica: calcular el número de tuplas que comienzan con un elemento dado, y el uso de esos números son los pesos en una elección al azar. Si $n$ es pequeña en comparación a $|M|$, este método es asintóticamente mucho más rápido. Sin embargo, es no más rápido que simplemente generar todas las posibles tuplas y elegir de manera uniforme a partir de ellos.

Deje $C_i$ ser el número de elementos distintos que han multiplicidad $i$$M$, y denotan $c_i = |C_i|$. Podemos suponer que la $c_i = 0$$i > n$. Denotar por $N^n_i(c_1, c_2, \ldots, c_n)$ el número de los distintos $n$-tuplas extraídas de $M$ cuya primera entrada es un elemento de $C_i$ (este número depende solo de los $n$, $i$, y el $c_j$). A continuación, tenemos la fórmula de recursión

$$ N^n_i(c_1, c_2, \ldots, c_n) = \left\{ \begin{array}{ll} 0, & \mbox{if } c_i = 0 \\ 1, & \mbox{if } n = 0 \\ c_i \sum_{j=1}^n N^{n-1}_j (d_1, \ldots, d_n) & \mbox{otherwise} \end{array} \right. $$

donde $d_{i-1} = c_{i-1} + 1$ (si $i>1$), $d_i = c_i - 1$, y $d_j = c_j$ para todos los otros $j$. Los dos primeros casos son auto-explicativos, y el último caso tiene porque podemos elegir un elemento de $C_i$, lo que le da el multiplicador $c_i$, y para la segunda ranura de la tupla, podemos elegir un elemento de una de las $j$ actualizado multiplicidad de clases, donde $C_i$ ha perdido uno de los elementos y $C_{i-1}$ ganado uno.

Después del cálculo, se utiliza $c_i^{-1} N^n_i(c_1, c_2, \ldots, c_n)$ el peso de los elementos de $C_i$, elegir al azar un elemento de $M$, y repita el proceso para la siguiente ranura.

Como @leonbloy sugiere, las tuplas deben ser almacenados para su rendimiento. El número de tuplas para mantener en la memoria, y el momento en que la complejidad del algoritmo, es en la mayoría de las $\sum_{\ell = 1}^n (\max \{ c_i : i = 1, \ldots, n \})^\ell$, $O(|M|^n)$ si $n$ es fijo. En @leonbloy del algoritmo, este número parece ser de la orden de $n^k$ donde $k$ es el número de elementos distintos en $M$. Si $n$ está cerca de a $|M|$ y/o $k$ es pequeña en comparación a $|M|$, @leonbloy la solución es probablemente más rápido. Tenga en cuenta que $n \leq |M|$ mantiene en todos trivial de los casos.

Answer 2

Deje que los elementos de la $k-$tamaño del alfabeto ser indexados por $i=0,1 \cdots k-1$. Deje $n$ ser la tupla de longitud, y dejar que el vector ${\bf a}=(a_0,a_1,\cdots , a_{k-1})$ ($a_i\ge 0$) indicar el número de elementos.

En el ejemplo: $n=2$, $k=3$, ${\bf a}=(1,2,3)$.

Deje $N({\bf a},n)$ contar el número total de tuplas sujeto a la restricción.

A continuación, un algoritmo puede ser: para cada una de las $t=0 \cdots n-1$, para cada una de las $i=0 \cdots k-1$ calcular $w_i = N({\bf a}^{[i]},n-t-1)$ donde ${\bf a}^{[i]}$ es igual a${\bf a}$, excepto para el $i-$th elemento, que se redujo por uno. A continuación, calcular un entero aleatorio $s$ $[0 \cdots k-1]$ con probabilidades proporcionales a los pesos $w_i$, asignarlo a la tupla $X_t:=s$ y actualización de ${\bf a}:= {\bf a}^{[s]}$

Para calcular los $N({\bf a},n)$ podemos utilizar la recursividad:

$$N({\bf a},n)=\sum_{i=0 }^{k-1 }N({\bf a}^{[i]},n-1) $$

con $N({\bf a},0)=1$, e $N({\bf a},n)=0$ si ${\bf a}_i <0$ algunos $i$.

Si nos preocupa el rendimiento, y si se va a generar muchas tuplas, debemos precompute o almacenar en caché los resultados de la anterior.

Ejemplo de código Java (no optimizado) en Ideone

Answer 3

Aquí, creo, es una forma de:

1. Construcción de la probabilidad de generación de función para ordenó $n$-tuplas de $M'$ (el conjunto de los distintos elementos de $M$ mencionado por @AndreiRykhalski) con reemplazo (es decir, sin restricciones en el número de apariciones de cualquier elemento). Los coeficientes son los $n^\text{th}$ lista de $|M|$-nomial coeficientes, pero las condiciones son necesarios para el siguiente paso.
2. Eliminar cualquier imposible términos, es decir, con las variables planteadas a los poderes más grandes que su cuenta en $M$. Concesión: Esto puede ser muy incómodo. Dependiendo de la aplicación, esto puede ser hecho en el paso 1, por lo que al final no calcular enorme funciones de generación. (Lo siento, esto implica el rechazo.)
3. La muestra del resto de los términos, ponderados en función de sus coeficientes.
4. De la muestra de manera uniforme desde el conjunto múltiple de permutaciones codificada por el plazo seleccionado.

En tu ejemplo, $M$ contiene 3 elementos distintos, por lo que la generación de la función de tuplas ordenadas de estos elementos tiene un trinomio coeficientes (paso 1): $$(x+y+z)^2=x^2+2xy+2xz+y^2+2yz+z^2$$ The term $x^2$ corresponds to the impossible pair $(1,1)$, so delete it (step 2). The remaining pairs have total weight 8, so sample an integer between 1 and 8 (step 3). I get 8, so i pick the term $z^2$, which corresponds to $(3,3)$. Had i instead gotten 3, i would pick the term $2xz$ and have to choose between $(1,3)$ and $(3,1)$ (paso 4).

Yo no soy un experimentado programador, así que no puedo hablar con la escalabilidad de la solución.