2 Foundations

2.1 Probability Theory

• $\Omega$ : An space of possible outcomes.
• $\mathcal{S}$ : A set of measurable events to which we are willing to assign probabilities. $\forall \alpha \in \mathcal{S} \ \cdot \ \alpha \subseteq \Omega$

Probability theory requires that $\mathcal{S}$ satisfy three basic properties:

• $\varnothing \in \mathcal{S}, \Omega \in \mathcal{S}$
• Closed under union: $\forall \alpha, \beta \in \mathcal{S} \ \cdot \ \alpha \cup \beta \in \mathcal{S}$
• Closed under complementation: $\forall \alpha \in \mathcal{S} \ \cdot \ (\Omega - \alpha) \in \mathcal{S}$

The latter two properties implies that $\mathcal{S}$ is also closed under other boolean operations, such as intersection and set difference

Definition 2.1 (Probability Distribution) A probability distribution $P$ over $(\Omega, \mathcal{S})$ is a mapping from events in $\Omega$ to real values that satisfies the following conditions:

• Probabilities are non negative : $\forall \alpha \in \mathcal{S} \ \cdot \ P(\alpha) \ge 0$.
• Trival event has the maximal possible probability of 1 : $P(\Omega) = 1$.
• $\forall \alpha, \beta \in \mathcal{S} \ \cdot \ \alpha \cap \beta = \varnothing \Rightarrow P(\alpha \cup \beta) = P(\alpha) + P(\beta)$.

This definition implies:

• $P(\varnothing) = 0$.
• $P(\alpha \cup \beta) = P(\alpha) + P(\beta) - P(\alpha \cap \beta)$.

The conditional probability of $\beta$ given $\alpha$ is defined as:

$P(\beta | \alpha) = \dfrac{P(\alpha \cap \beta)}{P(\alpha)}$

• The conditional probability is not defined when $P(\alpha) = 0$
• The conditional probability given an event (say $\alpha$) satisfies the properties of definition 2.1, and thus it is a probability distribution by its own right. Hence, we can think of the conditioning operation as taking one distribution and returning another over the same probability space

The chain rule of conditional probabilities:

• $P(\alpha \cap \beta) = P(\alpha) P(\beta | \alpha)$.
• $P(\alpha_1 \cap \alpha_2 \cdots \cap \alpha_k) = P(\alpha_1)P(\alpha_2 | \alpha_1) P(\alpha_3 | \alpha_1 \cap \alpha_2) \cdots P(\alpha_k | \alpha_1 \cap \alpha_2 \cdots \cap \alpha_{k-1} )$

Bayes' rule

$P(\alpha | \beta) = \dfrac{P(\beta | \alpha)P(\alpha)}{P(\beta)}$

$P(\alpha | \beta \cap \gamma) = \dfrac{P(\beta | \alpha \cap \gamma)P(\alpha | \gamma)}{P(\beta | \gamma)}$

A random variable is a way of reporting an attribute of the outcome.

A random variable is a function that associates with each outcome in $\Omega$ a value.

• Categorical random variables that take one of a few values.
• Random variables thta take integer value.
• Random variables that take real values.

$Val(X)$: the set of values that a random variable $X$ can take.

Marginal distribution: A probability distribution over one random variable.

Joint distribution: A probability distribution over two or more random variables.

Conditional Probability: .

$P(X | Y)$ : A set of conditional probability distributions.

Bayes' rule in term of conditional probability distributions:

$P(X | Y) = \dfrac{P(X)P(Y | X)}{P(Y)}$

Independence

Definition 2.2 (Independent events) An event $\alpha$ is independent of event $\beta$ in $P$, denoted $P \models (\alpha \bot \beta)$, if $P(\alpha | \beta) = P(\alpha)$ or if $P(\beta) = 0$.

Proposition 2.1 A distribution $P$ satisfy $(\alpha \bot \beta)$, if and only if $P(\alpha \cap \beta) = P(\alpha)P(\beta)$.

Conditional Independence

Definition 2.3 (Conditional Independent) An event $\alpha$ is conditionally independent of event $\beta$ given event $\gamma$, denoted $P \models (\alpha \bot \beta | \gamma)$, if $P(\alpha | \beta \cap \gamma ) = P(\alpha | \gamma)$, or if $P(\beta \cap \gamma) = 0$.

Proposition 2.2 $P \models (\alpha \bot \beta | \gamma)$, if and only if $P(\alpha \cap \beta | \gamma) = P(\alpha | \gamma) P(\beta | \gamma)$.

Independence of Random Variables

Definition 2.4 (Conditional Independence) Let $\mathcal{X}, \mathcal{Y}, \mathcal{Z}$ be sets of random variables. $\mathcal{X}$ is conditionally independent of $\mathcal{Y}$ given $\mathcal{Z}$ in a distribution $P$, if $P$ satisfies $(\mathcal{X}=\mathcal{x} \bot \mathcal{Y} = \mathcal{y} | \mathcal{Z} = \mathcal{z})$, for all values $\mathcal{x} \in \mathcal{X}, \mathcal{y} \in \mathcal{Y}$, and $\mathcal{z} \in \mathcal{Z}$.

If $\mathcal{Z}$ is empty, then we write $(\mathcal{X} \bot \mathcal{Y})$, and say that the two sets of random variables are marginally independent.

Proposition 2.3 The distribution $P$ satisfies $(\mathcal{X} \bot \mathcal{Y} | \mathcal{Z})$, if and only if $P(\mathcal{X}, \mathcal{Y} | \mathcal{Z}) = P(\mathcal{X} | \mathcal{Z})P(\mathcal{Y}|\mathcal{Z})$.

