Let , be two disjoint subsets of a universe such that ||=||=. Suppose we select a random subset ⊆ by independently sampling each element of with probability ; that means, for each element of independently we include in with probability . We say that the random subset is good if the following two conditions hold: ∩=∅ and ∩ has at least one element. Show that for =1/, the probability that is good is larger than some positive constant.
How would we do this? How to show it has a positive lower bound?
HINTS: Since you're looking for a lower bound, you might focus on the worst-case scenarios.
At a minimum, you need:
You can find the probabilities of each of these things occurring, and you can multiply them together since they're independent. I claim that the resulting expressions are related to a famous calculus limit, which is how you can get the more difficult of the two bounds.
Can you take it from here?