I'm trying to understand this simpler problem so I can apply the process to a more difficult homework problem.
Let $U$ be a set with $n$ elements. Select $2$ independent random subsets $A_1, A_2 \subset U.$ Both $A_i$ are chosen so that all $2^n$ choices are equally likely. I would like to compute the probability that $A_1, A_2$ are disjoint.
I am looking for a calculation based on counting. I have no idea how to compute this, and I would appreciate any help given.
Best Answer
Take an element $i$. Let $p_i$ denote the probability that $i$ is not in the intersection of your two randomly chosen sets. It is in exactly $2^{n-1}$ subsets, hence the probability that it is in a randomly chosen subset is $\frac 12$. It follows that the probability that it is in both of two randomly chosen subsets is $\frac 14$. Therefore $p_i =\frac 34$.
Now, knowing that $i$ is in a subset tells you nothing about whether or not $j$ is (for $j≠i$) Hence we have independence of the probabilities $p_i$ and $p_j$. It follows that the probability that the sets are disjoint is $\left(\frac 34\right)^n$.