La probabilidad de tener $k$ elementos similares en dos subconjuntos.

Question

Dado un conjunto distinto de los elementos de X y dos seleccionados al azar subconjuntos de ella $X_1,X_2$ (seleccionado con la igualdad de la distribución), me gustaría encontrar la probabilidad de que $|X_1 \cap X_2|\ge m$ donde $$0 \le m \le \min{\left(|X_1|,|X_2|\right)}$$ Ha sido un largo tiempo desde que he abordado cualquier probabilidad relacionados con el problema de matemáticas y estoy seguro de cómo acercarse a esta. Como tengo entendido que el número de combinaciones donde $|X_1 \cap X_2|=0$ es $$\dbinom{|X|}{|X_1|}\cdot \dbinom{|X|-|X_1|}{|X_2|}$$ y el número de combinaciones donde $|X_1 \cap X_2|=1$ es
$$\binom{|X|}{|X_1|}\cdot\binom{|X_1|}{1}\cdot \binom{|X|-|X_1|}{|X_2|-1}$$ Para que yo pueda tratar de resumir todas las combinaciones y dividirlos por $$\binom{|X|}{|X_1|}\cdot\binom{|X|}{|X_2|}$$ Es este enfoque correcto? Hay uno mejor?

Yo uso esto con el fin de encontrar relaciones entre las palabras en un texto de gran tamaño del corpus, por lo que prefiero evitar cálculos innecesarios.

Gracias

Answer 1

El enfoque es correcto, pero no es necesario para resumir todas las combinaciones, sólo $|X_1 \cap X_2| = m$ y los de después, todo el camino hasta la $|X_1 \cap X_2| = min\{|X_1|, |X_2|\}$.

Por ejemplo, el número de combinaciones donde $|X_1 \cap X_2| = m$ es $$ \binom{|X|}{|X_1|} \binom{|X_1|}{m} \binom{|X|-|X_1|}{|X_2|-m} $$

Por lo tanto la resultante de la probabilidad debe ser $$ \frac{\sum_{i = m}^{min\{|X_1|, |X_2|\}}\binom{|X|}{|X_1|} \binom{|X_1|}{i} \binom{|X|-|X_1|}{|X_2|-i}}{\binom{|X|}{|X_1|} \binom{|X|}{|X_2|}} $$

Answer 2

Si usted tiene un conjunto con $n$ elementos y se cruzan dos al azar seleccionado subconjuntos, la probabilidad de que la intersección se han exactamente $k$ elementos es: $4^{-n} 3^{n-k} \binom{n}{k}$ ( $4^{-n}$ es porque hay $4^n$ maneras de elegir un par de subconjuntos de a $n$ los elementos).

Yo no podía probar esto, pero estoy bastante seguro de que es verdad y que Sólo estoy siendo perezoso. Tal vez alguien más podría proporcionar una prueba?

Si usted acepta la fórmula anterior, la media para un valor dado de a $n$ es $\frac{n}{4}$, la varianza es $\frac{3 n}{16}$, y el estándar la desviación es lo $\frac{\sqrt{3 n}}{4}$

Para grandes valores de $n$, la distribución es esencialmente normal con los parámetros anteriormente mencionados.