Codes & Extensions:

Let $S,T$ be two finite sets, called the source and target alphabets....

0314

L4: Joint Entropy,Conditional Entropy, Mutual info & KL Divergence

条件熵
$H(Y\mid X=x_{i})$ ：当已知 $X=x_{i}$ 时，Y的熵值

对上式对 $X=x_{i}$ 的概率加权相加，得到的就是条件熵$H(Y\mid X)=\sum_{j}p(x_{j})H(Y\mid X=x_{j}) = \sum_{i,j}p...

0321

Differential Entropy
Definition:

$h(x) = -\int _{-\infty }^{\infty} f(x)\log f(x) \, dx$

这个Entropy与按 $\Delta$ 做间隔，对连续变量做离散化之后的熵 $H(X_{\Delta})$ 有联系：
$$
H(X_{\Delta}) - \log \frac{1}{\Delta} \approx ...

0404

decision problem: $L\subset \{ 0,1 \}^*$
不存在一个算法判定 $x$ 是否属于 $L$

如何证明Komogorov Complexity是不可计算问题？
给定一个bit 串，找出生成该比特串的最小程序长度

$\exists$ program $p$ , $\forall s\in \{0,1\}^*$ , $p(s)=K(s)$ ,其中K表示串s的Komogorov...

0411,0418

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

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

二者的答案均为肯定的。第一个的存在性是显然的，对于第二个，下面我们可以证明，$p(n)\sim \fr...

0425

估计 $C_{m}^k$ 的值：Chernoff bound

对独立同分布的随机变量 $X_{0},X_{1},X_{2},\dots X_{n}$ Bernoulli distribution: $E(X) = p,0\leq x\leq 1$
$$
P\left( \frac{1}{m} \sum_{i=1}^m X_{i} - p \geq \epsilon \right) \leq e^{-...

Intro to Info theory

假设正确概率分布是 $P$ ，猜测分布是 $Q$ ，得到 $N$ 个样本点后，得到结果是 $p_{i}N$ 个结果 $i$ ，从而得到我们所看到的概率的结果是$\mathcal{P}=\prod_{i=1}^{N}q_{i}^{p_{i}N} \frac{N!}{\prod_{j=1}^{N} (p_{j}N)!}\sim 2^{-N \sum_{i}p_{i}\left(\log p_{i}- \log q_{i}...

第一章 Introduction&Preview

随机变量X的熵： $H(X) = -\sum p(x)\log_{2}p(x)$ ， $H(X)$ 是描述信息量比特数的下限。

信息论中的信息熵和统计物理中的熵紧密相关。如果我们画出n个独立同分布的随机变量序列，则每个序列出现的概率将是大约 $2^{-nH(X)}$

随机变量的描述性复杂度可以扩展到描述一个字符串的复杂度。Kolmogorov Complexity就是用来描述这种复杂度的。它被定义为生...

第三章 Asymptotic Equipartition Theory

3.1 The AEP

The asymptotic equipartition property is formalized in the following theorem:
Theorem 3.1.1: If $X_{1},X_{2},\dots$ are i.i.d $\sim p(x)$ , then
$$
-\frac{1}{n}\log p(X_{1},X_{2},\dots,...

第九章 Differential Entropy

AEP for continuous random variables:
设 $X_{1},\dots,X_{n}$ 是独立同分布变量，分布函数 $f(x)$ ，则

$-\frac{1}{n} \log f(X_{1},\dots,X_{n}) \to E[-\log f(X)] = h(X)\ \text{in probability}$

typical set:
$$
A_{\epsilon...

第二章 Entropy, Relative Entropy and Mutual Information

2.1 Entropy

编码：必须唯一可解，不出现歧义
Huffman编码
Prefix-free codes:前缀码。有一组code words $c_{1}c_{2}\dots c_{n}$ , $\forall c_{i},c_{j}(i\neq j)$ 使得 $c_{i},c_{j}$ 都不互为前缀。前缀码是可唯一解码的。
克拉夫特不等式：设符号表原始符号为
$$
S={s_{1},s_{...

第五章 Data Compression

（选）
D-adic: 一个概率分布被称为D-adic的，如果每个概率值都是 $D^{-n}$ ，n为正整数
对于任意编码对应的码长 $l_{i}$ ，随机变量 $X$ ，都有平均码长大于等于随机变量 $X$ 对应的熵：

$L \equiv \sum_{i}p_{i}l_{i} \geq H_{D}(X)$

上式等号成立当且仅当编码是 $D-adic$ 的，此时各个$l_{i} = \log \frac{1}...

第八章 Channel Capacity

在这章中我们将找出，通信信道使用 $n$ 次后最大可分辨的信号量。这个数量随 $n$ 指数增长，指数值叫做channel capacity.
信道的物理模型如图所示。
来自有限符号表的源符号倍映射成信道符号的序列，之后经过信道的输出序列被接收方接收。输出序列是随机的，但有一个由输入序列决定的概率分布。从输出信号中，我们...

第六章 Gambling & Data Compression

6.1 The Horse Rase

设赛马中有m匹马，第 $i$ 只马赢的概率 $p_{i}$ ，如果它赢了，那么payoff就是 $o_{i}:1$ 的。意思是，每投资这匹马1元，这匹马胜利时就能获得 $o_{i}$ 元，否则获得0元。
有两种方式描述赔率：a for 1和b to 1。

a-for-1: 赛前赌徒投入1元，赢了收回a元，否则收回0元；
b-to-1: 赛前进行打赌，赛后如果赌赢...

第十一章 Maximum Entropy and Spectral Estimation

气体的温度对应于气体分子的平均动能。给定温度，我们可以得出什么有关气体速度分布的结论？从物理学中我们指导，这个分布是温度限制下的熵最大的分布，也被称作麦克斯韦-玻尔兹曼分布。最大熵分布对应了具有最多微观态的宏观态。

1. 最大熵分布

Maximize entropy $h(f)$ over all probability densities $f$ satisfying:

$f(x)...

第十二章 Information Theory and Statistics

12.1 The Method of Types

AEP是我们可以关注于一小部分典型序列，类型方法使我们可以考虑具有相同经验分布(empirical distribution)的序列。在该限制下，我们可以推出特定经验分布中序列个数的bounds，以及这个集合中每个序列的概率。

序列 $x_{1},\dots,x_{n}$ 的类型 $P_{\mathbf{x}}$ 是$\mathscr{H}...

第十章 The Gaussian Channel

最重要的连续符号信道是高斯信道。设输入随机变量为 $X_{i}$ ，输出

$Y_{i} = X_{i}+Z_{i},\qquad Z_{i} \sim \mathscr{N}(0,N)$

$Z_{i}$ 是信号 $X_{i}$ 的噪声。
如果噪声方差为0，那么所有实数X都可被精确传输到对端；如果噪声方差非零，我们可以选取一组有限集合作为输入，从而使得输出端的分辨具有任意小的错误率，信道从而有有限的容...

第四章 Entropy Rates of Markov Process

4.1 马尔可夫链

随机过程是一系列随机变量，它们可以存在任意的依赖关系。随机过程由它们的联合分布唯一确定：
$$
\text{Pr}\left{(X_{1},X_{2},\dots,X_{n})=(x_{1},x_{2},\dots,x_{n})\right} = p(x_{1},x_{2},\dots,x_{n}),\qquad(x_{1},x_{2},\dots,x_{n})\i...

TOC