台交大信息论 Lecture 3

课程主页：https://ocw.nctu.edu.tw/course_detail-c.php?bgid=8&gid=0&nid=612&pid=973

http://shannon.cm.nctu.edu.tw/it18.htm

老师主页：http://shannon.cm.nctu.edu.tw/

课程视频：https://www.youtube.com/playlist?list=PLj6E8qlqmkFsWS54o6gNWeDGXeI7c3eUd

这次回顾第三讲，主要回顾概率以及随机过程的知识，对应视频5-7，概率的一部分内容从略。

随机过程的统计属性

$\mathbb T-$不变以及遍历性

事件$E$关于偏移变换$\mathbb{T}: \mathcal{X}^{\infty} \rightarrow \mathcal{X}^{\infty}$被称为$\mathbb T-$不变，如果

$\mathbb{T} E \subseteq E$

其中

$\mathbb{T} E:=\{\mathbb{T} \boldsymbol{x}: \boldsymbol{x} \in E\}, \mathbb{T} \boldsymbol{x}:=\mathbb{T}\left(x_{1}, x_{2}, x_{3}, \ldots\right)=\left(x_{2}, x_{3}, \ldots\right)$

如果$E$为$\mathbb T-$不变，那么

$\mathbb{T} E \subseteq E, \mathbb{T}^2 E \subseteq \mathbb{T} E, \ldots, \mathbb{T}^{k+1} E \subseteq \mathbb{T}^k E$

即

$\cdots \subseteq \mathbb{T}^{3} E \subseteq \mathbb{T}^{2} E \subseteq \mathbb{T} E \subseteq E$

补充定义$\mathbb T^{-1}$：

$\mathbb{T}^{-1} E:=\left\{\boldsymbol{x} \in \mathcal{X}^{\infty}: \mathbb{T} \boldsymbol{x} \in E\right\}$

如果满足如下性质（遍历性，对应的集合称为遍历集）

$\mathbb T^{-1}E= E$

注意此时有

$\mathbb{T} E=\mathbb{T}\left(\mathbb{T}^{-1} E\right)=E$

持续作用$\mathbb T$可得

$\cdots=\mathbb{T}^{-2} E=\mathbb{T}^{-1} E=E=\mathbb{T} E=\mathbb{T}^{2} E=\cdots$

例子

$\begin{aligned} E:=\left\{\left(x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1, \ldots\right),\left(x_{1}=0, x_{2}=1, x_{3}=1, x_{4}=1, \ldots\right)\right.,\left.\left(x_{1}=0, x_{2}=0, x_{3}=1, x_{4}=1, \ldots\right)\right\} \end{aligned}$

那么

$\mathbb T E =\left\{\left(x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1, \ldots\right),\left(x_{1}=0, x_{2}=1, x_{3}=1, x_{4}=1, \ldots\right)\right.\left.\right\} \subseteq E$

所以$E$是$\mathbb T-$不变。

随机过程的性质

假设随机过程为

$\boldsymbol{X}=\left\{X_{1}, X_{2}, \ldots\right\}$

无记忆：如果随机变量$\boldsymbol X$的序列是独立同分布（i.i.d.），则称一个随机过程$\boldsymbol X$是无记忆的。
平稳过程：如果每个序列或事件的概率分布随偏移不变，则该过程称为平稳过程（或严平稳过程）。
遍历过程：如果$\mathcal{F}_{X}$中的任何遍历集（满足（$\mathbb T^{-1}E= E$））具有$1$或$0$的概率，则该过程称为遍历过程。此定义不是很直观，但是某些解释和示例可能会有所启发。

例子

假设$X_{1}, X_{2}, \cdots, X_{n}, \cdots$是遍历过程，其中$X_n \in \{0,1\}$。令$\Omega$是所有单边零一序列的集合。对$\alpha \in[0,1]$，定义

