Information Theory (1)

总得来说，思路很简单，描述反人类。

这里没写证明，如果需要考证明而且自由度较低的话还得翻 Lecture Note 。

Foundational concepts in discrete probability

Possible outcomes and outcome spaces

outcome 表示事件。在随机场景下，outcome space 表示所有可能的事件集合。

Probability mass functions

Definition 1.26. Suppose $\Omega$ is an outcome space. A probability mass function on $\Omega$
is a map $\rho \colon \Omega \to [0, 1]$ such that $\sum_{\omega \in \Omega} \rho(\omega) = 1$.

意思就是所有事件的概率之和为 $1$ 。

给定一个 outcome space $\Omega$ ，$\Delta_{\text{pmf}}(\Omega)$ 表示 $\Omega$ 上所有可能的概率质量函数(probability mass functions)的集合。

Lemma 1.27. Given any outcome space $\Omega$, we have

$$\begin{align*} \Delta_{\text{pmf}}(\Omega) = \{ f \in \ell^1_+(\Omega) \colon \|f\|_1 = 1 \}. \qquad (1.10) \end{align*}$$

Given $\rho \in \Delta_{\text{pmf}}(\Omega)$, the cozero set $\text{coz}(\rho) = \{ \omega \in \Omega \colon \rho(\omega) > 0 \}$ is countable.

表示离散概率下所有非零概率事件的概率之和为 $1$ ，而且所有事件的概率非负。

Discrete probability spaces

设 $\mathcal{P}(\Omega)$ 为 $\Omega$ 上所有可能的概率测度的集合(power set)：$\mathcal{P}(\Omega) = \{ A | A \subseteq \Omega \}$ 。

Lemma 1.28. Suppose $\rho \in \Delta_{\text{pmf}}(\Omega)$. Then, for all $A \subseteq \Omega$ we have

$$\sum_{\omega \in A} \rho(\omega) = \| \rho | A \|_1 = \| \rho \mathbf{1}_A \|_1 \in [0, 1].$$

表示任意事件子集的概率之和在 $0$ 至 $1$ 之间。

假设 $\rho \in \Delta_{\text{pmf}}(\Omega)$ ，我们可以通过以下方式定义一个函数 $\mathbb{P}_\rho \colon \mathcal{P}(\Omega) \to [0, 1]$：

$$\mathbb{P}_\rho(A) = \sum_{\omega \in A} \rho(\omega), \quad \forall A \subseteq \Omega, \qquad (1.11)$$

我们用 $\mathbb{P}_\rho$ 表示与 $\rho$ 相关的概率测度(probability measure)。在离散概率论的语境中，我们将 $\Omega$ 的子集 $A \subseteq \Omega$ 视为事件(events)，并使用记号 $\mathcal{E} = \mathcal{P}(\Omega)$ 来表示所有事件的集合，前提是 outcome space $\Omega$ 在语境中是明确的或对当前讨论不重要。

Definition 1.29. A discrete probability space is a triple $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ including an outcome space $\Omega$, the set of all events $\mathcal{E} = \mathcal{P}(\Omega)$, and a discrete probability measure $\mathbb{P}_\rho$ associated with a probability mass function $\rho \in \Delta_{\text{pmf}}(\Omega)$.

Theorem 1.30. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space associated with a probability mass function $\rho \in \Delta_{\text{pmf}}(\Omega)$. The countable set $\text{coz}(\rho) \subseteq \Omega$ satisfies $\mathbb{P}_\rho\{\text{coz}(\rho)\} = \mathbb{P}_\rho(\Omega) = 1$. Furthermore, given any collection $\mathcal{A} \subseteq \mathcal{E}$ of pairwise disjoint subsets of $\Omega$ we have

$$\mathbb{P}_\rho\left(\bigcup \mathcal{A}\right) = \sum_{E \in \mathcal{A}} \mathbb{P}_\rho(E). \qquad (1.12)$$

简单地说就是把各个独立（互斥）的events的概率相加，就是“或”的关系。

Corollary 1.31. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space. We have $\mathbb{P}_\rho(\emptyset) = 0$ and whenever $A \subseteq B \subseteq \Omega$ we have $0 \leq \mathbb{P}_\rho(A) \leq \mathbb{P}_\rho(B)$.

显然。

Corollary 1.32. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space and $A \subseteq \Omega$ is a
countable collection. Then

$$\mathbb{P}_\rho\left(\bigcup A\right) \leq \sum_{E \in A} \mathbb{P}_\rho(E).$$

不是彼此独立的情况，显然。

Lemma 1.33. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space and $A \subseteq \Omega$ has

$\mathbb{P}_\rho(A) = 1$. Then, we have $\text{coz}(\rho) \subseteq A$.

所有概率非零的 outcome 全部被 $A$ 包含，显然。

Rings of sets and σ-additive functions

