2
$\begingroup$

Given $m \geq 2$ subsets of $\{1,...,n\}$, say $A_1,...,A_m$, each of size $r$, we pick $B \subset \{1,...,n\}$ such that for any $i \in [n]$, $\displaystyle Pr\left[i \in B\right] = m^{-\frac{1}{r+1}}$, independently of the other choices. I want to show that there is a constant $\gamma_r$ (dependent only on $r$) such that

$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$

It seems that Janson's inequality should be used here, however I can't get that to give me a constant which depends only on r. I'd appreciate any idea, and if this is at all correct.

Thanks.

Edit: I had mistakenly written that I used Azuma's inequality, however I meant Janson's.

1 Answers 1

1

You seem to ask for the probability of the event $C=[A\not\subseteq B]$, where $A$ is the union of $m$ given sets $A_k$, and $B$ is random. This is the union of the events $[i\notin B]$ for every $i\in A$. These are independent and $P(i\in B)=p$ does not depend on $i$ hence $P(C)=1-p^a$ where $a$ is the size of $A$.

In your context, $p=m^{-1/(r+1)}$ and, unless some hypothesis is missing, $a$ can be anything between $r$ and $rm$, hence the only upper bound available for every family $(A_k)$ like in your post is $P(C)\le1-m^{-mr/(r+1)}.$ When $m\to\infty$, the RHS converges to $1$ and the RHS of the inequality to prove converges to $0$ hence the former cannot be bounded by the latter, for any value of $\gamma_r$.

Or maybe you are asking for the probability of the event that, for every $k$, $A_k\not\subseteq B$...

  • 0
    Didier: Sorry, indeed the way I wrote it was misleading. I'm looking to bound $Pr\left[A_1 \not\subseteq B \wedge A_2 \not\subseteq B \wedge ... \wedge A_m \not\subseteq B\right]$. I'll fix my post.2011-05-28