Overlapping Subsets

Step 1: Set up the distribution of $N$

We first need $P(N=k)$, the probability that $A$ and $B$ overlap in exactly $k$ elements.

To build such a pair $(A,B)$: choose which $k$ of the $20$ elements are the common ones: that's $\left(\genfrac{}{}{0ex}{}{20}{k}\right)$ ways. For the remaining $20-k$ elements, none of them may end up in both sets (otherwise the overlap would exceed $k$), so we need to count: in how many ways can the leftover elements be split between $A$ and $B$ so that no leftover element lands in both?

Step 2: A subproblem on mutually exclusive subsets

Define $N(n)=$ the number of ways to choose two subsets of an $n$-element set that share no elements (i.e. two mutually exclusive subsets, either of which may be empty). Two different lines of reasoning both nail this down.

First way: sum over the size of the first subset. Suppose the first subset takes $j$ of the $n$ elements ($j$ can range from $0$ to $n$); there are $\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ ways to pick which. The second subset must then live entirely inside the remaining $n-j$ elements, and can be any subset of those: $2^{n-j}$ choices. So

$$N(n)=\sum _{j=0}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)2^{n-j}$$

Recognize this as the binomial theorem $(x+y{)}^n={\sum }_j(\genfrac{}{}{0ex}{}{n}{j})x^{n-j}{y}^j$ with $x=2$, $y=1$:

$$N(n)=\sum _{j=0}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)2^{n-j}{1}^j=(2+1{)}^n=3^n$$