Definition 1.34. A ring of sets $\mathcal{F}$ is a collection of subsets $\mathcal{F} \subseteq P(\Omega)$ such that if $A \in \mathcal{F}$ and $B \in \mathcal{F}$ then $A \cup B \in \mathcal{F}$ and $A \setminus B \in \mathcal{F}$.

群论概念。

Definition 1.35. A function $\mathbb{M} : \mathcal{F} \rightarrow [0, 1]$ defined on some collection of subsets $\mathcal{F} \subseteq \mathcal{P}(\Omega)$ is said to be $\sigma$-additive if for any countable collection $\mathcal{A} \subseteq \mathcal{F}$ of pairwise disjoint subsets with $\bigcup \mathcal{A} \in \mathcal{F}$, we have

$$\mathbb{M}\left(\bigcup \mathcal{A}\right) = \sum_{E \in \mathcal{A}} \mathbb{M}(E). \qquad (1.13)$$

两两不相交的事件族的并的运算方式。

Corollary 1.36. Given $\rho \in \Delta_{\text{pmf}}(\Omega)$, the function $\mathbb{P}_\rho \colon \mathcal{P}(\Omega) \to [0, 1]$ is $\sigma$-additive.

Proposition 1.37. Suppose $\Omega$ is a set, $S \subseteq \Omega$ is a countable subset, and $\mathcal{F} \subseteq \mathcal{P}(\Omega)$ is
a ring of sets $\{S\} \cup \{\{\omega\} \colon \omega \in S\} \subseteq \mathcal{F}$ and $M \colon \mathcal{F} \to [0, 1]$ is a $\sigma$-additive function such that $M(S) = 1$. Then, there exists a probability mass function $\rho \colon \Omega \to [0, 1]$ such
that for all $A \in \mathcal{F}$ we have $M(A) = \sum_{\omega \in A} \rho(\omega) = \mathbb{P}_\rho(A)$.

事件的概率还原成单点概率。只要全部概率集中在一个可数集合上，事件的概率就完全由各单点的概率决定。

Random variables on discrete probability spaces

一个随机变量(random variable)是定义在离散概率空间$(\Omega, \mathcal{E}, \mathbb{P}_\rho)$上的实值函数 $X \colon \Omega \to \mathbb{R}$。

假设随机变量 $X \in \mathbb{R}^\Omega, Y \in \mathbb{R}^\Omega$，实数$\lambda \in \mathbb{R}$，则随机变量 $XY \in \mathbb{R}^\Omega, (\lambda X + Y) \in \mathbb{R}^\Omega$有

$$(XY)(\omega) = X(\omega)Y(\omega), \quad (\lambda X + Y)(\omega) = \lambda X(\omega) + Y(\omega), \quad \forall \omega \in \Omega.$$

Definition 1.38. The space of integrable random variables is $\mathcal{L}_1(\Omega, \mathbb{P}_\rho) := \{X \in \mathbb{R}^\Omega \colon X\rho \in \ell^1(\Omega)\} = \{X \in \mathbb{R}^\Omega \colon \|X\rho\|_1 < \infty\}$.
Given $X \in \mathcal{L}_1(\Omega, \mathbb{P}_\rho)$, its expectation is $\mathbb{E}_\rho(X) \colon= \sum_{\omega \in \Omega} X(\omega)\rho(\omega)$.

简单的说，期望的定义要求 $\sum_\omega | X(\omega) | \rho(\omega)$ 有限。

Lemma 1.39. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space and $A \subseteq \Omega$. Then

$\mathbf{1}_A \in \mathcal{L}_1(\Omega, \mathbb{P}_\rho)$ and $\mathbb{E}_\rho(\mathbf{1}_A) = \mathbb{P}_\rho(A)$.

显然，指示函数的期望等于其概率。

Lemma 1.40. Suppose $\rho \in \Delta_{\text{pmf}}(\Omega)$ and $X, Y \in \mathcal{L}_1(\Omega, \mathbb{P}_\rho)$ and $\lambda \in \mathbb{R}$. Then $\lambda X + Y \in \mathcal{L}_1(\Omega, \mathbb{P}_\rho)$ and

$$\mathbb{E}_\rho(\lambda X + Y) = \lambda \mathbb{E}_\rho(X) + \mathbb{E}_\rho(Y).$$

期望的线性。

Lemma 1.41. Suppose $X, Y \in \mathcal{L}_1(\Omega, \mathbb{P}_\rho)$ and $\mathbb{P}_\rho(X \leq Y) = 1$. Then $\mathbb{E}_\rho(X) \leq \mathbb{E}_\rho(Y)$.

$\{ X \le Y \} = \{ \omega \in \Omega : X(\omega) \leq Y(\omega) \}$，显然。

Random elements and their distributions

看不动了，GPT 启动。

