【信息论】AEP(渐进均分性)&随机过程熵率&数据压缩

AEP

$$-\frac{1}{n}\log p(X_1,X_2,...,X_n)\rightarrow H(X),依概率$$

证明很简单。就是X_i与X_j是相互独立的，然后就可以把联合分布展开出来，就变成均值公式了，依概率后就是期望了

典型集

是序列$(x_1,x_2,…,x_n)\in \mathscr{X}$的集合

$$H(X)-\epsilon\le -\frac{1}{n}\log p(x_1,x_2,...,x_n)\le H(X)+\epsilon$$

典型集的概率近似为1

典型集的大小为$2^{n(H+\epsilon)}$
于是典型序列需要${n(H+\epsilon)}+2\approx nH$bit来描述(每个变量都约需要H来描述,个数为n的序列就是nH)
加2是因为
1.为了防止非整数长度，加了个1
2.为了表示是典型集，加一个标志位

最小概率集

$$a_n\doteq b_n$$表示 $$\lim_{n\rightarrow n}\frac{1}{n}\log\frac{a_n}{b_n}=0$$

最小概率集

$$|B_\delta^{(n)}|\doteq 2^{nH}$$

随机过程熵率

平稳随机过程:
联合分布随时间下标位移不变
（就是某序列的联合分布，序列里全部随机变量下标加上相同时间后，这个联合分布的概率还是不变）

求解平稳概率

解$\mu P=\mu$
即可。$P$是概率转移矩阵
$\mu$是平稳概率矩阵。要求的是$\mu$
$\sum\mu_i=1$
某时刻状态n的熵

$$H(X_n)=H(\mu_1,\mu_2,...)$$

熵率

两种定义方式 $H(\mathscr{X})=\lim_{n\rightarrow\infty}\frac{1}{n}H(X_1,X_2,...,X_n)$ $H'(\mathscr{X})=\lim_{n\rightarrow\infty}H(X_n|X_1,X_2,...,X_{n-1})$ 对于平稳随机过程两者相等

马尔科夫链函数(隐马尔可夫模型)

$$H(Y_n|X_{n-1},...,Y_1,X_1)\le H(\mathscr{Y}) \le H(Y_n|Y_{n-1},...,Y_1)$$

Y_i是X_i加了个映射。服从p(y|x)
可以看到
1.H(y)的不确定度小于”知道前n-1个状态下,y_n状态的不确定度””
2.但是H(y)的不确定度又大于知道前n-1个y而且又知道x_1的情况下y_n状态的不确定度

数据压缩

Kraft不等式

对于即时码（可以自动划分的）
有

$$\sum D^{-l_i}\le 1$$

证明过程就是画颗树。然后剪枝，计算就行

香农码

非最优
平均码长$L=\sum p_il_i$
香农取$l_i=log_D\frac{1}{p_i}向上取整$

Huffman码

最优

偏码

如果真实分布为p(x)
却使用了非真实分布q(x)
那么不等式需要加个KL散度作为惩罚项

$$H(p)+D(p||q)\le L\le H(p)+D(p||q)+1$$

随机过程

对于平稳过程。L_n码长依概率逼近于熵率
否则
$\frac{H(X_1,X_2,…,X_n)}{n}\le L_n\le\frac{H(X_1,X_2,…,X_n)}{n}+\frac{1}{n}$

博弈论

双倍率

$$W(b,p)=\sum_{k=1}^mp_k\log b_ko_k$$

b表示投资比例向量。合为1
p_k表示第k个博弈事件成功概率
o_k表示k th博弈成功收益(为投资比例的相对值)

按比例博弈是最优的

$$W*(p)=\max_b W(b,p)=\sum p_i\log o_i-H(p)$$

移向可以发现存在守恒定律
双倍率和熵率之和为常数

边信息
由边信息Y，导致的双倍率增量为

$$\Delta W=I(X;Y)$$