Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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

share|cite|improve this question

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

share|cite|improve this answer
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. – shay May 28 '11 at 16:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.