Definition 1.42. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space and $\mathbb{A}$ is a set. A random element taking values in $\mathbb{A}$ is a function $X \colon \Omega \to \mathbb{A}$. The set $\mathbb{A}$ is referred to as the state space of $X$, and its elements are called states.

从随机变量推广到随机元素，输出可能为任何东西。

对于状态 $a\in \mathbb{A}$，记

$$\{X=a\}:=\{\omega\in\Omega:X(\omega)=a\}.$$

对于集合 $S \subseteq \mathbb{A}$，记

$$\{X\in S\} := \{\omega\in\Omega:X(\omega)\in S\} = X^{-1}(S).$$

如果再给定一个函数 $f:\mathbb{A}\to \mathbb{B}$，那么

$$f(X):=f\circ X$$

也是随机元素：

$$f(X)(\omega)=f(X(\omega)).$$

Definition 1.44. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_{\rho})$ is a discrete probability space and $X \colon \Omega \to \mathbb{A}$ is
a random element taking values in some state space $\mathbb{A}$. Then, the distribution of $X$ is the function $\mathbb{P}_X \colon \mathcal{P}(\mathbb{A}) \to [0, 1]$ defined by

$$\mathbb{P}_X(S) := \mathbb{P}_\rho(\{X \in S\})$$

for all $S \subseteq \mathbb{A}$. Further more, the induced probability mass function of $X$ is the function $\rho_X \colon \mathbb{A} \to [0, 1]$ defined by $\rho_X(a) := \mathbb{P}_\rho(\{X = a\})$ for all $a \in \mathbb{A}$.

把概率从样本空间转移到状态空间。

Lemma 1.45. Suppose $X \colon \Omega \rightarrow \mathbb{A}$ is a random element on a discrete probability space $(\Omega, \mathcal{E}, \mathbb{P}_{\rho})$. Then $\rho_X \in \Delta_{\text{pmf}}(\mathbb{A})$. Further more, given any $S \subseteq \mathbb{A}$, we have

$$\mathbb{P}_X(S) = \mathbb{P}_\rho(\{X \in S\}) = \sum_{a \in S} \rho_X(a). \qquad (1.14)$$

Hence, $\mathbb{P}_X$ is the discrete probability measure associated with $\rho_X$.

根据 Lemma 1.27，即使$\mathbb{A}$不可数，$\rho_X$的非零值集合是可数的。

Lemma 1.46. Suppose $X \colon \Omega \rightarrow \mathbb{A}$ is a random element on a discrete probability space $(\Omega, \mathcal{E}, \mathbb{P}_{\rho})$ and $f \colon \mathbb{A} \rightarrow \mathbb{R}$. Then $\|f (X)\rho\|_1 = \|f \rho_X\|_1$. Moreover, the following
conditions

$$\begin{align*} &(i) & f (X) \in& \mathcal{L}_1(\Omega, \mathbb{P}_\rho), \\ &(ii) & f (X)\rho \in& \ell_1(\Omega), \\ &(iii) & f\rho_X \in& \ell_1(\mathbb{A}), \\ &(iv) & f \in& \mathcal{L}_1(\mathbb{A}, \mathbb{P}_X), \end{align*}$$

are all equivalent. Further more, when $f(X) \in \mathcal{L}_1(\Omega, \mathbb{P}_\rho)$ we have

$$\mathbb{E}_\rho{f (X)} = \sum_{a \in \mathbb{A}} f (a) \rho_X(a) = \mathbb{E}_{\rho_X} (f). \qquad (1.15)$$

计算期望只需要知道分布。先证明

$$\sum_{\omega \in \Omega} | f(X(\omega)) | \rho(\omega) = \sum_{a \in \mathbb{A}} | f(a) | \rho_X (a).$$ $f(X)$ 是否可积，可以直接通过 $\rho_X$ 判断。若可积，则 $$\begin{align*} \mathbb{E}_\rho [f(X)] =& \sum_{\omega \in \Omega} f(X(\omega)) \rho(\omega) \\ =& \sum_{a \in \mathbb{A}} f(a) \sum_{\omega: X(\omega) = a} \rho(\omega) \\ =& \sum_{a \in \mathbb{A}} f(a) \rho_X(a) = \mathbb{E}_{\rho_X} (f). \end{align*}$$

Definition 1.47. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_{\rho})$ is a discrete probability space and $\mathbb{A}$ is a state
space. A collection of random elements $X_1, \dots, X_n \colon \Omega \to \mathbb{A}$ are said to be identically distributed if their respective distributions $\mathbb{P}_{X_1}, \dots, \mathbb{P}_{X_n}$ coincide: $\mathbb{P}_{X_1} = \dots = \mathbb{P}_{X_n}$.

Lemma 1.48. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_{\rho})$ is a discrete probability space and $X_1, \dots, X_n \colon \Omega \rightarrow \mathbb{A}$ are random elements. Then the following are equivalent conditions:

