# 2019_III_12_ProbStats

To show that T contains exactly 2^n sets, note that T is in bijection with the set of binary strings of length n, since any set in T is equivalent to the data of a truth value for each integer from 1 to n (i.e. saying whether or not that integer is in the set). Since the set of binary strings of length n is of cardinality 2^n, so too is T.

(i) Since A_1 is equally likely to be any set of T, and exactly half the sets of T contain 1, we see that \mathbb{P}(1\in A_1)=\frac12.

(ii) \mathbf{P}(A_1\cap A_2=\varnothing) = 1-\mathbf{P}(A_1\cap A_2\neq\varnothing). The probability of any integer m being in A_1\cap A_2 is (by the previous part) equal to \left(\frac12\right)^2=\frac14. So the probability of any integer m not being in A_1\cap A_2 is \frac34, which means that the probability of none of the n integers 1,\ldots,n being in A_1\cap A_2 (which is exactly the desired probability) is \left(\frac34\right)^n.

Similarly, \mathbb{P}(m\in A_1\cap\ldots\cap A_k)=\frac{1}{2^k}, whence \mathbb{P}(A_1\cap\ldots\cap A_k)=\left(\frac{2^k-1}{2^k}\right)^n (from which we see that \mathbb{P}(A_1\cap A_2\cap A_3=\varnothing)=\left(\frac78\right)^n).

(iii) For any integer m between 1 and n, if A_1\subseteq A_2, then either m\in A_1\cap A_2, m\in A_1^c\cap A_2, or m\in A_1^c\cap A_2^c (i.e. we cannot have m\in A_1\cap A_2^c if A_1\subseteq A_2). The probability of m being in any individual one of these intersections is \frac14, whence the probability of it being in only the first three (and not the one that is excluded if A_1\subseteq A_2) is \frac34. But having A_1\subseteq A_2 is exactly equivalent to having that, for all m between 1 and n, we never have m\in A_1\cap A_2^c. Thus \mathbb{P}(A_1\subseteq A_2)=\left(\frac34\right)^n.

Similarly, if A_1\subseteq A_2\subseteq A_3, then the only permissible intersections for m to belong to are A_1\cap A_2\cap A_3, A_1^c\cap A_2\cap A_3, A_1^c\cap A_2^c\cap A_3, and A_1^c\cap A_2^c\cap A_3^c. These are 4 of the 8 possible intersections, whence (as above) \mathbb{P}(A_1\subseteq A_2\subseteq A_3)=\left(\frac48\right)^n=\left(\frac12\right)^n.

Generalising this to arbitrary k, we get that \mathbb{P}(A_1\subseteq\ldots\subseteq A_k)=\left(\frac{k+1}{2^k}\right)^n.

Awesome!!!