Probability and subsets

Question

I was working through this (Cambridge STEP 3 probability) question:

The set S is a set of all integers from $1$ to $n$. The set $T$ is the set of all distinct subsets of $S$, including the empty set $\emptyset$ and $S$ itself. Show that $T$ contains exactly $2^n$ sets.

The sets $A_1, A_2, ..., A_m$, which are not necessarily distinct, are chosen randomly and independently from T, and for each $k$ $(1 \le k \le m)$ the set $A_k$ is equally likely to be any of the sets in $T$.

(i) Write down the value of $P(1 \in A).$

(ii) By considering each integer separately, show that $P(A_1 \cap A_2= \emptyset )= \binom{3}{4}^n$. Find $P(A_1 \cap A_2 \cap A_3 = \emptyset)$ and $P(A_1 \cap A_2 ... \cap A_m = \emptyset)$.

(iii) Find $P(A_1 \subseteq A_2)$, $P(A_1 \subseteq A_2 \subseteq A_3)$ and $P(A_1 \subseteq A_2 \subseteq ... \subseteq A_m)$.

Having successfully worked through all but the last part (and the first probability of the last part), I'm confused at how to extend my method for 2 subsets to more than 2 subsets (although I did find the last 2 probabilities via a different method). I'm asking as I am curious as to how to extend it for more than 2 subsets, and am unable to think of how myself.

So consider all possible pairs $(A_1,A_2)$. $A_1$ and $A_2$ can each take one of $2^n$ values, and so there are $2^{2n}$ such pairs. Now, for $A_1$ to be a subset of $A_2$, it has to be one of the possible subsets of $A_2$ itself. Say $|A_2|=k$ for some $0 \le k \le n$. Then the total number of possibilities for $A_1$ is $$\sum_{k=0}^{n}{{n}\choose{k}}{2^k}=(1+2)^n=3^n$$ by the Binomial theorem. $$\therefore \mathbb{P}(A_1\subseteq{A_2})=\frac{3^n}{2^{2n}}=(\frac{3}{4})^n$$

I can't determine how to extend this approach to m subsets; any insight would be appreciated.

Answer 1

So, i am going to go over the comment that i did. In your approach you did the following: $$3^n=\sum _{k=0}^n\binom{n}{k}2^{k}=\sum _{k+(n-k)=n}\binom{n}{k}2^{n-k},$$ where the right hand side(notice that the limit is attached to the equation $k+(n-k)=n$) of the above chain means choose $k$ elements out of the $n$ for the set $A_1$ and choosing $A_2\setminus A_1$ in $2^{n-k}$ ways.

So let $n_1$ be the number of elements of $A_1,$ let $n_2$ be the number of elements in $A_2\setminus A_1$ and let $n_3$ be the number of elements in $a_3$ up to $n_{m-1}$, then we want to choose them so we go $$\displaystyle \sum _{n_1+n_2+\cdots +n_{m-1}+(n-(n_1+n_2+\cdots + n_{m-1}))=n}\binom{n}{n_1}\binom{n-n_1}{n_2}\binom{n-n_1-n_2}{n_3}\cdots \binom{n-(n_1+\cdots+n_{m-2})}{n_{m-1}}2^{n-(n_1+n_2+\cdots + n_{m-1})},$$ notice further that $\binom{a}{b}\binom{a-b}{c}=\frac{a!}{b!c!},$ and so the expression inside the sum can be put as $$\frac{n!}{n_1!\cdot n_2!\cdots (n-(n_1+\cdots +n_{m-1}))!}=\binom{n}{n_1,\cdots ,(n-(n_1+\cdots +n_{m-1}))},$$ the rhs is called the multinomial numbers. So, using the multinomial theorem, we get that your sum is $$(2+\underbrace{1+\cdots +1}_{m-1 \text{ times}})^n=(m+1)^n.$$

A more combinatorial way to see this is imagine you have a function $f:[n]=\{1,2,\cdots ,n\}\longrightarrow [m+1]=\{1,2,\cdots ,m+1\}$ such that $f(i)=j$ if $i\in A_j\setminus A_{j-1}$ where $A_0=\emptyset$ or $f(i)=m+1$ if there is no such $j.$ This is clearly a bijection in between chains of the form $A_1\subseteq A_2\subseteq \cdots \subseteq A_m$ and functions from $[n]$ to $[m+1].$ The later has cardinality $(m+1)^n.$

Answer 2

Another way to solve the first part of (iii) is to use the method suggested for (ii).

For every integer $i \in S$, there are 4 possibilities.

1. $i \notin A_1, i \notin A_2$,
2. $i \notin A_1, i \in A_2$,
3. $i \in A_1, i \notin A_2$,
4. $i \in A_1, i \in A_2$.

Because the $A_k$ take each subset with equal probability, those 4 alternatives each have probability $\frac14$ of occuring. Only case 3) is a contradiction to $A_1 \subseteq A_2$, so the probability that the condition $A_1 \subseteq A_2$ is not violated for $i$ is $\frac34$. The probabilities are independent between the different $i$, so the probability that $A_1 \subseteq A_2$ is not violated for any $i \in S$ ist $\left(\frac34\right)^n$. But if it's not violated for any $i \in S$, then $A_1 \subseteq A_2$ is actually true. This leads to the same result you got, that

$$P(A_1 \subseteq A_2) = \left(\frac34\right)^n.$$

Now this method can be extended to more than 2 sets. If you have 3, then there are 8 possibilities:

1. $i \notin A_1, i \notin A_2, i \notin A_3$,

2. ...

   I hope this is enough to allow you to calculate the probabilities for $3$ and generally $m$ subsets.