Probability a Random Subset Is Contained in Another
Two subsets $A$ and $B$ are chosen independently and uniformly at random from all subsets of a set $X$ with $|X| = 5$.
What is the probability that $A \subseteq B$?
Generalize to $|X| = n$.
Hints
- Instead of counting subsets globally, think about what happens at each element independently. What are the possible membership patterns for a single element?
- For each element $x$, there are 4 equally likely patterns of $(x \in A?, x \in B?)$. How many of these are compatible with $A \subseteq B$?
- Each element independently has a $3/4$ chance of satisfying the constraint. Since elements are independent, multiply across all $n$ elements.
Worked Solution
How to Think About It: The trick is to think element by element. For each element $x \in X$, there are four equally likely possibilities for whether $x$ is in $A$ and whether $x$ is in $B$. The constraint $A \subseteq B$ means "if $x \in A$ then $x \in B$" -- i.e., the case $(x \in A, x \notin B)$ is forbidden. So 3 out of 4 possibilities are valid for each element, and since the elements are independent, you just raise $3/4$ to the power $n$.
Quick Estimate: For $n = 5$: $(3/4)^5 = 243/1024 \approx 0.237$. This makes sense -- it is a bit less than $1/4$, which is reasonable since requiring one random set to contain another is a fairly strong condition but not extreme.
Approach: Use element-wise independence to decompose the joint event.
Formal Solution:
The total number of ordered pairs $(A, B)$ of subsets of $X$ is $2^n \times 2^n = 4^n$, since each subset is chosen independently.
For $A \subseteq B$ to hold, we need: for every $x \in X$, if $x \in A$ then $x \in B$.
Consider any single element $x$. Independently, $x$ is in $A$ with probability $1/2$ and in $B$ with probability $1/2$. The four equally likely membership patterns are:
| $x \in A?$ | $x \in B?$ | Valid for $A \subseteq B$? | |---|---|---| | No | No | Yes | | No | Yes | Yes | | Yes | No | No | | Yes | Yes | Yes |
So for each element, the probability of a valid pattern is $3/4$.
Since the membership decisions for different elements are independent (both $A$ and $B$ are chosen uniformly), the events across elements are independent. Therefore:
$$P(A \subseteq B) = \left(\frac{3}{4}\right)^n$$
For $n = 5$: $$P(A \subseteq B) = \left(\frac{3}{4}\right)^5 = \frac{3^5}{4^5} = \frac{243}{1024}$$
Answer: $P(A \subseteq B) = (3/4)^n$. For $n = 5$, this equals $243/1024 \approx 0.237$.
Intuition
The element-wise decomposition trick is one of the most useful techniques in combinatorial probability. Whenever you have a condition on sets or sequences, ask: can I check the condition one coordinate at a time? If the coordinates are independent, the joint probability is just the product. This transforms a complicated counting problem into a simple per-element calculation.
This pattern shows up in many quant interview classics -- random graph properties, coupon collector variants, and digital option pricing on baskets of independent assets. The deeper lesson is that "uniform random subset" is the same as "each element included independently with probability $1/2$," and this Bernoulli-per-element view is almost always the right way to reason about random subsets.