$\begin{array}{l} \bar{E}_{n}(\alpha):=\left\{x \in\{0,1\}^{\infty}: \alpha \leq \limsup _{m \rightarrow \infty} \frac{x_{1}+\cdots+x_{m}}{m}<\alpha+\frac{1}{n}\right\} \\ \underline{E}_{n}(\alpha):=\left\{x \in\{0,1\}^{\infty}: \alpha \leq \liminf _{m \rightarrow \infty} \frac{x_{1}+\cdots+x_{m}}{m}<\alpha+\frac{1}{n}\right\} \end{array}$

可以证明，$\bar{E}_{n}(\alpha)$和$\underline{E}_{n}(\alpha)$都是遍历集，即

$\begin{aligned} \bar{E}_{n}(\alpha)&=\mathbb{T}^{-1} \bar{E}_{n}(\alpha)\\ \underline{E}_{n}(\alpha)&=\mathbb{T}^{-1} \underline{E}_{n}(\alpha) \end{aligned}$

上述事实是由于上确界和下确界的极限不会因为偏移改变。

逐点遍历定理

考虑一个离散时间平稳随机过程，$\boldsymbol{X}=\left\{X_{n}\right\}_{n=1}^{\infty}$。对于具有有限均值（即$\left|E\left[f\left(X_{n}\right)\right]\right|<\infty$）的$\mathbb R$上的实值函数$f(.)$，存在一个随机变量$\boldsymbol Y$使得

$\lim _{n \rightarrow \infty} \frac{1}{n} \sum_{k=1}^{n} f\left(X_{k}\right)=Y 以概率1成立$

如果该随机过程具有遍历性，那么

$\lim _{n \rightarrow \infty} \frac{1}{n} \sum_{k=1}^{n} f\left(X_{k}\right)=E\left[f\left(X_{1}\right)\right] 以概率1成立$

该定理说明平稳性加遍历性可以导出我们所熟悉的大数定律。

马尔可夫链

定义

$3$个随机变量$X, Y, Z$是马尔可夫链，如果

$P_{X, Y, Z}(x, y, z)=P_{X}(x) \cdot P_{Y | X}(y | x) \cdot P_{Z | Y}(z | y)$

即

$P_{Z | X, Y}(z | x, y)=P_{Z | Y}(z | y)$

这通常表示为

$X \rightarrow Y \rightarrow Z$

利用定义不难得出

$P_{X, Z | Y}(x, z | y)=P_{X | Y}(x | y) \cdot P_{Z | Y}(z | y)$

这说明给定$Y$，$X,Z$条件独立，利用这个事实可得$X,Z$对称，所以马尔可夫性也记作

$X \leftrightarrow Y \leftrightarrow Z$

$k$阶马尔可夫性

随机变量序列$\left\{X_{n}\right\}_{n=1}^{\infty}=X_{1}, X_{2}, X_{3}, \ldots$满足$k$阶马尔可夫性，如果

$\begin{array}{l} \operatorname{Pr}\left[X_{n}=x_{n} | X_{n-1}=x_{n-1}, \ldots, X_{1}=x_{1}\right] =\operatorname{Pr}\left[X_{n}=x_{n} | X_{n-1}=x_{n-1}, \ldots, X_{n-k}=x_{n-k}\right] \end{array}$

每个$x_{n-k}^{n-1}:=\left(x_{n-k}, x_{n-k+1}, \ldots, x_{n-1}\right) \in \mathcal{X}^{k}$被称为马尔可夫链在时间$n$的状态。

不可约

马尔可夫链是不可约的，如果对所有$x^{k}, y^{k} \in \mathcal{X}^{k}$，存在$j\ge 1$，使得

$\operatorname{Pr}\left\{X_{j}^{k+j-1}=x^{k} | X_{1}^{k}=y^{k}\right\}>0$

时不变

马尔可夫链被称为时不变或时齐，如果对每个$n>k$，

$\begin{array}{l} \operatorname{Pr}\left[X_{n}=x_{n} | X_{n-1}=x_{n-1}, \ldots, X_{n-k}=x_{n-k}\right] =\operatorname{Pr}\left[X_{k+1}=x_{k+1} | X_{k}=x_{k}, \ldots, X_{1}=x_{1}\right] \end{array}$

所以一阶时齐马尔可夫链可以由转移概率

