对于一个没有限制的、取值为全体正整数的离散随机变量X，考虑一下两个问题：

1. （无上界）是否存在一个$X_{n}$使得序列熵的极限为无穷：$\lim_{ n \to \infty } \mid H(X_{n})\mid = \infty$
2. 是否存在一个分布使得$H(X)=\infty$

二者的答案均为肯定的。第一个的存在性是显然的，对于第二个，下面我们可以证明，$p(n)\sim \frac{1}{n\ln^2 n}$是满足条件的一个概率分布。

$$\begin{align} \sum_{n=1}^\infty p(n) & \sim \sum_{n=1}^\infty \frac{1}{n\ln^2n}\sim \int _{1}^\infty \frac{1}{x\ln^2x}\, dx = \text{Const} \\ \sum_{n=1}^\infty p(n) \ln p(n) & \sim \sum_{n} \frac{1}{n\ln^2n} \ln \frac{1}{n\ln^2n} \\ & = \sum_{n} \frac{-\ln n-2\ln \ln n}{n\ln^2n} \\ & \sim \sum_{n} -\frac{1}{n\ln n} \\ & \sim \int _{1}^\infty -\frac{1}{x\ln x} \, dx \to -\infty \end{align}$$

式子中$\sim$表示一种估计，即左右两侧可能差一个常数系数，或差为常数，总之不影响结果的敛散性。其中还用到Cauchy积分判别法：

[!theorem] Cauchy判别法
对于一个定义在$[0,\infty )$上的正项递减函数$f(x)$,级数$\sum_{n=1}^\infty f(n)$和$\int _{1}^\infty f(x)\, dx$具有相同敛散性。

现考虑约束：随机变量具有均值$\mu$，此时最大熵分布是怎样的？
通过简单的变分法可以推出:

$$p_{i} \sim Ce^{-\lambda i}$$

对于任意的其他分布$g_{i}$，通过交叉熵同样可以证明

$$H(g\mid \mid p) = H(g)-H(p) \geq 0$$

即指数分布是该约束下的最大熵分布。

Lecture 9: Fisher Information and Cramer-Ral Inequality

概率统计中常见到Parameter Estimation问题。对于参数估计的好坏有一些准则，例如无偏性
Unbiased Parameter Estimation
Consider a sample $X=(X_{1},\dots,X_{n})$ i.i.d. $X$ has a density function $f(X;\theta) = \prod_{i=1}^n f(X_{i};\theta)$, for i.i.d
We want to estimate $\theta$ from X. By an estimator $\phi:X\to\theta$
我们希望这个估计是无偏的，也就是从样本得到的估计的期望等于真实期望：$E[\phi(X)] = \theta$
同时，还希望从样本得到的估计的方差越小越好。

Fisher Information

[!definition] Scure function
For a sample $X=(X_{1},\dots,X_{n})$, let $f(\cdot,0)$ be the probability distribution function.The scure function is defined as
$$
S\left( X;\theta\right) = \frac{ \partial }{ \partial \theta } \ln f(X;\theta)
$$

容易证明$E[S(X;\theta)] = 0$

\fcolorbox{yellow}{}{Proof}

$$\begin{align} \mathbb{E} S & = \int f(x,\theta) S(X,\theta) \, dx \\ & = \int \frac{ \partial }{ \partial \theta } f(x,\theta) \, dx \\ & = \frac{ \partial }{ \partial \theta } \int f(x,\theta) \, dx \\ & = 0 \end{align}$$

[!definition] Fisher information
Fisher info of param $\theta$ with a sample $X$ is defined as
$$
I(\theta) = E[S^2(X;\theta)] = Var[S(X;\theta)] = \int f(X;\theta) \left( \frac{ \partial }{ \partial \theta } \ln f(X;\theta) \right)^2 , dx
$$

容易证明：$I(\theta) = -E\left[ \frac{ \partial ^2 \ln f(X;\theta) }{ \partial \theta^2 } \right]$ 。

[!theorem] Cramer-Rao Inequality
For any unbiased estimator $\phi: X\to \mathbb{R}$ of $\theta_{j}$, we have $Var(\phi(X))\geq \frac{1}{I(\theta)}$

[!Proof]
要证明的式子等价于 $Var(\phi(X)) Var (S(X;\theta)) \geq 1$。这可以根据柯西史瓦兹不等式来证明：
定义内积$(u,v) = \sum_{i} u(x_{i})v(x_{i})f(x_{i})$，于是$(u,u)(v,v)\geq \mid(u,v) \mid^2$
$$
\begin{align}
原式 &= \sum_{i} S^2 (X_{i};\theta) f(X_{i}) \sum_{i} (\phi(X_{i})-\theta)^2 f(X_{i}) \ \
& \geq \mid \sum_{i} S(X_{i};\theta) (\phi(X_{i}-\theta))f(X_i)\mid^2 \
& = |\sum_{i} \frac{ \partial f(X;\theta) }{ \partial \theta } (\phi(X_{i})-\theta)|^2 \
& = |\partial \theta / \partial \theta -\theta \partial 1 / \partial \theta|^2 = 1
\end{align}
$$

Fisher information for multiple parameters:
Define Score Function as a random vector:

$$\vec{S}(X;\vec{\theta}) = \nabla_{\theta} \ln f(X;\vec{\theta})$$

易证明$E(S(X;\vec{\theta})) = \vec{0}$，定义Fisher information为S协方差矩阵矩阵

$$I(\vec{\theta}) = E[\vec{S}(X;\vec{\theta}) S(\vec{}X;\vec{\theta})^T] = Cov(\vec{S}(X;\vec{\theta}))$$

高维情形下，Fisher Information的二阶导数写法可换为函数的Hessian Matrix：

$$I(\vec{\theta}) = -E \left[\nabla ^2 \ln f(X;\theta)\right]$$

协方差矩阵为$Cov(\phi(X))$是一个半正定的矩阵。
Cramer-Rao 不等式成为：

$$Cov(\phi(X)) \geq I(\theta)^{-1}$$

其中$\geq$并不是一般的实数序关系，而是半正定矩阵的序关系，即对半正定矩阵$A,B$，有：$A\geq B\implies A-B\geq 0$，$A-B$为半正定矩阵

4.18 Channel Coding

信源编码目标是将码元中的冗余去除；而在信道传输时信道会引入噪声，从而有一定概率发生错误。信道编码目标是通过高度结构化的方式加入冗余，使编码之间的距离尽可能大。
如果允许信道发生$t$ bits error，那么任意两个codewords之间的距离必须大于等于$2t+1$

Leave a Comment

Plain Markdown

Post Comment

Markdown Preview