(i) The random variables $X_1, \dots, X_n$ are identically distributed ie. $\mathbb{P}_{X_1} = \dots = \mathbb{P}_{X_n}$ ;
(ii) Their respective probability mass functions coincide ie. $\rho_{X_1} = \dots = \rho_{X_n}$ ;
(iii) Given any function $f \colon \mathbb{A} \to \mathbb{R}$ such that $f (X_1), \dots, f (X_n) \in \mathcal{L}_1(\Omega, \mathbb{P}_\rho)$ we have

$\mathbb{E}_\rho \{f (X_1) \} = \dots = \mathbb{E}_\rho \{f (X_n) \}$.

独立同分布的条件。

Lemma 1.49. We have $X \in \mathcal{L}_1(\Omega, \mathbb{P}_\rho)$ if and only if $|X| \in \mathcal{L}_1(\Omega, \mathbb{P}_\rho)$. Further more, if

$X \in \mathcal{L}_1(\Omega, \mathbb{P}_\rho)$ then $\mathbb{E}_\rho(|X|) = \|X\rho\|_1$.

显然，$\rho > 0 \Rightarrow | X | \rho = | X \rho |$，然后参考 Lemma 1.6。

Joint distributions and independence on discrete probability spaces

Definition 1.52. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space, that $\mathbb{F}$ is a non-empty finite set and for each $i \in \mathbb{F}$ we have a random element $X_i \colon \Omega \rightarrow \mathbb{A}_i$ taking values in the state space $\mathbb{A}_i$.The joint random element $X_\mathbb{F} = (X_i)_{i\in\mathbb{F}}$ is the map $X_\mathbb{F} \colon \Omega \to \prod_{i\in\mathbb{F}} \mathbb{A}_i$ defined by

$$X_F(\omega) := (X_i(\omega))_{i\in\mathbb{F}} \in \prod_{i\in\mathbb{F}} \mathbb{A}_i,$$

for each $\omega \in \Omega$. Hence, $X_F$ is a random element taking values in $\prod_{i\in\mathbb{F}} \mathbb{A}_i$. We then refer to the distribution of $X_\mathbb{F}$ (Definition 1.44) $\mathbb{P}_{X_\mathbb{F}} \colon P(\prod_{i\in\mathbb{F}} \mathbb{A}_i) \to [0, 1]$, as the
joint distribution of $(X_i)_{i\in\mathbb{F}}$. We also refer to $\rho_{X_\mathbb{F}} \colon \prod_{i\in\mathbb{F}} \mathbb{A}_i \to [0, 1]$, the induced probability mass function of $X_\mathbb{F}$, as the joint probability mass function of $(X_i)_{i\in\mathbb{F}}$.

联合概率分布。

random vector：随即元素 $X_[n] : \Omega \to \mathbb{R}^n, X_[n] = (X_i)_{i \in [n]}, (X_1, \dots, X_n)$ 。

Definition 1.53. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space and $\mathbb{F}$ is a non-empty finite set. In addition, for each $i \in \mathbb{F}$ we have a random element $X_i \colon \Omega \rightarrow \mathbb{A}_i$, with probability mass function $\rho_{X_i} \colon \mathbb{A}_i \to [0, 1]$. We say that the indexed collection of random elements $(X_i)_i \in \mathbb{F}$ is independent if the joint distribution $\mathbb{P}_{X_\mathbb{F}} \colon P(\prod_{i\in\mathbb{F}} \mathbb{A}_i) \to [0, 1]$ satisfies

$$\mathbb{P}_{X_\mathbb{F}}(E) = \prod_{i\in\mathbb{F}} \mathbb{P}_{X_i}(E_i),$$

for all $E = \prod_{i\in\mathbb{F}} E_i$ with $E_j \subseteq \mathbb{A}_j$ for each $j \in \mathbb{F}$.

独立事件的联合概率可以分解成乘积的形式。

Lemma 1.54. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space and $\mathbb{F}$ is a non-empty finite set. In addition, for each $i \in \mathbb{F}$ we have a random element $X_i \colon \Omega \rightarrow \mathbb{A}_i$. Then,
the collection of random variables $(X_i)_{i\in\mathbb{F}}$ is independent if and only if $(X_i)_{i\in \mathbb{J}}$ is
independent for every $\mathbb{J} \in P(\mathbb{F}) \setminus \{\emptyset\}$.

一组相互独立的随机元素，其任意非空子组仍然相互独立。

$X_0$ 与 $X_1$ **两两**独立：$X_0 \perp \!\!\!\! \perp X_1$ 。

Definition 1.55. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space and $(X_i)_i \in \mathbb{F}$ is a
collection of random elements $X_i \colon \Omega \to \mathbb{A}_i$ with a finite and non-empty index set $\mathbb{F}$. We say that $(X_i)_{i\in\mathbb{F}}$ are pairwise independent if $X_j \perp \!\!\!\! \perp X_k$ for any $j, k \in \mathbb{F}$ with $j \neq k$.