$\left[\operatorname{Pr}\left\{X_{2}=x_{2} | X_{1}=x_{1}\right\}\right]_{|\mathcal{X}| \times|\mathcal{X}|}$

以及初始状态分布$P_{X_{1}}(x)$决定。

非周期性

在一阶马尔可夫链中，$x\in \mathcal X$的周期$d(x)$定义为
$d(x):=\operatorname{gcd}\left\{n \in\{1,2,3, \ldots\}: \operatorname{Pr}\left\{X_{n+1}=x | X_{1}=x\right\}>0\right\}$
如果对任意$n$，$\operatorname{Pr}\left\{X_{n+1}=x | X_{1}=x\right\}=0$，我们说状态$x$有无限周期，记为$d(x)=\infty$
如果$d(x)=1$，则称状态$x$是非周期的；如果$d(x)>1$，则称状态$x$是周期的。
一阶马尔可夫链被称为非周期的，如果所有状态都是非周期的，即
$\operatorname{gcd}\left\{n \in\{1,2,3, \ldots\}: \operatorname{Pr}\left\{X_{n+1}=x | X_{1}=x\right\}>0\right\}=1 \quad \forall x \in \mathcal{X}$

平稳分布

对于一阶时不变马尔可夫链，$\mathcal X$上的分布$\pi(.)$是平稳分布，如果对每个$y \in \mathcal{X}$，

$\pi(y)=\sum_{x \in \mathcal{X}} \pi(x) \operatorname{Pr}\left\{X_{2}=y | X_{1}=x\right\}$

几者的关系

随机变量序列的收敛

几种收敛性

逐点收敛

普通序列的收敛性，记作

$X_{n} \stackrel{p \cdot w.}{\longrightarrow} X$

几乎处处收敛

$X_{n} \stackrel{a . s .}{\longrightarrow} X \equiv \operatorname{Pr}\left\{\lim _{n \rightarrow \infty} X_{n}=X\right\}=1$

依概率收敛

$X_{n} \stackrel{p}{\longrightarrow} X \quad \equiv \quad(\forall \gamma>0) \lim _{n \rightarrow \infty} \operatorname{Pr}\left\{\left|X_{n}-X\right|<\gamma\right\}=1$

$r$阶收敛

$X_{n} \stackrel{L_{r}}{\longrightarrow} X \quad \equiv \quad \lim _{n \rightarrow \infty} E\left[\left|X_{n}-X\right|^{r}\right]=0$

依分布收敛

$X_{n} \stackrel{d}{\longrightarrow} X \quad \equiv \lim _{n \rightarrow \infty} F_{X_{n}}(x)=F_{X}(x) 对F_X(x)的每个连续点$

几者的关系

收敛的唯一性

如果$X_{n} \stackrel{p . w.}{\longrightarrow} X,X_{n} \stackrel{p . w.}{\longrightarrow} Y$，那么
$(\forall \omega \in \Omega) \quad X(\omega)=Y(\omega)$
$X_{n} \stackrel{a . s .}{\longrightarrow} X, X_{n} \stackrel{a . s .}{\longrightarrow} Y$或$X_{n} \stackrel{p}{\longrightarrow} X, X_{n} \stackrel{p}{\longrightarrow} Y$或$X_{n} \stackrel{L_{r}}{\longrightarrow} X, X_{n} \stackrel{L_{r}}{\longrightarrow} Y$，那么
$\operatorname{Pr}\{X=Y\}=1$
$X_{n} \stackrel{d}{\longrightarrow} X , X_{n} \stackrel{d}{\longrightarrow} Y$，那么对所有$x$，$F_X(x)=F_Y(y)$

收敛定理

单调收敛定理

$\left.\begin{array}{l} (i) X_{n} \stackrel{a . s .}{\rightarrow} X \\ (i i)(\forall n) Y \leq X_{n} \leq X_{n+1} \\ (i i i) E[|Y|]<\infty \end{array}\right\} \Rightarrow X_{n} \stackrel{L_{1}}{\longrightarrow} X \Rightarrow E\left[X_{n}\right] \rightarrow E[X]$

控制收敛定理

