Probability of having a good set by choosing independently from Universe

403 Views Asked by At

Let $S$, $T$ be two disjoint subsets of a universe $U$ such that $|S| = |T| = n$. Suppose we select a random subset $R\subseteq U$ by independently sampling each element of $U$ with probability $p$; that means, for each element $i$ of $U$ independently we include $i$ in $R$ with probability $p$. We say that the random subset $R$ is good if the following two conditions hold: $R\cap S = \emptyset$ and $R\cap T = \emptyset$. Show that for $p=1/n$, the probability that $R$ is good is larger than some positive constant.

1

There are 1 best solutions below

2
On

It does not matter what's the sampling result is for elements not in $S$ and $T$. and for each element in $S$ or $T$, the probability of not being chosen is $1-p$ (independently). Thus the overall probability of non overlapping is $(1-p)^{2n}$.

The series $(1-1/n)^{2n}$ converges to $e^{-2}$. So there must be a lower bound of the series, and obviously that lower bound is also positive.