Probability that random set is in an up-set?

Question

Let $X$ be a finite ground set and $\mathcal{A}\subset \mathcal{P}(X)$ be an up-set. That is, a family of sets such that if $A \in \mathcal{A}$ and $A \subseteq B$, then $B\in \mathcal{A}$.

Now let $X_p$ be a random subset of $X$ such that each element occurs in $X_p$ indepenedently with probability $p$.

My lecturer wrote the following:

$$\mathbb{P}(X_p \in \mathcal{A}) = \sum_{A\in \mathcal{A}}p^{|A|}(1-p)^{|X\setminus A|}$$

I am struglling to understand why this is true. Surely there should be some conditional dependence?

The way I would approach finding this probability is to consider $S\subseteq \mathcal{A}$ as a generating set for the family. i.e. a minimal set $S = \{S_1,...,S_m\}$ such that $A\in \mathcal{A}$ has $S_i \subseteq A$ for some $i$. I should think it would be easier to deal with the conditional probabilities in this way.

I feel I am missing something obvious in why we can take th answer to be as given in the lectures.

Answer 1

Let $A\in\mathscr{A}$. The probability that any given $x\in X$ is in $X_p$ is $p$, so that probability that every $x\in A$ is in $X_p$ is $p^{|A|}$. Similarly, the probability that any given $x\in X$ is not in $X_p$ is $1-p$, so the probability that every $x\in X\setminus A$ is in $X\setminus X_p$ (i.e., not in $X_p$) is $(1-p)^{|X\setminus A|}$. We get $X_p=A$ precisely when both of these things occur, so

$$\Bbb P(X_p=A)=p^{|A|}(1-p)^{|X\setminus A|}\,.$$

The events $X_p=A$ for $A\in\mathscr{A}$ are disjoint, so the probability that at least one of them occurs is just the sum of their individual probabilities:

$$\Bbb P(X_p\in\mathscr{A})=\sum_{A\in\mathscr{A}}\Bbb P(X_p=A)=\sum_{A\in\mathscr{A}}p^{|A|}(1-p)^{|X\setminus A|}\,.$$

Answer 2

This is the literal definition of the probability of an event for a discrete measure:

$$ \mathbb{P}(\mathcal A) = \sum_{A \in \mathcal{A}} \mathbb{P}(A) $$

This is because measures are $\sigma$-additive:

$$ \mathbb{P}(\mathcal{A}) = \mathbb{P}\left( \bigcup_{A \in \mathcal{A}} \{A\} \right) = \sum_{A \in \mathcal{A}} \mathbb{P}(\{A\})$$

where $\mathbb{P}(A)$ is notational short-hand for $\mathbb{P}(\{A\})$.

Then, for each $A \in \mathcal{A}$ what is $\mathbb{P}(A)$? Well it is

$$\mathbb{P}(x \in X_p \text{ for each } x \in A \text{ and } y \notin X_p \text{ for all } y \notin A)$$

But since the event $x \in X_p$ is independent, this becomes a product:

$$ \prod_{x \in A} \mathbb{P}(x \in X_p) \prod_{y \notin A} \mathbb{P}(y \notin X_p) = p^{|A|} (1 - p)^{|X \setminus A|}.$$