两两独立(pairwise independent)和相互独立(independent)存在区别：相互独立更强。

Proposition 1.57. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space, that $\mathbb{F}$ is a non-empty finite index set and for each $i \in \mathbb{F}$ we have a random element $X_i \colon \Omega \to \mathbb{A}_i$, with distribution $\mathbb{P}_{X_i} \colon P(\mathbb{A}_i) \to [0, 1]$ and probability mass function $\rho_{X_i} \colon \mathbb{A}_i \to [0, 1]$. Then, the following three conditions are equivalent:

(i) Given any $E = \prod_{i\in\mathbb{F}} E_i \subseteq \prod_{i\in\mathbb{F}} \mathbb{A}_i$ we have $\mathbb{P}_{X_\mathbb{F}}(E) = \prod_{i\in\mathbb{F}} \mathbb{P}_{X_i}(E_i)$;

(ii) Given any $a = (a_i)_{i\in\mathbb{F}} \in \prod_{i\in\mathbb{F}} \mathbb{A}_i$ we have $\rho_{X_\mathbb{F}}(a) = \prod_{i\in\mathbb{F}} \rho_{X_i}(a_i)$;

(iii) Given any collection of functions $(\varphi_i)_{i\in\mathbb{F}}$ with $\varphi_i \colon \mathbb{A}_i \to \mathbb{R}$ and $\varphi_i \in \mathcal{L}^1(\mathbb{A}_i, \mathbb{P}_{X_i})$ for each $i \in \mathbb{F}$, the function $\varphi \colon \prod_{j\in\mathbb{F}} \mathbb{A}_j \to \mathbb{R}$ by $\varphi(a) = \prod_{j\in\mathbb{F}} \varphi_j(a_j)$ for all $a = (a_j)_{j\in\mathbb{F}} \in \prod_{i\in\mathbb{F}} \mathbb{A}_i$ we have $\varphi \in \mathcal{L}^1(\prod_{i\in\mathbb{F}} \mathbb{A}_i, \mathbb{P}_{X_\mathbb{F}})$ and

$$\mathbb{E}_\rho\{\varphi(X_\mathbb{F})\} = \prod_{i\in\mathbb{F}} \mathbb{E}_\rho\{\varphi_i(X_i)\}.$$

三个条件等价：事件概率可以分解；联合概率质量函数可以分解；各变量的函数之积，其任意期望可以分解。

Corollary 1.58. Suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space and $(X_i)_{i\in\mathbb{F}}$ is an independent collection of random elements indexed by a finite set $\mathbb{F} \neq \emptyset$. Suppose $\mathbb{J}, \mathbb{K} \in P(\mathbb{F}) \setminus \{\emptyset\}$ with $\mathbb{J} \cap \mathbb{K} = \emptyset$. Then $X_\mathbb{J} \perp \!\!\!\! \perp X_\mathbb{K}$. Furthermore, if $f \colon \prod_{j\in\mathbb{J}} \mathbb{A}_j \to \mathbb{R}$ and $g \colon \prod_{k\in\mathbb{K}} \mathbb{A}_k \to \mathbb{R}$ are real-valued functions with $f(X_\mathbb{J}), g(X_\mathbb{K}) \in \mathcal{L}^1(\Omega, \mathbb{P}_\rho)$, then

$$\mathbb{E}_\rho\{f(X_\mathbb{J})g(X_\mathbb{K})\} = \mathbb{E}_\rho\{f(X_\mathbb{J})\}\mathbb{E}_\rho\{g(X_\mathbb{K})\}. \qquad (1.17)$$

一组相互独立的随机元素，按两个不相交的非空下标集 $\mathbb{J}, \mathbb{K}$ 分组后，两个随机向量 $X_\mathbb{J}, X_\mathbb{K}$ 仍然独立。分别对两组应用函数 $f, g$，所得随机变量也独立；若二者可积，其乘积的期望就等于各自期望的乘积。这里要求原变量相互独立，仅两两独立不足以保证结论，也不要求原变量同分布。

证明的关键是将联合概率质量函数按两组分解：

$$\rho_{(X_\mathbb{J}, X_\mathbb{K})}(a_\mathbb{J}, a_\mathbb{K}) = \prod_{i\in\mathbb{J}\cup\mathbb{K}} \rho_{X_i}(a_i) = \left(\prod_{j\in\mathbb{J}} \rho_{X_j}(a_j)\right) \left(\prod_{k\in\mathbb{K}} \rho_{X_k}(a_k)\right) = \rho_{X_\mathbb{J}}(a_\mathbb{J})\rho_{X_\mathbb{K}}(a_\mathbb{K}).$$

由 Proposition 1.57 的 (ii) $\Rightarrow$ (i) 得到两组独立，再由 (i) $\Rightarrow$ (iii) 得到公式 (1.17)。例如，若 $X_1, X_2, X_3, X_4$ 相互独立且可积，则 $X_1+X_2$ 与 $X_3+X_4$ 独立，并且

