Límite superior de la probabilidad de no elegir determinados subconjuntos

Question

Dado $m \geq 2$ subconjuntos de $\{1,...,n\}$ , digamos $A_1,...,A_m$ de tamaño $r$ elegimos $B \subset \{1,...,n\}$ tal que para cualquier $i \in [n]$ , $\displaystyle Pr\left[i \in B\right] = m^{-\frac{1}{r+1}}$ independientemente de las demás opciones. Quiero demostrar que existe una constante $\gamma_r$ (dependiente únicamente de $r$ ) tal que

$$Pr\left[A_1\not\subseteq B \wedge ... \wedge A_m \not\subseteq B\right] \leq \gamma_r \left(1-m^{-\frac{r}{r+1}}\right)^m$$

Parece que aquí debería usarse la desigualdad de Janson, sin embargo no consigo que me dé una constante que dependa sólo de r. Agradecería cualquier idea, y si esto es correcto.

Gracias.

Edito: Había escrito por error que utilizaba la desigualdad de Azuma, sin embargo me refería a la de Janson.

Answer 1

Usted parece preguntar por la probabilidad del evento $C=[A\not\subseteq B]$ donde $A$ es la unión de $m$ conjuntos dados $A_k$ y $B$ es aleatorio. Es la unión de los sucesos $[i\notin B]$ para cada $i\in A$ . Son independientes y $P(i\in B)=p$ no depende de $i$ de ahí $P(C)=1-p^a$ donde $a$ es el tamaño de $A$ .

En tu contexto, $p=m^{-1/(r+1)}$ y, a menos que falte alguna hipótesis, $a$ puede ser cualquier cosa entre $r$ et $rm$ por lo que es el único límite superior disponible para cada familia $(A_k)$ como en tu post es $$P(C)\le1-m^{-mr/(r+1)}.$$ En $m\to\infty$ el lado derecho converge a $1$ y el lado derecho de la desigualdad a demostrar converge a $0$ por lo que la primera no puede estar limitada por la segunda, para cualquier valor de $\gamma_r$ .

O tal vez usted está preguntando por la probabilidad de que, para cada $k$ , $A_k\not\subseteq B$ ...