Intersección de subconjuntos al azar

Question

Considere la posibilidad de $n$ obtenidas independientemente $q$-subconjuntos $e_1,...,e_n$ a partir de un conjunto finito $P$. ¿Cuál es la probabilidad de que la intersección de la $n$ subconjuntos no vacíos, en términos de $n$, $q$, y $|P|$?

$$\mathbb{P}\left[\bigcap_{i=1}^n e_i \neq \emptyset \right] = \,\,?$$

EDIT: se me pidió dar mi opinión sobre el problema. Se trata de un poco de investigación que estoy haciendo en el borde el color de los gráficos sin bichromatic ciclos. No estoy seguro de cómo atacar este tipo de problema. Yo debería haber mencionado: no estoy necesariamente en busca de una respuesta. Cualquier idea o sugerencias sobre cómo proceder sería bienvenido.

Answer 1

El crédito va a Studentmath y Ted Shifrin para discutir esto conmigo en el MSE de chat.

---

Uno de los más viables enfoques (aunque no exactamente elegante) es la aplicación de la inclusión-exclusión en el tamaño de la intersección $\displaystyle\bigcap_{i=1}^n e_i$.

Así podemos determinar la probabilidad de que la intersección contiene un cierto conjunto de tamaño $i$, dicen. Para ello, elegimos $i$ elementos y, a continuación, para cada una de las $q$-subconjunto, $q-i$ elementos para ir con ella. Este se obtiene: $$\binom p i \binom{p-i}{q-i}^n \binom{p}{q}^{-n}$$

Ahora, por supuesto, tenemos que hacer los familiares de corrección de la doble contabilización, produciendo los siguientes criterios de inclusión-exclusión suma: $$\sum_{i=1}^q (-1)^{i+1} \binom p i \binom{p-i}{q-i}^n \binom{p}{q}^{-n}$$

---

Actualización: Cuando hay un deseo para calcular varios valores, o para conocer la distribución exacta sobre los diferentes intersección tamaños, los siguientes recursiva enfoque puede ser útil:

Deje $N(k, i)$ denotar el número de maneras $k$ $q$-los subconjuntos pueden tener una intersección con $i$ elementos. Entonces podemos derivar $N(k, i)$ de la $N(k-1, *)$ como sigue:

$$\begin{align*} N(k,i) &= \frac 1n \sum_{j=i}^q N(k-1,j) \binom j i \binom{p-j}{q-i} \\ N(1,i) &= \begin{cases} 0 & :i \ne q \\ \binom p q & :i = q \end{casos} \end{align*}$$

donde el $\frac 1n$ corrige para el que lo ordene la secuencia de adición de los $q$-subconjuntos a nuestra consideración.