$$\mathbb{E}_\rho[(X_1+X_2)(X_3+X_4)] = \mathbb{E}_\rho[X_1+X_2]\,\mathbb{E}_\rho[X_3+X_4].$$

High probability bounds

GPT。本节的 $\log$ 均为自然对数。

Markov’s inequality

Theorem 1.59. Let’s suppose $(\Omega, \mathcal{E}, \mathbb{P}_\rho)$ is a discrete probability space and $X \in \mathcal{L}^1(\Omega, \mathbb{P}_\rho)$ is integrable with $\mathbb{P}_\rho(X \geq 0) = 1$. Then, for all $\zeta > 0$,

$$\mathbb{P}_\rho(X \geq \zeta) \leq \mathbb{E}_\rho(X)/\zeta.$$

$$\mathbb{E}_\rho(X) \geq \zeta\,\mathbb{E}_\rho[\mathbf{1}_{\{X\geq\zeta\}}] = \zeta\,\mathbb{P}_\rho(X\geq\zeta).$$

Bernoulli’s law of large numbers

Definition 1.60. A Bernoulli random variable $X$ is a random variable $X \colon \Omega \to \mathbb{R}$ which takes values in $\{0, 1\}$. Given $p \in [0, 1]$ we write $X \sim \operatorname{Bern}(p)$ to mean that $X$ is a Bernoulli random variable with $\mathbb{E}(X) = p$.

伯努利变量描述一次只有“成功/失败”两种结果的试验：成功记 $1$，失败记 $0$。一般地，

$$\rho_X(x)= \begin{cases} 1-p, & x=0,\\ p, & x=1,\\ 0, & \text{otherwise}. \end{cases} \qquad \mathbb{E}(X)=1\cdot p+0\cdot(1-p)=p.$$

Definition 1.61. A binomial random variable $Y \colon \Omega \to \mathbb{R}$ is a random sum of the form $Y = \sum_{i=1}^n X_i$ where $n \in \mathbb{N}$ and $X_1,\dots,X_n \colon \Omega \to \mathbb{R}$ are independent and identically distributed Bernoulli random variables on a common probability space $(\Omega,\mathcal{E},\mathbb{P})$. Given $n \in \mathbb{N}$ and $p \in [0,1]$ we write $Y \sim \operatorname{Bin}(n,p)$ to mean that $Y = \sum_{i=1}^n X_i$ with $n$ independent terms $X_i \sim \operatorname{Bern}(p)$.

二项变量记录 $n$ 次独立、成功概率相同的试验中的成功次数。对应的样本比例为

$$\widehat p_n:=\frac1n\sum_{i=1}^n X_i, \qquad n\widehat p_n\sim\operatorname{Bin}(n,p), \qquad \mathbb{E}(\widehat p_n)=p.$$

Theorem 1.62. Suppose $p \in [0,1]$ and for each $n \geq 1$, we have a random variable $\widehat p_n$ on a probability space $(\Omega_n,\mathcal{E}_n,\mathbb{P}_n)$ such that $n\widehat p_n \sim \operatorname{Bin}(n,p)$. Then, given any $\varepsilon > 0$, we have

$$\lim_{n\to\infty}\mathbb{P}_n\bigl(|\widehat p_n-p|\geq\varepsilon\bigr)=0.$$

伯努利大数定律，对任意固定误差 $\varepsilon>0$，样本比例偏离真实成功概率至少 $\varepsilon$ 的概率趋于 $0$。

The Chernoff–Chebyshev–Rubin method

直接对 $\widehat p_n$ 使用 Markov 不等式，只能得到

$$\mathbb{P}(\widehat p_n\geq p+\varepsilon) \leq \frac{\mathbb{E}(\widehat p_n)}{p+\varepsilon} =\frac{p}{p+\varepsilon}.$$

当 $p>0$ 时，这个上界不随 $n$ 减小，无法据此证明大数定律。改进方法是：先对随机变量作非负、单调变换，再应用 Markov 不等式。

Theorem 1.63. Let’s suppose $(\Omega,\mathcal{E},\mathbb{P}_\rho)$ is a discrete probability space, $f \colon \mathbb{R}\to[0,\infty)$ be a non-decreasing function and $X$ is a random variable such that $f(X)\in\mathcal{L}^1(\Omega,\mathbb{P}_\rho)$. Then, for all $\zeta\in\mathbb{R}$ with $f(\zeta)>0$ we have

$$\mathbb{P}_\rho(X\geq\zeta) \leq \mathbb{E}_\rho\{f(X)\}/f(\zeta).$$

因为 $f$ 单调不减，

$$\{X\geq\zeta\}\subseteq\{f(X)\geq f(\zeta)\}.$$

