¿Cuál es la probabilidad de que dos subconjuntos aleatorios de un superset no tengan intersección?

Question

Permite que $$ S={1,2,...,n} $$ Del conjunto de potencia, $ P(S) $, de $S$, dos subconjuntos $A$, $B$ son elegidos al azar. Si cada subconjunto tiene la misma probabilidad de ser elegido, entonces, la probabilidad de que los conjuntos $ A $ y $ B $ no tengan elementos en común es....

Aquí tienes algunos de mis intentos:

La probabilidad de que sean elegidos dos conjuntos particulares es $ 2^{-2n} $. Si del primer conjunto se elige $\phi$, no hay intersección garantizada, si un Singleton es elegido del primer conjunto entonces

1. si se elige $ \phi $ del segundo conjunto, entonces no hay intersección garantizada
2. si se elige algún conjunto con cardinalidad = 1 del segundo conjunto, entonces no hay intersección garantizada para todos los conjuntos $n$ excepto para 1 que es igual al primer conjunto.
3. si se elige algún conjunto con cardinalidad = 2 del segundo conjunto, entonces no hay intersección garantizada para todos los conjuntos $^{n}C _2 $ excepto para $n-1$ que contiene el singleton del primer conjunto.
4. si se elige algún conjunto con cardinalidad = 3 del segundo conjunto, entonces no hay intersección garantizada para todos los conjuntos $^ {n}C _2 $ excepto para???? No puedo pensar más. No puedo encontrar un término general para la cardinalidad $n$.

Hasta ahora, he encontrado.

$ P(A\bigcap B = \phi) = 2^{-2n} [^{n}C_0 * 1 + ^{n}C_1(^{n}C_0 * 1 + ^{n}C_1 -1 + ^{n}C_2 -(n-1) ..... ) + ^{n}C_2(....) .......^{n}C_n(....) ] $

He intentado encontrar el complemento de la pregunta (encontrando la probabilidad de que tengan al menos algo en común)

He intentado usar la ley de De Morgan, $ P(A\bigcap B = \phi) = P((A^c \bigcup B^c)^c) = \phi) $ pero no puedo resolverlo.

Creé un programa en python para encontrar la probabilidad sin embargo la computadora no puede calcular probabilidades para $n >= 25$ y el resultado no parece haber convergido. En $ n = 25 $, la probabilidad es alrededor de $0.001$.

He mirado otras preguntas similares sin embargo no tratan con subconjuntos de un superset sino con algún simple subconjunto de simples conjuntos.

La probabilidad de que dos subconjuntos seleccionados al azar del conjunto $\{1 , 2, 3, 4 , 5\}$ tengan exactamente dos elementos en su intersección , es

Answer 1

Construye los conjuntos $A$ y $B$ siguiendo este procedimiento: para cada elemento de $S$, lanza una moneda justa para decidir si es un miembro de $A$, y lanza de nuevo para decidir, de manera independiente, si es miembro de $B$. La probabilidad de que el elemento en cuestión no esté en $A\cap B$ es $3/4$, y la probabilidad de que ninguno de los $n$ elementos de $S$ estén en $A\cap B$ es entonces $(3/4)^n$.

Answer 2

El número de pares es $2^{2n}$, y para el número de pares $(A,B): A \cap B=\emptyset $, simplemente notamos que, para obtener dicho par $(A,B)$, es lo mismo que construir una relación de $S$ a $\{ x,y,z\}$ (relacionando elementos de $A$ con $x$, elementos de $B$ con $y$, elementos del complemento con $z$). Así que $3^{n}$ en total.

Answer 3

Elige un subconjunto $S_1 \subset S$, y supongamos que $\#S_1 = m$ es el número de elementos en $S_1$. Hay $n - m$ elementos en $S\setminus S_1$, por lo tanto la probabilidad de elegir un subconjunto de $S_2 \subset S$ disjunto a $S_1$ es $$P(S_1 \cap S_2 = \emptyset | \#S_1 = m) = \frac{2^{n-m}}{2^n} = \frac{1}{2^{m}}.$$ Sumando sobre todos los subconjuntos de $S$ de $m$ elementos tenemos $$P(S_1 \cap S_2 = \emptyset) = \frac{1}{2^n}\sum_{m=0}^n\left(\frac{1}{2}\right)^m\binom{n}{m} = \left(\frac{3}{4}\right)^n,$$ la igualdad final por el teorema binomial.

EDITAR: También depende de si "el orden importa". Como señalaron otros comentaristas, hay $3^n$ tuplas de subconjuntos disjuntos. Sin embargo, el orden importa en estas tuplas, es decir, si $A\cap B = \emptyset$ entonces el par de subconjuntos disjuntos $(A,B)$ y $(B,A)$ se consideran formas distintas de elegir los subconjuntos. Esto puede no ser un comportamiento deseable. En ese caso, claramente la solución $(\emptyset, \emptyset)$ está permitida, por lo tanto hay $3^n - 1$ tuplas disjuntas donde contamos dos veces; dividiendo a la mitad ese número y añadiendo de nuevo la solución $(\emptyset, \emptyset)$ obtenemos $$\frac{3^n-1}{2}+1 = \frac{3^n+1}{2}$$ tuplas de subconjuntos disjuntos de $S$ donde el orden no importa. Hay $$2^n + \binom{2^n}{2} = 2^{2n-1} + 2^{n-1}$$ tuplas de la forma $\{(a,a) : a\in 2^S\} \cup \{\{a,b\} : a,b\in 2^S\}$, ya que si elegimos dos subconjuntos de $S$ al azar podemos elegir el mismo subconjunto dos veces o dos subconjuntos distintos. Entonces, en esta interpretación la probabilidad es $$\frac{3^n+1}{4^n +2^n}.$$