Krdytkyu

Let $E = [![ 1, n ]!]$, with $n in mathbb N^*$. Suppose we randomly chose $(A,B) in mathscr{P} (E)^2$, what is the probability of $A subset B$?

For $i = 1, 2, ldots, n$, let $X_i$ denote the event $i in A rightarrow i in B$. Then for each $i$, $p(X_i) = frac{3}{4}$ (because the complement of the event is $i in A wedge i notin B$, which has probability $frac{1}{4}$). On the other hand, the events $X_i$ are independent, so
$$p(A subseteq B) = pleft(bigwedge_{i=1}^n X_iright) = prod_{i=1}^n p(X_i) = left(frac{3}{4}right)^n.$$

Define $X^{(n)} = (X^{(n)}_1, cdots, X^{(n)}_n)$ by

$$ X^{(n)}_i = ( mathbf{1}_{{i in A}}, mathbf{1}_{{i in B}} ),$$

where $mathbf{1}_{{cdots}}$ takes value $1$ if $cdots$ is true and $0$ otherwise. Then

1. $ A subseteq B$ if and only if $X^{(n)}_i in {(0, 0), (0, 1), (1, 1)} $ for all $i$.




2. For each fixed $n$, $X_{i}^{(n)}$ are independent.

So

$$ mathbb{P}[A subseteq B]
= prod_{i=1}^{n} mathbb{P}left[ X^{(n)}_i in { (0, 0), (0, 1), (1, 1)
}right]
= left( frac{3}{4} right)^n. $$

In general, if $A_1, cdots, A_m$ are chosen uniformly and independently at random from the power set of $[![ 1, n ]!]$, then

$$ mathbb{P}[ A_1 subseteq cdots subseteq A_m]
= prod_{i=1}^{n} mathbb{P} left[ mathbf{1}_{{i in A_1}} leq cdots leq mathbf{1}_{{i in A_m}} right]
= left( frac{m+1}{2^m} right)^n. $$

Let $Omega = mathscr{P} (E)^2$.

Since $E = [![ 1, n ]!]$, $text{card}(Omega) = 4^n$.

Let $mathscr U = {(A, B) in Omega | A subset B}$.

The following algorithm constructs all elements of $mathscr U$ one and only one time :

• choose an integer $ p in E $
  


• choose $ B in E $ with $text{card}(B) = p$
  


• choose $A subset B$
  

We can now easily calculate $text{card}(mathscr U)$:

$displaystyle text{card}(mathscr U) = sum_{p=0}^{n}binom{n}{p}cdot2^p = 3^n$

Finally, $text{P}(mathscr U) = frac{text{card}(mathscr U)}{text{card}(Omega)}=left(frac{3}{4}right)^n$.