$\left.\begin{array}{l} (i) X_{n} \stackrel{a . s .}{\rightarrow} X \\ (i i)(\forall n)\left|X_{n}\right| \leq Y \\ (i i i) E[|Y|]<\infty \end{array}\right\} \Rightarrow X_{n} \stackrel{L_{1}}{\longrightarrow} X \Rightarrow E\left[X_{n}\right] \rightarrow E[X]$

大数定律

弱大数定理

如果$\left\{X_{n}\right\}_{n=1}^{\infty}$是均值都为$E\left[X_{i}\right]=\mu$的不相关序列，并且

$\lim _{n \rightarrow \infty} \frac{1}{n^{2}} \sum_{i=1}^{n} \operatorname{Var}\left[X_{i}\right]=0$

那么

$\frac{X_{1}+\cdots+X_{n}}{n} \stackrel{p}{\longrightarrow} \mu$

证明：

$\operatorname{Pr}\left\{\left|\frac{1}{n} \sum_{i=1}^{n} X_{i}-\mu\right| \geq \varepsilon\right\} \leq \frac{1}{n^{2} \varepsilon^{2}} \sum_{i=1}^{n} \operatorname{Var}\left[X_{i}\right]$

强大数定律

如果$\left\{X_{n}\right\}_{n=1}^{\infty}$均值都为$E\left[X_{n}\right]=\mu$的独立随机变量，如果

$\sum_{i=1}^{\infty} \frac{\operatorname{Var}\left[X_{i}\right]}{i^{2}}<\infty$

那么

$\frac{X_{1}+\cdots+X_{n}}{n} \stackrel{a . s}{\longrightarrow} \mu$

中心极限定理

如果$\left\{X_{n}\right\}_{n=1}^{\infty}$是独立同分布随机变量序列，均值为$\mu$，方差为$\sigma^2$，那么

$\frac{1}{\sqrt{n}} \sum_{i=1}^{n}\left(X_{i}-\mu\right) \stackrel{d}{\longrightarrow} Z \sim \mathcal{N}\left(0, \sigma^{2}\right)$

凸（凹）性，琴生不等式

凸集

$\mathcal{O} \subset \mathbb{R}^{m}$是凸集，如果对$\mathcal O$中每个$\underline{x}=\left(x_{1}, x_{2}, \cdots, x_{m}\right)^{T}$以及$\underline{y}=\left(y_{1}, y_{2}, \cdots, y_{m}\right)^{T}$，对任意$0\le \lambda \le 1$，都有$\lambda \underline{x}+(1-\lambda) \underline{y} \in \mathcal{O}$

凸性

考虑凸集$\mathcal{O} \subset \mathbb{R}^{m}$，$f: \mathcal{O} \rightarrow \mathbb{R}$在集合$\mathcal O$上是凸的，如果对$\mathcal O$中每个$\underline{x}, \underline{y}$以及$0 \leq \lambda \leq 1$，

$f(\lambda \underline{x}+(1-\lambda) \underline{y}) \leq \lambda f(\underline{x})+(1-\lambda) f(\underline{y} )$

严格凸，如果等号成立当且仅当$\lambda =0$或$\lambda =1$。

凹性

函数$f$是凹的，如果$-f$是凸的。

琴生不等式

考虑凸集$\mathcal{O} \subset \mathbb{R}^{m}$，$f: \mathcal{O} \rightarrow \mathbb{R}$在集合$\mathcal O$上是凸的，如果$\underline{X}=\left(X_{1}, X_{2}, \cdots, X_{m}\right)^{T}$是$m$维随机变量，那么

$E[f(\underline{X})] \geq f(E[\underline{X}])$

拉格朗日乘数法和KKT条件

考虑优化问题

$\min _{x \in \mathcal{Q}} f(x)$

其中

$\mathcal{Q}:=\left\{x \in \mathcal{X}: g_{i}(\boldsymbol{x}) \leq 0 \text { for } 1 \leq i \leq m \text { and } h_{i}(\boldsymbol{x})=0 \text { for } 1 \leq j \leq \ell\right\}$

考虑对偶问题

