$P$ and $Q$ are subsets of ${(a_1,a_2,a_3…a_n)}$ chosen at random. Find the probability that $Q$ is a subset of $P$.
I chose $r$ elements from the set for $P$, then $Q$. could have $0,1,2…(r-1)$ elements from those $r$. Thus total would be (ignoring edge case of $r=0$ and such for now) $$\sum {n \choose r}({r \choose 0}+{r \choose 1}…+{r \choose r})$$ $$\Rightarrow \sum{n \choose r}(2^r)$$
I am not sure how to solve this further
I also thought of another way, in which we select $r$ elements that are common first, and then decide if the rest are in $P$ or not in $P$. $$\sum{n \choose r}(2^{n-r})$$
But it gives a similar expression so I wasn't able to solve this either
Best Answer
Since you asked, here is an approach that uses a binomial series.
Take $A=\{a_1,\ldots,a_n\}$. Partition your sample space $2^A\times 2^A$ based on the size of $P$ to say $$\begin{eqnarray*}\mathbb{P}(Q\subseteq P) &=& \sum_{k=0}^{n}\mathbb{P}(Q\subseteq P,|P|=k) \\ &=& \sum_{k=0}^n\frac{\big|\big\{(P,Q)\in2^A \times 2^A: Q\subseteq P, |P|=k\big\}\big|}{\big|2^A \times 2^A\big|} \\ &=&\sum_{k=0}^n \frac{2^k{n \choose k}}{4^n} \\ &=&\frac{1}{4^n}\sum_{k=0}^n{n \choose k}2^k1^{n-k} \\ &=& \frac{1}{4^n}(1+2)^n \\ &=& (3/4)^n\end{eqnarray*}$$