• Symmetry: $(\mathcal{X} \bot \mathcal{Y} | \mathcal{Z}) \Rightarrow (\mathcal{Y} \bot \mathcal{X} | \mathcal{Z})$.

• Decomposition: $(\mathcal{X} \bot \mathcal{Y},\mathcal{W} | \mathcal{Z}) \Rightarrow (\mathcal{X} \bot \mathcal{Y} | \mathcal{Z})$

Proof: $\begin{aligned} P(\mathcal{X},\mathcal{Y}|\mathcal{Z}) & = \sum_w P(\mathcal{X},\mathcal{Y},w|\mathcal{Z})\\ & = \sum_w P(\mathcal{X}|\mathcal{Z})P(\mathcal{Y},w|\mathcal{Z})\\ & = P(\mathcal{X}|\mathcal{Z}) \sum_w P(\mathcal{Y},w|\mathcal{Z})\\ & = P(\mathcal{X}|\mathcal{Z}) P(\mathcal{Y}|\mathcal{Z}) \end{aligned}$

• Weak union: $(\mathcal{X} \bot \mathcal{Y},\mathcal{W} | \mathcal{Z}) \Rightarrow (\mathcal{X} \bot \mathcal{Y} | \mathcal{Z},\mathcal{W})$

Proof:

$\begin{aligned} P(\mathcal{X}, \mathcal{Y} | \mathcal{Z},\mathcal{W}) & = \dfrac{P(\mathcal{X},\mathcal{Y},\mathcal{W}|\mathcal{Z})}{P(\mathcal{W})} \\ & = P(\mathcal{X}|\mathcal{Z}) \dfrac{P(\mathcal{Y},\mathcal{W}|\mathcal{Z})}{P(\mathcal{W})}\\ & = \dfrac{P(\mathcal{X}|\mathcal{Z})P(\mathcal{W}|\mathcal{Z})}{P(\mathcal{W}|\mathcal{Z})} P(\mathcal{Y} | \mathcal{Z},\mathcal{W})\\ & = \dfrac{P(\mathcal{X},\mathcal{W}|\mathcal{Z})}{P(\mathcal{W}|\mathcal{Z})} P(\mathcal{Y} | \mathcal{Z},\mathcal{W})\\ & = P(\mathcal{X} | \mathcal{Z},\mathcal{W})P(\mathcal{Y} | \mathcal{Z},\mathcal{W})\\ \end{aligned}$

• Contraction: $(\mathcal{X} \bot \mathcal{W}|\mathcal{Z},\mathcal{Y})\&(\mathcal{X} \bot \mathcal{Y}|\mathcal{Z}) \Rightarrow (\mathcal{X} \bot \mathcal{Y},\mathcal{W} | \mathcal{Z})$

Proof:

$\begin{aligned} P(\mathcal{X},\mathcal{Y},\mathcal{W}|\mathcal{Z}) & = P(\mathcal{X},\mathcal{W}|\mathcal{Z},\mathcal{Y})P(\mathcal{Y}|\mathcal{Z})\\ & = P(\mathcal{X}|\mathcal{Z},\mathcal{Y})P(\mathcal{W}|\mathcal{Z},\mathcal{Y})P(\mathcal{Y}|\mathcal{Z})\\ & = \dfrac{P(\mathcal{X},\mathcal{Y}|\mathcal{Z})}{P(\mathcal{Y}|\mathcal{Z})} \dfrac{P(\mathcal{W},\mathcal{Y}|\mathcal{Z})}{P(\mathcal{Y}|\mathcal{Z})} P(\mathcal{Y}|\mathcal{Z})\\ & = P(\mathcal{X}|\mathcal{Z})P(\mathcal{W},\mathcal{Y}|\mathcal{Z}) \end{aligned}$

Definition 2.5 (Positive Distribution) A distribution $P$ is said to be positive, if $\forall \alpha \in \mathcal{S} \ \cdot \ \alpha \ne \varnothing \Rightarrow P(\alpha) > 0$.

• Intersection: For positive distribution, and for mutually disjoint sets $\mathcal{X},\mathcal{Y},\mathcal{Z},\mathcal{W}$:

  $(\mathcal{X} \bot \mathcal{Y}|\mathcal{Z},\mathcal{W})\&(\mathcal{X} \bot \mathcal{W}|\mathcal{Z},\mathcal{Y}) \Rightarrow (\mathcal{X} \bot \mathcal{Y},\mathcal{W}|\mathcal{Z})$

  Proof:

$\begin{aligned} P(\mathcal{X},\mathcal{Y},\mathcal{W}|\mathcal{Z}) & = P(\mathcal{X},\mathcal{Y}|\mathcal{Z},\mathcal{W})P(\mathcal{W}|\mathcal{Z})\\ & = P(\mathcal{X}|\mathcal{Z},\mathcal{W})P(\mathcal{Y}|\mathcal{Z},\mathcal{W})P(\mathcal{W}|\mathcal{Z})\\ & = P(\mathcal{X}|\mathcal{Z},\mathcal{W}) \dfrac{P(\mathcal{Y},\mathcal{W}|\mathcal{Z})}{P(\mathcal{W}|\mathcal{Z})}P(\mathcal{W}|\mathcal{Z})\\ & = P(\mathcal{X}|\mathcal{Z},\mathcal{W}) P(\mathcal{Y},\mathcal{W}|\mathcal{Z})\\ & = ? \\ & = P(\mathcal{X}|\mathcal{Z})P(\mathcal{Y},\mathcal{W}|\mathcal{Z})\\ \end{aligned}$

X Y Z