Grocery on Distributed Algorithms

T1: The Law of total probability and Tower Rule

Reminder: This post contains 1386 words · 4 min read · by Xianbin

The law of total probability

\(\textbf{Lemma 1}\). Given \(Y_1,\cdots,\) a partition of the sample space \(\Omega\), then for any event \(X\), we have

\[P(X) = \sum_i P(X\mid Y_i) P(Y_i)\]

Conditional Expectation

Background

  1. See measure theory for the definition of \(\sigma\)-algebra, the probability space.

  2. Any \(\sigma\)-field F of events with the probability \(F\subset A\) is called sub-\(\sigma\)-field.

  3. What is measurable? Let \((X, a)\) and \((Y,b)\) be measurable spaces where \(X\) is a set and \(a\) is a \(\sigma\)-algebra of subsets of \(X\). A function \(f: X \to Y\) is measurable if for each \(b_i \in b\), \(f^{-1}(b_i) \in a\).

  4. What is a random variable?

Let \((\Omega, F, P)\) is a probability space and \(X: \Omega \to R\) is measurable, then \(X\) is called a random variable.

\(\textbf{Lemma}\)(Existence of conditional expectation). Let \((\Omega, F, P)\) be a probability space, and let \(A\) be a random variable. Let \(B\) be a sub-\(\sigma\)-field of \(F\). If \(E(A)\) exists, then there exists a version of \(E(A\mid B)\)

The following lemma is used a lot (tower property of conditional property, and law of total probability).

\(\textbf{Lemma}\) (William’s Tower Property). If \(C_1 \subseteq C_2 \subseteq F\) are sub-\(\sigma\)-filed’s and \(E(X)\) exists, then we have

\[E(X\mid C_1) = E[E(X\mid C_2 ) \mid C_1)]\]

If all the following expectations are finite, then for any random variables \(X\) AND \(Y\), we have

\[E(X) = E_Y[E(X \mid Y)]\]

Particularly, let \(X\) be a random variable, and let events \(A_1,\cdots, A_n\) partition the sample space, we have

\[E[X] = \sum_{i=1}^n E[X \mid A_i] P(A_i)\]