再对非负随机变量 $f(X)$ 应用 Markov 不等式即可。此时无需要求 $X$ 非负，但必须保证 $f(X)$ 非负且可积，分母 $f(\zeta)>0$。

常用变换是 $f(x)=e^{\lambda x}$，其中 $\lambda>0$。只要 $\mathbb{E}(e^{\lambda X})<\infty$，就有

$$\mathbb{P}(X\geq\zeta) \leq e^{-\lambda\zeta}\mathbb{E}(e^{\lambda X}).$$

指数变换的好处是把和变为积：$e^{\lambda\sum_i X_i}=\prod_i e^{\lambda X_i}$。若各 $X_i$ 独立，就能利用 Proposition 1.57 将乘积的期望分解，再选择 $\lambda$ 使上界尽量小。

Hoeffding’s bound and the Kullback–Leibler divergence

Binary Kullback–Leibler divergence

Definition 1.64. Given $p\in(0,1)$ and $q\in[0,1]$, the binary Kullback–Leibler divergence of $q$ with respect to $p$ is

$$\operatorname{kl}(q\|p) :=q\log\left(\frac qp\right) +(1-q)\log\left(\frac{1-q}{1-p}\right)\in[0,\infty),$$

where we use the convention $0\log0:=\lim_{x\searrow0}x\log x=0$ for $q\in\{0,1\}$.

二元 KL 散度比较 $\operatorname{Bern}(q)$ 与 $\operatorname{Bern}(p)$ 两个分布：

• $\operatorname{kl}(q\|p)\geq0$，且仅在 $q=p$ 时为 $0$；
• 一般有 $\operatorname{kl}(q\|p)\neq\operatorname{kl}(p\|q)$，因此它不是通常意义上的距离；
• 固定 $p$ 后，它关于 $q$ 严格凸，在 $q=p$ 处取最小值。

为统一处理越出 $[0,1]$ 的阈值

$$\operatorname{\underline{kl}}(r\|p) :=\operatorname{kl}\bigl(\min\{\max\{r,0\},1\}\|p\bigr), \qquad r\in\mathbb{R},\ p\in(0,1).$$

即先将第一个参数截断到 $[0,1]$。

Tail bounds in terms of KL divergence

Theorem 1.65. Suppose $p\in(0,1)$ and for each $n\geq1$, we have a random variable $\widehat p_n$ on a probability space $(\Omega,\mathcal{E},\mathbb{P})$ such that $n\widehat p_n\sim\operatorname{Bin}(n,p)$. Then, for $\varepsilon>0$ we have

$$\mathbb{P}(\widehat p_n\geq p+\varepsilon) \leq e^{-n\operatorname{\underline{kl}}(p+\varepsilon\|p)} \quad\text{and}\quad \mathbb{P}(\widehat p_n\leq p-\varepsilon) \leq e^{-n\operatorname{\underline{kl}}(p-\varepsilon\|p)}. \qquad (1.18)$$

这是样本比例的上下尾界。对于固定的 $p$ 和非零偏差，右边随样本量 $n$ 指数衰减；KL 散度给出该上界的指数系数。它控制尾概率，并不等于实际尾概率。证明需要 Lemma 1.66 和 Lemma 1.67。

Lemma 1.66. Suppose $p\in(0,1)$ and for each $n\geq1$, we have a random variable $\widehat p_n$ on a probability space $(\Omega,\mathcal{E},\mathbb{P})$ such that $n\widehat p_n\sim\operatorname{Bin}(n,p)$. Given $q\in(p,1)$ and $\lambda>0$,

$$\frac1n\log\mathbb{P}(\widehat p_n\geq q) \leq\log\{pe^\lambda-p+1\}-\lambda q. \qquad (1.19)$$

推导关键： 将 $n\widehat p_n$ 表示为 $n$ 个独立的 $\operatorname{Bern}(p)$ 变量之和。对 $\widehat p_n$ 使用变换 $x\mapsto e^{n\lambda x}$，得到

$$\mathbb{P}(\widehat p_n\geq q) \leq e^{-n\lambda q}\mathbb{E}(e^{n\lambda\widehat p_n}). \qquad (1.20)$$

利用独立性，

$$\begin{aligned} \mathbb{E}(e^{n\lambda\widehat p_n}) &=\mathbb{E}\left(\prod_{i=1}^n e^{\lambda X_i}\right)\\ &=\prod_{i=1}^n\mathbb{E}(e^{\lambda X_i}) =(1-p+pe^\lambda)^n. \end{aligned}$$

这里 $\mathbb{E}(e^{\lambda X_i})=(1-p)e^0+pe^\lambda$，且变量有界，因此这些期望都有限。代回并取对数，就得到 Lemma 1.66。

Lemma 1.67. Given $p\in(0,1)$ and $q\in(p,1)$ let $\psi_{p,q}\colon\mathbb{R}\to\mathbb{R}$ be the function given by

