distribución de probabilidad de la cobertura de un conjunto tras $X$ miembros del conjunto seleccionados aleatoriamente de forma independiente

Question

Tengo un conjunto de números en el que estoy seleccionando de forma aleatoria e independiente elementos dentro de un conjunto . Después de un número de estas selecciones aleatorias de elementos quiero saber la cobertura de los elementos del conjunto. La cobertura es el número de elementos del conjunto que se han seleccionado al menos una vez dividido por el número total de elementos del conjunto.

Dicho de otro modo: ¿cuál es la distribución de probabilidad de los distintos valores de cobertura de un conjunto tras $X$ ¿elementos del conjunto seleccionados de forma aleatoria e independiente?

Answer 1

Si hay $n$ elementos del conjunto entonces la probabilidad de que $M=m$ se han seleccionado tras una muestra de $x$ (con sustitución) es

$$\frac{S_2(x,m) \; n!}{n^x \; (n-m)!} $$

donde $S_2(x,m)$ es un Número de Stirling del segundo tipo .

El valor esperado de $M$ es: $n \left(1- \left(1-\dfrac{1}{n}\right)^x \right)$ .

La varianza es: $n\left(1-\dfrac{1}{n}\right)^x + n^2 \left(1-\dfrac{1}{n}\right)\left(1-\dfrac{2}{n}\right)^x - n^2\left(1-\dfrac{1}{n}\right)^{2x}. $

Answer 2

La proporción prevista de elementos cubiertos, $E\left(\frac{m}{n}\right)$ , tiene una forma límite simple como $n \rightarrow \infty$ con la frecuencia de muestreo $ r / n $ fijo. Tenga en cuenta que $\lim_{n \rightarrow \infty} \left(1-\frac{1}{n}\right)^n = e^{-1}$ y reescribir:

$$\lim_{n \rightarrow \infty} E\left(\frac{m}{n}\right) = 1 - e^{-\frac{r}{n}}$$

de modo que, por ejemplo, el muestreo $r=n$ veces se espera cubrir alrededor del 63% del conjunto. Se trata de una aproximación razonable incluso para $n > 100$ .

Answer 3

Derivación de $\operatorname E [M]$ con un uso clásico de variables indicadoras y expectativas totales:

Tomamos una muestra del conjunto $X = \{1, \dots, n \}$ . Sea $X_i$ sea $1$ si es miembro $i$ está en nuestra muestra, $0$ de lo contrario.

Para una muestra de tamaño $x$ la probabilidad de que ninguno de los valores sea $i$ es $\left(\frac{n-1}{n}\right)^x$ . Por lo tanto, la probabilidad de que la muestra incluya $i$ y, por lo tanto $X_i = 1$ es $1-\left(\frac{n-1}{n}\right)^x$ .

Tenemos $$\operatorname E[M] = \operatorname E[X_1 + \dots + X_n] = \operatorname E[X_1] + \dots + \operatorname E[X_n] = n \left(1-\left(\frac{n-1}{n}\right)^x\right)$$

La varianza se calcula de forma similar, pero tenemos que considerar por separado $\operatorname E[X_i^2] $ y $\operatorname E[X_i X_j]$ para $ i \ne j$ .

Answer 4

Puede construir una relación de recurrencia para construir la distribución de probabilidad utilizando programación dinámica.

Definimos la recurrencia p(m, x) como la probabilidad de seleccionar m elementos únicos después de x selecciones de un conjunto de tamaño n.

Después de 0 selecciones, debemos haber seleccionado exactamente 0 elementos únicos.

p(m=0, x=0) = 1
p(m!=0, x=0) = 0

Digamos que la selección x da como resultado m elementos únicos seleccionados. Entonces, o bien esta última selección ya había sido elegida previamente (con probabilidad m/n del estado (m, x-1)), o bien esta selección añade un nuevo m-ésimo valor único (con probabilidad 1 - (m-1)/n) del estado (m-1, x-1)).

Así que fijamos la recurrencia en:

p(m,x) = p(m-1, x-1) * (1 - (m-1)/n) + p(m, x-1) * (m/n)