Second way: go element by element. Instead of thinking in terms of subset sizes, just decide the fate of each of the $n$ elements independently: it can go into the first subset, into the second subset, or into neither (a subset doesn't need to contain every element). That's $3$ choices per element, and $n$ independent elements, so directly

$$N(n)=3^n$$

Both routes agree, reassuringly, since they're counting the exact same thing.

Step 3: The distribution of $N$

Plugging $n=20-k$ (the leftover elements) into Step 2, and combining with the $\left(\genfrac{}{}{0ex}{}{20}{k}\right)$ choice of which elements are shared from Step 1:

$$\text{Numerator (favorable pairs with exactly }k\text{ common elements)}=\left(\genfrac{}{}{0ex}{}{20}{k}\right)3^{20-k}$$

The denominator is the total number of ways to pick $(A,B)$ with no restriction: each of $A$, $B$ independently has $2^{20}$ possible values, so $2^{20}\cdot 2^{20}=4^{20}$ total pairs. Hence

$$P(N=k)=\frac{\left(\genfrac{}{}{0ex}{}{20}{k}\right)3^{20-k}}{4^{20}}$$

Sanity check. These probabilities should sum to $1$ over $k=0,\dots ,20$. By the binomial theorem again,

$$\sum _{k=0}^{20}\left(\genfrac{}{}{0ex}{}{20}{k}\right)3^{20-k}=(3+1{)}^{20}=4^{20}$$

so ${\sum }_{k}P(N=k)=4^{20}/4^{20}=1$. ✓

Step 4: Computing $E[N]$ via differentiation

Rather than quote a known formula, we can get $E[N]$ directly from the generating function that produced Step 3. Introduce a dummy variable $r$ and write

$$f(r)=\sum _{k=0}^{20}\left(\genfrac{}{}{0ex}{}{20}{k}\right)3^{20-k}{r}^k=(3+r{)}^{20}$$

(this is just the binomial theorem with $x=3$, $y=r$; setting $r=1$ recovers the numerator sum from Step 3). Differentiating with respect to $r$ pulls down a factor of $k$ from each term:

$$f^{\prime }(r)=\sum _{k=0}^{20}k\left(\genfrac{}{}{0ex}{}{20}{k}\right)3^{20-k}{r}^{k-1}=20(3+r{)}^{19}$$

Multiplying through by $r$ and setting $r=1$:

$$\sum _{k=0}^{20}k\left(\genfrac{}{}{0ex}{}{20}{k}\right)3^{20-k}=20\cdot 1\cdot (3+1{)}^{19}=20\cdot 4^{19}$$

so

$$E[N]=\frac{20\cdot 4^{19}}{4^{20}}=\frac{20}{4}=5$$

Step 5: Computing $E[N^2]$ the same way

Differentiate once more. Starting again from $f(r)=(3+r{)}^{20}$ and its first derivative $f^{\prime }(r)=20(3+r{)}^{19}$, differentiate a second time:

$$f^{\prime \prime }(r)=\sum _{k=0}^{20}k(k-1)\left(\genfrac{}{}{0ex}{}{20}{k}\right)3^{20-k}{r}^{k-2}=20\cdot 19(3+r{)}^{18}$$

Multiplying by $r^2$ and setting $r=1$:

$$\sum _{k=0}^{20}k(k-1)\left(\genfrac{}{}{0ex}{}{20}{k}\right)3^{20-k}=380\cdot 4^{18}$$

which gives $E[N(N-1)]=\frac{380\cdot 4^{18}}{4^{20}}=\frac{380}{16}=\frac{95}{4}$, and so

$$E[N^2]=E[N(N-1)]+E[N]=\frac{95}{4}+5=\frac{95}{4}+\frac{20}{4}=\frac{115}{4}$$

Step 6: Variance and the final ratio

$$\text{Var}(N)=E[N^2]-(E[N]{)}^2=\frac{115}{4}-25=\frac{115}{4}-\frac{100}{4}=\frac{15}{4}$$ $$\boxed{\frac{\text{Var}(N)}{E[N]}=\frac{15/4}{5}=\frac{15}{20}=\frac{3}{4}}$$

Alternate Way of Thinking?. Choosing a subset of $\Omega$ uniformly from its power set is the same as flipping a fair coin independently for each of the $20$ elements, to decide membership. So for element $i$, define the indicator

$$X_i=1[i\in A\cap B]=\{\begin{array}{ll}1& i\in A\text{ and }i\in B\\ 0& \text{otherwise}\end{array}$$

$i\in A$ and $i\in B$ are themselves independent fair coin flips, so

$$P(X_i=1)=P(i\in A)\cdot P(i\in B)=\frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}⟹X_i\sim \text{Bernoulli}\left(\frac{1}{4}\right)$$

and since membership is decided independently across elements too, $X_1,\dots ,X_{20}$ are i.i.d. Bernoulli$(\frac{1}{4})$. Now $N=|A\cap B|={\sum }_{i=1}^{20}{X}_i$ is literally a sum of $20$ i.i.d. Bernoulli$(\frac{1}{4})$ trials, which is exactly the definition of $N\sim \text{Binomial}(20,\frac{1}{4})$, with no need to have derived the $\left(\genfrac{}{}{0ex}{}{20}{k}\right)3^{20-k}/4^{20}$ formula at all.

From here $E[N]$ and $\text{Var}(N)$ follow from the single-trial moments, without touching a binomial coefficient. For a single Bernoulli$(p)$ trial, $E[X_i]=p$ and $\text{Var}(X_i)=E[X_i^2]-E[X_i{]}^2=p-p^2=p(1-p)$ (using $X_i^2=X_i$, since $X_i\in \{0,1\}$). Linearity of expectation, and additivity of variance across independent summands, then give

$$E[N]=\sum _{i=1}^{20}E[X_i]=20p,\text{Var}(N)=\sum _{i=1}^{20}\text{Var}(X_i)=20p(1-p)$$

so the ratio collapses immediately, with the $20$ (and even $p$ itself, partially) cancelling out:

$$\frac{\text{Var}(N)}{E[N]}=\frac{20p(1-p)}{20p}=1-p$$

With $p=\frac{1}{4}$, that's $1-\frac{1}{4}=\frac{3}{4}$, matching Step 6 exactly, but now visibly true for any ground set size (not just $20$), since $n$ never even appears in the final ratio. The long derivation above (via $P(N=k)$ and differentiating generating functions) rebuilds all of this from first principles; recognizing the Bernoulli/Binomial structure up front just lets you skip straight to the answer.

Thus, $\frac{\text{Var}(N)}{E[N]}=\frac{3}{4}$