One random subset inside another

MediumProbability Combinatorics~5m

Let $X$ be a set with $5$ elements. Choose two subsets $A$ and $B$ independently and uniformly at random from all subsets of $X$ . What is the probability that $A \subseteq B$ ? Write it as a fraction $\tfrac{p}{q}$ in lowest terms and report $p + q$ .

Show hints (2)+

A uniform random subset decides each element independently with probability $1/2$ . Consider one element's four $(A,B)$ patterns.
Containment fails for an element only when it's in $A$ but not $B$ (prob $1/4$ ). Combine across the $5$ independent elements.

Answer

Reveal answer →

1267

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Hedge Fund Quant

One random subset inside another

Answer

Related questions