Probability of two sets being contained in a set $S$.

Question

I'm working on the following problem, and I'm afraid there is something fundamental I am not understanding.

Let $s_1,\dots,s_m$ be independent random elements in $[n]$ not necessarily uniform or identically distributed; chosen with replacement, and let $S = \{s_1,\dots,s_m\}$. Let $I$ and $J$ be disjoint subsets of $[n]$. Prove that $$ P((I\cup J)\subseteq S) \leq P(I\subseteq S)P(J\subseteq S).$$

The event $I\cup J \subseteq S$ is the event that $I\subseteq S$ and $J\subseteq S$. But since $I$ and $J$ are disjoint, aren't these two events independent? If they are independent, doesn't that give us that $$ P((I\cup J)\subseteq S) = P(I\subseteq S)P(J\subseteq S)$$ holds?

How can I proceed with this problem? Thanks!

Answer 1

To see the error, consider the case where $n = 100$, $m = 10$, and $|I| = |J| = 10$. If $I \ \subset S$, what does this tell you about $J \subset S$? (The fact that it tells you anything is important.)

A hint for how to proceed: consider a conditional probability approach. Specifically: since $\mathbb P(A \cap B) = \mathbb P(A) \cdot \mathbb P(B \mid A)$, we could say $$\mathbb P((I \cup J) \subset S) = \mathbb P(I \subset S) \cdot \mathbb P(J \subset S \mid I \subset S).$$

Can you take it from here?

Answer 2

We have $$ \mathbb{P}(I\cup J \subset S)=\mathbb{P}(I\subset S \wedge J\subset S) = \mathbb{P}(I\subset S | J\subset S) \mathbb{P} (J\subset S).$$ Now, if $J\subset S$, then at least $|J|$ of $m$ elements chosen were selected in $J$, and as $I$ and $J$ are disjoint there are then at most $m-|J|$ candidates to be selected from $I$. So $\mathbb{P}(I\subset S | J\subset S) \leq \mathbb{P}(I\subset S)$.