Probability of $A \subset B$ when $A,B$ are subsets of $[\![ 1, n ]\!]$?

Question

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$?

Answer 1

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 [\![ 0, n ]\!] $
• choose $ B \in \mathscr{P} (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$.

Answer 2

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) = p\left(\bigwedge_{i=1}^n X_i\right) = \prod_{i=1}^n p(X_i) = \left(\frac{3}{4}\right)^n.$$

Answer 3

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. $$