Entropy Rate

5.4 Asymptotic Equipartition Property

Intuition

The AEP states that the sample average of surprisal has a limit $H(X)$ for an i.i.d. sequence following the distribution $p$ on the simplex $\Delta_\cal X$.

• ==Almost every sequence of a long length $n$ has an empirical entropy (mean surprisal, approximating the real entropy) close to the real entropy.==
• 几乎所有的iid长序列都具有相似的统计特性，即它们的经验熵都约等于真实的单变量熵，或者都属于epsilon弱典型序列。

AEP Form 1:

$\mathbb X=(X_n,n\in\Z)$ is i.i.d. following $p$.

Then $\log {1\over p(X_k)}$ is a random variable for each $k\in \Z$, and $(\log p(X_n),n\in\Z)$ is also an i.i.d. real-valued sequence. Hence $\frac1n \sum_{k=1}^n\log {1\over p(X_k)}$ converges in probability (= with a probability converging to zero of being outside) to $E[-\log p(X_0)]=H(X_0)=H(\mathbb X)$, from Weak Law of Large Numbers:

Note here because of the i.i.d. property, $H(X_0)=H(X_k),\forall k\in\Z$.

Def: $\epsilon$-weakly Typical Set (of length $n$)

We define $\epsilon$-weakly typical set of length $n$ as a subset of $\mathcal X^n$:

A sequence in this set is called an $\epsilon$-weakly typical sequence.

AEP Form 2:

For $\forall \epsilon>0$, (the convergence in probability means)

Corollaries

Denote $\bold x=\bold x^n=x_{1:n}$ and $\bold X=\bold X^n=X_{1:n}$ for convenience when there are too many.

Denote $\Pr(A_\epsilon^{(n)}):=\sum_{\bold x\in A_\epsilon^{(n)}}p(\bold x)$, then

For any sufficiently large integer $n$: $\forall n\ge N(\delta,\epsilon)$:

1. If $x_{1:n}\in A_{\epsilon}^{(n)}$, we have

   $$ n(H(X_0)-\epsilon)\le \sum_{i=1}^n \log\frac1{p(X_i)}\equiv {1\over \log p(X_{1:n})}\le n(H(X_0)+\epsilon) $$

   (the lower/upper bounds of total surprisal, which can also be the bounds of average surprisal/empirical entropy)

   • -> Moreover, $$ 2^{-n\epsilon-nH(X_0)}\le p(x_{1:n})\le 2^{-n(X_0)+n\epsilon},\quad\forall x_{1:n}\in A_\epsilon^{(n)}. $$

2. $\forall \delta,\epsilon>0$, we denote $\Pr(A_\epsilon^{(n)})=\sum_{\bold x\in A_\epsilon^{(n)}}p(\bold x)$.

   $$ \Pr(A_\epsilon^{(n)})>1-\delta $$

   for all sufficiently large $n$.

3. The cardinality/size upper bound of the typical set: $\forall \epsilon>0$, for sufficiently large $n$,

   $$ |A_\epsilon^{(n)}|\le 2^{n(H(X_0)+\epsilon)} $$

   Proof.

   $$ \begin{aligned} 1 & = \sum_{\bold x\in{\cal X^n}} p(\bold x) \\&\ge \sum_{\bold x\in A_\epsilon^{(n)}} p(\bold x) \\&\ge \sum_{\bold x\in A_\epsilon^{(n)}} 2^{-n(H(X_0)+\epsilon)} \\&=|A_\epsilon^{(n)}|2^{-n(H(X_0)+\epsilon)} \end{aligned} $$

   so $|A_\epsilon^{(n)}|\le 2^{n(H(X_0)+\epsilon)}$. Q.E.D.

4. $\forall \delta,\epsilon > 0$, for sufficiently large $n$,

   $$ |A_\epsilon^{(n)}|\ge (1-\delta) 2^{n(H(X_0)-\epsilon)} $$

   Proof.

   $$ \begin{aligned} 1-\delta &<\Pr(A_\epsilon^{(n)}) \\&=\sum_{\bold x\in{A_\epsilon^{(n)}}} p(\bold x) \\&\le \sum_{\bold x\in A_\epsilon^{(n)}}2^{-n(H(X_0)-\epsilon)} \\&=|A_\epsilon^{(n)}|2^{-n(H(X_0)-\epsilon)} \end{aligned} $$

   so $|A_\epsilon^{(n)}|>(1-\delta)2^{n(H(X_0)-\epsilon)}$.

   We can also set $\delta=\epsilon$ to exclude the $\delta$ variable.

5.5 Lossless Data Compression

Setup

假设我们有一个随机过程中的序列 $\bold X^n$ on the domain $\mathcal X^n$, 想要压缩这个序列。使用一个单射的对照表，每个序列对应一个 index, 与一个 bit string.

Assume we have a finite stochastic sequence $\bold X^n$, and we want to compress this sequence. We use an lossless encoding map, every sequence corresponding to an index and a bit string.

如上定义 typical set $A_\epsilon^{(n)}$. 有一些 $\bold X^n$ 序列属于这个集合。

We define $A_\epsilon^{(n)}$ as above, and some sequences belong to this set.

$\forall \epsilon>0,\forall \delta>0,\exist n(\epsilon,\delta)$ s.t. there exists some encoding map

• We use a bit 0/1 to denote if the seq. is in the typical set.
• $\phi,\psi$ is a map mapping from a sequence to a bit string.
• If the sequence is typical, we use $\phi(\cdot)$ to encode. $\phi(\bold x^n)$ is a unique string of length $\lceil \log|A_\epsilon^{(n)}|\rceil$ bits since there are $|A_\epsilon^{(n)}|$ input sequences. For an encoded string, we know if it’s typical or not by the first bit 0/1. 可以压缩到典型集的大小
  • $l(e_n(\bold x^n))=1+\lceil \log|A_\epsilon^{(n)}|\rceil$
    • 最小充分长度，也就是密码表里最大的长度是这个的情况下，这个最大值是最小的。。
    • Minimum value of the maximum length of the encoding map
• If the sequence is not typical, we use $\psi(\cdot)$ to encode. $\psi(\bold x^n)$ is a unique string of length $\lceil \log |\mathcal X^n|\rceil = \lceil n\log |\mathcal X|\rceil$ bits, equal to no compression. 相当于不压缩
  • $l(e_n(\bold x^n))=1+\lceil \log |\mathcal X^n|\rceil = 1+\lceil n\log |\mathcal X|\rceil$

So we have the expected length

If every symbol has the maximum length in the encoding map then this is an equality. 当且仅当每个symbol都要用密码本里最长的那个来encode的情况下取等。

Expected Length of Lossless Compression: Upper Bound

Hence we have the upper part of 1st Shannon’s Theorem: Source Coding Theorem by setting $\delta=\epsilon$:

$\forall \epsilon>0$, there exists a lossless compression scheme $((e_n,d_n),n\ge 1)$ (this is, $((e_1,d_1),(e_2,d_2),\dots)$) s.t.

Converse: Lower Bound

$\forall \epsilon>0$, for all lossless compression themes $((e_n,d_n),n\ge 1)$, we have

Proof

懒得写了

First Shannon Theorem: Source Coding Theorem

信源编码定理/无失真(Lossless)变长(Length-variant)编码定理(Coding Theorem)/在无损情况下，数据压缩的临界值

The limit of lossless data compression

This theorem is the composition of the Upper Bound and the Lower Bound.