$$\psi_{p,q}(\lambda):=\log(1-p+pe^\lambda)-\lambda q,$$

for all $\lambda\in\mathbb{R}$. Then, we have

$$\inf\{\psi_{p,q}(\lambda):\lambda\in(0,\infty)\} =-\operatorname{\underline{kl}}(q\|p).$$

优化参数： 对 $\lambda$ 求导，

$$\psi_{p,q}'(\lambda) =\frac{pe^\lambda}{1-p+pe^\lambda}-q, \qquad \psi_{p,q}''(\lambda) =\frac{p(1-p)e^\lambda}{(1-p+pe^\lambda)^2}>0.$$

唯一最小点满足

$$\lambda^\star=\log\frac{q(1-p)}{p(1-q)}>0, \qquad \psi_{p,q}(\lambda^\star)=-\operatorname{\underline{kl}}(q\|p).$$

所以对 $p<q<1$，

$$\mathbb{P}(\widehat p_n\geq q) \leq e^{-n\operatorname{\underline{kl}}(q\|p)}.$$

取 $q=p+\varepsilon$ 就得到上尾界；下尾界可对 $1-X_i\sim\operatorname{Bern}(1-p)$ 使用同一结论，并利用 $\operatorname{kl}(1-q\|1-p)=\operatorname{kl}(q\|p)$。在端点 $q=1$ 或 $q=0$，事件分别要求全部成功或全部失败，概率为 $p^n$ 或 $(1-p)^n$；阈值超出 $[0,1]$ 时，相应尾事件为空。这些情况一起给出 Theorem 1.65。

Hoeffding’s bound

Theorem 1.68. Suppose $p\in[0,1]$ and for each $n\geq1$, we have a random variable $\widehat p_n$ on a probability space $(\Omega,\mathcal{E},\mathbb{P})$ such that $n\widehat p_n\sim\operatorname{Bin}(n,p)$. Then, for $\varepsilon>0$ we have

$$\mathbb{P}\bigl(|\widehat p_n-p|\geq\varepsilon\bigr) \leq 2e^{-2n\varepsilon^2}. \qquad (1.23)$$

这个双侧界更简洁，且右边不含未知的 $p$。与 KL 形式相比，它用一个统一的二次下界替代散度，通常会更宽松。

Lemma 1.69. Given any $p\in(0,1)$ and $q\in[0,1]$ we have $\operatorname{kl}(q\|p)\geq2(q-p)^2$.

令 $g_p(q)=\operatorname{kl}(q\|p)-2(q-p)^2$。因为

$$g_p(p)=g_p'(p)=0, \qquad g_p''(q)=\frac1{q(1-q)}-4\geq0 \quad (0<q<1),$$

所以 $g_p$ 在 $p$ 处取得最小值 $0$，端点由连续性得到。这就给出了 Lemma 1.69。

当 $p\in(0,1)$ 且相应阈值位于 $[0,1]$ 内时，将该引理代入 Theorem 1.65，得到

$$\mathbb{P}(\widehat p_n\geq p+\varepsilon)\leq e^{-2n\varepsilon^2}, \qquad \mathbb{P}(\widehat p_n\leq p-\varepsilon)\leq e^{-2n\varepsilon^2}.$$

阈值越出 $[0,1]$ 时，相应事件概率为 $0$；$p\in\{0,1\}$ 时，$\widehat p_n=p$ 几乎必然成立。因此两个单侧界对所有 $p\in[0,1]$、$\varepsilon>0$ 都成立。最后由并集界，

$$\begin{aligned} \mathbb{P}(|\widehat p_n-p|\geq\varepsilon) &\leq \mathbb{P}(\widehat p_n\geq p+\varepsilon) +\mathbb{P}(\widehat p_n\leq p-\varepsilon)\\ &\leq2e^{-2n\varepsilon^2}. \end{aligned}$$

固定 $\varepsilon>0$ 后，右边随 $n\to\infty$ 趋于 $0$，因此 Theorem 1.68 直接推出 Theorem 1.62。大数定律给出极限结论，Hoeffding 界进一步量化有限样本下的误差概率。

补充应用：样本量与误差。 给定允许的失败概率 $\delta\in(0,1)$，若

$$n\geq\frac{\log(2/\delta)}{2\varepsilon^2},$$

则 $\mathbb{P}(|\widehat p_n-p|\geq\varepsilon)\leq\delta$。例如，要求误差小于 $0.05$ 的概率至少为 $0.95$，$n\geq738$ 是一个充分条件。等价地，固定 $n$ 时，以至少 $1-\delta$ 的概率有

$$|\widehat p_n-p| <\sqrt{\frac{\log(2/\delta)}{2n}}.$$

因此，在固定失败概率下，将保证的误差幅度减半，需要将样本量增至原来的四倍。上述保证依赖于独立、成功概率相同的伯努利试验假设。