$L(\boldsymbol{\lambda}, \boldsymbol{\nu}):=\min _{\boldsymbol{x} \in \mathcal{X}}\left(f(\boldsymbol{x})+\sum_{i=1}^{m} \lambda_{i} g_{i}(\boldsymbol{x})+\sum_{j=1}^{\ell} \nu_{j} h_{j}(\boldsymbol{x})\right)=\min _{\boldsymbol{x} \in \mathcal{X}} L(\boldsymbol{x} ; \boldsymbol{\lambda}, \boldsymbol{\nu})$

其中$\lambda=\left(\lambda_{1}, \ldots, \lambda_{m}\right),\nu=\left(\nu_{1}, \ldots, \nu_{\ell}\right)$被称为拉格朗日乘子，$L(\boldsymbol{\lambda}, \boldsymbol{\nu})$被称为拉格朗日对偶函数。

当$\lambda_i\ge 0, 1\le i\le m$，

$L(\boldsymbol{\lambda}, \boldsymbol{\nu}) \leq \min _{\boldsymbol{x} \in \mathcal{Q}}\left(f(\boldsymbol{x})+\sum_{i=1}^{m} \lambda_{i} g_{i}(\boldsymbol{x})+\sum_{j=1}^{\ell} \nu_{j} h_{j}(\boldsymbol{x})\right) \leq \min _{\boldsymbol{x} \in \mathcal{Q}} f(\boldsymbol{x})$

在强对偶条件下，上述不等号变成等号，对应的参数为非负$\tilde {\boldsymbol \lambda}$和$\tilde {\boldsymbol \nu}$，那么

$\begin{aligned} f\left(\boldsymbol{x}^{*}\right) &=\min _{\boldsymbol{x} \in \mathcal{Q}} f(\boldsymbol{x}) \\ &=L(\tilde{\boldsymbol{\lambda}}, \tilde{\boldsymbol{\nu}})\\ &=\min _{\boldsymbol{x} \in \mathcal{X}}\left(f(\boldsymbol{x})+\sum_{i=1}^{m} \tilde{\lambda}_{i} g_{i}(\boldsymbol{x})+\sum_{j=1}^{\ell} \tilde{\nu}_{j} h_{j}(\boldsymbol{x})\right) \\ & \leq f\left(\boldsymbol{x}^{*}\right)+\sum_{i=1}^{m} \tilde{\lambda}_{i} g_{i}\left(\boldsymbol{x}^{*}\right)+\sum_{j=1}^{\ell} \tilde{\nu}_{j} h_{j}\left(\boldsymbol{x}^{*}\right) \\ & \leq f\left(\boldsymbol{x}^{*}\right) \end{aligned}$

这说明在强对偶条件下，$f(x)$的最小值$f\left(\boldsymbol{x}^{*}\right)$和$L(\tilde{\boldsymbol{\lambda}}, \tilde{\boldsymbol{\nu}})$相同。

KKT条件

在KKT条件下，强对偶性成立，这里有如下前提：

$f(\cdot),\left\{g_{i}(\cdot)\right\}_{i=1}^{m}$都是凸的，$\left\{h_{j}(\cdot)\right\}_{j=1}^{\ell}$是仿射函数，这些函数可微。

KKT条件：

$\left\{\begin{array}{ll} g_{i}(\boldsymbol{x}) \leq 0, \quad \lambda_{i} \geq 0, \quad \lambda_{i} g_{i}(\boldsymbol{x})=0 & i=1, \ldots, m \\ h_{j}(\boldsymbol{x})=0 & j=1, \ldots, \ell \\ \frac{\partial L}{\partial x_{k}}(\boldsymbol{x} ; \boldsymbol{\lambda}, \boldsymbol{\nu})=\frac{\partial f}{\partial x_{k}}(\boldsymbol{x})+\sum_{i=1}^{m} \lambda_{i} \frac{\partial g_{i}}{\partial x_{k}}(\boldsymbol{x})+\sum_{j=1}^{\ell} \nu_{j} \frac{\partial h_{j}}{\partial x_{k}}(\boldsymbol{x})=0 & k=1, \ldots, n \end{array}\right.$