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

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Jane Street, Citadel

One random subset inside another

Answer

Related questions